1.3. Line Search Methods¶
Line search methods are techniques used in optimization to find an appropriate step size along a given search direction. These methods aim to efficiently determine the step size that minimizes the objective function. This section covers some common line search methods.
1.3.1. Golden Section Search¶
The Golden Section Search is an iterative method used to find the minimum of a unimodal function. It is based on the golden ratio and reduces the interval of uncertainty at each iteration.
Algorithm:
Choose an initial interval \([a, b]\) such that the minimum lies within this interval.
Compute the interior points using the golden ratio:
\[c = a + \frac{b - a}{\phi}, \quad d = b - \frac{b - a}{\phi}\]where \(\phi = \frac{1 + \sqrt{5}}{2}\) is the golden ratio.
Evaluate the objective function at \(c\) and \(d\).
Update the interval:
If \(f(c) < f(d)\), set \(b = d\).
If \(f(c) \geq f(d)\), set \(a = c\).
Repeat steps 2-4 until the interval \([a, b]\) is sufficiently small.
1.3.2. Bisection Method¶
The Bisection Method is a simple yet effective line search technique that repeatedly divides the interval into two halves to locate the minimum.
Algorithm:
Choose an initial interval \([a, b]\) such that the minimum lies within this interval.
Compute the midpoint:
\[m = \frac{a + b}{2}\]Evaluate the objective function at \(m\).
Update the interval:
If \(f'(m) = 0\), \(m\) is the minimum.
If \(f'(m) > 0\), set \(b = m\).
If \(f'(m) < 0\), set \(a = m\).
Repeat steps 2-4 until the interval \([a, b]\) is sufficiently small.
1.3.3. Armijo Rule¶
The Armijo Rule is a condition used to determine the step size in gradient descent methods. It ensures sufficient decrease in the objective function.
Algorithm: 1. Choose parameters \(\sigma \in (0, 1)\) and \(\beta \in (0, 1)\).
Set the initial step size \(\alpha = 1\).
Check the Armijo condition:
\[f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + \sigma \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k\]If the condition is not satisfied, reduce the step size: \(alpha = \beta \alpha\).
Repeat step 3-4 until the condition is satisfied.
1.3.4. Wolfe Conditions¶
The Wolfe Conditions are a set of criteria used to ensure both sufficient decrease and curvature conditions for the step size.
Algorithm: 1. Choose parameters \(0 < \sigma_1 < \sigma_2 < 1\).
Set the initial step size \(\alpha = 1\).
Check the Wolfe conditions:
Sufficient decrease (Armijo condition):
\[f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + \sigma_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k\]Curvature condition:
\[\nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \geq \sigma_2 \nabla f(\mathbf{x}_k)^T \mathbf{d}_k\]
If the conditions are not satisfied, adjust the step size (alpha).
Repeat step 3-4 until both conditions are satisfied.
These line search methods help ensure that the optimization process converges efficiently and effectively by selecting appropriate step sizes.