Fritz John and KKT Conditions

Setting

$$(P) \quad \min \; f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \quad i = 1, \ldots, m$$

with $f, g_1, \ldots, g_m : \mathbb{R}^n \to \mathbb{R}$ continuously differentiable. Write $\vec{g} = (g_1, \ldots, g_m) : \mathbb{R}^n \to \mathbb{R}^m$ and its Jacobian $\nabla \vec{g}(x) = \big[ \nabla g_1(x) \,|\, \cdots \,|\, \nabla g_m(x) \big] \in \mathbb{R}^{n \times m}$.

For $x$ feasible, the active constraints are the ones on the boundary,

$$\mathcal{A}_x = \{ i : g_i(x) = 0 \}$$

Road to Fritz John

Let $x$ be feasible and a local min of $(P)$.

1. There is no $d \in \mathbb{R}^n$ that is a descent direction for $f$ and all active $g_i$. Otherwise, for all small enough $\alpha > 0$, $g_i(x + \alpha d) < g_i(x) = 0$ for $i \in \mathcal{A}_x$ and, by continuity, $g_i(x + \alpha d) < 0$ for $i \notin \mathcal{A}_x$, so $x + \alpha d$ is feasible with $f(x + \alpha d) < f(x)$, a contradiction.
2. Equivalently, there is no $d$ with $J^T d < \vec{0}$, where the rows of $J^T$ are $\nabla f(x)^T$ and $\nabla g_i(x)^T$ for $i \in \mathcal{A}_x$.
3. By Gordan, there is $\lambda \ge \vec{0}$, $\lambda \neq \vec{0}$, with $J\lambda = \vec{0}$.
4. Setting the multipliers of inactive constraints to 0, there is a nonzero $(\beta, \lambda) \ge \vec{0}$, $\beta \in \mathbb{R}$, $\lambda \in \mathbb{R}^m$, with $\beta \nabla f(x) + \nabla \vec{g}(x) \lambda = \vec{0}$ and $\lambda_i = 0$ whenever $g_i(x) \neq 0$.
5. The last condition is $\lambda_i g_i(x) = 0$ for all $i$. Since $\lambda_i \ge 0$ and $g_i(x) \le 0$, every term $\lambda_i g_i(x) \le 0$, so it is equivalent to $\sum_i \lambda_i g_i(x) = \lambda^T \vec{g}(x) = 0$ (complementary slackness, $\lambda \ge \vec{0}$ and $\vec{g}(x) \le \vec{0}$ are orthogonal).

Fritz John Conditions

If $x$ is feasible and a local min of $(P)$, there are $\beta \in \mathbb{R}$, $\lambda \in \mathbb{R}^m$ with

$$\beta \nabla f(x) + \nabla \vec{g}(x) \lambda = \vec{0}, \qquad \lambda^T \vec{g}(x) = 0, \qquad \begin{bmatrix} \beta \\ \lambda \end{bmatrix} \ge \vec{0}, \text{ nonzero}$$

or, $\beta \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) = \vec{0}$, $\lambda_i g_i(x) = 0$ for all $i$, $\beta, \lambda_i \ge 0$ not all zero.

KKT Conditions

If $x$ is feasible, a local min of $(P)$, and satisfies the constraint qualification that $\{\nabla g_i(x)\}_{i \in \mathcal{A}_x}$ are linearly independent, then there is $\lambda \in \mathbb{R}^m$ with

$$\nabla f(x) + \nabla \vec{g}(x) \lambda = \vec{0}, \qquad \lambda^T \vec{g}(x) = 0, \qquad \lambda \ge \vec{0}$$

Proof Take $(\beta, \lambda)$ from Fritz John. If $\beta = 0$, then $\sum_{i \in \mathcal{A}_x} \lambda_i \nabla g_i(x) = \vec{0}$ with the $\lambda_i$ not all zero, a nontrivial linear combination of the active gradients giving $\vec{0}$, which contradicts independence. So $\beta > 0$, and scaling $(\beta, \lambda)$ by $1/\beta$ gives $\beta = 1$, after which nonzero is automatic.

So under the constraint qualification, a point that is not a KKT point is not a local min.

Checking a point For a candidate $\hat{x}$, check feasibility and that the gradients of the active constraints are linearly independent. Inactive constraints have $\lambda_i = 0$ by complementary slackness, so solve the linear system $\nabla f(\hat{x}) + \sum_{i \in \mathcal{A}_{\hat{x}}} \lambda_i \nabla g_i(\hat{x}) = \vec{0}$ and check $\lambda \ge \vec{0}$.

Sufficiency

Convex programs Let $\mathcal{S} \subseteq \mathbb{R}^n$ be nonempty, open and convex, and $f, g_1, \ldots, g_m : \mathcal{S} \to \mathbb{R}$ continuously differentiable and convex. If $\bar{x} \in \mathcal{S}$ is a KKT point of

$$\min \; f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \; i = 1, \ldots, m, \quad x \in \mathcal{S}$$

i.e. $g_i(\bar{x}) \le 0$, $\nabla f(\bar{x}) + \sum_i \lambda_i \nabla g_i(\bar{x}) = \vec{0}$, $\lambda_i g_i(\bar{x}) = 0$, $\lambda_i \ge 0$, then $\bar{x}$ is a global min. No constraint qualification is needed.

Local version Let $\mathcal{S}$ be nonempty and open and $f, g_i$ twice continuously differentiable. If $\bar{x}$ is a KKT point with $\nabla^2 f(\bar{x})$ PD and $\nabla^2 g_i(\bar{x})$ PD for all $i \in \mathcal{A}_{\bar{x}}$, then $\bar{x}$ is a local min.

Proof By continuity of the $g_i$ and of the eigenvalues of the Hessians, and since $\mathcal{S}$ is open, there is $\varepsilon > 0$ with $N_\varepsilon(\bar{x}) \subseteq \mathcal{S}$ such that on $N_\varepsilon(\bar{x})$

• $g_i(x) < 0$ for $i \notin \mathcal{A}_{\bar{x}}$,
• $\nabla^2 g_i(x)$ is PSD for $i \in \mathcal{A}_{\bar{x}}$,
• $\nabla^2 f(x)$ is PSD.

Consider

$$(P') \quad \min \; f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \; i \in \mathcal{A}_{\bar{x}}, \quad x \in N_\varepsilon(\bar{x})$$

$N_\varepsilon(\bar{x})$ is open and convex, and $f$ and the active $g_i$ are convex on it, so $(P')$ is a convex program. $\bar{x}$ is a KKT point of $(P)$, with inactive multipliers 0, so it is a KKT point of $(P')$ and hence a global min of $(P')$. Within $N_\varepsilon(\bar{x})$ the feasible sets of $(P)$ and $(P')$ agree, so $\bar{x}$ is a local min of $(P)$.

Equality Constraints

With equality constraints $h_j(x) = 0$, $j = 1, \ldots, \ell$, stationarity becomes

$$\nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) + \sum_{j=1}^{\ell} \mu_j \nabla h_j(x) = \vec{0}$$

with $\lambda_i g_i(x) = 0$, $\lambda \ge \vec{0}$, and $\mu$ free in sign.

Equality constrained QP

$$\min \; \frac{1}{2} x^T Q x + c^T x + d \quad \text{s.t.} \quad Ax = b$$

with $Q \in \mathbb{R}^{n \times n}$ PD, $A \in \mathbb{R}^{m \times n}$. This is always convex. With $\nabla f(x) = Qx + c$,

$$Qx + c + A^T \mu = \vec{0}, \quad Ax = b \iff \begin{bmatrix} Q & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ \mu \end{bmatrix} = \begin{bmatrix} -c \\ b \end{bmatrix}$$

and the KKT matrix is invertible if $A$ has full row rank.

KKT for Linear Programs

$$(LP) \quad \min \; c^T x \quad \text{s.t.} \quad Ax \ge b, \; x \ge \vec{0} \qquad \qquad (DP) \quad \max \; b^T y \quad \text{s.t.} \quad A^T y \le c, \; y \ge \vec{0}$$

Rewrite the constraints as $\vec{g}(x) \le \vec{0}$,

$$\begin{bmatrix} b - Ax \\ -x \end{bmatrix} \le \vec{0} \iff \begin{bmatrix} -A \\ -I \end{bmatrix} x + \begin{bmatrix} b \\ \vec{0} \end{bmatrix} \le \vec{0}$$

so $\nabla f = c$ and $\nabla \vec{g} = [-A^T \,|\, -I]$. With multipliers $\lambda = (y, z)$, $x$ is a KKT point iff

$$Ax \ge b, \; x \ge \vec{0}, \qquad c - A^T y - z = \vec{0}, \qquad y^T (b - Ax) = 0, \; -z^T x = 0, \qquad y, z \ge \vec{0}$$

Substituting $z = c - A^T y$,

$$\underbrace{Ax \ge b, \; x \ge \vec{0}}_{\text{primal feasible}}, \qquad \underbrace{A^T y \le c, \; y \ge \vec{0}}_{\text{dual feasible}}, \qquad \underbrace{y^T (Ax - b) = 0, \; x^T (c - A^T y) = 0}_{\text{complementary slackness}}$$

i.e. primal feasibility of $x$, dual feasibility of $y$, and complementary slackness.