Continuous Optimisation HT26, Useful miscellany
Flashcards
Rayleigh quotient eigenvalue bound
@State the Rayleigh quotient bound for eigenvalues.
Suppose:
- $s \in \mathbb R^n \setminus \{0\}$
- $\mathbf M \in \mathbb R^{n \times n}$ symmetric
Then:
\[\lambda _ \min(\mathbf M) \le \frac{s^\top \mathbf M s}{ \vert \vert s \vert \vert ^2} \le \lambda _ \max(\mathbf M)\]@Prove the ∆rayleigh-ritz-theorem, i.e. that if
- $s \in \mathbb R^n \setminus \{0\}$
- $\mathbf M \in \mathbb R^{n \times n}$ symmetric
then:
\[\lambda _ \min(\mathbf M) \le \frac{s^\top \mathbf M s}{ \vert \vert s \vert \vert ^2} \le \lambda _ \max(\mathbf M)\]
Since $\mathbf M$ is symmetric, it has an orthonormal eigenbasis $\{v _ 1, \ldots, v _ n\}$ with corresponding eigenvalues $\lambda _ 1 \le \lambda _ 2 \le \cdots \le \lambda _ n$, so $\lambda _ \min(\mathbf M) = \lambda _ 1$ and $\lambda _ \max(\mathbf M) = \lambda _ n$.
Any $s \in \mathbb R^n$ can be written as $s = \sum^n _ {i=1} c _ i v _ i$ where $c _ i := v _ i^\top s$. Then
\[ \vert \vert s \vert \vert ^2 = \sum^n _ {i=1} c _ i^2, \qquad s^\top \mathbf M s = \sum^n _ {i=1} \lambda _ i c _ i^2.\]Since $\lambda _ 1 \le \lambda _ i \le \lambda _ n$ for all $i$,
\[\lambda _ 1 \sum^n _ {i=1} c _ i^2 \le \sum^n _ {i=1} \lambda _ i c _ i^2 \le \lambda _ n \sum^n _ {i=1} c _ i^2.\]Dividing through by $ \vert \vert s \vert \vert ^2 = \sum^n _ {i=1} c _ i^2 > 0$ gives the result.
Characterisation of Lipschitz continuity in terms of bounded Hessian
@State an exact characterisation of when $\nabla f$ is Lipschitz continuous in terms of the Hessian.
Suppose $f \in \mathcal C^2$, then $\nabla f$ is Lipschitz continuous iff $\nabla^2 f$ is uniformly bounded above.
@Prove that for $f \in \mathcal C^2$, $\nabla f$ is Lipschitz continuous iff $\nabla^2 f$ is uniformly bounded above.
(⇐) Bounded Hessian implies Lipschitz gradient. Assume $ \vert \vert \nabla^2 f(x) \vert \vert \le L$ for all $x \in \mathbb R^n$. By the fundamental theorem of calculus,
\[\nabla f(y) - \nabla f(x) = \int _ 0^1 \nabla^2 f(x + t(y-x))(y-x) \,\text dt.\]Taking norms and pulling the bound under the integral,
\[ \vert \vert \nabla f(y) - \nabla f(x) \vert \vert \le \int _ 0^1 \vert \vert \nabla^2 f(x + t(y-x)) \vert \vert \cdot \vert \vert y - x \vert \vert \,\text dt \le L \vert \vert y - x \vert \vert .\](⇒) Lipschitz gradient implies bounded Hessian. Assume $ \vert \vert \nabla f(x) - \nabla f(y) \vert \vert \le L \vert \vert x-y \vert \vert $ for all $x,y$. For any $x \in \mathbb R^n$ and any unit vector $d \in \mathbb R^n$,
\[\nabla^2 f(x)\, d = \lim _ {t \to 0} \frac{\nabla f(x + td) - \nabla f(x)}{t}.\]Hence
\[ \vert \vert \nabla^2 f(x)\, d \vert \vert = \lim _ {t \to 0} \frac{ \vert \vert \nabla f(x + td) - \nabla f(x) \vert \vert }{ \vert t \vert } \le \lim _ {t \to 0} \frac{L \vert t \vert }{ \vert t \vert } = L.\]Since this holds for every unit $d$, $ \vert \vert \nabla^2 f(x) \vert \vert \le L$ for all $x$.
Descent lemma
Suppose $f \in \mathcal C^1(\mathbb R^n)$ with $\nabla f$ Lipschitz continuous, with constant $L$. @State and @prove the descent lemma.
For all $x, d \in \mathbb R^n$,
\[f(x + d) \le f(x) + \nabla f(x)^\top d + \frac{L}{2} \|d\|^2.\]Proof: by the fundamental theorem of calculus applied to $g(t) := f(x = td)$,
\[f(x + d) = f(x) + \int^1 _ 0 \nabla f(x + td)^\top d \, \text dt.\]Subtracting $\nabla f(x)^\top d$ from both sides and using Cauchy-Schwarz with the Lipschitz condition:
\[\begin{aligned} \left \vert \int^1 _ 0 [\nabla f(x + td) - \nabla f(x)]^\top d \, \text dt \right \vert &\le \int^1 _ 0 \| \nabla f(x + td) - \nabla f(x)\| \cdot \|d\|\, \text dt \\ &\le \int^1 _ 0 Lt \|d\|^2 \, \text dt \\ &= \frac{L}{2} \|d\|^2. \end{aligned}\]Sherman-Morrison-Woodbury formula
@State the Sherman-Morrison-Woodbury (SMW) formula, and @justify why it reduces the per-iteration cost of BFGS and symmetric rank-1 (SR1) updates from $O(n^3)$ to $O(n^2)$.
Let $B \in \mathbb R^{n \times n}$ be invertible, $U, V \in \mathbb R^{n \times m}$ with $I + V^\top B^{-1} U$ invertible. Then
\[(B + UV^\top)^{-1} = B^{-1} - B^{-1}U(I + V^\top B^{-1} U)^{-1} V^\top B^{-1}.\](Verify by multiplying both sides on the left by $B + UV^\top$ and simplifying).
Quasi-Newton application: the SR1 update $B^{k+1} = B^k + \rho u u^\top$ is a rank-1 perturbation; we may apply SMW with $U := \rho u$, $V := u$, so $I + V^\top B{-1} U = 1 + \rho B^\top (B^k)^{-1} u$ is a scalar:
\[(B^{k+1})^{-1} = (B^k)^{-1} - \frac{\rho (B^k)^{-1} u v^\top (B^k)^{-1}}{1 + \rho u^\top (B^k) u}.\]Bite-sized
Rayleigh quotient corollary: for a symmetric matrix $\mathbf M$ with smallest and largest eigenvalues $\lambda _ {\min}, \lambda _ {\max}$, the bilinear form $s^\top \mathbf M s$ on the unit sphere takes all values in $[\lambda _ {\min}, \lambda _ {\max}]$, with the extremes attained at the corresponding eigenvectors. This is the workhorse inequality whenever we want to bound $s^\top \mathbf M s / \ \vert s\ \vert ^2$ in terms of eigenvalues.
When $\nabla f$ is Lipschitz with constant $L$, the Hessian operator norm is bounded by $\ \vert \nabla^2 f(x)\ \vert \le L$ for all $x$ (∆lipschitz-continuous-iff-bounded-hessian). This is the bound used in trust-region and linesearch convergence proofs to control quadratic-model error.
The descent lemma in one line: for $f \in \mathcal C^1$ with $\nabla f$ Lipschitz of constant $L$, $f(x + d) \le f(x) + \nabla f(x)^\top d + \tfrac{L}{2} \ \vert d\ \vert ^2$. This upper-bounds $f$ by a concrete quadratic, which is what lets steepest-descent / gradient methods choose a stepsize that guarantees decrease without a linesearch.
Sherman-Morrison (rank-1 specialisation of SMW): for $B$ invertible and vectors $u, v$ with $1 + v^\top B^{-1} u \ne 0$, $(B + uv^\top)^{-1} = B^{-1} - \dfrac{B^{-1} u v^\top B^{-1</span>{1 + v^\top B^{-1} u}$ }}. This is what makes SR1 and (via two applications) BFGS quasi-Newton updates cost $O(n^2)$ rather than $O(n^3)$.
Give the proof strategy for ∆rayleigh-ritz-theorem-proof.
- Use symmetry of $\mathbf M$: orthonormal eigenbasis $\{v _ 1, \ldots, v _ n\}$ with eigenvalues $\lambda _ 1 \le \cdots \le \lambda _ n$.
- Expand any $s$ in the basis: $s = \sum _ i c _ i v _ i$, then $\|s\|^2 = \sum _ i c _ i^2$ and $s^\top \mathbf M s = \sum _ i \lambda _ i c _ i^2$.
- Sandwich the weighted sum: $\lambda _ 1 \sum c _ i^2 \le \sum \lambda _ i c _ i^2 \le \lambda _ n \sum c _ i^2$.
- Divide through by $\|s\|^2 = \sum c _ i^2 > 0$.
The proof is purely algebraic — orthonormality is what makes both sums share the same denominator.
Give the proof strategy for ∆lipschitz-continuous-iff-bounded-hessian-proof (both directions).
- ($\Leftarrow$) bounded Hessian ⟹ Lipschitz gradient: fundamental theorem of calculus for $\nabla f$ along the segment from $x$ to $y$, $\nabla f(y) - \nabla f(x) = \int _ 0^1 \nabla^2 f(x + t(y-x))(y-x) \, dt$. Triangle inequality and $\|\nabla^2 f\| \le L$ under the integral give $\|\nabla f(y) - \nabla f(x)\| \le L\|y - x\|$.
- ($\Rightarrow$) Lipschitz gradient ⟹ bounded Hessian: realise the Hessian as a directional derivative: for unit $d$, $\nabla^2 f(x) d = \lim _ {t \to 0} [\nabla f(x + td) - \nabla f(x)] / t$. Lipschitz upper-bounds the difference quotient by $L \vert t \vert / \vert t \vert = L$, hence $\|\nabla^2 f(x) d\| \le L$ for every unit $d$, so $\|\nabla^2 f(x)\| \le L$.
The two directions are dual: integral form vs differential form of the same calculus identity.
Give the proof strategy for ∆descent-lemma (descent lemma: $f(x + d) \le f(x) + \nabla f(x)^\top d + \tfrac{L}{2}\|d\|^2$ under Lipschitz $\nabla f$).
- Apply fundamental theorem of calculus to the scalar function $g(t) := f(x + td)$, $t \in [0, 1]$, with $g'(t) = \nabla f(x + td)^\top d$: $f(x + d) = f(x) + \int _ 0^1 \nabla f(x + td)^\top d \, dt$.
- Subtract the would-be linear approximation $\nabla f(x)^\top d$: the residual is $\int _ 0^1 [\nabla f(x + td) - \nabla f(x)]^\top d \, dt$.
- Bound the residual by Cauchy–Schwarz + Lipschitz: $ \vert [\nabla f(x + td) - \nabla f(x)]^\top d \vert \le \|\nabla f(x + td) - \nabla f(x)\| \cdot \|d\| \le Lt\|d\|^2$.
- Integrate $\int _ 0^1 Lt\|d\|^2 dt = \tfrac{L}{2}\|d\|^2$ to close the bound.
Give the proof strategy for ∆sherman-morrison-woodbury (the SMW formula $(B + UV^\top)^{-1} = B^{-1} - B^{-1} U(I + V^\top B^{-1} U)^{-1} V^\top B^{-1}$).
- Verify by direct multiplication: compute $(B + UV^\top) \cdot \text{RHS}$ and show it equals $I$.
- Expand: $(B + UV^\top)\bigl[B^{-1} - B^{-1} U(I + V^\top B^{-1} U)^{-1} V^\top B^{-1}\bigr]$ gives four terms.
- Collect the two $-U(\ldots)V^\top B^{-1}$ terms by factoring $U$ on the left and $V^\top B^{-1}$ on the right; their joint coefficient becomes $-(I + V^\top B^{-1} U)(I + V^\top B^{-1} U)^{-1} = -I$, so they sum to $-UV^\top B^{-1}$.
- This cancels the $+UV^\top B^{-1}$ term from the expansion, leaving $I$.
The proof is just clever bookkeeping — no calculus, no eigenvalue theory.