LineSearch

From TomWiki
Jump to navigationJump to search

Purpose

LineSearch solves line search problems of the form



where .

Calling Syntax

Result = LineSearch(f, g, x, p, f_0, g_0, LineParam, alphaMax, pType, PriLev, varargin)

Inputs

Input Description
f Name of m-file computing the objective function f (x).
g Name of m-file computing the gradient vector g(x).
x Current iterate x.
p Search direction p.
f_0 Function value at a = 0.
g_0 Gradient at a = 0, the directed derivative at the present point.
LineParam Structure with line search parameters (see TOMLAB Appendix A), the following fields are used:
LineAlg Type of line search algorithm, 0 = quadratic interpolation, 1 = cubic interpolation.
fLowBnd Lower bound on the function value at optimum.

sigma InitStepLength rho tau1 tau2 tau3 eps1 eps2 see TOMLAB Appendix A.

alphaMax Maximal value of step length α.
pType Type of problem:
0 Normal problem.
1 Nonlinear least squares.
2 Constrained nonlinear least squares.
3 Merit function minimization.
4 Penalty function minimization.
PriLev Printing level:
PriLev > 0 Writes a lot of output in LineSearch.
PriLev > 3 Writes a lot of output in intpol2 and intpol3.
varargin Other parameters directly sent to low level routines.

Outputs

Output Description
Result Result structure with fields:
alpha Optimal line search step α.
f_alpha Optimal function value at line search step α.
g_alpha Optimal gradient value at line search step α.
alphaVec Vector of trial step length values.
r_k Residual vector if Least Squares problem, otherwise empty.
J_k Jacobian matrix if Least Squares problem, otherwise empty.
f_k Function value at x + αp.
g_k Gradient value at x + αp.
c_k Constraint value at x + αp.
dc_k Constraint gradient value at x + αp.

Description

The function LineSearch together with the routines intpol2 and intpol3 implements a modified version of a line search algorithm by Fletcher. The algorithm is based on the Wolfe-Powell conditions and therefore the availability of first order derivatives is an obvious demand. It is also assumed that the user is able to supply a lower bound fLow on f(α). More precisely it is assumed that the user is prepared to accept any value of f(α) for which f(α) = fLow . For example in a nonlinear least squares problem fLow = 0 would be appropriate.

LineSearch consists of two parts, the bracketing phase and the sectioning phase. In the bracketing phase the iterates a(k) moves out in an increasingly large jumps until either f <= fLow is detected or a bracket on an interval of acceptable points is located. The sectioning phase generates a sequence of brackets [a(k) , b(k)] whose lengths tend to zero. Each iteration pick a new point a(k) in [a(k) , b(k)] by minimizing a quadratic or a cubic polynomial which interpolates f(a(k)), f'(a(k)), f(b(k) ) and f'(b(k)) if it is known. The sectioning phase terminates when a(k) is an acceptable point.