KKT Conditions

Chapter 12: Optimization Methods. In the chapter mind map this icon labels KKT Optimality Conditions & Multipliers. The discussion below is excerpted and lightly edited from § Karush–Kuhn–Tucker (KKT) Conditions in Mathematics for AI and Machine Learning.

Let $f$, $g_i$ and $h_i$ be differentiable and suppose strong duality holds (for example, under Slater's condition). Then a primal optimal $x$ and a dual optimal $(\eta, \nu)$ satisfy the Karush–Kuhn–Tucker conditions:

1. Primal feasibility: $g_i(x) \le 0$, $h_i(x) = 0$ 2. Dual feasibility: $\eta \ge 0$ 3. Complementary slackness: $\eta_i g_i(x)=0$ 4. Stationarity:

For a convex program the converse also holds: any point that satisfies all four conditions is optimal, so solving the KKT system solves the problem. Stationarity says that $x$ minimizes the Lagrangian @eq:lagrangian, and complementary slackness says that every inequality is either active, $g_i(x) = 0$, or carries no weight, $\eta_i = 0$: a constraint that is not tight does not affect the optimum.

Geometrically, $-\nabla f(x)$ is a nonnegative combination of the outward normals $\nabla g_i(x)$ of the active constraints (plus a combination of the $\nabla h_i(x)$), so no feasible direction can still decrease $f$.

In the support vector machine above, complementary slackness gives a nonzero multiplier only to training points on or inside the margin, $y^{(m)} \mathbf w^\top \mathbf x^{(m)} \le 1$; these are the support vectors, and every other point could be removed without changing $\mathbf w$.