Optimo  0.1.0
A C++ header library for optimization
 All Classes Functions Variables Pages
newton_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_NEWTON_API_H_
33 #define OPTIMO_SOLVERS_NEWTON_API_H_
34 #include "optimo/core/objects.h"
35 #include "optimo/utils/matrix_utils.h"
36 #include <Eigen/Core>
37 #include <Eigen/SparseCore>
38 #include <Eigen/Cholesky>
39 #include "optimo/solvers/solver.h"
40 
41 namespace optimo {
42 namespace solvers {
44 
50 template <typename Scalar, uint m, uint n>
51 class Newton : public Solver<Scalar> {
52  public:
53  enum Type {
54  UNCONSTRAINED,
55  EQUALITY_CONSTRAINED,
56  INFEASIBLE_EQUALITY_CONSTRAINED
57  };
58 
60  Newton(const Type type = UNCONSTRAINED ) : type_(type) {
61  v_.setConstant(static_cast<Scalar>(1.0));
62  switch (type) {
63  case UNCONSTRAINED:
64  method_ = new UnconstrainedMethod(this->options.alpha_,
65  this->options.beta_);
66  break;
67  case EQUALITY_CONSTRAINED:
68  method_ = new EqualityConstrainedMethod(this->options.alpha_,
69  this->options.beta_);
70  break;
71  case INFEASIBLE_EQUALITY_CONSTRAINED:
72  method_ = new InfeasibleMethod(this->options.alpha_,
73  this->options.beta_, &v_);
74  break;
75  }
76  }
77 
78  // Destructor
79  virtual ~Newton(void) {
80  delete method_;
81  }
82 
84  TERMINATION_TYPE
85  operator()(const Problem<Scalar, m, n>& problem,
86  Eigen::Matrix<Scalar, n, 1>* x,
87  Scalar* min_value);
88 
89  protected:
91  // Type (Method)
92  struct Method {
93  virtual ~Method(void) { }
94 
95  virtual TERMINATION_TYPE
96  operator()(const Problem<Scalar, m, n>& problem,
97  const Eigen::Matrix<Scalar, n, n>& hessian,
98  const Eigen::Matrix<Scalar, n, 1>& gradient,
99  const Scalar& epsilon,
100  Eigen::Matrix<Scalar, n, 1>* x,
101  Scalar* min_value) = 0;
102 
103  const Scalar alpha_;
104  const Scalar beta_;
105 
106  Method(const Scalar alpha, const Scalar beta) :
107  alpha_(alpha), beta_(beta) { }
108  Eigen::Matrix<Scalar, n, 1> xnt_; // Newton Step (Dense)
109  };
110 
111  struct UnconstrainedMethod : public Method {
112  UnconstrainedMethod(const Scalar alpha, const Scalar beta) :
113  Method(alpha, beta) { }
114 
115  virtual TERMINATION_TYPE
116  operator()(const Problem<Scalar, m, n>& problem,
117  const Eigen::Matrix<Scalar, n, n>& hessian,
118  const Eigen::Matrix<Scalar, n, 1>& gradient,
119  const Scalar& epsilon,
120  Eigen::Matrix<Scalar, n, 1>* x,
121  Scalar* min_value);
122 
123  virtual
124  Scalar line_search(const ObjectiveFunctor<Scalar, n>& objective,
125  const Eigen::Matrix<Scalar, n, 1>& x,
126  const Eigen::Matrix<Scalar, n, 1>& g);
127 
128  Scalar t_;
129  Scalar fx_;
130  Scalar lambda_sqrd_;
131  };
132 
133  struct EqualityConstrainedMethod : public UnconstrainedMethod {
134  EqualityConstrainedMethod(const Scalar alpha, const Scalar beta) :
135  UnconstrainedMethod(alpha, beta) { }
136 
137  // Overriding
138  virtual TERMINATION_TYPE
139  operator()(const Problem<Scalar, m, n>& problem,
140  const Eigen::Matrix<Scalar, n, n>& hessian,
141  const Eigen::Matrix<Scalar, n, 1>& gradient,
142  const Scalar& epsilon,
143  Eigen::Matrix<Scalar, n, 1>* x,
144  Scalar* min_value);
145  };
146 
147  struct InfeasibleMethod : public Method {
148  InfeasibleMethod(const Scalar alpha,
149  const Scalar beta,
150  Eigen::Matrix<Scalar, m, 1>* v) :
151  Method(alpha, beta), v_(v) { }
152 
153  virtual TERMINATION_TYPE
154  operator()(const Problem<Scalar, m, n>& problem,
155  const Eigen::Matrix<Scalar, n, n>& hessian,
156  const Eigen::Matrix<Scalar, n, 1>& gradient,
157  const Scalar& epsilon,
158  Eigen::Matrix<Scalar, n, 1>* x,
159  Scalar* min_value);
160 
161  Scalar line_search(const ObjectiveFunctor<Scalar, n>& objective,
162  const Eigen::Matrix<Scalar, n, 1>& x,
163  const Eigen::Matrix<Scalar, m, 1>& v,
164  const Eigen::Matrix<Scalar, m, n>& A,
165  const Eigen::Matrix<Scalar, m, 1>& b,
166  const Eigen::Matrix<Scalar, n, 1>& g);
167 
168  Scalar t_;
169  Eigen::Matrix<Scalar, m, 1>* v_; // Dual Eq.
170  Eigen::Matrix<Scalar, m, 1> vnt_; // Dual Eq. step # of rows is m
171  };
172 
174  // Members
175  // const Scalar epsilon;
176  const Type type_;
177  // const int max_iter;
178  Method* method_;
179  Eigen::Matrix<Scalar, m, 1> v_; // Ineq. Constraints Lagrange mult.
180 };
181 } // solvers
182 } // optimo
183 #endif // OPTIMO_SOLVERS_NEWTON_API_H_
Abstract class for a Solver algorithm.
Definition: solver.h:53
TERMINATION_TYPE operator()(const Problem< Scalar, m, n > &problem, Eigen::Matrix< Scalar, n, 1 > *x, Scalar *min_value)
Solve the problem.
struct optimo::solvers::Solver::Options options
Solver parameters.
Scalar alpha_
Backtracking (Line search) parameter.
Definition: solver.h:58
Class defining a convex Problem.
Definition: objects.h:197
Implements Newton&#39;s algorithm.
Definition: newton_api.h:51
Newton(const Type type=UNCONSTRAINED)
Constructor for Newton Solver.
Definition: newton_api.h:60