# Line searches¶

Module containing various line searches.

Line searches are at the heart of many optimizers. After finding a suitable search direction (e.g. the steepest descent direction) we are left with a one-dimensional optimization problem, which can then be solved by a line search.

class climin.linesearch.BackTrack(wrt, f, decay=0.9, max_iter=inf, tolerance=1e-20)

Class implementing a back tracking line search.

The idea is to jump to a starting step length $$t$$ and then shrink that step length by multiplying it with $$\gamma$$ until we improve upon the loss.

At most max_iter attempts will be done. If the largest absolut value of a component of the step falls below tolerance, we stop as well. In both cases, a step length of 0 is returned.

To not possibly iterate forever, the field tolerance holds a small value (1E-20 per default). As soon as the absolute value of every component of the step (direction multiplied with the scalar from schedule) is less than tolerance, we stop.

Attributes

 wrt (array_like) Parameters over which the optimization is done. f (Callable) Objective function. decay (float) Factor to multiply trials for the step length with. tolerance (float) Minimum absolute value of a component of the step without stopping the line search.

Methods

__init__(wrt, f, decay=0.9, max_iter=inf, tolerance=1e-20)

Create BackTrack object.

Parameters: wrt : array_like Parameters over which the optimization is done. f : Callable Objective function. decay : float Factor to multiply trials for the step length with. max_iter : int, optional, default infinity Number of step lengths to try. tolerance : float Minimum absolute value of a component of the step without stopping the line search.
search(direction, initialization=1, args=None, kwargs=None, loss0=None)

Return a step length t given a search direction.

Perform the line search along a direction. Search will start at initialization and assume that the loss is loss0 at t == 0.

Parameters: direction : array_like Has to be of the same size as .wrt. Points along that direction will tried out to reduce the loss. initialization : float First attempt for a step size. Will be reduced by a factor of .decay afterwards. args : list, optional, default: None list of optional arguments for .f. kwargs : dictionary, optional, default: None list of optional keyword arguments for .f. loss0 : float, optional Loss at the current parameters. Will be calculated of not given.
class climin.linesearch.StrongWolfeBackTrack(wrt, f, fprime, decay=None, c1=0.0001, c2=0.9, tolerance=1e-20)

Class implementing a back tracking line search that finds points satisfying the Strong Wolfe conditions.

The idea is to jump to a starting step length $$t$$ and then shrink that step length by multiplying it with $$\gamma$$ until the strong Wolfe conditions are satisfied. That is the Armijo rule

$\begin{split}f(\theta_t+ \alpha_t d_t) & \leq f(\theta)+ c_1 \alpha_t d_t^T f'(\theta),\end{split}$

and the curvature condition

$\begin{split}\big|d_k^TTf('\theta_t+\alpha_t d_t)\big| & \leq c_2 \big|d_t^T f'(\theta_t)\big|.\end{split}$

At most max_iter attempts will be done. If the largest absolut value of a component of the step falls below tolerance, we stop as well. In both cases, a step length of 0 is returned.

To not possibly iterate forever, the field tolerance holds a small value (1E-20 per default). As soon as the absolute value of every component of the step (direction multiplied with the scalar from schedule) is less than tolerance, we stop.

Attributes

 wrt (array_like) Parameters over which the optimization is done. f (Callable) Objective function. decay (float) Factor to multiply trials for the step length with. tolerance (float) Minimum absolute value of a component of the step without stopping the line search. c1 (float) Constant in the strong Wolfe conditions. c2 (float) Constant in the strong Wolfe conditions.

Methods

__init__(wrt, f, fprime, decay=None, c1=0.0001, c2=0.9, tolerance=1e-20)

Create StrongWolfeBackTrack object.

Parameters: wrt : array_like Parameters over which the optimization is done. f : Callable Objective function. decay : float Factor to multiply trials for the step length with. tolerance : float Minimum absolute value of a component of the step without stopping the line search.
class climin.linesearch.ScipyLineSearch(wrt, f, fprime)

Wrapper around the scipy line search.

Methods

class climin.linesearch.WolfeLineSearch(wrt, f, fprime, c1=0.0001, c2=0.9, maxiter=25, min_step_length=1e-09, typ=4)

Port of Mark Schmidt’s line search.

Methods