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 onedimensional optimization problem, which can then be solved by a line search.

class
climin.linesearch.
BackTrack
(wrt, f, decay=0.9, max_iter=inf, tolerance=1e20)¶ 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 belowtolerance
, 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 (1E20 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=1e20)¶ 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 isloss0
att == 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=1e20)¶ 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}\bigd_k^TTf('\theta_t+\alpha_t d_t)\big & \leq c_2 \bigd_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 belowtolerance
, 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 (1E20 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=1e20)¶ 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=1e09, typ=4)¶ Port of Mark Schmidt’s line search.
Methods