Notes - Optimisation for Data Science HT25, Optimisation terminology

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:

$x^\ast \in \mathcal F$ is:

A local minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon (x^\ast)$ for some $\varepsilon > 0$.
A strict local minimiser if $f(x^\ast) < f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon(x^\ast)$
A global minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F$.

Suppose $f : \mathbb R^n \to \mathbb R \cup \{+\infty\}$ is a proper convex function. Consider the optimisation model

\[\min _ {x \in \mathbb R^n} f(x) \quad\text{ subject to }x \in \mathcal F\]

Recall that $x^\ast \in \mathcal F$ is:

A local minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon (x^\ast)$ for some $\varepsilon > 0$.
A strict local minimiser if $f(x^\ast) < f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon(x^\ast)$
A global minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F$.

@State three results about the minimisation of proper convex functions.

(1): $x^\ast$ is a local minimiser iff it is a global minimiser.

(2): The set of minimisers

\[\text{argmin} _ {x \in \mathbb R^n} f(x) := \\{x^\ast \mid f(x^\ast) = \min _ {x \in \mathbb R^n} f(x)\\}\]

is a convex set.

(3): $x^\ast \in \text{argmin} _ {x \in \mathbb R^n} f(x)$ if and only if $\pmb 0 \in \partial f(x^\ast)$.

Suppose $f : \mathbb R^n \to \mathbb R \cup \{+\infty\}$ is a proper convex function. Consider the optimisation model

\[\min _ {x \in \mathbb R^n} f(x) \quad\text{ subject to }x \in \mathcal F\]

Recall that $x^\ast \in \mathcal F$ is:

A local minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon (x^\ast)$ for some $\varepsilon > 0$.
A strict local minimiser if $f(x^\ast) < f(x)$ for all $x \in \mathcal F \cap B _ \varepsilon(x^\ast)$
A global minimiser if $f(x^\ast) \le f(x)$ for all $x \in \mathcal F$.

@Prove the following three results about the minimisation of proper convex functions:

$x^\ast$ is a local minimiser iff it is a global minimiser.
The set of minimisers $\text{argmin} _ {x \in \mathbb R^n} f(x) := \{x^\ast \mid f(x^\ast) = \min _ {x \in \mathbb R^n} f(x)\}$ is a convex set.
$x^\ast \in \text{argmin} _ {x \in \mathbb R^n} f(x)$ if and only if $\pmb 0 \in \partial f(x^\ast)$.

@todo, after sheet one.

Suppose:

@Define what it means for $(\phi _ k) _ {k \in \mathbb N}$ to converge:

and state the implications between these convergence rates.

Sublinearly: Slower than $R$-linearly
$R$-linearly: $\exists \sigma \in (0, 1)$ and $C > 0$ such that $\forall k \in \mathbb N$, $\phi _ k \le C(1 - \sigma)^k$.
$Q$-linearly: $\exists \sigma \in (0, 1)$ such that $\forall k \in \mathbb N$, $\frac{\phi _ {k+1} }{\phi _ k} \le 1 - \sigma$.
$Q$-superlinearly: $\lim _ {k \to \infty} \frac{\phi _ {k+1} }{\phi _ k} = 0$
$R$-superlinearly: $\exists (\nu _ k) _ {k \in \mathbb N} \in \mathbb R _ +^{\mathbb N}$ such that $\nu _ k \to 0$ $Q$-superlinearly and $\forall k \in \mathbb N$, $\phi _ k \le \nu _ k$
$Q$-quadratically: $\exists C > 0$ such that $\forall k \in \mathbb N$, $\frac{\phi _ {k+1} }{\phi _ k^2} \le C$.

All the following implications are strictly one directional: