LineSearch: Difference between revisions
No edit summary |
No edit summary |
||
Line 11: | Line 11: | ||
where <math>x, p \in \ | where <math>x, p \in \mathbb{R}^{n}</math>. | ||
==Calling Syntax== | ==Calling Syntax== |
Latest revision as of 10:57, 8 December 2011
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:
| |||||||||||
alphaMax | Maximal value of step length α. | |||||||||||
pType | Type of problem:
| |||||||||||
PriLev | Printing level:
| |||||||||||
varargin | Other parameters directly sent to low level routines. |
Outputs
Output | Description | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Result | Result structure with fields:
|
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.