# `optimize.linesearch`¶

## Module Contents¶

### Functions¶

 `line_search_wolfe1`(f,fprime,xk,pk,gfk=None,old_fval=None,old_old_fval=None,args=tuple,c1=0.0001,c2=0.9,amax=50,amin=1e-08,xtol=1e-14) As scalar_search_wolfe1 but do a line search to direction pk `scalar_search_wolfe1`(phi,derphi,phi0=None,old_phi0=None,derphi0=None,c1=0.0001,c2=0.9,amax=50,amin=1e-08,xtol=1e-14) Scalar function search for alpha that satisfies strong Wolfe conditions `line_search_wolfe2`(f,myfprime,xk,pk,gfk=None,old_fval=None,old_old_fval=None,args=tuple,c1=0.0001,c2=0.9,amax=None,extra_condition=None,maxiter=10) Find alpha that satisfies strong Wolfe conditions. `scalar_search_wolfe2`(phi,derphi=None,phi0=None,old_phi0=None,derphi0=None,c1=0.0001,c2=0.9,amax=None,extra_condition=None,maxiter=10) Find alpha that satisfies strong Wolfe conditions. `_cubicmin`(a,fa,fpa,b,fb,c,fc) Finds the minimizer for a cubic polynomial that goes through the `_quadmin`(a,fa,fpa,b,fb) Finds the minimizer for a quadratic polynomial that goes through `_zoom`(a_lo,a_hi,phi_lo,phi_hi,derphi_lo,phi,derphi,phi0,derphi0,c1,c2,extra_condition) Part of the optimization algorithm in scalar_search_wolfe2. `line_search_armijo`(f,xk,pk,gfk,old_fval,args=tuple,c1=0.0001,alpha0=1) Minimize over alpha, the function `f(xk+alpha pk)`. `line_search_BFGS`(f,xk,pk,gfk,old_fval,args=tuple,c1=0.0001,alpha0=1) Compatibility wrapper for line_search_armijo `scalar_search_armijo`(phi,phi0,derphi0,c1=0.0001,alpha0=1,amin=0) Minimize over alpha, the function `phi(alpha)`. `_nonmonotone_line_search_cruz`(f,x_k,d,prev_fs,eta,gamma=0.0001,tau_min=0.1,tau_max=0.5) Nonmonotone backtracking line search as described in  `_nonmonotone_line_search_cheng`(f,x_k,d,f_k,C,Q,eta,gamma=0.0001,tau_min=0.1,tau_max=0.5,nu=0.85) Nonmonotone line search from 
class `LineSearchWarning`
`line_search_wolfe1`(f, fprime, xk, pk, gfk=None, old_fval=None, old_old_fval=None, args=tuple, c1=0.0001, c2=0.9, amax=50, amin=1e-08, xtol=1e-14)

As scalar_search_wolfe1 but do a line search to direction pk

f : callable
Function f(x)
fprime : callable
Gradient of f
xk : array_like
Current point
pk : array_like
Search direction
gfk : array_like, optional
Gradient of f at point xk
old_fval : float, optional
Value of f at point xk
old_old_fval : float, optional
Value of f at point preceding xk

The rest of the parameters are the same as for scalar_search_wolfe1.

stp, f_count, g_count, fval, old_fval
As in line_search_wolfe1
gval : array
Gradient of f at the final point
`scalar_search_wolfe1`(phi, derphi, phi0=None, old_phi0=None, derphi0=None, c1=0.0001, c2=0.9, amax=50, amin=1e-08, xtol=1e-14)

Scalar function search for alpha that satisfies strong Wolfe conditions

alpha > 0 is assumed to be a descent direction.

phi : callable phi(alpha)
Function at point alpha
derphi : callable dphi(alpha)
Derivative d phi(alpha)/ds. Returns a scalar.
phi0 : float, optional
Value of f at 0
old_phi0 : float, optional
Value of f at the previous point
derphi0 : float, optional
Value derphi at 0
c1, c2 : float, optional
Wolfe parameters
amax, amin : float, optional
Maximum and minimum step size
xtol : float, optional
Relative tolerance for an acceptable step.
alpha : float
Step size, or None if no suitable step was found
phi : float
Value of phi at the new point alpha
phi0 : float
Value of phi at alpha=0

Uses routine DCSRCH from MINPACK.

`line_search_wolfe2`(f, myfprime, xk, pk, gfk=None, old_fval=None, old_old_fval=None, args=tuple, c1=0.0001, c2=0.9, amax=None, extra_condition=None, maxiter=10)

Find alpha that satisfies strong Wolfe conditions.

f : callable f(x,*args)
Objective function.
myfprime : callable f’(x,*args)
Objective function gradient.
xk : ndarray
Starting point.
pk : ndarray
Search direction.
gfk : ndarray, optional
Gradient value for x=xk (xk being the current parameter estimate). Will be recomputed if omitted.
old_fval : float, optional
Function value for x=xk. Will be recomputed if omitted.
old_old_fval : float, optional
Function value for the point preceding x=xk
args : tuple, optional
Additional arguments passed to objective function.
c1 : float, optional
Parameter for Armijo condition rule.
c2 : float, optional
Parameter for curvature condition rule.
amax : float, optional
Maximum step size
extra_condition : callable, optional
A callable of the form `extra_condition(alpha, x, f, g)` returning a boolean. Arguments are the proposed step `alpha` and the corresponding `x`, `f` and `g` values. The line search accepts the value of `alpha` only if this callable returns `True`. If the callable returns `False` for the step length, the algorithm will continue with new iterates. The callable is only called for iterates satisfying the strong Wolfe conditions.
maxiter : int, optional
Maximum number of iterations to perform
alpha : float or None
Alpha for which `x_new = x0 + alpha * pk`, or None if the line search algorithm did not converge.
fc : int
Number of function evaluations made.
gc : int
Number of gradient evaluations made.
new_fval : float or None
New function value `f(x_new)=f(x0+alpha*pk)`, or None if the line search algorithm did not converge.
old_fval : float
Old function value `f(x0)`.
new_slope : float or None
The local slope along the search direction at the new value `<myfprime(x_new), pk>`, or None if the line search algorithm did not converge.

Uses the line search algorithm to enforce strong Wolfe conditions. See Wright and Nocedal, ‘Numerical Optimization’, 1999, pg. 59-60.

For the zoom phase it uses an algorithm by […].

`scalar_search_wolfe2`(phi, derphi=None, phi0=None, old_phi0=None, derphi0=None, c1=0.0001, c2=0.9, amax=None, extra_condition=None, maxiter=10)

Find alpha that satisfies strong Wolfe conditions.

alpha > 0 is assumed to be a descent direction.

phi : callable f(x)
Objective scalar function.
derphi : callable f’(x), optional
Objective function derivative (can be None)
phi0 : float, optional
Value of phi at s=0
old_phi0 : float, optional
Value of phi at previous point
derphi0 : float, optional
Value of derphi at s=0
c1 : float, optional
Parameter for Armijo condition rule.
c2 : float, optional
Parameter for curvature condition rule.
amax : float, optional
Maximum step size
extra_condition : callable, optional
A callable of the form `extra_condition(alpha, phi_value)` returning a boolean. The line search accepts the value of `alpha` only if this callable returns `True`. If the callable returns `False` for the step length, the algorithm will continue with new iterates. The callable is only called for iterates satisfying the strong Wolfe conditions.
maxiter : int, optional
Maximum number of iterations to perform
alpha_star : float or None
Best alpha, or None if the line search algorithm did not converge.
phi_star : float
phi at alpha_star
phi0 : float
phi at 0
derphi_star : float or None
derphi at alpha_star, or None if the line search algorithm did not converge.

Uses the line search algorithm to enforce strong Wolfe conditions. See Wright and Nocedal, ‘Numerical Optimization’, 1999, pg. 59-60.

For the zoom phase it uses an algorithm by […].

`_cubicmin`(a, fa, fpa, b, fb, c, fc)

Finds the minimizer for a cubic polynomial that goes through the points (a,fa), (b,fb), and (c,fc) with derivative at a of fpa.

If no minimizer can be found return None

`_quadmin`(a, fa, fpa, b, fb)

Finds the minimizer for a quadratic polynomial that goes through the points (a,fa), (b,fb) with derivative at a of fpa,

`_zoom`(a_lo, a_hi, phi_lo, phi_hi, derphi_lo, phi, derphi, phi0, derphi0, c1, c2, extra_condition)

Part of the optimization algorithm in scalar_search_wolfe2.

`line_search_armijo`(f, xk, pk, gfk, old_fval, args=tuple, c1=0.0001, alpha0=1)

Minimize over alpha, the function `f(xk+alpha pk)`.

f : callable
Function to be minimized.
xk : array_like
Current point.
pk : array_like
Search direction.
gfk : array_like
Gradient of f at point xk.
old_fval : float
Value of f at point xk.
args : tuple, optional
Optional arguments.
c1 : float, optional
Value to control stopping criterion.
alpha0 : scalar, optional
Value of alpha at start of the optimization.

alpha f_count f_val_at_alpha

Uses the interpolation algorithm (Armijo backtracking) as suggested by Wright and Nocedal in ‘Numerical Optimization’, 1999, pg. 56-57

`line_search_BFGS`(f, xk, pk, gfk, old_fval, args=tuple, c1=0.0001, alpha0=1)

Compatibility wrapper for line_search_armijo

`scalar_search_armijo`(phi, phi0, derphi0, c1=0.0001, alpha0=1, amin=0)

Minimize over alpha, the function `phi(alpha)`.

Uses the interpolation algorithm (Armijo backtracking) as suggested by Wright and Nocedal in ‘Numerical Optimization’, 1999, pg. 56-57

alpha > 0 is assumed to be a descent direction.

alpha phi1

`_nonmonotone_line_search_cruz`(f, x_k, d, prev_fs, eta, gamma=0.0001, tau_min=0.1, tau_max=0.5)

Nonmonotone backtracking line search as described in 

f : callable
Function returning a tuple `(f, F)` where `f` is the value of a merit function and `F` the residual.
x_k : ndarray
Initial position
d : ndarray
Search direction
prev_fs : float
List of previous merit function values. Should have `len(prev_fs) <= M` where `M` is the nonmonotonicity window parameter.
eta : float
Allowed merit function increase, see 
gamma, tau_min, tau_max : float, optional
Search parameters, see 
alpha : float
Step length
xp : ndarray
Next position
fp : float
Merit function value at next position
Fp : ndarray
Residual at next position
 “Spectral residual method without gradient information for solving
large-scale nonlinear systems of equations.” W. La Cruz, J.M. Martinez, M. Raydan. Math. Comp. 75, 1429 (2006).
`_nonmonotone_line_search_cheng`(f, x_k, d, f_k, C, Q, eta, gamma=0.0001, tau_min=0.1, tau_max=0.5, nu=0.85)

Nonmonotone line search from 

f : callable
Function returning a tuple `(f, F)` where `f` is the value of a merit function and `F` the residual.
x_k : ndarray
Initial position
d : ndarray
Search direction
f_k : float
Initial merit function value
C, Q : float
Control parameters. On the first iteration, give values Q=1.0, C=f_k
eta : float
Allowed merit function increase, see 
nu, gamma, tau_min, tau_max : float, optional
Search parameters, see 
alpha : float
Step length
xp : ndarray
Next position
fp : float
Merit function value at next position
Fp : ndarray
Residual at next position
C : float
New value for the control parameter C
Q : float
New value for the control parameter Q
  (1, 2, 3, 4, 5, 6) W. Cheng & D.-H. Li, ‘’A derivative-free nonmonotone line search and its application to the spectral residual method’‘, IMA J. Numer. Anal. 29, 814 (2009).