Optimization Theory and Practice

---

Unconstrained Optimization

Instructor: Hasan A. Poonawala

Mechanical and Aerospace Engineering
University of Kentucky, Lexington, KY, USA

Topics:
Solutions
Necessary and Sufficient Conditions
Overview of Algorithms

Example: Curve Fitting

Suppose we have data in the form of pairs $$\{t_{i},y_{i}\}_ {i \in \{1,\dots,m\}}.$$

We believe that the model is of the form $$\phi(t; \theta) = \theta_{1} + \theta_{2} e^{\frac{(\theta_{3}-t )^2}{\theta_{4}}} + \theta_{5} \cos(\theta_{6} t).$$

A standard approach is to find the values of $\theta_{j}$, $j \in \{1,\dots,6\}$ by solving $$\min_{\theta \in \mathbb R^6} \sum_{j=1}^{6} r_{i}^{2}(\theta)$$ where $$r_{i}(\theta) = y_{i} - \phi(t_{i}; \theta)$$

This is a nonlinear least-square problem.

Solutions

Global minimizer

A point $x^{*}$ is a global minimizer if $f(x^*) \leq f(x)$ for all $x \in \mathbb R^n$.

Local minimizer

A point $x^{*}$ is a local minimizer if there is a neighborhood $\mathcal N$ of $x^*$ where $f(x^*) \leq f(x)$ for all $x \in \mathcal N$, where a neighbor of $y$ is an open set containing $y$.

Strict local minimizer

A point $x^{*}$ is a strict local minimizer if there is a neighborhood $\mathcal N$ of $x^*$ where $f(x^*) < f(x)$ for all $x \in \mathcal N$ with $x \neq x^*$.

Taylor’s theorem

Taylor’s Theorem

Suppose that $f \colon \mathbb R^n \to \mathbb R$ is continuously differentiable and that $p \in \mathbb{R}^n$. Then we have that $$f(x+p) = f(x) + \nabla f(x+t p) p$$ for some $t \in (0,1)$. Moreover, if $f$ is twice continuously differentiable, we have that $$\nabla f(x+p) = \nabla f(x) + \int_{0}^{1} \nabla^2 f(x+t p) p dt$$ and that $$f(x+p) = f(x) + \nabla f(x) p + \frac{1}{2} p^T \nabla^2 f(x+t p) p$$ for some $t \in (0,1)$.

First-order Necessary Condition

FONC

If $x^{\star}$ is a local minimizer and $f$ is continuously differentiable in an open neighborhood of $x^{\star}$, then $\nabla f (x^{\star}) = 0$.

Notice that this is not the same as $\nabla f (x^{\star}) = 0 \implies x^{\star}$ is a local minimizer

Stationary point

A point $x^{\star}$ is a stationary point if it satisfies $\nabla f(x^{\star})=0$

Second-order Necessary Condition

SONC

If $x^{\star}$ is a local minimizer of $f$ and $\nabla^2 f$ exists and is continuous in an open neighborhood of $x^{\star}$, then $\nabla f (x^{\star}) = 0$ and $\nabla^2 f (x^{\star})$ is positive semidefinite.

Second-order Sufficient Condition

SONC

Suppose that $\nabla^2 f (x^{\star})$ is continuous in a neighborhood of $x^{\star}$ and that $\nabla f (x^{\star}) = 0$ and $\nabla^2 f (x^{\star})$ is positive definite. Then $x^{\star}$ is a strict local minimizer of $f$.

First-order Sufficient Condition

There is no first-order sufficient condition for $f$ when it is only differentiable

However, when $f$ is also convex, there is:

FOSC for convex $f$

When $f$ is convex, any local minimizer $x^{\star}$ is a global minimizer of $f$ . If in addition $f$ is differentiable, then any stationary point $x^{\star}$ is a global minimizer of $f$.