Continuous Optimisation HT26, Optimisation terminology
Flashcards
Consider the optimisation model
\[\min _ {x \in \mathbb R^n} f(x) \quad\text{ subject to }x \in \mathcal F\]
@Define what is meant by a constrained local minimiser.
$x^\ast \in \mathcal F$ is a constrained local minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon(x^\ast)$ for some $\varepsilon > 0$ (and hence $x^\ast$ may lie directly on a constraint).
Let $\{x^k\} \subset \mathbb R^n$ with $x^k \to x^\ast$ as $k \to \infty$.
@Define what it means for $x^k$ to converge to $x^\ast$ with $p$-rate, and give the three special cases (linear, quadratic, superlinear).
$x^k \to x^\ast$ with $p$-rate of convergence $(p \ge 1)$ if there exists $k _ 0 \ge 0$ and $\rho > 0$ such that
\[\|x^{k+1} - x^\ast\| \le \rho \|x^k - x^\ast\|^p \quad \text{ for all }k \ge k _ 0.\]$\rho$ is the convergence factor and $e^k := x^k - x^\ast$ is the error.
- Linear ($p = 1$): requires $\rho < 1$. Asymptotically, the number of correct digits grows linearly in $k$.
- Quadratic ($p = 2$): the number of correct digits roughly doubles per iteration. (e.g. this is what pure Newton achieves locally).
- Superlinear:
Faster than any linear rate, but slower than quadratic. (e.g. this is what BFGS achieves locally).
Bite-sized
$x^\ast$ is a global minimiser of $f$ over $\Omega$ if $f(x) \ge f(x^\ast)$ for all $x \in \Omega$.
$x^\ast \in \Omega$ is a local minimiser of $f$ over $\Omega$ if there exists $\delta > 0$ such that $f(x) \ge f(x^\ast)$ for all $x \in \Omega \cap \mathcal N(x^\ast, \delta)$, where $\mathcal N(x^\ast, \delta) := \{ x \in \mathbb R^n : \ \vert x - x^\ast\ \vert \le \delta \}$.
A stationary point of $f \in \mathcal C^1$ is a point $x$ satisfying $\nabla f(x) = 0$.
A direction $s \ne 0$ is a descent direction for $f$ at $x$ if $\nabla f(x)^\top s < 0$.
How can the descent-direction condition $\nabla f(x)^\top s < 0$ be interpreted geometrically, in terms of the angle between $s$ and $-\nabla f(x)$?
The angle $\theta$ between $-\nabla f(x)$ and $s$ satisfies $\theta \in [0, \pi/2)$, since
\[\cos \theta = \frac{(-\nabla f(x))^\top s}{\|\nabla f(x)\| \cdot \|s\|} > 0.\]So $s$ points into the same open half-space as $-\nabla f(x)$.
Whenever $\nabla f(x) \ne 0$, the negative gradient $s = -\nabla f(x)$ is a descent direction for $f$ at $x$, because $\nabla f(x)^\top (-\nabla f(x)) = -\ \vert \nabla f(x)\ \vert ^2 < 0$.
In the definition of $p$-rate convergence
\[\|x^{k+1} - x^\ast\| \le \rho \|x^k - x^\ast\|^p, \quad k \ge k_0,\]the constant $\rho > 0$ is called the convergence factor, and $e^k := x^k - x^\ast$ is the error.
The first-order necessary condition $\nabla f(x^\ast) = 0$ holds at every local minimiser. Why is it not enough on its own to identify $x^\ast$ as a minimiser?
$\nabla f(x^\ast) = 0$ is also satisfied at local maximisers and saddle points. Higher-order (Hessian) information is needed to distinguish between them — except in the convex case, where any stationary point is automatically a global minimiser.