The Karush-Kuhn-Tucker conditions combine stationarity with the one-sided geometry of inequality constraints. They are necessary only under a constraint qualification, but in convex problems they become a complete certificate of global optimality.
Primal and dual variables
Consider \[ \min_x f(x) \quad\text{subject to}\quad g_i(x)\le0\ (1\le i\le m),\qquad h_j(x)=0\ (1\le j\le r). \] Its Lagrangian is \[ \mathcal L(x,\lambda,\nu) =f(x)+\sum_{i=1}^m\lambda_i g_i(x) +\sum_{j=1}^r\nu_jh_j(x), \qquad \lambda\in\mathbb R_+^m,\quad\nu\in\mathbb R^r. \]
Definition. A feasible point \(x^\star\) and multipliers \((\lambda^\star,\nu^\star)\) satisfy the KKT conditions if
\[ \begin{aligned} &\nabla f(x^\star)+\sum_i\lambda_i^\star\nabla g_i(x^\star) +\sum_j\nu_j^\star\nabla h_j(x^\star)=0 &&\text{(stationarity)},\\ &g_i(x^\star)\le0,\quad h_j(x^\star)=0 &&\text{(primal feasibility)},\\ &\lambda_i^\star\ge0 &&\text{(dual feasibility)},\\ &\lambda_i^\star g_i(x^\star)=0 &&\text{(complementary slackness)}. \end{aligned} \]
Complementary slackness says that an inactive constraint has zero multiplier. A positive multiplier can occur only where the constraint touches the solution.
Necessity under linear independence
KKT necessity under LICQ. Suppose \(f,g_i,h_j\) are continuously differentiable and \(x^\star\) is a local minimizer. Let \(I(x^\star)=\{i:g_i(x^\star)=0\}\). If the vectors \[ \{\nabla g_i(x^\star):i\in I(x^\star)\} \cup\{\nabla h_j(x^\star):1\le j\le r\} \] are linearly independent, then KKT multipliers exist.
Proof outline. Under LICQ, the feasible-direction cone is described to first order by \[ \langle\nabla g_i(x^\star),v\rangle\le0 \quad(i\in I(x^\star)),\qquad \langle\nabla h_j(x^\star),v\rangle=0. \] Local optimality rules out a vector satisfying these relations and \(\langle\nabla f(x^\star),v\rangle<0\). The separating alternative for linear inequalities, equivalently Farkas' lemma, therefore represents \(-\nabla f(x^\star)\) as a nonnegative combination of active inequality gradients plus a linear combination of equality gradients. Set inactive multipliers to zero. This gives stationarity, dual feasibility, and complementary slackness.
Constraint qualifications cannot simply be omitted. Minimizing \(x\) subject to \(x^2\le0\) has the unique feasible solution \(0\), but \(\nabla g(0)=0\), and stationarity \(1+\lambda\nabla g(0)=0\) is impossible.
Slater's condition and convex strong duality
Convex KKT theorem. Assume \(f\) and \(g_i\) are proper convex functions, the equality constraints are affine, and there is a point \(\bar x\) in the relative interior of the common domain such that \(g_i(\bar x)<0\) and \(h_j(\bar x)=0\). Then a feasible \(x^\star\) is optimal if and only if it admits KKT multipliers. The primal and Lagrange dual values coincide.
Proof. Slater's condition makes the perturbation value function closed at the origin. A supporting hyperplane at the optimal value produces nonnegative inequality multipliers and free equality multipliers, proving necessity and zero duality gap.
For sufficiency, stationarity and convexity imply that \(x^\star\) globally minimizes \(x\mapsto\mathcal L(x,\lambda^\star,\nu^\star)\). For any feasible \(x\), \[ f(x)\ge\mathcal L(x,\lambda^\star,\nu^\star) \ge\mathcal L(x^\star,\lambda^\star,\nu^\star) =f(x^\star), \] where the first inequality uses \(\lambda^\star\ge0,\ g(x)\le0\), and the last equality uses feasibility and complementary slackness.
A quadratic program with an active boundary
Example. Minimize \[ f(x)=\frac12\|x-a\|^2 \quad\text{subject to}\quad c^\top x\le b, \] with \(c\ne0\). The KKT equations are \(x-a+\lambda c=0\), \(c^\top x\le b\), \(\lambda\ge0\), and \(\lambda(c^\top x-b)=0\). If \(c^\top a\le b\), then \(x^\star=a,\lambda^\star=0\). Otherwise the constraint is active and \[ \lambda^\star=\frac{c^\top a-b}{\|c\|^2}, \qquad x^\star=a-\frac{c^\top a-b}{\|c\|^2}c. \] Thus KKT recovers the orthogonal projection onto a half-space, and the multiplier equals the normal displacement measured in the constraint's scale.