Continuous Optimisation HT26, Linesearch methods

• Choose $\epsilon > 0$ and $x^0 \in \mathbb R^n$.
• For $k \ge 0$ and while $ \vert \vert \nabla f(x^k) \vert \vert > \epsilon$:
  • Compute descent direction $s^k \in \mathbb R^n$ (i.e. such that $\nabla f(x^k)^\top s^k < 0$).
  • Compute step size $\alpha^k > 0$ along $s^k$ such that $f(x^k + \alpha^k s^k) < f(x^k)$
  • Set $x^{k+1} = x^k + \alpha^k s^k$ and $k = k+1$

Where the step size $\alpha^k$ is chosen so that

We write

Then

We also have

and hence

thus $\alpha^\ast$ is the stationary point of $\phi(\alpha)$ iff $(s^k)^\top H s^k \ne 0$ and

where this is the global minimiser of $\phi(\alpha)$ when $(s^k)^\top H s^k > 0$.

• Choose $\alpha _ {(0)} > 0$ and $\tau \in (0, 1)$.
• While $f(x^k + \alpha _ {(i)} s^k) \ge f(x^k)$, repeat:
  • Set $\alpha _ {(i+1)} = \tau \alpha _ {(i)}$
  • $i = i + 1$
• Set $\alpha^k = \alpha _ {(i)}$.

For some $\beta \in (0, 1)$, we aim to choose a stepsize such that

Remarks:

• Existence: Since $s^k$ is a descent direction, there always exists some $\overline \alpha^k > 0$ such that the Armijo condition holds for all $\alpha \in [0, \overline \alpha^k]$. The intuition is that for $\alpha = 0$, both sides of the Armijo inequality equal $f(x^k)$, and the RHS slope in $\alpha$ is $\beta \nabla f(x^k)^\top s^k$ (less negative, since $\beta < 1$ and the gradient inner product is negative) while the LHS lies below the RHS, and Armijo holds on some right-neighbourhood of $0$.
• We want the maximal $\alpha^k$: small step-sizes trivially satisfy Armijo but give very little progress per iteration. The ∆backtracking-armijo-linesearch aims for the largest feasible $\alpha^k$, found by starting at a large $\alpha _ {(0)}$ and shrinking by $\tau$ until Armijo is met.
• Under Lipschitz $\nabla f$, ∆armijo-condition-satisifed-when-lipschitz gives an explicit value $\alpha^k _ \max$ for one such interval $[0, \alpha^k _ \max]$.

• Choose $\alpha _ {(0)} > 0$ and $\tau \in (0, 1)$.
• While $f(x^k + \alpha _ {(i)} s^k) > f(x^k) + \beta \alpha _ {(i)} \nabla f(x^k)^\top s^k$, repeat:
  • Set $\alpha _ {(i+1)} = \tau \alpha _ {(i)}$
  • $i = i + 1$
• Set $\alpha^k = \alpha _ {(i)}$.

If $s^k$ is a descent direction so that $\nabla f(x^k)^\top s^k < 0$, then this algorithm terminates in a finite number of steps.

The Armijo condition is satisfied for all $\alpha \in [0, \alpha^k _ \max]$ where

Remark: this is the lecture’s bound, obtained via the crude $\tilde \alpha \le \alpha$ step in the proof; it is not tight. Replacing that step with the ∆descent-lemma (the sharp $L$-smooth bound $f(x + d) \le f(x) + \nabla f(x)^\top d + \tfrac L 2 \vert \vert d \vert \vert ^2$) improves $\alpha^k _ \max$ by a factor of two, to

Both are sufficient conditions, not necessary.

Note that $\alpha^k _ \max > 0$ since $\beta \in (0, 1)$ and $s^k$ is a descent direction. Then for any $\alpha > 0$ and some $\tilde \alpha \in (0, \alpha)$, we have

where:

• $(\star 1)$ is justified by the first-order Taylor expansion
• $(\star 2)$ is justified by the Cauchy-Schwarz inequality
• $(\star 3)$ is justified by the Lipschitz continuity of the gradient
• $(\star 4)$ is justified by the fact that $\tilde \alpha \le \alpha$

Thus the Armijo condition is (guaranteed to be / sufficiently) satisfied for all $\alpha \ge 0$ such that

which is equivalent to $\alpha \in [0, \alpha^k _ \max]$.

(note that this is a sufficient condition, but not a necessary one).

Remark (a factor-of-2 sharper interval): steps $(\star 3)$–$(\star 4)$ bound the intermediate point crudely by $\tilde \alpha \le \alpha$, which inflates the quadratic coefficient to $L$. Using the ∆descent-lemma instead,

halves that coefficient to $L/2$ (its integral form contributes $\int _ 0^1 t \, \mathrm dt = \tfrac 1 2$, exactly the factor the $\tilde \alpha \le \alpha$ bound throws away). Repeating the Armijo solve with $\tfrac{L}{2} \alpha^2 \|s^k\|^2$ in place of $\alpha^2 L \|s^k\|^2$ then doubles the guaranteed interval:

The headline statement above keeps the course’s (cruder) $\alpha^k _ \max$, since ∆armijo-stepsize-bound and ∆global-convergence-of-backtracking-armijo-proof are stated against that constant; the sharper version only changes constants, not the conclusion.

for all $k \ge 0$ where $\alpha^k _ \max$ is defined as

Case 1: If $\alpha _ {(0)}$ satisfies the Armijo condition, bArmijo terminates at $i = 0$ with $\alpha^k = \alpha _ 0 \ge \min\{\alpha _ {(0)}, \tau \alpha^k _ \max\}$.

Case 2: Otherwise by ∆armijo-condition-satisifed-when-lipschitz, the Armijo condition holds for all $\alpha \in [0, \alpha^k _ \max]$, so bArmijo terminates by at least the first index $i$ at which $\alpha _ {(i)} \le \alpha^k _ \max$. Such an $i$ exists since $\alpha _ {(i)} = \tau^i \alpha _ {(0)} \le \alpha^k _ \max$ once $i \ge \log(\alpha _ {(0)}/\alpha^k _ \max) / \vert \log \tau \vert $.

Since iterates are decreasing in $i$, $\alpha^k \ge \alpha _ {(i)} = \tau \alpha _ {(i-1)} > \tau \alpha^k _ \max$, where $\alpha _ {(i-1)} > \alpha^k _ \max$ by the minimality of $i$.

Combining both cases gives the bound.

Either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, or

If there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, we are done.

Assume now that $\nabla f(x^k) \ne 0$ for all $k \ge 0$. Then the ∆armijo-condition with $\alpha := \alpha^k$ and $x^{k+1} = x^k + \alpha^k s^k$ give

for all $k \ge 0$, or equivalently for all $k \ge 0$

Since $\nabla f(x^k)^\top s^k < 0$ (as $s^k$ is a descent direction), it follows $(-\nabla f(x^k))^\top s^k = \vert \nabla f(x^k)^\top s^k \vert $ and therefore

Let $i \ge 0$. Summing up this inequality from $k = 0$ to $k = i$ gives a telescoping sum and hence

As $f$ is bounded below by $f _ \text{low}$, $f(x^{i+1}) \ge f _ \text{low}$ for all $i \ge 0$. Thus as $i \to \infty$ in $(2)$, it follows that

Since this series converges, the individual terms must tend towards 0. Hence

Recall from the ∆armijo-stepsize-bound that

Define the following sets

and note that every iteration $k$ either belongs to $\mathcal K _ 1$ or $\mathcal K _ 2$.

For all $k \in \mathcal K _ 1$, we have from the ∆armijo-stepsize-bound and ∆armijo-condition-satisifed-when-lipschitz that

and hence the limit above implies that

The ∆armijo-stepsize-bound also gives that $\alpha^k \ge \alpha _ {(0)}$ for all $k \in \mathcal K _ 2$, so furthermore

These two limits for the $\mathcal K _ 1$ and $\mathcal K _ 2$ subsequences together imply the required result, namely that

Let $\theta _ k$ be the angle between the descent direction $s^k$ and the steepest-descent direction $-\nabla f(x^k)$, so that

(the second equality uses $\nabla f(x^k)^\top s^k < 0$ from descent, so $-\nabla f(x^k)^\top s^k = \vert \nabla f(x^k)^\top s^k \vert $).

Derivation: rearranging, $ \vert \nabla f(x^k)^\top s^k \vert = \|\nabla f(x^k)\| \cdot \|s^k\| \cdot \cos \theta_k$, so

• $\dfrac{ \vert \nabla f(x^k)^\top s^k \vert }{\|s^k\|} = \|\nabla f(x^k)\| \cos \theta_k$, and
• $ \vert \nabla f(x^k)^\top s^k \vert = \|\nabla f(x^k)\| \cos \theta_k \cdot \|s^k\|$, hence
• $\min\!\left\{\dfrac{ \vert \nabla f(x^k)^\top s^k \vert }{\|s^k\|}, \; \vert \nabla f(x^k)^\top s^k \vert \right\} = \|\nabla f(x^k)\| \cos \theta_k \cdot \min\{1, \|s^k\|\}$.

So the result is equivalent to

Implication: for $\|\nabla f(x^k)\| \to 0$ (true global convergence), we need to stop $\cos \theta_k$ or $\|s^k\|$ from driving the product to zero on their own. The first is the substantive condition: require $\cos \theta_k \ge \delta > 0$ for all $k$, i.e. $s^k$ stays within a bounded angle of $-\nabla f(x^k)$ and never becomes orthogonal to the steepest-descent direction.

There exist constants $0 < c _ 1 < c _ 2 < 1$ such that for all $k \in \mathbb N$:

• (W1, Armijo condition / sufficient decrease):

• (W2, curvature condition):

Why each:

• (W1) is an “upgraded” version of the simple monotone-decrease condition $f(x^{k+1}) < f(x^k)$, with an additional term proportional to the step length and the directional derivative to ensure that there is sufficient decrease (not just any decrease).
• (W2) prevents (W1) from being satisfied by just taking very small values of $\alpha^k$. The original directional derivative $\nabla f(x^k)^\top s^k$ is negative, and (W2) requires that at the new point the directional derivative is “less negative” by a factor of $c _ 2$ — i.e. that the function has flattened along $s^k$.

For chosen $0 < \beta < \tfrac{1}{2}$, the Goldstein-Armijo conditions on $\alpha^k$ are the two function-value inequalities:

• (GA1, sufficient decrease — same as the standard ∆armijo-condition) rules out stepsizes that are too long:

• (GA2, Goldstein lower bound) rules out stepsizes that are too short by forcing the achieved decrease to be at most $(1 - \beta) \alpha^k \vert \nabla f(x^k)^\top s^k \vert $:

Versus Wolfe. Wolfe also has a sufficient-decrease half (W1), but enforces the “not too short” side via a gradient condition $\nabla f(x^k + \alpha^k s^k)^\top s^k \ge c _ 2 \nabla f(x^k)^\top s^k$ (W2). Goldstein-Armijo uses two function-value inequalities (no extra gradient evaluation), which is cheaper but can exclude the exact minimiser of $f(x^k + \alpha s^k)$.

Define the line $y _ \beta(\alpha) := \Phi _ k(0) + \beta \alpha \Phi _ k'(0)$, $\alpha \ge 0$. Then $\alpha$ satisfies Armijo iff $\Phi _ k(\alpha) \le y _ \beta(\alpha)$, i.e. the graph of $\Phi _ k$ lies on or below the line $y _ \beta$.

• $\beta = 0$: $y _ \beta$ is horizontal at $\Phi _ k(0)$ — Armijo reduces to “$f$ strictly decreases.”
• $\beta = 1$: $y _ \beta$ is the tangent line to $\Phi _ k$ at $\alpha = 0$ — Armijo is almost impossible to satisfy.
• Practical $\beta \in (0, 1)$ (often $\beta = 0.1$ or smaller): $y _ \beta$ is a “shallow” line slightly steeper than horizontal, and Armijo is satisfied on a generous interval around $\alpha = 0$.

The condition is given by the top line, the bottom line is the extra condition from the ∆wolfe-conditions.

• Parameterise: define $\phi _ k(\alpha) := q(x^k + \alpha s^k)$ so the linesearch becomes a 1D problem in $\alpha$.
• Differentiate via chain rule: $\phi _ k'(\alpha) = (s^k)^\top \nabla q(x^k + \alpha s^k)$.
• Substitute $\nabla q(x) = g + Hx$ to expand $\nabla q(x^k + \alpha s^k)$ linearly in $\alpha$, giving $\phi _ k'(\alpha) = (s^k)^\top \nabla q(x^k) + \alpha (s^k)^\top H s^k$.
• Set $\phi _ k'(\alpha^\ast) = 0$ and solve, valid whenever $(s^k)^\top H s^k \ne 0$; this is a global minimiser when $(s^k)^\top H s^k > 0$.

• First-order Taylor with mean-value remainder: $f(x^k + \alpha s^k) = f(x^k) + \alpha \nabla f(x^k + \tilde\alpha s^k)^\top s^k$ for some $\tilde\alpha \in (0, \alpha)$.
• Add and subtract $\alpha \nabla f(x^k)^\top s^k$ to isolate a gradient-difference term.
• Cauchy–Schwarz to bound the gradient-difference inner product by norms.
• Apply Lipschitz of $\nabla f$ to convert $\|\nabla f(x^k + \tilde\alpha s^k) - \nabla f(x^k)\|$ to $L \tilde\alpha \|s^k\|$, then use $\tilde\alpha \le \alpha$ to get the quadratic-in-$\alpha$ upper bound $\alpha^2 L \|s^k\|^2$.
• Solve the resulting linear-in-$\alpha$ inequality (after dividing through by $\alpha > 0$) to read off the threshold $\alpha^k _ \max = (\beta - 1) \nabla f(x^k)^\top s^k / (L \|s^k\|^2)$.

• Lipschitz enters at line $(\star 3)$ to convert the gradient-difference norm $\|\nabla f(x^k + \tilde\alpha s^k) - \nabla f(x^k)\|$ into $L \tilde\alpha \|s^k\|$, a multiple of the step length. This is the move that produces the $\alpha^2$ term needed to close the inequality.
• Without Lipschitz the remainder is only $o(1)$ as $\alpha \to 0$ (mere continuity), so the Armijo condition still holds on some interval $[0, \bar\alpha^k]$ but with no explicit lower bound on $\bar\alpha^k$ — meaning bArmijo’s stepsize bound ∆armijo-stepsize-bound (and hence the global-convergence proof) would fail.

• $\beta$ enters in the final solve: the threshold $\alpha^k _ \max = (\beta - 1) \nabla f(x^k)^\top s^k / (L \|s^k\|^2)$ requires the numerator to be strictly positive. Since $s^k$ is descent ($\nabla f(x^k)^\top s^k < 0$), this needs $\beta - 1 < 0$, i.e. $\beta < 1$.
• $\beta = 1$: the Armijo “line” coincides with the tangent to $\Phi _ k$ at $0$, so the only feasible $\alpha$ is $0$ (no progress).
• $\beta = 0$: Armijo collapses to “$f$ strictly decreases”, which has no quantitative decrease — global convergence fails because the descent per step is no longer $\Omega(\alpha^k \|\nabla f^\top s^k\|)$.

• Split into two cases on whether $\alpha _ {(0)}$ itself already satisfies Armijo.
• Case 1 ($\alpha _ {(0)}$ accepted): bArmijo terminates at $i = 0$ with $\alpha^k = \alpha _ {(0)} \ge \min$.
• Case 2 ($\alpha _ {(0)}$ rejected): by ∆armijo-condition-satisifed-when-lipschitz, the Armijo set contains $[0, \alpha^k _ \max]$, so backtracking terminates at the first index $i$ with $\alpha _ {(i)} \le \alpha^k _ \max$. Such an $i$ exists since $\alpha _ {(i)} = \tau^i \alpha _ {(0)} \to 0$.
• Use the minimality of $i$ to argue $\alpha _ {(i-1)} > \alpha^k _ \max$, then $\alpha^k = \alpha _ {(i)} = \tau \alpha _ {(i-1)} > \tau \alpha^k _ \max \ge \min$.

• Apply Armijo at iterate $k$ to get the per-step decrease $f(x^k) - f(x^{k+1}) \ge \beta \alpha^k \vert \nabla f(x^k)^\top s^k \vert $.
• Telescope from $k = 0$ to $i$; bounded-below $f \ge f _ \text{low}$ gives a convergent series, hence $\alpha^k \vert \nabla f(x^k)^\top s^k \vert \to 0$.
• Split iterates by stepsize regime: $\mathcal K _ 1 = \{k : \alpha _ {(0)} \ge \tau \alpha^k _ \max\}$ versus $\mathcal K _ 2 = \{k : \alpha _ {(0)} < \tau \alpha^k _ \max\}$.
• On $\mathcal K _ 1$: combine ∆armijo-stepsize-bound ($\alpha^k \ge \tau \alpha^k _ \max$) with ∆armijo-condition-satisifed-when-lipschitz (Lemma 2’s $\alpha^k _ \max$ formula) to bound $\alpha^k \vert \nabla f^\top s^k \vert $ below by $\frac{(1-\beta)\tau}{L}( \vert \nabla f^\top s^k \vert /\|s^k\|)^2$; deduce $ \vert \nabla f^\top s^k \vert /\|s^k\| \to 0$.
• On $\mathcal K _ 2$: $\alpha^k \ge \alpha _ {(0)}$ directly, so $ \vert \nabla f(x^k)^\top s^k \vert \to 0$.
• Combine via $\min\{a, b\} \le a, b$ for both subsequences to get the joint $\min$-limit.

• Bounded-below enters at the telescoping step: summing the per-step decrease gives $f(x^0) - f(x^{i+1}) \ge \beta \sum _ {k=0}^i \alpha^k \vert \nabla f(x^k)^\top s^k \vert $. The LHS is bounded by $f(x^0) - f _ \text{low}$ as $i \to \infty$, so the full series converges and $\alpha^k \vert \nabla f(x^k)^\top s^k \vert \to 0$.
• Without a lower bound, $f(x^k) \to -\infty$ is allowed; the series could diverge and the individual terms need not vanish, so we lose the limit that feeds both the $\mathcal K _ 1$ and $\mathcal K _ 2$ arguments.