KKT Conditions, Linear Duality, and Sharpness

Conceptual map

III-16.01Constrained optimization
III-16.02Corners
III-16.03Linear-program duality
III-16.04Infeasibility certificates
III-16.05Minimum enabling cost

1. KKT conditions need a model and a qualification

A constrained optimum is certified by feasibility, stationarity, dual signs, and complementarity. In convex programs these conditions become sufficient; a constraint qualification supplies necessity and strong dual conclusions.

For the convex problem $\operatorname{min}_{x}$ $$f(x)$$ subject to $g_{j}(x)\le0$ and $$Ax=b$$ , define

\[L(x,\lambda ,\nu )=f(x)+\sum _{j}\lambda _{j}g_{j}(x)+\nu ^{\top }(Ax-b).\](1)

KKT requires primal feasibility, $\lambda \ge0$ , stationarity $0\in \partial _{x}L$ , and $\lambda _{j}g_{j}(x)=0$ . Slater's condition is a common qualification for convex inequality systems.

2. Minimum-cost enabling and its dual

Consider the covering linear program

\[\begin{aligned}\text{Primal:}\quad & \min_x\ c^{\top}x && \text{subject to }Ax\ge b,\ x\ge0, \\ \text{Dual:}\quad & \max_y\ b^{\top}y && \text{subject to }A^{\top}y\le c,\ y\ge0.\end{aligned}\](2)

Proposition 1 · Weak duality certificate

Every primal-feasible $$x$$ and dual-feasible $$y$$ satisfy $b^{\top}y\le c^{\top}x$ . Equality certifies optimality of both solutions.

Proof. Since $y\ge0$ and $Ax\ge b$ , $b^{\top}y\le x^{\top}A^{\top}y$ . Dual feasibility and $x\ge0$ give $x^{\top}A^{\top}y\le x^{\top}c$ . ∎

3. A sharp two-requirement package

Let

\[A=\begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}, \quad b=(1,1)^{\top }, \quad c=(1,\frac{3}{2},1)^{\top }.\](3)

The primal allocation $x^{*}=(0,1,0)^{\top}$ enables both requirements at cost 3/2. The dual vector $y^{*}=(3/4,3/4)^{\top}$ satisfies $A^{\top}y^{*}=(3/4,3/2,3/4)^{\top}\le c$ and has value 3/2. Equality in weak duality certifies the optimum. Complementary slackness records that both requirements bind and only the shared second input is used.

On the efficient boundary with $0\le x_{2}\le1$ , set $x_{1}=x_{3}=1-x_{2}$ . Cost is $2-x_{2}/2$ , so the optimizer is unique at $x_{2}=1$ .

4. Infeasibility and separation

Proposition 2 · Farkas alternative

Exactly one of the following systems has a solution: (i) $$Ax=b$$ , $x\ge0$ ; (ii) $A^{\top}y\ge0$ and $b^{\top}y<0$ .

Take $A=\begin{bmatrix}1 & 1 \\ 1 & 1\end{bmatrix}$ and $b=(1,0)^{\top}$ . The equal rows cannot produce unequal coordinates in $$b$$ . The multiplier $y=(-1,1)^{\top}$ has $A^{\top}y=0$ and $b^{\top}y=-1$ , providing a finite certificate.

Failure case · Solver status used as sharpness

A numerical status code reports behavior under tolerances and scaling. Sharpness requires a feasible extremizer and a matching dual or separation certificate, together with primal, dual, and complementarity residuals.

5. Implementation, exercises, and sources

Rescale rows and variables, retain the original economic units for reporting, and print primal violation, dual violation, objective gap, and complementarity products. For infeasibility, request a dual ray and verify its inequalities outside the solver.

Download the volume verification script →

Exercises

Derive the dual in (2) from the Lagrangian and verify all residuals for (3).
Change the shared-input cost from 3/2 to a parameter $c_{2}$ ; characterize the optimizer face for every $c_{2}\ge0$ .
Verify the Farkas certificate and construct a minimally infeasible subsystem with three equations.

Partial solutions

1. Attach nonnegative multipliers to $b-Ax\le0$ . The infimum over $x\ge0$ is finite when $A^{\top}y\le c$ , producing (2). In (3), both primal slacks and the second dual slack are zero; unused inputs have positive dual slack. 2. Along the efficient boundary cost is $2+(c_{2}-2)x_{2}$ . The shared input is uniquely used when $c_{2}<2$ , the entire boundary is optimal at equality, and the two separate inputs are used when $c_{2}>2$ .

Dimitris Bertsimas and John Tsitsiklis, Introduction to Linear Optimization, Chapters 4–5.Duality and certificates.
Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Chapter 5.KKT conditions and constraint qualifications.
Alexander Schrijver, Theory of Linear and Integer Programming, Chapters 7–8.Farkas lemmas and polyhedral duality.

6. Audit checkpoint

Report the primal and dual, sign conventions, qualification, active set, primal and dual solutions, feasibility residuals, objective gap, complementarity, and any independent Farkas certificate.

7. Scope boundary

The chapter covers convex KKT conditions, finite linear-program duality, corner solutions, and infeasibility certificates. Integer and general nonconvex optimization are outside scope.