Numerical Optimization¶

Introduction¶

Given the following notation:

• x : a vector of variable/unkowns/paramters
• f : objective function
• $c_i$ constraint functions

We can write an optimization problem in the format

where I and $\epsilon$ are equality and inequality constraints

Unconstrained optimization¶

When doing an unconstrained optimization, we define the optimization problem as

Where N $\geq 1 $ and the objective function (f(x)) is smooth. When solving we define the solutions ($x^*$) as follows:

• $x^*$ is a global minimizer if f($x^*$) $ < $ f(x) for all x $\neq x^*$
• $x^*$ is a weak local minimizer if f($x^*$) $ \leq $ f(x) for some x $\in N$ where N is a neighborhood of values
• $x^*$ is a strict/strong local minimizer if f($x^*$) $ < $ f(x) for some x $\in N$ where N is a neighborhood of values and $x^* \neq x$

How do we define a minimimum value?¶

Necessary conditions for optimizatiy are derived by assuming $x^*$ is a local minimizer and then proving facts about $\nabla f$ and $\nabla^2 f$

First-Order Necessary conditions (Theorm 2.2)¶

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

In essence:

• given an objective function at a minimum the derivative is zero

Second-Order Necessary conditions (Theorm 2.3)¶

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

In essence:

• given an objective function at a minimum the derivative is zero
• given an objective function at a minimum the second derivative is positive semi definite implies a weak local minimizer

Second-Order Sufficient conditions (Theorm 2.4)¶

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

In essence:

• given an objective function at a minimum the derivative is zero
• given an objective function at a minimum the second derivative is positive definite implies a strict local minimizer

Examples of Global, local, strict and weak minimizer:¶

Convex functions only have one minimum (Theorm 2.5)¶

Any local minimizer of a convex function is the global minimizer

Calculating the next step¶

Usually when calculating the next step we write this mathematically as follows: $$x_{k+1} = x_k + \alpha p_k$$

Where k is the current iteration, $p_k$ is the search direction at a given iteration and $\alpha$ is how far we are moving in the direction.