Notes - Continuous Optimisation HT26, Unconstrained optimality conditions

[[Course - Continuous Optimisation HT26]]^U

Flashcards

Consider the unconstrained optimisation problem

\[\min _ {x \in \mathbb R^n} f(x)\]

where $f \in \mathcal C^1 (\mathbb R^n)$. @State the first-order necessary conditions for some point $x^\ast$ to be a local minimiser.

\[x^\ast \text{ local minimiser} \implies \nabla f(x^\ast) = 0\]

Consider the unconstrained optimisation problem

\[\min _ {x \in \mathbb R^n} f(x)\]

where $f \in \mathcal C^1 (\mathbb R^n)$. @State an exact characterisation for when $x^\ast$ is a stationary point of $f$.

\[x \text{ stationary point of } f \iff \nabla f(x) = 0\]

Suppose:

$f \in \mathcal C^1 (\mathbb R^n)$
$x \in \mathbb R^n$
$s \in \mathbb R^n \setminus { 0 }$

@State a result about always being able to find a descent direction.

If $\nabla f(x)^\top s < 0$, then $f(x + \alpha s) < f(x)$ for all $\alpha > 0$ sufficiently small.

Suppose:

$f \in \mathcal C^1 (\mathbb R^n)$
$x \in \mathbb R^n$
$s \in \mathbb R^n \setminus {0}$
$\nabla f(x)^\top s < 0$

@Prove that then $f(x + \alpha s) < f(x)$ for all $\alpha > 0$ sufficiently small.

As $f \in \mathcal C^1 (\mathbb R^n)$, there exists some $\bar \alpha > 0$ such that

\[\nabla f(x + \alpha s)^\top s < 0, \quad \forall \alpha \in [0, \bar \alpha]\]

By Taylor’s theorem, we also have

\[f(x + \alpha s) = f(x) + \alpha \nabla f(x + \tilde \alpha s)^\top s\]

for some $\tilde \alpha \in (0, \alpha)$. Then by the above, we have

\[f(x + \alpha s) < f(x) \quad \forall \alpha \in (0, \bar \alpha]\]

Suppose:

$f \in \mathcal C^1 (\mathbb R^n)$
$x \in \mathbb R^n$
$s \in \mathbb R^n \setminus {0}$

@State a sufficient condition for $s$ to be a descent direction.

\[\nabla f(x)^\top s < 0\]

When is $-\nabla f(x)$ a descent direction?

Whenever $\nabla f(x) \ne 0$.

Suppose:

$f \in \mathcal C^1 (\mathbb R^n)$
$x^\ast \in \mathbb R^n$

@State a second-order necessary condition for $x^\ast$ to be a local minimiser of $f$.

\[x^\ast \text{local minimiser} \implies \nabla ^2 f(x^\ast) \text{ positive semidefinite}\]

Give an @example of a function that has both the first-order and second-order derivative equal to $0$ at some point $x^\ast$ yet $x^\ast$ is not a local minimiser.

\[f(x) = x^3\]

Suppose $f \in \mathcal C^2 (\mathbb R^n)$. @State second-order sufficient conditions for $x^\ast$ to be a local minimiser of $f$.

\[\nabla f(x^\ast) = 0, \nabla^2 f(x^\ast) \succ 0 \implies x^\ast \text{ strict local minimiser of }f\]

Give an @example to show that the sufficient conditions for $x^\ast$ to be a local minimiser of $f$ given by $\nabla f(x^\ast) = 0$ and $\nabla^2 f(x^\ast) \succ 0$ are not necessary.

\[f(x) = x^4\]

Suppose:

$f \in \mathcal C^2 (\mathbb R^n)$
$x^\ast \in \mathbb R^n$

@Prove the second-order necessary conditions for $x^\ast$ to be a local minimiser of $f$, i.e. that

\[\nabla f(x^\ast) = 0, \nabla^2 f(x^\ast) \succ 0 \implies x^\ast \text{ strict local minimiser of }f .\]

Assume for a contradiction that there exists $s \in \mathbb R^n$ with $s^\top \nabla^2 f(x^\ast) s < 0$. Then since $s \ne 0$ and $f \in \mathcal C^2$, we have that there exists some $\hat \alpha > 0$ such that

\[s^\top \nabla^2 f(x^\ast + \alpha s)s < 0 \quad\text{for all }\alpha \in [0, \hat \alpha]\]

Let $\alpha \in [0, \hat \alpha]$. Then considering the Taylor expansion around $x = x^\ast$ we have that

\[f(x^\ast + \alpha s) = f(x^\ast) + \frac{\alpha^2}{2} s^\top \nabla^2 f(x^\ast + \tilde \alpha s) s\]

for some $\tilde \alpha \in (0, \alpha)$. Since $0 < \tilde \alpha < \alpha \le \hat \alpha$, by the continuity of $f$, we obtain $s^2 \nabla^2 f(x^\ast + \tilde \alpha s) s < 0$. Thus implies $f(x^\ast + \alpha s) < f(x^\ast)$ and this holds for all $\alpha \in (0, \hat \alpha]$. Contradiction, as $x^\ast$ is a local minimiser.

Suppose:

$f \in \mathcal C^2(\mathbb R^n)$
$x^\ast \in \mathbb R^n$

@Prove the second order sufficient conditions that if

\[\nabla f(x^\ast) = 0, \nabla^2 f(x^\ast) \succ 0 \implies x^\ast \text{ strict local minimiser of }f\]

The continuity and positive definiteness imply there exists a neighbourhood $\mathcal N(x^\ast, \delta)$ of $x^\ast$ such that

\[\nabla^2 f(x^\ast + s) \succ 0 \text{ for all }x^\ast + s \in \mathcal N(x^\ast, \delta)\]

By the second-order Taylor expansion we have

\[f(x + \alpha s) = f(x) + \alpha s^\top \nabla f(x) + \frac{\alpha^2}{2} s^\top \nabla^2 f(x + \tilde \alpha s) s\]

Setting $x = x^\ast$ and $\alpha = 1$. Then for any $s$ with $x^\ast + s \in \mathcal N(x^\ast, \delta)$, we obtain

\[f(x^\ast + s) = f(x^\ast) + s^\top \nabla f(x^\ast) + \frac 1 2 s^\top \nabla^2 f(x^\ast + \tilde \alpha s) s\]

for some $\tilde \alpha \in (0, 1)$.

Then note that

\[\vert \vert x^\ast + \tilde \alpha s - x^\ast \vert \vert = \tilde \alpha \vert \vert s \vert \vert \le \delta\]

since $\tilde \alpha \in (0, 1)$ and $x^\ast + s \in \mathcal N(x^\ast, \delta)$ (so that $ \vert \vert s \vert \vert \le \delta)$, thus $x^\ast + \tilde \alpha s \in \mathcal N(x^\ast, \delta)$, which ensures that $\nabla^2 f(x^\ast + \tilde \alpha s) \succ 0$.

This, the above result and $\nabla f(x^\ast) = 0$ imply $f(x^\ast + s) > f(x^\ast)$ for all $s \ne 0$ with $x^\ast + s \in \mathcal N(x^\ast, \delta)$.

Suppose:

$H \in \mathbb R^{n \times n}$ is a symmetric matrix
$g \in \mathbb R^n$
$q(x) := \frac 1 2 x^\top H x + g^\top x$ is a quadratic function
$H$ is nonsingular

@State the unique stationary point $x^\ast$ of $q$ and sufficient conditions for it to be a minimiser, maximiser and a saddle point.

\[x^\ast = -H^{-1}g\]

$H$ positive definite $\implies x^\ast$ minimiser
$H$ negative definite $\implies x^\ast$ maximiser
$H$ indefinite $\implies x^\ast$ saddle point

Suppose:

$H \in \mathbb R^{n \times n}$ is a symmetric matrix
$g \in \mathbb R^n$
$q(x) := \frac 1 2 x^\top H x + g^\top x$ is a quadratic function
$H$ is singular

Under what conditions will $q$ have a solution and what type of solution will it be?

$g + Hx = 0$ must be consistent.

Flashcards

Related posts