Optimo  0.1.0
A C++ header library for optimization
 All Classes Functions Variables Pages
gradient_descent.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_GRADIENT_DESCENT_H_
33 #define OPTIMO_SOLVERS_GRADIENT_DESCENT_H_
34 
35 #include <glog/logging.h>
36 #include <Eigen/Core>
37 #include "optimo/core/objects.h"
38 #include "optimo/core/objects_ls.h"
39 #include "optimo/utils/matrix_utils.h"
40 #include "optimo/solvers/solver.h"
41 
42 namespace optimo {
43 namespace solvers {
45 
59 template <typename Scalar, uint m, uint n>
60 class GradientDescent : public Solver<Scalar> {
61  public:
63  explicit GradientDescent(const Scalar step_size = 1e-3 ) :
64  step_size_(step_size) { }
65 
66  // Destructor
67  virtual ~GradientDescent(void) { }
68 
70  TERMINATION_TYPE
71  operator()(const Problem<Scalar, m, n>& problem,
72  Eigen::Matrix<Scalar, n, 1>* x,
73  Scalar* min_value);
74 
75  protected:
76  const Scalar step_size_; // Step size for update
77 };
78 
79 template <typename Scalar, uint m, uint n>
80 TERMINATION_TYPE
82  Eigen::Matrix<Scalar, n, 1>* x,
83  Scalar* min_value) {
84  uint iter = 0;
85  Eigen::Matrix<Scalar, n, 1> gradient = Eigen::Matrix<Scalar, n, 1>::Zero();
86  const GradientFunctor<Scalar, n>& gradient_functor = problem.gradient;
87  const ObjectiveFunctor<Scalar, n>& objective_functor = problem.objective;
88  TERMINATION_TYPE r;
89 
90  while (++iter < this->options.max_iter_) {
91  // 1. Compute descent direction
92  gradient_functor(*x, &gradient);
93 
94  // 1.1 Check that gradient does not have inf or nan elements.
95  if (!optimo::utils::isFinite<Scalar, n, 1>(gradient)) {
96  return FAIL_NAN_INF;
97  }
98 
99  // 2. Check norm, if norm is really small then we are in a local optima
100  if (gradient.norm() <= this->options.epsilon_) {
101  // TODO(vfragoso): Check Hessian to see if it is a minima or maxima
102  // if it is minima we are done, if not then the problem was not solved!
103  r = SOLVED;
104  *min_value = objective_functor(*x);
105  return r;
106  }
107 
108  // 2. Update
109  // TODO(vfragoso): Implement a line-search method
110  *x -= step_size_*gradient;
111  }
112 
113  return MAX_ITERATIONS;
114 }
115 
117 
127 template <typename Scalar>
128 class GradientDescentLS : public Solver<Scalar> {
129  public:
131  GradientDescentLS(const int n,
132  const Scalar alpha = 1e-3 )
133  : n_(n), step_size_(alpha) { }
134 
135  // Destructor
136  virtual ~GradientDescentLS(void) { }
137 
139  TERMINATION_TYPE
140  operator()(const ProblemLS<Scalar>& problem,
141  Eigen::Matrix<Scalar, Eigen::Dynamic, 1>* x,
142  Scalar* min_value);
143 
144  protected:
145  const int n_; // Number of variables
146  const Scalar step_size_; // Step size for update
147 };
148 
149 template <typename Scalar>
150 TERMINATION_TYPE
152  const ProblemLS<Scalar>& problem,
153  Eigen::Matrix<Scalar, Eigen::Dynamic, 1>* x,
154  Scalar* min_value) {
155  uint iter = 0;
156  Eigen::Matrix<Scalar, Eigen::Dynamic, 1> gradient(n_);
157  gradient.setZero();
158  const GradientFunctorLS<Scalar>& gradient_functor = problem.gradient;
159  const ObjectiveFunctorLS<Scalar>& objective_functor = problem.objective;
160  TERMINATION_TYPE r;
161 
162  while (++iter < this->options.max_iter_) {
163  // 1. Compute descent direction
164  gradient_functor(*x, &gradient);
165 
166  // 1.1 Check that gradient does not have inf or nan elements.
167  if (!optimo::utils::isFinite<Scalar>(gradient)) {
168  return FAIL_NAN_INF;
169  }
170 
171  // 2. Check norm, if norm is really small then we are in a local optima
172  if (gradient.norm() <= this->options.epsilon_) {
173  r = SOLVED;
174  *min_value = objective_functor(*x);
175  return r;
176  }
177 
178  // 2. Update
179  // TODO(vfragoso): Implement a line-search method
180  *x -= step_size_*gradient;
181  }
182 
183  return MAX_ITERATIONS;
184 }
185 } // solvers
186 } // optimo
187 
188 #endif // OPTIMO_SOLVERS_GRADIENT_DESCENT_H_
TERMINATION_TYPE operator()(const Problem< Scalar, m, n > &problem, Eigen::Matrix< Scalar, n, 1 > *x, Scalar *min_value)
Solve the problem.
Definition: gradient_descent.h:81
const GradientFunctorLS< Scalar > & gradient
Gradient functor.
Definition: objects_ls.h:202
Abstract class for a Solver algorithm.
Definition: solver.h:53
Objective functor.
Definition: objects_ls.h:51
Standard Gradient Descent method.
Definition: gradient_descent.h:128
Objective functor.
Definition: objects.h:54
Standard Gradient Descent method.
Definition: gradient_descent.h:60
TERMINATION_TYPE operator()(const ProblemLS< Scalar > &problem, Eigen::Matrix< Scalar, Eigen::Dynamic, 1 > *x, Scalar *min_value)
Solve the problem.
Definition: gradient_descent.h:151
Class defining a convex Problem.
Definition: objects_ls.h:198
Class defining a convex Problem.
Definition: objects.h:197
Gradient functor.
Definition: objects_ls.h:88
Gradient functor.
Definition: objects.h:88
GradientDescent(const Scalar step_size=1e-3)
Constructor.
Definition: gradient_descent.h:63
const ObjectiveFunctorLS< Scalar > & objective
Objective functor.
Definition: objects_ls.h:200
GradientDescentLS(const int n, const Scalar alpha=1e-3)
Constructor.
Definition: gradient_descent.h:131