Continuous Optimisation HT26, Steepest descent
Flashcards
Basic definitions
Recall the ∆generic-linesearch-method
- 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$
In this context, @define what is meant by steepest descent.
- 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$
Choose $s _ k = -\nabla f(x^k)$.
When is $s _ k = -\nabla f(x^k)$ a descent direction?
Whenever $\nabla f(x^k) \ne 0$.
Recall the ∆generic-linesearch-method
- 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$
In this context, steepest descent chooses $s^k = -\nabla f(x^k)$. Why is this called steepest descent?
- 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$
It is the unique global solution of
\[\min _ {s \in \mathbb R^n, \vert \vert s \vert \vert = \vert \vert \nabla f(x^k) \vert \vert } f(x^k) + s^\top \nabla f(x^k)\]i.e. this direction decreases the linear model of $f$ the most.
Convergence
Recall the ∆generic-linesearch-method
- 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$
In this context, steepest descent chooses $s _ k = -\nabla f(x^k)$.
@State a result about the convergence of this algorithm when used with backtracking and Armijo backtracking.
- 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$
Suppose:
- $f \in \mathcal C^1(\mathbb R^n)$
- $f$ is bounded below on $\mathbb R^n$
- $\nabla f$ is Lipschitz continuous
Then with both standard backtracking and Armijo backtracking, either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, or $ \vert \vert \nabla f(x^k) \vert \vert \to 0$ as $k \to \infty$.
Recall the ∆generic-linesearch-method
- 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$
In this context, steepest descent chooses $s _ k = -\nabla f(x^k)$. @Prove, by appealing to another result, that if
- $f \in \mathcal C^1(\mathbb R^n)$
- $f$ is bounded below on $\mathbb R^n$
- $\nabla f$ is Lipschitz continuous
Then with Armijo backtracking either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, or $ \vert \vert \nabla f(x^k) \vert \vert \to 0$ as $k \to \infty$.
- 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$
Let $s^k = -\nabla f(x^k)$ for all $k$ in ∆global-convergence-of-backtracking-armijo.
Can you give an @example of where steepest descent converges very slowly due to the objective function being poorly scaled?
where $a > 0$ (unique minimiser $x^\ast = 0$). Applying steepest descent with exact linesearch from $x^0 = (1, a)^\top$ yields
\[x^k = \left( \frac{a-1}{a+1} \right)^k \begin{pmatrix} (-1)^k \\ a \end{pmatrix}, \quad k \ge 0\](see redacted?). Hence $x^k \to 0$ as $k \to \infty$. When $a \gg 1$, then steepest descent converges very slowly.
Steepest descent struggles with scale dependence. If we have the objective
\[f(x) = \frac 1 2 (a x _ 1^2 + x _ 2^2) = \frac 1 2 x^\top \begin{pmatrix}a & 0 \\ 0 & 1\end{pmatrix} x\]
then steepest descent iterations yield
\[x^k = \left( \frac{a-1}{a+1} \right)^k \begin{pmatrix} (-1)^k \\ a \end{pmatrix}, \quad k \ge 0\]
and when $a \gg 1$ then steepest descent converges very slowly. Give an @example of a linear transformation of variables that improves the scaling and @visualise why this works.
Let
\[y = \begin{pmatrix} a^{1/2} & 0 \\ 0 & 1 \end{pmatrix} x\]and set $\bar f(y) = f(x(y))$. Then steepest descent from any $y^0 \in \mathbb R^2$ converges to the global minimiser in one step. This is because the global minimum goes from being very narrow to being a perfect bowl shape.
Asymptotically, steepest descent converges linearly to a solution since if $x^k \to x^\ast$ as $k \to \infty$, then
\[ \vert \vert x^{k+1} - x^\ast \vert \vert \le \rho \vert \vert x^k - x^\ast \vert \vert \]
for all $k$ sufficiently large.
Why is steepest descent often slow in practice?
Because $\rho$ is often very close to $1$.
@State a theorem about the convergence of steepest descent to a local minimiser $x^\ast$ of $f \in \mathcal C^2(\mathbb R^n)$ in terms of the eigenvalues of the Hessian.
Suppose:
- $f \in \mathcal C^2(\mathbb R^n)$
- $x^\ast$ local minimiser of $f$
- $\nabla^2 f(x^\ast)$ is positive definite with extremal eigenvalues $\lambda^\ast _ \min, \lambda^\ast _ \max$
- $x^k \to x^\ast$ via steepest descent iterations
Then $x^k$ converges linearly to $x^\ast$ with rate
\[\rho \le \frac{\kappa(x^\ast) - 1}{\kappa(x^\ast) + 1} := \rho _ \text{SD}\]where $\kappa(x^\ast) = \lambda^\ast _ \max / \lambda^\ast _ \min$ (i.e. the condition number of $\nabla^2 f(x^\ast)$). In practice, $\rho \approx \rho _ \text{SD}$.
Bite-sized
For a symmetric positive definite matrix $A$ with eigenvalues $\lambda _ {\min}, \lambda _ {\max}$, the (spectral) condition number of $A$ is $\kappa(A) := <span class="cloze" tabindex="0">\lambda _ {\max} / \lambda _ {\min}</span>$. At a strict local minimiser $x^\ast$, the condition number $\kappa(x^\ast)$ controls the steepest descent convergence factor.
The local linear convergence factor of steepest descent (with exact linesearch) at a strict local minimiser $x^\ast$ with PD Hessian is bounded by
\[\rho_{\text{SD}} = <span class="cloze" tabindex="0">\frac{\kappa(x^\ast) - 1}{\kappa(x^\ast) + 1}</span>\]where $\kappa(x^\ast)$ is the condition number of $\nabla^2 f(x^\ast)$. Ill-conditioning ($\kappa \gg 1$) drives $\rho _ {\text{SD}} \to 1$, making convergence very slow.
Unlike Newton’s method, steepest descent is scale-dependent: a linear change of variables $y = Ax$ can dramatically change the SD trajectory. Poor scaling (large $\kappa$) makes SD zigzag and slow down; a rescaling that makes $\nabla^2 f$ closer to the identity can recover one-step convergence on quadratics.
@State the three main disadvantages of steepest descent (SD) for unconstrained optimisation.
- Scale-dependent: a poorly scaled problem makes the SD direction give little progress per iteration, and rescaling is often expensive or impossible.
- Slow asymptotic convergence: only linear with factor $\rho _ {\text{SD}} = (\kappa - 1)/(\kappa + 1)$, which is close to $1$ whenever $\kappa(x^\ast)$ is large.
- No second-order guarantees: SD’s global convergence delivers $\nabla f(x^k) \to 0$, but says nothing about $\nabla^2 f(x^k)$ — convergence can be to a saddle or maximiser.
For the Rosenbrock function $f(x _ 1, x _ 2) = 10(x _ 2 - x _ 1^2)^2 + (x _ 1 - 1)^2$ at its minimiser $(1, 1)$, the Hessian’s condition number is $\kappa(x^\ast) \approx <span class="cloze" tabindex="0">258</span>$, giving steepest-descent rate bound $\rho _ {\text{SD}} \approx <span class="cloze" tabindex="0">0.992</span>$ — close enough to $1$ that thousands of SD iterations are needed in practice.