1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2015 Google Inc. All rights reserved.
3 // http://ceres-solver.org/
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
8 // * Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 // used to endorse or promote products derived from this software without
15 // specific prior written permission.
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
29 // Author: sameeragarwal@google.com (Sameer Agarwal)
31 // Interface for and implementation of various Line search algorithms.
33 #ifndef CERES_INTERNAL_LINE_SEARCH_H_
34 #define CERES_INTERNAL_LINE_SEARCH_H_
38 #include "ceres/function_sample.h"
39 #include "ceres/internal/eigen.h"
40 #include "ceres/internal/port.h"
41 #include "ceres/types.h"
47 class LineSearchFunction;
49 // Line search is another name for a one dimensional optimization
50 // algorithm. The name "line search" comes from the fact one
51 // dimensional optimization problems that arise as subproblems of
52 // general multidimensional optimization problems.
54 // While finding the exact minimum of a one dimensionl function is
55 // hard, instances of LineSearch find a point that satisfies a
56 // sufficient decrease condition. Depending on the particular
57 // condition used, we get a variety of different line search
58 // algorithms, e.g., Armijo, Wolfe etc.
65 : interpolation_type(CUBIC),
66 sufficient_decrease(1e-4),
67 max_step_contraction(1e-3),
68 min_step_contraction(0.9),
70 max_num_iterations(20),
71 sufficient_curvature_decrease(0.9),
72 max_step_expansion(10.0),
76 // Degree of the polynomial used to approximate the objective
78 LineSearchInterpolationType interpolation_type;
80 // Armijo and Wolfe line search parameters.
82 // Solving the line search problem exactly is computationally
83 // prohibitive. Fortunately, line search based optimization
84 // algorithms can still guarantee convergence if instead of an
85 // exact solution, the line search algorithm returns a solution
86 // which decreases the value of the objective function
87 // sufficiently. More precisely, we are looking for a step_size
90 // f(step_size) <= f(0) + sufficient_decrease * f'(0) * step_size
91 double sufficient_decrease;
93 // In each iteration of the Armijo / Wolfe line search,
95 // new_step_size >= max_step_contraction * step_size
97 // Note that by definition, for contraction:
99 // 0 < max_step_contraction < min_step_contraction < 1
101 double max_step_contraction;
103 // In each iteration of the Armijo / Wolfe line search,
105 // new_step_size <= min_step_contraction * step_size
106 // Note that by definition, for contraction:
108 // 0 < max_step_contraction < min_step_contraction < 1
110 double min_step_contraction;
112 // If during the line search, the step_size falls below this
113 // value, it is truncated to zero.
114 double min_step_size;
116 // Maximum number of trial step size iterations during each line search,
117 // if a step size satisfying the search conditions cannot be found within
118 // this number of trials, the line search will terminate.
119 int max_num_iterations;
121 // Wolfe-specific line search parameters.
123 // The strong Wolfe conditions consist of the Armijo sufficient
124 // decrease condition, and an additional requirement that the
125 // step-size be chosen s.t. the _magnitude_ ('strong' Wolfe
126 // conditions) of the gradient along the search direction
127 // decreases sufficiently. Precisely, this second condition
128 // is that we seek a step_size s.t.
130 // |f'(step_size)| <= sufficient_curvature_decrease * |f'(0)|
132 // Where f() is the line search objective and f'() is the derivative
133 // of f w.r.t step_size (d f / d step_size).
134 double sufficient_curvature_decrease;
136 // During the bracketing phase of the Wolfe search, the step size is
137 // increased until either a point satisfying the Wolfe conditions is
138 // found, or an upper bound for a bracket containing a point satisfying
139 // the conditions is found. Precisely, at each iteration of the
142 // new_step_size <= max_step_expansion * step_size.
144 // By definition for expansion, max_step_expansion > 1.0.
145 double max_step_expansion;
149 // The one dimensional function that the line search algorithm
151 LineSearchFunction* function;
154 // Result of the line search.
158 num_function_evaluations(0),
159 num_gradient_evaluations(0),
161 cost_evaluation_time_in_seconds(-1.0),
162 gradient_evaluation_time_in_seconds(-1.0),
163 polynomial_minimization_time_in_seconds(-1.0),
164 total_time_in_seconds(-1.0) {}
167 FunctionSample optimal_point;
168 int num_function_evaluations;
169 int num_gradient_evaluations;
171 // Cumulative time spent evaluating the value of the cost function across
173 double cost_evaluation_time_in_seconds;
174 // Cumulative time spent evaluating the gradient of the cost function across
176 double gradient_evaluation_time_in_seconds;
177 // Cumulative time spent minimizing the interpolating polynomial to compute
178 // the next candidate step size across all iterations.
179 double polynomial_minimization_time_in_seconds;
180 double total_time_in_seconds;
184 explicit LineSearch(const LineSearch::Options& options);
185 virtual ~LineSearch() {}
187 static LineSearch* Create(const LineSearchType line_search_type,
188 const LineSearch::Options& options,
191 // Perform the line search.
193 // step_size_estimate must be a positive number.
195 // initial_cost and initial_gradient are the values and gradient of
196 // the function at zero.
197 // summary must not be null and will contain the result of the line
200 // Summary::success is true if a non-zero step size is found.
201 void Search(double step_size_estimate,
203 double initial_gradient,
204 Summary* summary) const;
205 double InterpolatingPolynomialMinimizingStepSize(
206 const LineSearchInterpolationType& interpolation_type,
207 const FunctionSample& lowerbound_sample,
208 const FunctionSample& previous_sample,
209 const FunctionSample& current_sample,
210 const double min_step_size,
211 const double max_step_size) const;
214 const LineSearch::Options& options() const { return options_; }
217 virtual void DoSearch(double step_size_estimate,
219 double initial_gradient,
220 Summary* summary) const = 0;
223 LineSearch::Options options_;
226 // An object used by the line search to access the function values
227 // and gradient of the one dimensional function being optimized.
229 // In practice, this object provides access to the objective
230 // function value and the directional derivative of the underlying
231 // optimization problem along a specific search direction.
232 class LineSearchFunction {
234 explicit LineSearchFunction(Evaluator* evaluator);
235 void Init(const Vector& position, const Vector& direction);
237 // Evaluate the line search objective
239 // f(x) = p(position + x * direction)
241 // Where, p is the objective function of the general optimization
244 // evaluate_gradient controls whether the gradient will be evaluated
247 // On return output->*_is_valid indicate indicate whether the
248 // corresponding fields have numerically valid values or not.
249 void Evaluate(double x, bool evaluate_gradient, FunctionSample* output);
251 double DirectionInfinityNorm() const;
253 // Resets to now, the start point for the results from TimeStatistics().
254 void ResetTimeStatistics();
255 void TimeStatistics(double* cost_evaluation_time_in_seconds,
256 double* gradient_evaluation_time_in_seconds) const;
257 const Vector& position() const { return position_; }
258 const Vector& direction() const { return direction_; }
261 Evaluator* evaluator_;
265 // scaled_direction = x * direction_;
266 Vector scaled_direction_;
268 // We may not exclusively own the evaluator (e.g. in the Trust Region
269 // minimizer), hence we need to save the initial evaluation durations for the
270 // value & gradient to accurately determine the duration of the evaluations
271 // we invoked. These are reset by a call to ResetTimeStatistics().
272 double initial_evaluator_residual_time_in_seconds;
273 double initial_evaluator_jacobian_time_in_seconds;
276 // Backtracking and interpolation based Armijo line search. This
277 // implementation is based on the Armijo line search that ships in the
278 // minFunc package by Mark Schmidt.
280 // For more details: http://www.di.ens.fr/~mschmidt/Software/minFunc.html
281 class ArmijoLineSearch : public LineSearch {
283 explicit ArmijoLineSearch(const LineSearch::Options& options);
284 virtual ~ArmijoLineSearch() {}
287 virtual void DoSearch(double step_size_estimate,
289 double initial_gradient,
290 Summary* summary) const;
293 // Bracketing / Zoom Strong Wolfe condition line search. This implementation
294 // is based on the pseudo-code algorithm presented in Nocedal & Wright [1]
295 // (p60-61) with inspiration from the WolfeLineSearch which ships with the
296 // minFunc package by Mark Schmidt [2].
298 // [1] Nocedal J., Wright S., Numerical Optimization, 2nd Ed., Springer, 1999.
299 // [2] http://www.di.ens.fr/~mschmidt/Software/minFunc.html.
300 class WolfeLineSearch : public LineSearch {
302 explicit WolfeLineSearch(const LineSearch::Options& options);
303 virtual ~WolfeLineSearch() {}
305 // Returns true iff either a valid point, or valid bracket are found.
306 bool BracketingPhase(const FunctionSample& initial_position,
307 const double step_size_estimate,
308 FunctionSample* bracket_low,
309 FunctionSample* bracket_high,
310 bool* perform_zoom_search,
311 Summary* summary) const;
312 // Returns true iff final_line_sample satisfies strong Wolfe conditions.
313 bool ZoomPhase(const FunctionSample& initial_position,
314 FunctionSample bracket_low,
315 FunctionSample bracket_high,
316 FunctionSample* solution,
317 Summary* summary) const;
320 virtual void DoSearch(double step_size_estimate,
322 double initial_gradient,
323 Summary* summary) const;
326 } // namespace internal
329 #endif // CERES_INTERNAL_LINE_SEARCH_H_