# Notes - Continuous Optimisation HT26, Linesearch methods

> Source: https://ollybritton.com/notes/uni/part-c/ht26/continuous-optimisation/notes/linesearch-methods/ · Updated: 2026-06-08 · Tags: uni, notes

- [Course - Continuous Optimisation HT26](https://ollybritton.com/notes/uni/part-c/ht26/continuous-optimisation/)
	- [Notes - Continuous Optimisation HT26, Steepest descent](https://ollybritton.com/notes/uni/part-c/ht26/continuous-optimisation/notes/steepest-descent/)
	- See also:
	- [Notes - Optimisation for Data Science HT25, Steepest descent with inexact line search](https://ollybritton.com/notes/uni/part-b/ht25/optimisation-for-data-science/notes/steepest-descent-with-inexact-line-search/)

### Flashcards
<!-- flash-start -->
Suppose we wish to minimise $f(x)$ subject to $x \in \mathbb R^n$, where $f \in \mathcal C^1$ or $\mathcal C^2$.

@State the @algorithm corresponding to generic linesearch methods.::

- Choose $\epsilon > 0$ and $x^0 \in \mathbb R^n$.
- For $k \ge 0$ and while $||\nabla f(x^k)|| > \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$

^generic-linesearch-method
<!-- flash-end -->

<!-- flash-start -->
Suppose we are minimising $f$ at iteration $k$. @Define what is meant by a descent direction.::

$$
\nabla f(x^k)^\top s^k < 0
$$

^descent-direction
<!-- flash-end -->

### Exact linesearch
<!-- flash-start -->
@Define what is meant by an exact linesearch method.::

Where the step size $\alpha^k$ is chosen so that
$$
\alpha^k := \text{argmin}_{\alpha > 0} f(x^k + \alpha s^k)
$$

^exact-linesearch-definition
<!-- flash-end -->

<!-- flash-start -->
Suppose we have a quadratic function
$$
q(x) = g^\top x + \frac 1 2 x^\top H x
$$
where $x \in \mathbb R^n$ and aim to minimise this via a linesearch method along directions $s^k$.

@State the optimal stepsize $\alpha^\ast$ at step $k$ in this case.::

$$
\alpha^\ast = -\frac{(s^k)^\top \nabla q(x^k)}{(s^k)^\top H s^k}
$$

^exact-linesearch-quadratic-optimal-stepsize
<!-- flash-end -->

<!-- flash-start -->
Suppose we have a quadratic function
$$
q(x) = g^\top x + \frac 1 2 x^\top H x
$$
where $x \in \mathbb R^n$ and aim to minimise this via a linesearch method along directions $s^k$.

@Prove that the optimal stepsize $\alpha^\ast$ at step $k$ in this case is
$$
\alpha^\ast = -\frac{(s^k)^\top \nabla q(x^k)}{(s^k)^\top H s^k}
$$

::

We write
$$
\phi_k(\alpha) := q(x^k + \alpha s^k)
$$
Then
$$
\begin{aligned}
\phi'(\alpha) &= \frac{\text d}{\text d \alpha} \phi(\alpha) \\
&= \sum^n_{i = 1} \frac{\text d x_i}{\text d \alpha} \frac{\partial}{\partial x_i} \phi(\alpha) \\
&= \sum^n_{i = 1} s^k_i \frac{\partial}{\partial x_i} q(x^k + \alpha s^k) \\
&= (s^k)^\top \nabla q(x^k + \alpha s^k)
\end{aligned}
$$
We also have
$$
\begin{aligned}
\nabla q(x) &= g + Hx \\
\nabla q(x^k + \alpha s^k) &= g + H(x^k + \alpha s^k)
\end{aligned}
$$
and hence
$$
\phi'(\alpha) = (s^k)^\top \nabla q(x^k) + \alpha (s^k)^\top H s^k
$$
thus $\alpha^\ast$ is the stationary point of $\phi(\alpha)$ iff $(s^k)^\top H s^k \ne 0$ and
$$
\alpha^\ast = -\frac{(s^k)^\top \nabla q(x^k)}{(s^k)^\top H s^k}
$$
where this is the global minimiser of $\phi(\alpha)$ when $(s^k)^\top H s^k > 0$.

^exact-linesearch-quadratic-optimal-stepsize-proof
<!-- flash-end -->

### Backtracking
<!-- flash-start -->
Suppose we are trying to find some $\alpha^k$ to use as our stepsize to minimise $f(x^k + \alpha^k s^k)$. Describe the basic backtracking @algorithm that can be used in this case.::

- 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)}$.

^basic-backtracking-algorithm
<!-- flash-end -->

<!-- flash-start -->
@State the Armijo condition.::

For some $\beta \in (0, 1)$, we aim to choose a stepsize such that
$$
f(x^k + \alpha^k s^k) \le f(x^k) + \beta \alpha^k \nabla f(x^k)^\top s^k
$$

---

**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]$.

^armijo-condition
<!-- flash-end -->

<!-- flash-start -->
The ∆armijo-condition states that for some $\beta \in (0, 1)$, we aim to choose a stepsize such that
$$
f(x^k + \alpha^k s^k) \le f(x^k) + \beta \alpha^k \nabla f(x^k)^\top s^k
$$
What values of $\beta$ are typically used in practice?::

$$
\beta = 0.1, 0.01, 0.001
$$

^armijo-typical-beta-values
<!-- flash-end -->

<!-- flash-start -->
Suppose we are trying to find some $\alpha^k$ to use as our stepsize to minimise $f(x^k + \alpha^k s^k)$. Describe the Armijo backtracking (bArmijo) @algorithm that can be used in this case.::

- 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)}$.

^backtracking-armijo-linesearch
<!-- flash-end -->

<!-- flash-start -->
Suppose we are trying to find some $\alpha^k$ to use as our stepsize to minimise $f(x^k + \alpha^k s^k)$. The Armijo backtracking algorithm in this case is as follows:

- 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)}$.

@State a result about the termination of this algorithm.::

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.

^barmijo-terminates-finite-steps
<!-- flash-end -->

### Convergence of GLM
<!-- flash-start -->
Suppose:

- $f \in \mathcal C^1(\mathbb R^n)$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$

@State a result about when the ∆armijo-condition
$$
f(x^k + \alpha s^k) \le f(x^k) + \beta \alpha \nabla f(x^k)^\top s^k
$$
is satisfied when a generic linesearch method is applied to minimising $f$.::

The Armijo condition is satisfied for all $\alpha \in [0, \alpha^k_\max]$ where
$$
\alpha^k_\max = \frac{(\beta - 1)\nabla f(x^k)^\top s^k}{L||s^k||^2}
$$

**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 ||d||^2$) improves $\alpha^k_\max$ by a factor of two, to
$$
\alpha^k_\max = \frac{2(\beta - 1)\nabla f(x^k)^\top s^k}{L||s^k||^2}.
$$
Both are sufficient conditions, not necessary.

^armijo-condition-satisifed-when-lipschitz
<!-- flash-end -->

<!-- flash-start -->
Suppose:

- $f \in \mathcal C^1(\mathbb R^n)$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$

@Prove that then the ∆armijo-condition
$$
f(x^k + \alpha s^k) \le f(x^k) + \beta \alpha \nabla f(x^k)^\top s^k
$$
is satisfied for all $\alpha \in [0, \alpha^k_\max]$ where
$$
\alpha^k_\max = \frac{(\beta - 1) \nabla f(x^k)^\top s^k}{L||s^k||^2}
$$
::

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
$$
\begin{aligned}
f(x^k + \alpha s^k) &= f(x^k) + \alpha \nabla f(x^k + \tilde \alpha s^k)^\top s^k &&(\star1)\\
&= f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha [\nabla f(x^k + \tilde \alpha s^k) - \nabla f(x^k)]^\top s^k \\
&\le f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha || \nabla f(x^k + \tilde \alpha s^k) - \nabla f(x^k)|| \, ||s^k|| &&(\star 2) \\
&\le f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha L ||x^k + \tilde \alpha s^k - x^k|| \, ||s^k|| &&(\star 3) \\
&\le f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha^2 L ||s^k||^2 &&(\star 4)
\end{aligned}
$$
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
$$
f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha^2 L ||s^k||^2 \le f(x^k) + \beta \alpha \nabla f(x^k)^\top s^k
$$
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,
$$f(x^k + \alpha s^k) \le f(x^k) + \alpha \nabla f(x^k)^\top s^k + \tfrac{L}{2} \alpha^2 \|s^k\|^2,$$
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:
$$\alpha^k_\max = \frac{2(\beta - 1) \nabla f(x^k)^\top s^k}{L \|s^k\|^2}.$$
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.

^armijo-condition-satisfied-when-lipschitz-proof
<!-- flash-end -->

<!-- flash-start -->
Suppose:

- $f \in \mathcal C^1(\mathbb R^n)$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$

Recall that when we are trying to find some $\alpha^k$ to use as our stepsize to minimise $f(x^k + \alpha^k s^k)$, the Armijo backtracking algorithm finds this via the algorithm

- 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)}$.

@State a result about the size of $\alpha^k$ found by this method.::

$$
\alpha^k \ge \min \{\alpha_{(0)}, \tau \alpha^k_\max\}
$$
for all $k \ge 0$ where $\alpha^k_\max$ is defined as
$$
\alpha^k_\max = \frac{(\beta - 1)\nabla f(x^k)^\top s^k}{L||s^k||^2}
$$

^armijo-stepsize-bound
<!-- flash-end -->

<!-- flash-start -->
Suppose:

- $f \in \mathcal C^1(\mathbb R^n)$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$

Recall that when we are trying to find some $\alpha^k$ to use as our stepsize to minimise $f(x^k + \alpha^k s^k)$, the Armijo backtracking algorithm finds this via the algorithm

- 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)}$.

@Prove that we then have
$$
\alpha^k \ge \min \{\alpha_{(0)}, \tau \alpha^k_\max\}
$$
for all $k \ge 0$ where $\alpha^k_\max$ is defined as
$$
\alpha^k_\max = \frac{(\beta - 1)\nabla f(x^k)^\top s^k}{L||s^k||^2}
$$

::

**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) / |\log \tau|$.

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.

^armijo-backtracking-bound
<!-- flash-end -->

<!-- flash-start -->
Suppose:

- $f \in \mathcal C^1(\mathbb R^n)$
- $f$ is bounded below on $\mathbb R^n$ by $f_\text{low}$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$
- We apply a generic backtracking Armijo linesearch method

@State a result about the convergence of $x^k$ in this case.::

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

$$\lim_{k \to \infty} \min \left\{\frac{|\nabla f(x^k)^\top s^k|}{||s^k||}, |\nabla f(x^k)^\top s^k|\right\} = 0$$

^global-convergence-of-backtracking-armijo
<!-- flash-end -->

<!-- flash-start -->
@Prove that if

- $f \in \mathcal C^1(\mathbb R^n)$
- $f$ is bounded below on $\mathbb R^n$ by $f_\text{low}$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$
- We apply a generic backtracking Armijo linesearch method

then either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$ or
$$
\lim_{k \to \infty} \min \left\{\frac{|\nabla f(x^k)^\top s^k|}{||s^k||}, |\nabla f(x^k)^\top s^k|\right\} = 0
$$

::

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
$$
f(x^{k+1}) \le f(x^k) + \beta \alpha^k \nabla f(x^k)^\top s^k
$$
for all $k \ge 0$, or equivalently for all $k \ge 0$
$$
f(x^k) - f(x^{k+1}) \ge -\beta \alpha^k \nabla f(x^k)^\top s^k
$$
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 = |\nabla f(x^k)^\top s^k|$ and therefore
$$
f(x^k) - f(x^{k+1}) \ge \beta \alpha^k |\nabla f(x^k)^\top s^k|
$$
Let $i \ge 0$. Summing up this inequality from $k = 0$ to $k = i$ gives a telescoping sum and hence
$$
f(x^0) - f(x^{i+1}) \ge \beta \sum^i_{k=0} \alpha^k |\nabla f(x^k)^\top s^k|
$$
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
$$
\beta \sum^\infty_{k = 0} \alpha^k |\nabla f(x^k)^\top s^k| \le f(x^0) - f_\text{low} < \infty
$$
Since this series converges, the individual terms must tend towards 0. Hence
$$
\lim_{k \to \infty} \alpha^k |\nabla f(x^k)^\top s^k| = 0
$$
Recall from the ∆armijo-stepsize-bound that
$$
\alpha^k \ge \min \{ \alpha_{(0)}, \tau \alpha^k_\max \}
$$
Define the following sets
$$
\mathcal K_1 = \{k : \alpha_{(0)} \ge \tau \alpha^k_\max \}, \quad \mathcal K_2 = \{k : \alpha_{0} < \tau \alpha^k_\max\}
$$
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
$$
\alpha^k |\nabla f(x^k)^\top s^k| \ge \frac{(1-\beta)\tau}{L} \cdot \left( \frac{|\nabla f(x^k)^\top s^k|}{||s^k||} \right)^2 \ge 0
$$
and hence the limit above implies that
$$
\lim_{k \to \infty, k \in \mathcal K_1} \frac{|\nabla f(x^k)^\top s^k|}{||s^k||} = 0
$$
The ∆armijo-stepsize-bound also gives that $\alpha^k \ge \alpha_{(0)}$ for all $k \in \mathcal K_2$, so furthermore
$$
\lim_{k \to \infty, k \in \mathcal K_2} |\nabla f(x^k)^\top s^k| = 0
$$
These two limits for the $\mathcal K_1$ and $\mathcal K_2$ subsequences together imply the required result, namely that
$$
\lim_{k \to \infty} \min \left\{\frac{|\nabla f(x^k)^\top s^k|}{||s^k||}, |\nabla f(x^k)^\top s^k|\right\} = 0
$$

^global-convergence-of-backtracking-armijo-proof
<!-- flash-end -->

<!-- flash-start -->
Recall ∆global-convergence-of-backtracking-armijo, i.e. that if

- $f \in \mathcal C^1(\mathbb R^n)$
- $f$ is bounded below on $\mathbb R^n$ by $f_\text{low}$
- $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$
- $s^k$ is a descent direction at step $k$
- We apply a generic backtracking Armijo linesearch method

then either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$ or
$$
\lim_{k \to \infty} \min \left\{\frac{|\nabla f(x^k)^\top s^k|}{||s^k||}, |\nabla f(x^k)^\top s^k|\right\} = 0
$$

Give an intuitive explanation of this result.::

Let $\theta_k$ be the angle between the descent direction $s^k$ and the steepest-descent direction $-\nabla f(x^k)$, so that
$$
\cos \theta_k := \frac{(-\nabla f(x^k))^\top s^k}{\|\nabla f(x^k)\| \cdot \|s^k\|} = \frac{|\nabla f(x^k)^\top s^k|}{\|\nabla f(x^k)\| \cdot \|s^k\|}
$$
(the second equality uses $\nabla f(x^k)^\top s^k < 0$ from descent, so $-\nabla f(x^k)^\top s^k = |\nabla f(x^k)^\top s^k|$).

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

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

So the result is equivalent to
$$
\lim_{k \to \infty} \|\nabla f(x^k)\| \cdot \cos \theta_k \cdot \min\{1, \|s^k\|\} = 0.
$$

**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.

^global-convergence-of-backtracking-armijo-intuition
<!-- flash-end -->

<!-- flash-start -->
In a generic linesearch method for minimising $f$, the step-size $\alpha^k$ along descent direction $s^k$ must be neither too short nor too long. @State the Wolfe conditions and @justify why each is needed.::

There exist constants $0 < c_1 < c_2 < 1$ such that for all $k \in \mathbb N$:

- **(W1, Armijo condition / sufficient decrease)**: $$f(x^k + \alpha^k s^k) \le f(x^k) + c_1 \alpha^k \nabla f(x^k)^\top s^k.$$
- **(W2, curvature condition)**: $$\nabla f(x^k + \alpha^k s^k)^\top s^k \ge c_2 \nabla f(x^k)^\top s^k.$$

**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$.

![Screenshot 2026-05-20 at 12.08.24.png](https://ollybritton.com/assets/attachments/img/Screenshot 2026-05-20 at 12.08.24.png)

^wolfe-conditions
<!-- flash-end -->

### Visualising the Armijo and Wolfe conditions

The ∆armijo-condition and the ∆wolfe-conditions both read off the one-dimensional slice $\phi(\alpha) = f(x^k + \alpha s^k)$ along the descent direction, as in ∆bite-armijo-phi-k-geometric-interpretation. Armijo asks the curve to sit below a shallow line of slope $c_1 \phi'(0)$ (ruling out steps that are too long), while the curvature condition asks the slope at $\alpha$ to have flattened to at least $c_2 \phi'(0)$ (ruling out steps that are too short). Toggle each line independently and drag the trial step $\alpha$; the shaded band is the set of step lengths satisfying both, which is what an inexact linesearch is hunting for.

*An interactive visualisation appears here on the web page.*

### Bite-sized

<!-- cloze-start -->
$\nabla f : \mathbb R^n \to \mathbb R^n$ is **Lipschitz continuous** with constant $L > 0$ on $\mathbb R^n$ iff $\|\nabla f(y) - \nabla f(x)\| \le L \|y - x\|$ for all $x, y \in \mathbb R^n$ .

**Source**: Lecture 3, **Global convergence of GLM** slide.

^bite-lipschitz-gradient-definition
<!-- cloze-end -->

<!-- cloze-start -->
The generic linesearch method (GLM) terminates once the gradient norm is small enough: typically the loop runs while $\|\nabla f(x^k)\| > \epsilon$  for a chosen tolerance $\epsilon > 0$.

**Source**: Lecture 3, **A generic linesearch method (GLM)** slide.

^bite-glm-termination-criterion
<!-- cloze-end -->

<!-- cloze-start -->
**Stepsize too short.** For $f(x) = x^2$, $x^0 = 2$, $s^k = -1$ and $\alpha^k = 2^{-(k+1)}$ , GLM produces iterates $x^k \to 1$ — convergent but to a non-stationary point, because the stepsizes shrink too fast for $\sum \alpha^k |\nabla f^\top s^k|$ to overcome the descent already achieved.

**Source**: Lecture 3, **Stepsize not "too short"** example.

^bite-stepsize-too-short-counterexample
<!-- cloze-end -->

<!-- cloze-start -->
**Stepsize too long.** For $f(x) = x^2$, $x^0 = 2$, $s^k = (-1)^{k+1}$ and $\alpha^k = 1$ , GLM produces iterates $x^k \to \pm 1$ — oscillating between two non-stationary points because each unit step overshoots without enough decrease in $f$ per iteration.

**Source**: Lecture 3, **Stepsize not "too long"** example.

^bite-stepsize-too-long-counterexample
<!-- cloze-end -->

<!-- flash-start -->
@State the **Goldstein-Armijo** conditions on $\alpha^k$ and explain how they differ from the ∆wolfe-conditions.

::

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:
$$
f(x^k + \alpha^k s^k) \le f(x^k) + \beta \alpha^k \nabla f(x^k)^\top s^k.
$$
- **(GA2, Goldstein lower bound)** rules out stepsizes that are too short by forcing the achieved decrease to be at most $(1 - \beta) \alpha^k |\nabla f(x^k)^\top s^k|$:
$$
f(x^k + \alpha^k s^k) \ge f(x^k) + (1 - \beta) \alpha^k \nabla f(x^k)^\top s^k.
$$

**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)$.

**Source**: Lecture 3, closing remark "Other popular/useful inexact linesearch techniques include the Wolfe conditions and Goldstein-Armijo conditions."

^bite-goldstein-armijo-conditions
<!-- flash-end -->

<!-- flash-start -->
The Armijo condition $f(x^k + \alpha^k s^k) \le f(x^k) + \beta \alpha^k \nabla f(x^k)^\top s^k$ has a geometric interpretation in terms of $\Phi_k(\alpha) := f(x^k + \alpha s^k)$. State it.

::

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$.

![Screenshot 2026-05-20 at 12.08.24.png](https://ollybritton.com/assets/attachments/img/Screenshot 2026-05-20 at 12.08.24.png)

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

**Source**: Lecture 3, **Interpretation via $\Phi_k$** discussion.

^bite-armijo-phi-k-geometric-interpretation
<!-- flash-end -->

<!-- cloze-start -->
Three canonical example sequences for the three rates of convergence to $0$ as $k \to \infty$:
$l^k = (1/2)^k$  converges linearly ($p = 1$, $\rho = 1/2$); $q^k = (1/2)^{2^k}$  converges quadratically ($p = 2$); $s^k = k^{-k}$  converges superlinearly (faster than any linear rate, slower than quadratic).

**Source**: Lecture 3, **Rates of convergence of sequences** examples.

^bite-convergence-rates-canonical-examples
<!-- cloze-end -->

<!-- flash-start -->
Give the proof strategy for ∆exact-linesearch-quadratic-optimal-stepsize, i.e. that for a quadratic $q(x) = g^\top x + \tfrac{1}{2} x^\top H x$ the exact-linesearch stepsize along $s^k$ is $\alpha^\ast = -(s^k)^\top \nabla q(x^k) / (s^k)^\top H s^k$.

::

- 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$.

**Source**: Lecture 3, **Exact linesearches for quadratic objectives** slide.

 

^bite-exact-linesearch-quadratic-strategy
<!-- flash-end -->

<!-- flash-start -->
Give the proof strategy for ∆armijo-condition-satisifed-when-lipschitz, i.e. Lemma 2: that Armijo holds for $\alpha \in [0, \alpha^k_\max]$ when $\nabla f$ is Lipschitz with constant $L$.

::

- 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)$.

**Source**: Lecture 3, **Lemma 2** proof.

 

^bite-lipschitz-armijo-strategy
<!-- flash-end -->

<!-- cloze-start -->
**Descent-lemma-style upper bound**, the key inequality driving Lemma 2 (∆armijo-condition-satisifed-when-lipschitz). Under $\nabla f$ Lipschitz with constant $L$, for any $\alpha > 0$:
$$f(x^k + \alpha s^k) \le f(x^k) + \alpha \nabla f(x^k)^\top s^k + \alpha^2 L \|s^k\|^2 .$$
Setting this RHS equal to the Armijo bound $f(x^k) + \beta \alpha \nabla f(x^k)^\top s^k$ and solving for $\alpha$ gives the threshold $\alpha^k_\max$.

**Source**: Lecture 3, **Lemma 2** proof, line $(\star 4)$.

 

^bite-lipschitz-armijo-key-inequality-quadratic-bound
<!-- cloze-end -->

<!-- flash-start -->
In the proof of Lemma 2 (∆armijo-condition-satisifed-when-lipschitz), where does the Lipschitz hypothesis $\|\nabla f(y) - \nabla f(x)\| \le L \|y - x\|$ enter, and what would the conclusion look like without it?

::

- 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.

**Source**: Lecture 3, **Lemma 2** proof, justification of line $(\star 3)$; cf. the GLM global-convergence assumptions which need explicit $L$.

 

^bite-lipschitz-armijo-hypothesis-lipschitz-role
<!-- flash-end -->

<!-- flash-start -->
In Lemma 2 (∆armijo-condition-satisifed-when-lipschitz), where does the hypothesis $\beta \in (0, 1)$ enter, and what goes wrong at the boundary values $\beta = 0$ or $\beta = 1$?

::

- $\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\|)$.

**Source**: Lecture 3, **Lemma 2** proof and ∆armijo-condition geometric discussion.

 

^bite-lipschitz-armijo-hypothesis-beta-range
<!-- flash-end -->

<!-- flash-start -->
Give the proof strategy for ∆armijo-backtracking-bound, i.e. Lemma 3: that bArmijo accepts $\alpha^k \ge \min\{\alpha_{(0)}, \tau \alpha^k_\max\}$.

::

- 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$.

**Source**: Lecture 3, **Lemma 3** proof.

 

^bite-armijo-backtracking-strategy
<!-- flash-end -->

<!-- cloze-start -->
The key "one-step-too-far" inequality in the proof of Lemma 3 (∆armijo-backtracking-bound). If bArmijo terminates at the first index $i$ with $\alpha_{(i)} \le \alpha^k_\max$, then by minimality of $i$ we have $\alpha_{(i-1)} > \alpha^k_\max$, and therefore $\alpha^k = \alpha_{(i)} = \tau \alpha_{(i-1)}$, giving
$$\alpha^k > \tau \alpha^k_\max .$$
The factor $\tau$ is the "price" of having to backtrack once past the safe region.

**Source**: Lecture 3, **Lemma 3** proof.

 

^bite-armijo-backtracking-key-inequality-tau-alphamax
<!-- cloze-end -->

<!-- flash-start -->
Give the proof strategy for ∆global-convergence-of-backtracking-armijo (Theorem 4 / GLM global convergence with bArmijo).

::

- Apply Armijo at iterate $k$ to get the per-step decrease $f(x^k) - f(x^{k+1}) \ge \beta \alpha^k |\nabla f(x^k)^\top s^k|$.
- Telescope from $k = 0$ to $i$; bounded-below $f \ge f_\text{low}$ gives a convergent series, hence $\alpha^k |\nabla f(x^k)^\top s^k| \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 |\nabla f^\top s^k|$ below by $\frac{(1-\beta)\tau}{L}(|\nabla f^\top s^k|/\|s^k\|)^2$; deduce $|\nabla f^\top s^k|/\|s^k\| \to 0$.
- On $\mathcal K_2$: $\alpha^k \ge \alpha_{(0)}$ directly, so $|\nabla f(x^k)^\top s^k| \to 0$.
- Combine via $\min\{a, b\} \le a, b$ for both subsequences to get the joint $\min$-limit.

**Source**: Lecture 4, **Theorem 4** proof.

 

^bite-glm-bArmijo-convergence-strategy
<!-- flash-end -->

<!-- cloze-start -->
The Armijo per-step decrease used in the proof of ∆global-convergence-of-backtracking-armijo (Theorem 4). Applying Armijo with $\alpha := \alpha^k$ at iterate $k+1$ and using $-\nabla f(x^k)^\top s^k = |\nabla f(x^k)^\top s^k|$ (since $s^k$ is descent):
$$f(x^k) - f(x^{k+1}) \ge \beta \alpha^k |\nabla f(x^k)^\top s^k| .$$
Summed and telescoped, this drives the whole global-convergence argument.

**Source**: Lecture 4, **Theorem 4** proof, inequality (1).

 

^bite-glm-bArmijo-convergence-key-inequality-per-step-decrease
<!-- cloze-end -->

<!-- cloze-start -->
The $\mathcal K_1$ lower bound in the proof of ∆global-convergence-of-backtracking-armijo (Theorem 4). For $k \in \mathcal K_1 = \{k : \alpha_{(0)} \ge \tau \alpha^k_\max\}$, combining ∆armijo-stepsize-bound (giving $\alpha^k \ge \tau \alpha^k_\max$) with the expression of $\alpha^k_\max$ from ∆armijo-condition-satisifed-when-lipschitz yields
$$\alpha^k |\nabla f(x^k)^\top s^k| \ge \frac{(1-\beta)\tau}{L} \left(\frac{|\nabla f(x^k)^\top s^k|}{\|s^k\|}\right)^2 .$$
This is the only step where the Lipschitz constant $L$ explicitly appears.

**Source**: Lecture 4, **Theorem 4** proof, $\mathcal K_1$ case.

 

^bite-glm-bArmijo-convergence-key-inequality-K1-bound
<!-- cloze-end -->

<!-- flash-start -->
In the proof of ∆global-convergence-of-backtracking-armijo (Theorem 4), where does the hypothesis "$f$ bounded below by $f_\text{low}$" enter, and what would happen without it?

::

- 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 |\nabla f(x^k)^\top s^k|$. The LHS is bounded by $f(x^0) - f_\text{low}$ as $i \to \infty$, so the full series converges and $\alpha^k |\nabla f(x^k)^\top s^k| \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.

**Source**: Lecture 4, **Theorem 4** proof, telescoping step.

 

^bite-glm-bArmijo-convergence-hypothesis-bounded-below
<!-- flash-end -->

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt