Optimo  0.1.0
A C++ header library for optimization
 All Classes Functions Variables Pages
primal_dual_lp_api.h
1 // Copyright (C) 2014 Victor Fragoso <vfragoso@cs.ucsb.edu>
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 //
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following
13 // disclaimer in the documentation and/or other materials provided
14 // with the distribution.
15 //
16 // * Neither the name of the University of California, Santa Barbara nor the
17 // names of its contributors may be used to endorse or promote products
18 // derived from this software without specific prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 // ARE DISCLAIMED. IN NO EVENT SHALL VICTOR FRAGOSO BE LIABLE FOR ANY DIRECT,
24 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
27 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 //
31 
32 #ifndef OPTIMO_SOLVERS_PRIMAL_DUAL_LP_API_H_
33 #define OPTIMO_SOLVERS_PRIMAL_DUAL_LP_API_H_
34 
35 #include <Eigen/Dense>
36 #include <algorithm>
37 #include <vector>
38 #include "optimo/solvers/solver.h"
39 
40 namespace optimo {
41 namespace solvers {
42 
43 using Eigen::Matrix;
44 using Eigen::Dynamic;
45 using Eigen::DiagonalMatrix;
47 
77 template <typename Scalar, uint n, uint m, uint p>
78 class PrimalDualLP : public Solver<Scalar> {
79  public:
81  struct Params {
82  Params(void) : c(n), Ain(m, n), bin(m), Aeq(p, n), beq(p) {
83  Ain.setConstant(static_cast<Scalar>(0.0));
84  Aeq.setConstant(static_cast<Scalar>(0.0));
85  c.setConstant(static_cast<Scalar>(0.0));
86  bin.setConstant(static_cast<Scalar>(0.0));
87  beq.setConstant(static_cast<Scalar>(0.0));
88  }
89 
90  // LP Params
91  Matrix<Scalar, Dynamic, 1> c;
92  Matrix<Scalar, Dynamic, Dynamic> Aeq;
93  Matrix<Scalar, Dynamic, 1> beq;
94  Matrix<Scalar, Dynamic, Dynamic> Ain;
95  Matrix<Scalar, Dynamic, 1> bin;
96  };
97 
98  // Constructor
99  PrimalDualLP(void) { }
100 
101  // Destructor
102  virtual ~PrimalDualLP(void) { }
103 
105  TERMINATION_TYPE
106  operator()(const Params& params,
107  Matrix<Scalar, Dynamic, 1>* y,
108  Scalar* min_value);
109 
110  protected:
111  // Calculate residuals
112  void calculateResiduals(const Params& params,
113  const Matrix<Scalar, Dynamic, 1>& y,
114  const DiagonalMatrix<Scalar, Dynamic, Dynamic>& diag,
115  const Matrix<Scalar, Dynamic, 1>& fx,
116  const Scalar t_inv,
117  Matrix<Scalar, Dynamic, 1>* residuals);
118  // Line Search
119  Scalar backTracking(const double t_inv,
120  const double r_norm,
121  const Matrix<Scalar, Dynamic, 1>& ynt,
122  const Matrix<Scalar, Dynamic, 1>& y,
123  const Params& params);
124 
125  // Buld the KKT System
126  void buildKKTSystem(const Params& params,
127  const Matrix<Scalar, Dynamic, 1>& y,
128  const Scalar mu,
129  Scalar* eta,
130  Scalar* t,
131  Matrix<Scalar, Dynamic, 1>* residuals,
132  Scalar* rd_norm,
133  Scalar* rp_norm);
134 
135  private:
136  // Members
137  Matrix<Scalar, Dynamic, Dynamic> F_; // KKT system
138  Matrix<Scalar, Dynamic, 1> r_; // Residuals
139  Matrix<Scalar, Dynamic, 1> y_plus_; // Variables for line search
140  Matrix<Scalar, Dynamic, 1> r_plus_; // Residuals for line search
141 };
142 } // solvers
143 } // optimo
144 #endif // OPTIMO_SOLVERS_PRIMAL_DUAL_LP_API_H_
Abstract class for a Solver algorithm.
Definition: solver.h:53
Matrix< Scalar, Dynamic, 1 > c
Costs vector.
Definition: primal_dual_lp_api.h:91
Matrix< Scalar, Dynamic, Dynamic > Aeq
Equality constraints.
Definition: primal_dual_lp_api.h:92
Matrix< Scalar, Dynamic, 1 > beq
Equality constraints vector.
Definition: primal_dual_lp_api.h:93
Matrix< Scalar, Dynamic, Dynamic > Ain
Inequality constraints.
Definition: primal_dual_lp_api.h:94
Solves a constrained linear program (LP)
Definition: primal_dual_lp_api.h:78
Matrix< Scalar, Dynamic, 1 > bin
Inequality constraints vector.
Definition: primal_dual_lp_api.h:95
TERMINATION_TYPE operator()(const Params &params, Matrix< Scalar, Dynamic, 1 > *y, Scalar *min_value)
Solves the LP program defined in params.
Linear Program (LP) Parameters defining the problem.
Definition: primal_dual_lp_api.h:81