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 [1]
_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 [1]
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 [1]

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 [1]
gamma, tau_min, tau_max : float, optional
Search parameters, see [1]
alpha : float
Step length
xp : ndarray
Next position
fp : float
Merit function value at next position
Fp : ndarray
Residual at next position
[1] “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 [1]

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 [1]
nu, gamma, tau_min, tau_max : float, optional
Search parameters, see [1]
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](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).