relentless.optimize.LineSearch#

class relentless.optimize.LineSearch(tolerance, max_iter)#

Line search algorithm

Given an ObjectiveFunction \(f\left(\mathbf{x}\right)\) and a search interval defined as \(\mathbf{d}=\mathbf{x}_{end}-\mathbf{x}_{start}\), the line search algorithm seeks an optimal step size \(0<\alpha<1\) such that the following quantity is minimized:

\[f\left(\mathbf{x}_{start}+\alpha\mathbf{d}\right)\]

This is done by defining a scalar “target” value \(t\) as:

\[t = -\mathbf{d} \cdot \nabla{f\left(\mathbf{x}\right)}\]

One measure of the optimal value of \(\alpha\) is when \(t\) decreases sufficiently relative to its value at the start of the interval:

\[t(\alpha) < c\left\lvert t_{start}\right\rvert\]

where \(c\) is a defined relative tolerance value, and \(t_{start}\) is the target value at the start of the search interval. This is the strong Wolfe condition on curvature.

Because \(\mathbf{d}\) is a descent direction, the target at the start of the search interval is always positive. If the target is positive (or within the tolerance) at the end of the search interval, then the maximum step size is acceptable and the algorithm steps to the end of the search interval. If the target is negative (outside of the tolerance) at the end of the search interval, then the algorithm iteratively computes a new step size by linear interpolation within the search interval until the target at the new location is minimized to within the tolerance.

If directory is specified, one directory is created for each iteration of the line search, e.g., directory/0.

Parameters:

  • tolerance (float) – The relative tolerance for the target (\(c\)).

  • max_iter (int) – The maximum number of line search iterations allowed.

Methods

find(objective, start, end[, directory, scale])

Apply the line search algorithm to take the optimal step.

Attributes

max_iter

The maximum number of line search iterations allowed.

tolerance

The relative tolerance for the target.
find(objective, start, end, directory=None, scale=1.0)#

Apply the line search algorithm to take the optimal step.

Note that the objective function is kept at its initial state, and the function evaluted after taking the optimal step is returned separately.

Parameters:

  • objective (ObjectiveFunction) – The objective function for which the line search is applied.

  • start (ObjectiveFunctionResult) – The objective function evaluated at the start of the search interval.

  • end (ObjectiveFunctionResult) – The objective function evaluated at the end of the search interval.

  • directory (str or Directory) – Directory for writing output during search. Default of None requests no output is written.

  • scale (float or dict) – A scalar scaling parameter or scaling parameters (:math:mathbf{X}`) keyed on one or more ObjectiveFunction design variables (defaults to 1.0, so that the variables are unscaled).

Returns:

The objective function evaluated at the new, “optimal” location.

Return type:

ObjectiveFunctionResult

property max_iter#

The maximum number of line search iterations allowed.

Type:

int

property tolerance#

The relative tolerance for the target. Must be between 0 and 1.

Type:

float