Optimization

Throughout, $f : \mathbb{R}^n \to \mathbb{R}$.

First-Order Condition

For an extremum point $x \in \mathbb{R}^n$ of a differentiable $f$,

$$\nabla_x f(x) = \vec{0}, \quad \vec{0} \in \mathbb{R}^n$$

Second-Order Condition

For a point $x$ with $\nabla_x f(x) = \vec{0}$,

• if $\nabla_x^2 f(x)$ is positive definite, the function is locally convex at $x$ $\to$ local minimum,
• if $\nabla_x^2 f(x)$ is negative definite, the function is locally concave at $x$ $\to$ local maximum.

Note if $f : \mathbb{R} \to \mathbb{R}$, then $\nabla f = f'$ and $\nabla^2 f = f''$. Also only for $f : \mathbb{R} \to \mathbb{R}$, $\nabla_x^2 f$ being positive definite means $f''(x) > 0$, and negative definite means $f''(x) < 0$.

Global Extrema

Not so simple, but

• convex function $\implies$ any local minimum is a global minimum,
• concave function $\implies$ any local maximum is a global maximum.

See convexity.

Lagrange Multipliers

Let

• $x \in \mathbb{R}^n$ (point),
• $f : \mathbb{R}^n \to \mathbb{R}$ (objective function),
• $g : \mathbb{R}^n \to \mathbb{R}^m$ ($m$ many equality constraints),
• $\lambda \in \mathbb{R}^m$ (one Lagrange multiplier per constraint).

We want to solve

$$\min \text{ (or max) } f(x) \quad \text{s.t.} \quad g(x) = 0$$

or the same thing with scalar valued functions, $g_1(x) = 0, \ldots, g_m(x) = 0$. Define the Lagrangian

$$\mathcal{L}(x, \lambda) = f(x) + \lambda^T g(x) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)$$

Then if $x$ is an extremum (and the constraint gradients $\nabla g_i(x)$ are linearly independent), there is a multiplier $\lambda$ such that

1. $\nabla_x \mathcal{L}(x, \lambda) = \nabla_x f(x) + \nabla_x g(x)^T \lambda = \nabla_x f(x) + \sum_{i=1}^{m} \lambda_i \nabla_x g_i(x) = 0$ (stationarity),
2. $g(x) = \vec{0}$, i.e. $g_i(x) = 0$ for all $i$ (feasibility).

KKT Conditions

Let

• $x \in \mathbb{R}^n$ (point),
• $f : \mathbb{R}^n \to \mathbb{R}$ (objective function),
• $g : \mathbb{R}^n \to \mathbb{R}^m$ ($m$ many equality constraints),
• $h : \mathbb{R}^n \to \mathbb{R}^p$ ($p$ many inequality constraints),
• $\lambda \in \mathbb{R}^m$ (one Lagrange multiplier per equality constraint),
• $\mu \in \mathbb{R}^p$ (one Lagrange multiplier per inequality constraint).

We want to solve

$$\min f(x) \quad \text{s.t.} \quad g(x) = 0, \quad h(x) \le 0$$

(to maximize, minimize $-f$).

$$\mathcal{L}(x, \lambda, \mu) = f(x) + \lambda^T g(x) + \mu^T h(x) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{i=1}^{p} \mu_i h_i(x)$$

The following are the KKT conditions for a point $x$ and multipliers $\lambda, \mu$:

1. $\nabla_x \mathcal{L}(x, \lambda, \mu) = \nabla_x f(x) + \nabla_x g(x)^T \lambda + \nabla_x h(x)^T \mu = 0$ (stationarity), equivalently $\nabla_x f(x) + \sum_{i=1}^{m} \lambda_i \nabla_x g_i(x) + \sum_{i=1}^{p} \mu_i \nabla_x h_i(x) = 0$,
2. $g(x) = 0$, $h(x) \le 0$ (primal feasibility),
3. $\mu \ge 0$ (dual feasibility),
4. $\mu^T h(x) = 0$ (complementary slackness).

Complementary slackness means for each $i$, either $\mu_i = 0$, meaning the constraint is not active, or $h_i(x) = 0$, meaning the constraint is active.

For a minimum $x$ (under a constraint qualification, e.g. linearly independent gradients of the active constraints), there are $\lambda, \mu$ such that the KKT conditions hold, i.e. $x$ is an extremum only if the KKT conditions hold. If $f$ and $h$ are convex and $g$ is affine, the KKT conditions are also sufficient.