Turi Create  4.0
Functions
Line Search
Convex Optimization

Functions

bool turi::optimization::cstep (double &stx, double &fx, double &dx, double &sty, double &fy, double &dy, double &stp, double &fp, double &dp, bool &brackt, double stpmin, double stpmax)
 
template<typename Vector >
ls_return turi::optimization::more_thuente (first_order_opt_interface &model, double init_step, double init_func_value, DenseVector point, Vector gradient, DenseVector direction, double function_scaling=1.0, const std::shared_ptr< smooth_regularizer_interface > reg=NULL, size_t max_function_evaluations=LS_MAX_ITER)
 
template<typename Vector >
ls_return turi::optimization::armijo_backtracking (first_order_opt_interface &model, double init_step, double init_func_value, DenseVector point, Vector gradient, DenseVector direction)
 
template<typename Vector >
ls_return turi::optimization::backtracking (first_order_opt_interface &model, double init_step, double init_func_value, DenseVector point, Vector gradient, DenseVector direction, const std::shared_ptr< regularizer_interface > reg=NULL)
 
double turi::optimization::gradient_bracketed_linesearch (double dist, double f1, double f2, double g1, double g2)
 

Detailed Description

Function Documentation

◆ armijo_backtracking()

template<typename Vector >
ls_return turi::optimization::armijo_backtracking ( first_order_opt_interface &  model,
double  init_step,
double  init_func_value,
DenseVector  point,
Vector  gradient,
DenseVector  direction 
)
inline

Armijo backtracking to compute step sizes for line search methods.

Note
Applicable for smooth functions only.

Line search based on an backtracking strategy to ensure sufficient decrease in function values at each iteration.

References: (1) Wright S.J and J. Nocedal. Numerical optimization. Vol. 2. New York: Springer, 1999.

Parameters
[in]modelAny model with a first order optimization interface.
[in]init_stepInitial step size.
[in]init_funcInitial function value.
[in]pointStarting point for the solver.
[in]gradientGradient value at this point.
[in]directionDirection of the next step .
Returns
stats Line searnorm ch return object

Definition at line 615 of file line_search-inl.hpp.

◆ backtracking()

template<typename Vector >
ls_return turi::optimization::backtracking ( first_order_opt_interface &  model,
double  init_step,
double  init_func_value,
DenseVector  point,
Vector  gradient,
DenseVector  direction,
const std::shared_ptr< regularizer_interface >  reg = NULL 
)
inline

Backtracking to compute step sizes for line search methods.

Note
Applicable for non-smooth functions.

Line search based on an backtracking strategy to "some" decrease in function values at each iteration.

References: (1) Wright S.J and J. Nocedal. Numerical optimization. Vol. 2. New York: Springer, 1999.

Parameters
[in]modelAny model with a first order optimization interface.
[in]init_stepInitial step size.
[in]init_funcInitial function value.
[in]pointStarting point for the solver.
[in]gradientGradient value at this point.
[in]directionDirection of the next step .
[in]regRegularizer interface!
Returns
stats Line searnorm ch return object

Definition at line 681 of file line_search-inl.hpp.

◆ cstep()

bool turi::optimization::cstep ( double &  stx,
double &  fx,
double &  dx,
double &  sty,
double &  fy,
double &  dy,
double &  stp,
double &  fp,
double &  dp,
bool &  brackt,
double  stpmin,
double  stpmax 
)
inline

"Zoom" phase for More and Thuente line seach.

Note
Applicable for smooth functions only.

This code is a C++ port of Jorge Nocedal's implementaiton of More and Thuente [2] line search. This code was availiable at http://www.ece.northwestern.edu/~nocedal/lbfgs.html

Nocedal's Condition for Use: This software is freely available for educational or commercial purposes. We expect that all publications describing work using this software quote at least one of the references given below. This software is released under the BSD License

The purpose of cstep is to compute a safeguarded step for a linesearch and to update an interval of uncertainty for a minimizer of the function.

The parameter stx contains the step with the least function value. The parameter stp contains the current step. It is assumed that the derivative at stx is negative in the direction of the step. If brackt is set true then a minimizer has been bracketed in an interval of uncertainty with endpoints stx and sty.

Parameters
[in]stxBest step obtained so far.
[in]fxFunction value at the best step so far.
[in]dxDirectional derivative at the best step so far.
[in]styStep at the end point of the uncertainty interval.
[in]fyFunction value at end point of uncertainty interval.
[in]dyDirectional derivative at end point of uncertainty interval.
[in]stpCurrent step.
[in]fpFunction value at current step.
[in]dpDirectional derivative at the current step.
[in]bracktHas the minimizer has been bracketed?
[in]stpminMin step size
[in]stpmaxMax step size.

Definition at line 76 of file line_search-inl.hpp.

◆ gradient_bracketed_linesearch()

double turi::optimization::gradient_bracketed_linesearch ( double  dist,
double  f1,
double  f2,
double  g1,
double  g2 
)
inline

This function estimates a minumum point between two function values with known gradients.

The minimum value must lie between the two function values, f1 and f2, and the gradients must indicate the minimum lies between the two values and that the function is convex.

Under these situations, a third degree polynomial / cubic spline can be fit to the two function points, and this is gauranteed to have a single minimum between f1 and f2. This is what this function returns.

Parameters
[in]distThe distance between the points f1 and f2.
[in]f1The value of the function at the left point.
[in]f2The value of the function at the right point.
[in]g1The derivative of the function at the left point.
[in]g2The derivative of the function at the right point.

Definition at line 744 of file line_search-inl.hpp.

◆ more_thuente()

template<typename Vector >
ls_return turi::optimization::more_thuente ( first_order_opt_interface &  model,
double  init_step,
double  init_func_value,
DenseVector  point,
Vector  gradient,
DenseVector  direction,
double  function_scaling = 1.0,
const std::shared_ptr< smooth_regularizer_interface >  reg = NULL,
size_t  max_function_evaluations = LS_MAX_ITER 
)
inline

Compute step sizes for line search methods to satisfy Strong Wolfe conditions.

Note
Applicable for smooth functions only.

This code is a C++ port of Jorge Nocedal's implementaiton of More and Thuente [2] line search. This code was availiable at http://www.ece.northwestern.edu/~nocedal/lbfgs.html

Line search based on More' and Thuente [1] to find a step which satisfies a Wolfe conditions for sufficient decrease condition and a curvature condition.

At each stage the function updates an interval of uncertainty with endpoints. The interval of uncertainty is initially chosen so that it contains a minimizer of the modified function 

 f(x+stp*s) - f(x) - ftol*stp*(gradf(x)'s).

If a step is obtained for which the modified function has a nonpositive function value and nonnegative derivative, then the interval of uncertainty is chosen so that it contains a minimizer of f(x+stp*s).

The algorithm is designed to find a step which satisfies the sufficient decrease condition f(x+stp*s) .le. f(x) + ftol*stp*(gradf(x)'s), [W1] and the curvature condition std::abs(gradf(x+stp*s)'s)) .le. gtol*std::abs(gradf(x)'s). [W2]

References:

(1) More, J. J. and D. J. Thuente. "Line Search Algorithms with Guaranteed Sufficient Decrease." ACM Transactions on Mathematical Software 20, no. 3 (1994): 286-307.

(2) Wright S.J and J. Nocedal. Numerical optimization. Vol. 2. New York: Springer, 1999.

Parameters
[in]modelAny model with a first order optimization interface.
[in]init_stepInitial step size
[in]pointStarting point for the solver.
[in]gradientGradient value at this point (saves computation)
[in]regShared ptr to an interface to a smooth regularizer.
Returns
stats Line searnorm ch return object

Definition at line 329 of file line_search-inl.hpp.