public class LineSearch
extends java.lang.Object
f(s) <= f(0) + ftol*f'(0)*s,and the curvature condition (2) is
abs(f'(s)) <= gtol*abs(f'(0)),for specified non-negative tolerances ftol and gtol. Condition (1) ensures a sufficient decrease in the function f(s), provided that s is not too small. Condition (2) ensures that s is not too small, and usually guarantees that s is near a local minimizer of f. It is called a curvature condition because it implies that
f'(s) - f'(0) > (1-gtol)*abs(f'(0)),so that the average curvature of f on the interval (0,s) is positive. The curvature condition (2) is especially important in a quasi-Newton method for function minimization, because it guarantees that a positive-definite quasi-Newton update is possible. If ftol is less than gtol and the function f(s) is bounded below, then there exists a step s that satisfies both conditions. If such a step cannot be found, then only the first sufficient-decrease condition (1) is satisfied. Mor'e and Thuente's algorithm initially choses an interval [sa,sb] that contains a minimizer of a modified function
h(s) = f(s) - f(0) - ftol*f'(0)*sIf h(s) <= 0 and f'(s) >= 0 for some step s, then the interval [a,b] is chosen so that it contains a minimizer of f. If no step can be found that satisfies both conditions, then the algorithm ends unconverged. In this case the step s satisifies only the sufficient-decrease condition. References:
Modifier and Type | Class and Description |
---|---|
static interface |
LineSearch.Function
The function to be minimized.
|
static class |
LineSearch.Result
The result of a line search.
|
Modifier and Type | Field and Description |
---|---|
static int |
CONVERGED
Line search converged.
|
static int |
FAILED
Line search failed due to rounding error.
|
static int |
SMAX
Line search ended because the step equals a specified maximum.
|
static int |
SMIN
Line search ended because the step equals a specified minimum.
|
static int |
STOL
Line search ended because the step has been resolved to within
a specified tolerance.
|
Constructor and Description |
---|
LineSearch(LineSearch.Function func,
double stol,
double ftol,
double gtol)
Constructs a line search with specified tolerances.
|
Modifier and Type | Method and Description |
---|---|
LineSearch.Result |
search(double s,
double f,
double g,
double smin,
double smax)
Searches for a minimizing step.
|
public static final int CONVERGED
public static final int SMIN
public static final int SMAX
public static final int STOL
public static final int FAILED
public LineSearch(LineSearch.Function func, double stol, double ftol, double gtol)
func
- Function to search.stol
- non-negative relative tolerance for an acceptable step.
The search ends if the search interval [slo,shi] is smaller than
this tolerance times the upper bound shi.ftol
- non-negative tolerance for sufficient-decrease condition (1).gtol
- non-negative tolerance for curvature condition (2).public LineSearch.Result search(double s, double f, double g, double smin, double smax)
s
- current estimate of a satisfactory step. Must be positive.f
- value f(0) of the function f at s = 0.g
- value f'(0) of the derivative of f at s = 0.smin
- Minimum value of s to be searched.smax
- Maximum value of s to be searched.