Karush-Kuhn-Tucker Conditions: Constraint Qualifications and Second-Order Conditions

Intuition Beginner

When a problem has no rules, finding the lowest point is plain: walk downhill until the ground is flat. At a flat spot the slope is zero in every direction, and that zero-slope test is the whole story. Constraints change the picture. Now a fence blocks part of the ground, and the lowest reachable point may sit pressed against the fence, where the ground is still tilted but you cannot step further because the fence stops you.

The Karush-Kuhn-Tucker conditions are the fence-aware version of "the slope is zero." At a best point, the downhill pull of the cost must be exactly balanced by the push-back of the fences you are leaning on. Each fence you touch pushes outward with some strength, and at the optimum the cost's pull is a blend of those pushes. The strength of each push is a price, the same multiplier from Lagrangian pricing: a high price means that fence is really holding you back.

A fence you are not touching cannot push at all, so its price must be zero. This pairing — either you lean on a fence and it may charge a price, or you stand clear of it and it charges nothing — is called complementary slackness. It is the bookkeeping that says only the rules currently binding you matter for balance.

For the well-behaved problems built from convex costs and convex fences, this balance test is not just a clue that you might be at the best point: it is a complete certificate. Find prices that balance the pull, with idle fences priced at zero, and you have proven you are at the true optimum. For wilder problems the same equations are still necessary, but only once the fences meet a mild non-degeneracy requirement that keeps the geometry honest.

Visual Beginner

Figure: a contour map of a cost function with one straight constraint fence. The unconstrained minimum sits outside the allowed region. The constrained best point sits on the fence, where the cost's downhill arrow points straight into the fence and the fence's outward normal arrow points straight back. The two arrows lie on one line: the cost pull equals a positive price times the fence push.

   cost contours (rings around the free minimum *)
        ___________
       /   _____    \         allowed side  |  blocked side
      /   /     \    \                       |
     |   |   *   |    |   <- free min here   |   FENCE
      \   \_____/    /                       |
       \___________ /          best feasible | point x* sits ON
                                  x* o-----> | the fence
       cost pull (gradient, into fence)  ->  | <- fence push (normal, out)

   at x*:  -grad f0(x*)  =  lambda * (outward normal),   lambda >= 0
   idle fences: not touched  =>  their price is 0  (complementary slackness)

Worked example Beginner

Minimize $f(x,y)=(x-2{)}^2+(y-2{)}^2$ subject to the rule $x+y\le 2$. The cost is the squared distance to the point $(2,2)$, so without the rule the best point is $(2,2)$ itself, with cost $0$. But $(2,2)$ breaks the rule, since $2+2=4>2$. The best allowed point must sit on the fence line $x+y=2$.

Step 1. Set up the balance. The cost pull (negative gradient) at a point is the arrow toward $(2,2)$, namely $2(2-x,2-y)$. The fence $x+y\le 2$ pushes outward along the direction $(1,1)$. Balance asks for a price $\lambda \ge 0$ with $2(2-x)=\lambda$ and $2(2-y)=\lambda$.

Step 2. Use the fence. Equal right-hand sides force $2-x=2-y$, so $x=y$. On the fence $x+y=2$ this gives $x=y=1$.

Step 3. Read the price. Then $\lambda =2(2-1)=2$, which is at least $0$, as required. The fence is touched ($1+1=2$), so a positive price is allowed; complementary slackness is satisfied because the fence is active.

Step 4. Check the cost. At $(1,1)$ the cost is $(1-2{)}^2+(1-2{)}^2=1+1=2$.

What this tells us. The balance equations picked out the point $(1,1)$ with price $\lambda =2$, and that point is the closest allowed point to $(2,2)$. The cost arrow points straight across the fence and the fence pushes straight back with strength $2$: pull balanced by push, exactly the KKT picture.

Check your understanding Beginner

Formal definition Intermediate+

Consider the nonlinear program over $x\in {\mathbb{R}}^n$,

$$\underset{x}{\min }{f}_0(x)\text{subject to}{f}_i(x)\le 0(i\in \mathcal{I}=\{1,\dots ,m\}),h_j(x)=0(j\in \mathcal{E}=\{1,\dots ,p\}),$$

with $f_0,f_i,h_j$ continuously differentiable. The feasible set is $\Omega =\{x:f_i(x)\le 0,h_j(x)=0\}$. At a feasible $x$ the active set is $\mathcal{A}(x)=\mathcal{E}\cup \{i\in \mathcal{I}:f_i(x)=0\}$: the equalities plus the inequalities holding with equality. The Lagrangian is $L(x,\lambda ,\nu )=f_0(x)+{\sum }_i{\lambda }_i{f}_i(x)+{\sum }_j{\nu }_j{h}_j(x)$, with $\lambda \in {\mathbb{R}}^m$, $\nu \in {\mathbb{R}}^p$.

Definition (KKT point). A point $x^{\star }\in \Omega$ is a Karush-Kuhn-Tucker point if there exist multipliers ${\lambda }^{\star }\in {\mathbb{R}}^m$, ${\nu }^{\star }\in {\mathbb{R}}^p$ with

$${\nabla }_{x}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=\nabla f_0(x^{\star })+\sum _i{\lambda }_i^{\star }\nabla f_i(x^{\star })+\sum _j{\nu }_j^{\star }\nabla h_j(x^{\star })=0\text{(stationarity)},$$

together with ${\lambda }^{\star }⪰0$ (dual feasibility), $f_i(x^{\star })\le 0$ and $h_j(x^{\star })=0$ (primal feasibility), and

$${\lambda }_i^{\star }{f}_i(x^{\star })=0\text{for all }i\in \mathcal{I}\text{(complementary slackness)}.$$

Complementary slackness forces ${\lambda }_i^{\star }=0$ whenever $f_i(x^{\star })<0$, so the stationarity sum runs effectively over the active set $\mathcal{A}(x^{\star })$.

Definition (tangent cone and linearized feasible cone). The tangent cone $T_{\Omega }(x^{\star })$ collects all limiting feasible directions: $d\in T_{\Omega }(x^{\star })$ if there are feasible points $z_k\to x^{\star }$ and scalars $t_k\downarrow 0$ with $(z_k-x^{\star })/t_k\to d$. The linearized feasible cone uses only first-order data,

$$F(x^{\star })=\{d\in {\mathbb{R}}^n:⟨\nabla f_i(x^{\star }),d⟩\le 0(i\in \mathcal{A}(x^{\star })\cap \mathcal{I}),⟨\nabla h_j(x^{\star }),d⟩=0(j\in \mathcal{E})\}.$$

Always $T_{\Omega }(x^{\star })\subseteq F(x^{\star })$; the tangent cone respects the curved feasible set, while $F$ replaces each constraint by its tangent half-space.

Definition (constraint qualifications). A constraint qualification (CQ) is a condition on the active constraints at $x^{\star }$ that makes the linear approximation faithful. The linear independence CQ (LICQ) holds if the active gradients $\{\nabla f_i(x^{\star }):i\in \mathcal{A}(x^{\star })\cap \mathcal{I}\}\cup \{\nabla h_j(x^{\star }):j\in \mathcal{E}\}$ are linearly independent. The Mangasarian-Fromovitz CQ (MFCQ) holds if the equality gradients $\{\nabla h_j(x^{\star })\}$ are linearly independent and there is a direction $d$ with $⟨\nabla f_i(x^{\star }),d⟩<0$ for all active $i\in \mathcal{I}$ and $⟨\nabla h_j(x^{\star }),d⟩=0$ for all $j$. The linear-constraints CQ holds when all $f_i,h_j$ are affine. For convex problems Slater's condition of 44.02.01 plays the same role globally. Each CQ forces $T_{\Omega }(x^{\star })=F(x^{\star })$, the equality that makes stationarity necessary.

Counterexamples to common slips

• Without a CQ, a minimizer need not be a KKT point. Minimize $x_1$ subject to $x_2\le 0$ and $x_2-x_1^3\ge 0$. The origin is the unique minimizer, but the active gradients are $\nabla f$-values that are linearly dependent and the linearized cone is strictly larger than the tangent cone; no multipliers satisfy stationarity. The cusp degeneracy, not the objective, breaks KKT.
• KKT is necessary, not sufficient, off the convex case. A KKT point can be a maximizer or a saddle of a nonconvex problem; the first-order system only certifies stationarity of the Lagrangian. Sufficiency for a local minimum needs the second-order condition; global sufficiency needs convexity.
• Active set is the right index set, not the full constraint list. Including inactive inequalities in the stationarity sum with nonzero multipliers violates complementary slackness; only constraints with $f_i(x^{\star })=0$ may carry positive multipliers.

Key theorem with proof Intermediate+

The headline is the convex case, where KKT is both necessary and sufficient, followed by the general first-order necessary theorem under LICQ. The convex case rests on the saddle-point characterization of 44.02.01; the general case rests on the Farkas alternative of 44.02.04.

Theorem (KKT for the convex problem). Suppose $f_0,f_1,\dots ,f_m$ are convex and differentiable, the $h_j(x)=a_j^{\top }x-b_j$ are affine, and Slater's condition holds. Then $x^{\star }$ is a global minimizer if and only if there exist $({\lambda }^{\star },{\nu }^{\star })$ with ${\lambda }^{\star }⪰0$ such that $(x^{\star },{\lambda }^{\star },{\nu }^{\star })$ satisfies the KKT conditions.

Proof. ($\Rightarrow$) Let $x^{\star }$ be a global minimizer, so $p^{\star }=f_0(x^{\star })$ is finite. Slater and convexity give strong duality with dual attainment by 44.02.01: there is $({\lambda }^{\star },{\nu }^{\star })$, ${\lambda }^{\star }⪰0$, with $g({\lambda }^{\star },{\nu }^{\star })=p^{\star }$. By definition $g({\lambda }^{\star },{\nu }^{\star })={\inf }_{x}L(x,{\lambda }^{\star },{\nu }^{\star })\le L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=f_0(x^{\star })+{\sum }_i{\lambda }_i^{\star }{f}_i(x^{\star })+{\sum }_j{\nu }_j^{\star }{h}_j(x^{\star })$. Using $h_j(x^{\star })=0$ and ${\lambda }_i^{\star }{f}_i(x^{\star })\le 0$, the right side is $\le f_0(x^{\star })=p^{\star }=g({\lambda }^{\star },{\nu }^{\star })$. Equality throughout forces two facts: ${\sum }_i{\lambda }_i^{\star }{f}_i(x^{\star })=0$, hence (each term $\le 0$) ${\lambda }_i^{\star }{f}_i(x^{\star })=0$ termwise — complementary slackness; and $x^{\star }$ minimizes $x\mapsto L(x,{\lambda }^{\star },{\nu }^{\star })$ over ${\mathbb{R}}^n$. Since that map is convex and differentiable, its unconstrained minimum is characterized by ${\nabla }_{x}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=0$ — stationarity. Primal and dual feasibility hold by hypothesis, so the KKT system holds.

($\Leftarrow$) Suppose $(x^{\star },{\lambda }^{\star },{\nu }^{\star })$ satisfies KKT. The map $x\mapsto L(x,{\lambda }^{\star },{\nu }^{\star })$ is convex (a nonnegative-weighted sum of the convex $f_i$, the affine $h_j$, and convex $f_0$, using ${\lambda }_i^{\star }\ge 0$; this is the convex-operation calculus of 44.01.01). Stationarity ${\nabla }_{x}L(x^{\star })=0$ then certifies $x^{\star }$ as its global minimizer: $L(x,{\lambda }^{\star },{\nu }^{\star })\ge L(x^{\star },{\lambda }^{\star },{\nu }^{\star })$ for all $x$. For any feasible $x$ (so $f_i(x)\le 0$, $h_j(x)=0$),

$$f_0(x)\ge f_0(x)+\sum _i{\lambda }_i^{\star }{f}_i(x)+\sum _j{\nu }_j^{\star }{h}_j(x)=L(x,{\lambda }^{\star },{\nu }^{\star })\ge L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=f_0(x^{\star }),$$

where the first inequality uses ${\lambda }_i^{\star }{f}_i(x)\le 0$ and $h_j(x)=0$, and the final equality uses complementary slackness and feasibility of $x^{\star }$. So $x^{\star }$ is a global minimizer. $\square$

Theorem (first-order necessary conditions under LICQ, general NLP). Let $x^{\star }$ be a local minimizer of the differentiable NLP at which LICQ holds. Then there exist unique multipliers $({\lambda }^{\star },{\nu }^{\star })$ with ${\lambda }^{\star }⪰0$ satisfying the KKT conditions.

Proof. Two geometric facts drive the argument. First, local optimality gives $⟨\nabla f_0(x^{\star }),d⟩\ge 0$ for every $d\in T_{\Omega }(x^{\star })$: any tangent direction is a limit of feasible secants, along which $f_0$ cannot decrease to first order. Second, LICQ gives $T_{\Omega }(x^{\star })=F(x^{\star })$ (proved in the Full proof set via the implicit function theorem applied to the active constraints). Combining, $⟨\nabla f_0(x^{\star }),d⟩\ge 0$ for all $d\in F(x^{\star })$, i.e. $-\nabla f_0(x^{\star })$ makes a nonpositive inner product with no feasible linearized direction; equivalently $⟨\nabla f_0(x^{\star }),d⟩\ge 0$ whenever $⟨\nabla f_i(x^{\star }),d⟩\le 0$ (active $i$) and $⟨\nabla h_j(x^{\star }),d⟩=0$.

This is exactly the hypothesis of the Farkas alternative of 44.02.04. Assemble the active inequality gradients as columns of $A$ and the equality gradients (and their negatives) to encode the sign-free conditions; the statement "$⟨\nabla f_0(x^{\star }),d⟩\ge 0$ on the polyhedral cone $\{d:A^{\top }d\le 0\}$" is precisely the case where Farkas yields nonnegative coefficients ${\lambda }_i^{\star }\ge 0$ (active $i$) and free ${\nu }_j^{\star }$ with

$$\nabla f_0(x^{\star })=-\sum _{i\in \mathcal{A}\cap \mathcal{I}}{\lambda }_i^{\star }\nabla f_i(x^{\star })-\sum _j{\nu }_j^{\star }\nabla h_j(x^{\star }).$$

Setting ${\lambda }_i^{\star }=0$ for inactive $i$ gives stationarity and complementary slackness simultaneously, and ${\lambda }^{\star }⪰0$ is dual feasibility. Uniqueness: any two multiplier vectors satisfying stationarity differ by a vector in the kernel of the active-gradient map, which LICQ (linear independence of active gradients) forces to be zero. $\square$

Bridge. This theorem builds toward the second-order conditions of the Advanced results and the constrained Newton and SQP algorithms of chapters 03-04, and appears again in every certificate of local optimality for nonlinear programs. This is exactly the differential form of the saddle-point characterization of 44.02.01: stationarity is "$x^{\star }$ minimizes the Lagrangian," complementary slackness is the saddle bookkeeping, and the multiplier ${\lambda }^{\star }$ is the same supporting-hyperplane slope. The foundational reason a constraint qualification is needed is that KKT is a statement about the linearized feasible cone $F(x^{\star })$, while optimality lives on the true tangent cone $T_{\Omega }(x^{\star })$; the central insight is that a CQ is precisely what forces $T_{\Omega }=F$ so the linear model is faithful. Putting these together, the convex case generalises the elementary zero-gradient test by replacing flatness with Lagrangian flatness, and is dual to the strong-duality theorem it consumes; the general case is dual to the Farkas alternative of 44.02.04, with the active gradients as the cone columns and the multipliers as the nonnegative combination certifying that $-\nabla f_0$ lies in the cone they span.

Exercises Intermediate+

Advanced results Master

The tangent cone, the linearized cone, and Abadie's qualification

The exact necessary condition with no qualification is geometric: at a local minimizer, $-\nabla f_0(x^{\star })$ lies in the polar of the tangent cone, $-\nabla f_0(x^{\star })\in T_{\Omega }(x^{\star }{)}^{\circ }$ ^{[Nocedal & Wright §12.4]}. This is unconditional and contentless until the tangent cone is described by gradients, which is the role of a CQ. Abadie's constraint qualification is the weakest standard one, asserting exactly $T_{\Omega }(x^{\star })=F(x^{\star })$; KKT then follows because $T_{\Omega }^{\circ }=F^{\circ }$ is the cone generated by the active constraint gradients (Farkas of 44.02.04 computes the polar of a polyhedral cone). LICQ and MFCQ are sufficient conditions for Abadie's CQ, and the hierarchy

$$\text{LICQ}\Rightarrow \text{MFCQ}\Rightarrow \text{Abadie}\Rightarrow \text{KKT necessary},$$

orders the qualifications by strength, with the constant-rank CQ and the linear-constraints CQ sitting between MFCQ and Abadie. The Guignard CQ, requiring only $T_{\Omega }^{\circ }=F^{\circ }$ (polars equal, cones possibly not), is the genuinely weakest qualification under which KKT is necessary at every objective; everything weaker fails for some objective.

Multiplier existence, uniqueness, and the Fritz John form

Dropping every qualification, the Fritz John conditions always hold at a local minimizer: there exist $({\lambda }_0,\lambda ,\nu )\ne 0$ with ${\lambda }_0,\lambda ⪰0$ and ${\lambda }_0\nabla f_0(x^{\star })+{\sum }_i{\lambda }_i\nabla f_i(x^{\star })+{\sum }_j{\nu }_j\nabla h_j(x^{\star })=0$, plus complementary slackness ^{[Mangasarian & Fromovitz 1967]}. KKT is the normalized case ${\lambda }_0=1$; a CQ is precisely what excludes the degenerate ${\lambda }_0=0$, in which the objective drops out and the conditions say nothing about optimality. MFCQ is equivalent to ${\lambda }_0>0$ being forced and, by Gauvin's theorem, to boundedness of the multiplier set; LICQ strengthens this to the multiplier set being a singleton. The pairing-with-the-MFCQ-direction bound of Exercise 8 is the quantitative form, and it is exactly the dual-attainment-plus-compactness phenomenon that Slater produces globally in 44.02.01.

Second-order necessary and sufficient conditions on the critical cone

First-order conditions cannot separate minima from maxima and saddles at a KKT point; the second-order theory does this on the critical cone. Given a KKT point $(x^{\star },{\lambda }^{\star },{\nu }^{\star })$, the critical cone is

$$C(x^{\star })=\{d\in F(x^{\star }):⟨\nabla f_i(x^{\star }),d⟩=0\text{ for active }i\text{ with }{\lambda }_i^{\star }>0\},$$

the linearized feasible directions along which the objective's first-order change is zero. The second-order necessary condition states that if $x^{\star }$ is a local minimizer and LICQ holds, then $d^{\top }{\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })d\ge 0$ for all $d\in C(x^{\star })$. The second-order sufficient condition states that if $(x^{\star },{\lambda }^{\star },{\nu }^{\star })$ is KKT and $d^{\top }{\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })d>0$ for all nonzero $d\in C(x^{\star })$, then $x^{\star }$ is a strict local minimizer with a quadratic growth bound $f_0(x)\ge f_0(x^{\star })+c\Vert x-x^{\star }{\Vert }^2$ on a neighborhood ^{[Nocedal & Wright §12.5]}. The curvature is read off the Lagrangian Hessian, not the objective Hessian, and only on the critical cone, because the constraints absorb the curvature in their own active directions. Strict complementarity (${\lambda }_i^{\star }>0$ for all active $i$) collapses the critical cone to the lineality space $\{d:\nabla f_i^{\top }d=0(\text{active }i),\nabla h_j^{\top }d=0\}$, simplifying the test to a reduced-Hessian positive-definiteness check.

Sensitivity, the value function, and reduced-space curvature

Under LICQ, strict complementarity, and the second-order sufficient condition, the KKT solution map is differentiable in problem data and the optimal multipliers are the sensitivities $\partial p^{\star }/\partial b_i=-{\lambda }_i^{\star }$ of the value function to constraint perturbations, the smooth refinement of the global subgradient bound of 44.02.01. The implicit function theorem applied to the KKT system $({\nabla }_{x}L=0,h(x)=0,\lambda \odot f(x)=0)$ has nonsingular Jacobian exactly when the second-order sufficient condition holds, which is why that condition is the workhorse hypothesis for the local quadratic convergence of SQP and interior-point methods. On the active manifold the second-order condition is equivalent to positive definiteness of the reduced Hessian $Z^{\top }{\nabla }_{xx}^{2}LZ$, where the columns of $Z$ are a basis for the null space of the active-constraint Jacobian — the same projected-curvature object that null-space and range-space constrained-Newton methods factor.

Synthesis. The KKT conditions are exactly the differential shadow of the saddle-point characterization of 44.02.01, and the central insight of this unit is that first-order optimality is a statement about cones: at a minimizer $-\nabla f_0(x^{\star })$ lies in the polar of the tangent cone, and a constraint qualification is the single hypothesis that makes the tangent cone equal to its computable linearization $F(x^{\star })$. The foundational reason KKT can fail without a CQ is a tangent-cone/linearized-cone mismatch — the cusp degeneracy where the curved feasible set is thinner than its tangent half-spaces — and the LICQ $\Rightarrow$ MFCQ $\Rightarrow$ Abadie hierarchy orders exactly the strength of the guarantee that no such mismatch occurs. Putting these together, multiplier existence is dual to the Farkas alternative of 44.02.04: the active gradients are the cone columns and the multipliers are the nonnegative combination expressing $-\nabla f_0$, so LICQ (independence) yields a unique multiplier and MFCQ (a strict feasible direction, the local Slater) yields a bounded compact multiplier set. The second-order theory generalises the elementary Hessian test by reading curvature off the Lagrangian on the critical cone, and this is exactly the reduced-Hessian positive-definiteness that appears again in the constrained Newton, SQP, and interior-point algorithms of chapters 03-04, where the KKT system is the nonlinear target and its Jacobian is nonsingular precisely under the second-order sufficient condition.

Full proof set Master

Proposition 1 (tangent cone is contained in the linearized cone). For any feasible $x^{\star }$, $T_{\Omega }(x^{\star })\subseteq F(x^{\star })$.

Proof. Let $d\in T_{\Omega }(x^{\star })$, witnessed by feasible $z_k\to x^{\star }$, $t_k\downarrow 0$, $(z_k-x^{\star })/t_k\to d$. For an active inequality $i$, $f_i(x^{\star })=0$ and $f_i(z_k)\le 0$, so by differentiability $f_i(z_k)=f_i(x^{\star })+⟨\nabla f_i(x^{\star }),z_k-x^{\star }⟩+o(\Vert z_k-x^{\star }\Vert )\le 0$; dividing by $t_k>0$ and passing to the limit gives $⟨\nabla f_i(x^{\star }),d⟩\le 0$. For an equality $j$, $h_j(z_k)=0=h_j(x^{\star })$ gives $⟨\nabla h_j(x^{\star }),d⟩=0$ by the same expansion applied to $h_j$ and $-h_j$. So $d\in F(x^{\star })$. $\square$

Proposition 2 (LICQ forces $T_{\Omega }(x^{\star })=F(x^{\star })$). If LICQ holds at $x^{\star }$, then $F(x^{\star })\subseteq T_{\Omega }(x^{\star })$, hence equality.

Proof. Let $d\in F(x^{\star })$. Stack the active constraints into a map $c(x)$ whose components are $f_i$ ($i$ active) and $h_j$; LICQ says the Jacobian $J=Dc(x^{\star })$ has full row rank $r=|\mathcal{A}|$. Choose a smooth curve $z(t)$ with $z(0)=x^{\star }$, $z^{\prime }(0)=d$, and active constraints held at their first-order targets: by full row rank, the implicit function theorem solves $c(z(t))=tw(t)$ where $w_i=⟨\nabla f_i,d⟩\le 0$ for active inequalities and $w_j=0$ for equalities, with $z^{\prime }(0)=d$. Concretely, parametrize $z(t)=x^{\star }+td+J^{\top }(J{J}^{\top }{)}^{-1}u(t)$ and solve $c(z(t))=(\text{prescribed first-order values})$ for the correction $u(t)=o(t)$ via the implicit function theorem, valid because $J$ has full row rank. Then for active inequalities $f_i(z(t))=t⟨\nabla f_i,d⟩+o(t)\le 0$ for small $t>0$, equalities are held to $0$, and inactive inequalities remain strictly negative by continuity; so $z(t)\in \Omega$ for small $t>0$, and $(z(t)-x^{\star })/t\to d$, giving $d\in T_{\Omega }(x^{\star })$. With Proposition 1 this is equality. $\square$

Proposition 3 (KKT first-order necessary conditions under LICQ). If $x^{\star }$ is a local minimizer and LICQ holds, KKT multipliers exist and are unique.

Proof. Local optimality gives $⟨\nabla f_0(x^{\star }),d⟩\ge 0$ for all $d\in T_{\Omega }(x^{\star })$: along the witnessing curve, $f_0(z(t))\ge f_0(x^{\star })$ for small $t$, and the first-order expansion forces the directional derivative to be nonnegative. By Proposition 2, $T_{\Omega }(x^{\star })=F(x^{\star })$, so $⟨\nabla f_0(x^{\star }),d⟩\ge 0$ for every $d$ with $⟨\nabla f_i(x^{\star }),d⟩\le 0$ (active $i$) and $⟨\nabla h_j(x^{\star }),d⟩=0$. Splitting each equality into two inequalities, this is the premise of the Farkas alternative of 44.02.04: $-\nabla f_0(x^{\star })$ lies in the cone generated by $\{-\nabla f_i(x^{\star }):\text{active }i\}$ and $\{\pm \nabla h_j(x^{\star })\}$, yielding ${\lambda }_i^{\star }\ge 0$ (active), free ${\nu }_j^{\star }$, and $\nabla f_0(x^{\star })+{\sum }_{\text{active }i}{\lambda }_i^{\star }\nabla f_i(x^{\star })+{\sum }_j{\nu }_j^{\star }\nabla h_j(x^{\star })=0$. Set inactive ${\lambda }_i^{\star }=0$: stationarity and complementary slackness hold, ${\lambda }^{\star }⪰0$. Uniqueness is Exercise 8's LICQ argument. $\square$

Proposition 4 (second-order necessary condition). Let $x^{\star }$ be a local minimizer at which LICQ holds, with KKT multipliers $({\lambda }^{\star },{\nu }^{\star })$. Then $d^{\top }{\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })d\ge 0$ for all $d\in C(x^{\star })$.

Proof. Fix $d\in C(x^{\star })$. By the curve construction of Proposition 2 (LICQ), there is a feasible $C^2$ curve $z(t)$ with $z(0)=x^{\star }$, $z^{\prime }(0)=d$, and the active constraints with ${\lambda }_i^{\star }>0$ held identically at their boundary (possible since $⟨\nabla f_i,d⟩=0$ on the critical cone for those $i$); the equalities are held to $0$. Along this curve $L(z(t),{\lambda }^{\star },{\nu }^{\star })=f_0(z(t))$ because every active term with ${\lambda }_i^{\star }>0$ stays $0$ and inactive ${\lambda }_i^{\star }=0$. Local optimality gives $f_0(z(t))\ge f_0(x^{\star })$. Differentiating $L(z(t))$ twice at $0$: the first derivative is $⟨{\nabla }_{x}L,d⟩=0$ (stationarity), so the second-order Taylor expansion of 02.05.05 gives $0\le f_0(z(t))-f_0(x^{\star })=\frac{1}{2}{t}^2{d}^{\top }{\nabla }_{xx}^{2}Ld+o(t^2)$. Dividing by $t^2$ and letting $t\to 0$ yields $d^{\top }{\nabla }_{xx}^{2}Ld\ge 0$. $\square$

Proposition 5 (second-order sufficient condition). Let $(x^{\star },{\lambda }^{\star },{\nu }^{\star })$ be a KKT point with $d^{\top }{\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star },{\nu }^{\star })d>0$ for all nonzero $d\in C(x^{\star })$. Then $x^{\star }$ is a strict local minimizer, with $f_0(x)\ge f_0(x^{\star })+c\Vert x-x^{\star }{\Vert }^2$ near $x^{\star }$ for some $c>0$.

Proof. Suppose not: there are feasible $x_k\to x^{\star }$, $x_k\ne x^{\star }$, with $f_0(x_k)\le f_0(x^{\star })+o(\Vert x_k-x^{\star }{\Vert }^2)$. Set $d_k=(x_k-x^{\star })/\Vert x_k-x^{\star }\Vert$; passing to a subsequence $d_k\to d$, $\Vert d\Vert =1$. Feasibility forces $d\in T_{\Omega }(x^{\star })\subseteq F(x^{\star })$ (Proposition 1). For active $i$, the second-order expansion of $L$ along the secant, using stationarity $⟨{\nabla }_{x}L,d_k⟩$ small and complementary slackness, gives $f_0(x_k)-f_0(x^{\star })\ge L(x_k,{\lambda }^{\star },{\nu }^{\star })-L(x^{\star },{\lambda }^{\star },{\nu }^{\star })=\frac{1}{2}\Vert x_k-x^{\star }{\Vert }^2{d}_k^{\top }{\nabla }_{xx}^{2}L{d}_k+o(\Vert x_k-x^{\star }{\Vert }^2)$, where the inequality uses ${\lambda }_i^{\star }{f}_i(x_k)\le 0$. The assumption $f_0(x_k)-f_0(x^{\star })\le o(\Vert x_k-x^{\star }{\Vert }^2)$ forces $d^{\top }{\nabla }_{xx}^{2}Ld\le 0$. One checks $d\in C(x^{\star })$: $⟨\nabla f_0,d⟩\le 0$ from the assumed near-non-increase combines with $⟨\nabla f_0,d⟩\ge 0$ on $F$ (stationarity paired with the multiplier signs) to give equality, forcing $⟨\nabla f_i,d⟩=0$ for $i$ with ${\lambda }_i^{\star }>0$. Thus $d\in C(x^{\star })$, $d\ne 0$, with $d^{\top }{\nabla }_{xx}^{2}Ld\le 0$, contradicting the hypothesis. The quadratic growth bound follows from the uniform positive curvature on the unit critical sphere. $\square$

Connections Master

• The saddle-point and strong-duality theory of 44.02.01 is the direct parent: the convex KKT theorem is the differential reading of the saddle-point characterization, stationarity is "$x^{\star }$ minimizes the Lagrangian," and complementary slackness is the saddle bookkeeping that closes the duality gap. The multiplier ${\lambda }^{\star }$ produced here is exactly the supporting-hyperplane slope and dual optimizer of that unit, and Slater's condition there is the global convex instance of the constraint qualifications studied here.

• Farkas' lemma and the theorems of the alternative 44.02.04 are the multiplier-existence engine: the general first-order necessary theorem is Farkas applied to the objective gradient against the active-constraint gradients, with the linearized feasible cone as the polyhedral cone and the multipliers as the nonnegative combination certifying that $-\nabla f_0(x^{\star })$ lies in the cone the active gradients span. The polar-cone computation $T_{\Omega }^{\circ }=F^{\circ }$ underlying Abadie's CQ is Farkas computing the dual of a finitely generated cone.

• The multivariable Taylor and extremum theory of 02.05.05 supplies the smooth machinery: the first-order expansion of constraints proves $T_{\Omega }\subseteq F$, the implicit function theorem proves the reverse inclusion under LICQ, and the second-order Taylor remainder is what turns the Lagrangian-Hessian sign on the critical cone into the second-order necessary and sufficient conditions. KKT is the constrained generalization of the unconstrained stationary-point-plus-Hessian test established there.

• The convex-operation calculus and supporting-hyperplane apparatus of 44.01.01 underwrites both directions of the convex KKT theorem: convexity of $x\mapsto L(x,{\lambda }^{\star },{\nu }^{\star })$ for ${\lambda }^{\star }⪰0$ makes stationarity globally sufficient, and the same epigraph/supporting-line structure is what gives the first-order characterization of unconstrained convex minima that the proof invokes.

Historical & philosophical context Master

The conditions carry three names because they were discovered twice. William Karush stated the first-order necessary conditions for inequality-constrained minima, together with a constraint qualification, in his 1939 University of Chicago master's thesis ^{[Karush 1939]}, supervised in the calculus-of-variations tradition of Lawrence Graves and Magnus Hestenes; the thesis remained unpublished and unnoticed for decades. Harold Kuhn and Albert Tucker rediscovered and published the conditions in their 1951 paper Nonlinear Programming ^{[Kuhn & Tucker 1951]} (Proceedings of the Second Berkeley Symposium, 481-492), framing them within the emerging linear- and nonlinear-programming theory and explicitly identifying the role of a constraint qualification — they used a qualification on attainable directions that later analysis showed to be one of a graded family. Kuhn himself later credited Karush's priority, and the three-name attribution became standard.

The qualification theory was systematized in the 1960s. Fritz John's 1948 conditions had already shown that a degenerate multiplier on the objective could appear without a qualification; Olvi Mangasarian and Stan Fromovitz's 1967 paper ^{[Mangasarian & Fromovitz 1967]} (Journal of Mathematical Analysis and Applications 17, 37-47) isolated the qualification now bearing their names and proved it both excludes the degenerate Fritz John case and bounds the multiplier set, a result sharpened to compactness by Gauvin. The reorganization around convex analysis is due to Rockafellar, whose treatment placed the multipliers as subgradients of the value function, and the second-order theory on the critical cone reached its modern form in the numerical-optimization literature codified by Nocedal and Wright, where it is the standard regularity hypothesis for the local convergence analysis of constrained Newton, sequential quadratic programming, and interior-point methods.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{nocedal2006numerical,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2nd},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{bertsekas1999nonlinear,
  author    = {Bertsekas, Dimitri P.},
  title     = {Nonlinear Programming},
  edition   = {2nd},
  publisher = {Athena Scientific},
  year      = {1999}
}

@mastersthesis{karush1939minima,
  author  = {Karush, William},
  title   = {Minima of Functions of Several Variables with Inequalities as Side Conditions},
  school  = {Department of Mathematics, University of Chicago},
  year    = {1939}
}

@inproceedings{kuhn1951nonlinear,
  author    = {Kuhn, Harold W. and Tucker, Albert W.},
  title     = {Nonlinear Programming},
  booktitle = {Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability},
  pages     = {481--492},
  publisher = {University of California Press},
  year      = {1951}
}

@article{mangasarian1967fritz,
  author  = {Mangasarian, Olvi L. and Fromovitz, Stan},
  title   = {The {Fritz John} Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints},
  journal = {Journal of Mathematical Analysis and Applications},
  volume  = {17},
  pages   = {37--47},
  year    = {1967}
}

@article{john1948extremum,
  author  = {John, Fritz},
  title   = {Extremum Problems with Inequalities as Subsidiary Conditions},
  journal = {Studies and Essays Presented to R. Courant on his 60th Birthday},
  pages   = {187--204},
  year    = {1948}
}