Skip to content

Lesson 44: The Kuhn–Tucker (KKT) Conditions

44.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the KKT conditions for a problem with inequality constraints.
  2. Explain complementary slackness and the sign restriction on the multipliers.
  3. Solve KKT systems by enumerating active sets, and check every candidate for feasibility.
  4. State when KKT is sufficient as well as necessary (convexity), and what a constraint qualification is.
  5. Recognise the KKT conditions as the general form of LP duality from Unit I.

44.2 From Equalities to Inequalities

\[\begin{aligned} \text{minimise}\quad & f(\mathbf{x})\\ \text{subject to}\quad & g_i(\mathbf{x})\le0,\quad i=1,\dots,m\\ & h_j(\mathbf{x})=0,\quad j=1,\dots,p \end{aligned}\]

An inequality constraint is either active (\(g_i=0\), the point is on the boundary) or inactive (\(g_i<0\), strictly inside). Only active constraints can restrain the optimum; inactive ones might as well not exist. The difficulty is that which constraints are active is not known in advance.

The sign of the multiplier now matters

For an equality constraint the multiplier could take either sign, because the constraint can be pushed either way. An inequality \(g\le0\) can only be relaxed in one direction, so its multiplier is sign-restricted.

At a minimum with \(g\) active, \(-\nabla f\) (the descent direction) must point out of the feasible region — otherwise one could move inside and downhill. Since \(\nabla g\) also points outward, \(-\nabla f=\mu\nabla g\) with \(\mu\ge0\):

\[\boxed{\ \nabla f+\mu\nabla g=\mathbf{0},\qquad \mu\ge0\ }\]

If \(\mu\) came out negative, the constraint would be pushing the wrong way — a signal that it is not really active and the candidate must be rejected.

44.3 The KKT Conditions

Theorem (Karush 1939, Kuhn–Tucker 1951). Let \(\mathbf{x}^{*}\) be a local minimum at which a constraint qualification holds. Then there exist multipliers \(\mu_i\ge0\) and \(\lambda_j\) such that:

Condition Name
1 \(\nabla f(\mathbf{x}^{*})+\displaystyle\sum_i\mu_i\nabla g_i(\mathbf{x}^{*})+\sum_j\lambda_j\nabla h_j(\mathbf{x}^{*})=\mathbf{0}\) stationarity
2 \(g_i(\mathbf{x}^{*})\le0\), \(h_j(\mathbf{x}^{*})=0\) primal feasibility
3 \(\mu_i\ge0\) dual feasibility
4 \(\mu_i\,g_i(\mathbf{x}^{*})=0\) for every \(i\) complementary slackness

Complementary slackness — the key idea

Condition 4 says that for each \(i\), at least one of \(\mu_i\) and \(g_i\) is zero:

\[g_i<0\ (\text{inactive})\ \Longrightarrow\ \mu_i=0 \qquad\qquad \mu_i>0\ \Longrightarrow\ g_i=0\ (\text{active})\]

A slack constraint has zero shadow price; a positive shadow price means the constraint binds. This is word-for-word the complementary slackness of Lesson 7 — Unit I's LP duality is the linear special case of KKT.

Sufficiency

KKT is necessary for a local minimum (given a constraint qualification), not sufficient. But:

Theorem. If \(f\) and all \(g_i\) are convex and all \(h_j\) are affine, then the KKT conditions are necessary and sufficient for a global minimum.

So for a convex programme, solving the KKT system solves the problem completely. Once again, convexity converts a local statement into a global one — the thread running through all of Unit IV.

Constraint qualifications

The theorem needs a regularity condition; the two most used are:

  • LICQ: the gradients of the active constraints are linearly independent at \(\mathbf{x}^{*}\).
  • Slater's condition (for convex problems): there exists a strictly feasible point with \(g_i(\mathbf{x})<0\) for all \(i\).

Without one of these, KKT can fail at a genuine optimum. The classic counterexample is minimising \(x_1\) subject to \(x_2\le0\) and \(x_1^{3}\ge x_2\) near the origin, where the active gradients are parallel and no multipliers exist.

Maximisation and ≥ constraints

Convert everything to the standard form above: maximise \(f\) becomes minimise \(-f\), and \(g(\mathbf{x})\ge0\) becomes \(-g(\mathbf{x})\le0\). Signs are the only real hazard in this topic; converting first is safer than memorising four sets of rules.

44.4 The Solution Procedure: Active-Set Enumeration

With \(m\) inequality constraints there are \(2^{m}\) possible active sets. For small \(m\), enumerate:

  1. Guess which constraints are active.
  2. Set \(\mu_i=0\) for the assumed-inactive ones and \(g_i=0\) for the assumed-active ones.
  3. Solve the resulting equality-constrained system (Lesson 43).
  4. Check the two conditions the guess did not impose: \(\mu_i\ge0\) for the active constraints, and \(g_i\le0\) for the inactive ones.
  5. Any candidate failing either check is rejected. Survivors are KKT points.

A sensible order of attack: try the unconstrained optimum first. If it is feasible, it is the answer and no constraint is active.

\(2^{m}\) is hopeless for large \(m\), which is why real algorithms (active-set and interior-point methods) update the active set intelligently rather than enumerating it. But by hand, for \(m\le3\), enumeration is exactly right.

44.5 Solved Problems

Problem 1 — One inequality constraint

\[\text{minimise } f=(x_1-3)^{2}+(x_2-2)^{2}\quad\text{s.t.}\quad x_1+x_2\le4,\ x_1,x_2\ge0.\]

Solution.

Step 0 — try the unconstrained optimum. \(\nabla f=\mathbf{0}\) at \((3,2)\), where \(x_1+x_2=5>4\): infeasible. So the constraint must be active.

Step 1 — KKT with \(g_1=x_1+x_2-4\) active. Ignore the non-negativity constraints for now (they will turn out slack).

\[L=(x_1-3)^{2}+(x_2-2)^{2}+\mu(x_1+x_2-4)\]
\[\frac{\partial L}{\partial x_1}=2(x_1-3)+\mu=0,\qquad \frac{\partial L}{\partial x_2}=2(x_2-2)+\mu=0\]

So \(x_1=3-\mu/2\) and \(x_2=2-\mu/2\). With \(g_1=0\):

\[\left(3-\frac\mu2\right)+\left(2-\frac\mu2\right)=4\ \Rightarrow\ 5-\mu=4\ \Rightarrow\ \mu=1\]
\[\boxed{x_1^{*}=2.5,\quad x_2^{*}=1.5,\quad \mu=1,\quad f^{*}=0.25+0.25=0.5}\]

Step 2 — check every KKT condition.

Condition Check Status
Stationarity \(2(-0.5)+1=0\) ✓ and \(2(-0.5)+1=0\) ✓ ✓
Primal feasibility \(2.5+1.5=4\le4\) ✓; \(x_1,x_2\ge0\) ✓ ✓
Dual feasibility \(\mu=1\ge0\) ✓ ✓
Complementary slackness \(\mu g_1=1(0)=0\) ✓; the \(x\ge0\) constraints are slack with zero multipliers ✓ ✓

Step 3 — sufficiency. \(f\) is convex (Hessian \(=2I\)) and all constraints are linear, so KKT is sufficient: this is the global minimum.

Interpretation. Geometrically, \(f\) is the squared distance from \((3,2)\), so the problem asks for the nearest feasible point to \((3,2)\) — the perpendicular foot on the line \(x_1+x_2=4\), which is \((2.5,1.5)\). The multiplier \(\mu=1\) says that relaxing the constraint to \(x_1+x_2\le5\) would reduce \(f^{*}\) by about \(1\); and indeed at \(b=5\) the point \((3,2)\) becomes feasible and \(f^{*}=0\), a drop of exactly \(0.5\) — less than \(\mu\) predicts, because \(f^{*}(b)\) flattens to zero and stops falling. Shadow prices are tangents; they do not survive a change of active set.

Problem 2 — Two constraints, one binding

\[\text{minimise } f=x_1^{2}+x_2^{2}-4x_1-6x_2\quad\text{s.t.}\quad x_1+x_2\le4,\ x_1\le3,\ x_1,x_2\ge0.\]

Solution.

Case A — no constraint active. \(\nabla f=(2x_1-4,\ 2x_2-6)=\mathbf{0}\) gives \((2,3)\), where \(x_1+x_2=5>4\): infeasible. Reject.

Case B — only \(g_1=x_1+x_2-4\) active.

\[2x_1-4+\mu_1=0,\qquad 2x_2-6+\mu_1=0\ \Rightarrow\ x_1=2-\frac{\mu_1}{2},\ x_2=3-\frac{\mu_1}{2}\]
\[x_1+x_2=5-\mu_1=4\ \Rightarrow\ \mu_1=1,\quad x^{*}=(1.5,\ 2.5)\]

Checks: \(\mu_1=1\ge0\) ✓; \(g_2=x_1-3=-1.5\le0\) ✓ (inactive, so \(\mu_2=0\) ✓); \(x_1,x_2\ge0\) ✓. All conditions satisfied — accept.

\[f^{*}=2.25+6.25-6-15=\mathbf{-12.5}\]

Case C — only \(g_2=x_1-3\) active. Then \(x_1=3\) and \(2x_2-6=0\) gives \(x_2=3\); but \(x_1+x_2=6>4\): infeasible. Reject.

Case D — both active. \(x_1=3\) and \(x_1+x_2=4\) give \(x_2=1\). Stationarity:

\[2(3)-4+\mu_1+\mu_2=0\ \Rightarrow\ \mu_1+\mu_2=-2\]
\[2(1)-6+\mu_1=0\ \Rightarrow\ \mu_1=4\ \Rightarrow\ \mu_2=-6<0\]

\(\mu_2<0\) violates dual feasibility. Reject.

\[\boxed{\mathbf{x}^{*}=(1.5,\ 2.5),\quad f^{*}=-12.5,\quad \mu_1=1,\ \mu_2=0}\]

Sufficiency. \(f\) is convex and the constraints are linear, so this is the global minimum.

Interpretation — what Case D teaches. Case D was feasible — the point \((3,1)\) satisfies every constraint. It was rejected purely because \(\mu_2\) came out negative, meaning the second constraint was pushing the solution away from the optimum rather than restraining it towards it. Feasibility is not enough; the multiplier signs are what distinguish a genuine KKT point from an arbitrary boundary point. Beginners commonly stop at feasibility and accept a wrong answer.

Problem 3 — A non-negativity constraint that binds

\[\text{minimise } f=(x_1-1)^{2}+(x_2+2)^{2}\quad\text{s.t.}\quad x_1\ge0,\ x_2\ge0.\]

Solution. Write in standard form: \(g_1=-x_1\le0\), \(g_2=-x_2\le0\).

Case A — neither active. \(\nabla f=\mathbf{0}\) at \((1,-2)\), where \(x_2=-2<0\): infeasible.

Case B — only \(g_2\) active (\(x_2=0\)).

\[2(x_1-1)+0=0\Rightarrow x_1=1;\qquad 2(x_2+2)-\mu_2=0\Rightarrow \mu_2=2(0+2)=4\]

Checks: \(\mu_2=4\ge0\) ✓; \(g_1=-1\le0\) ✓ (inactive).

\[\boxed{\mathbf{x}^{*}=(1,\ 0),\quad f^{*}=0+4=4,\quad \mu_1=0,\ \mu_2=4}\]

Cases C and D (\(x_1=0\), or both zero) give \(\mu_1=2(0-1)=-2<0\): rejected.

Interpretation. The unconstrained optimum wanted \(x_2=-2\); the bound \(x_2\ge0\) intervenes and the solution is pushed to the boundary. Note \(\dfrac{\partial f}{\partial x_2}=4>0\) at the optimum — the gradient does not vanish, which is exactly why Lesson 37's test cannot handle constrained problems.

The multiplier \(\mu_2=4\) is the reduced cost of \(x_2\): pushing \(x_2\) one unit negative (if it were allowed) would reduce \(f\) by about \(4\). That is precisely the quantity the simplex method reports for a non-basic variable in Unit I. The same object appears in every optimisation framework in this course, under three different names.

Problem 4 — A non-linear constraint

\[\text{maximise } f=x_1x_2\quad\text{s.t.}\quad x_1^{2}+x_2^{2}\le8,\ x_1,x_2\ge0.\]

Solution. Convert: minimise \(-x_1x_2\) subject to \(g=x_1^{2}+x_2^{2}-8\le0\).

Case A — inactive. \(\nabla(-x_1x_2)=(-x_2,-x_1)=\mathbf{0}\) only at the origin, where \(f=0\) — a saddle of the objective and clearly not a maximum. Reject.

Case B — active, \(x_1^{2}+x_2^{2}=8\).

\[-x_2+2\mu x_1=0,\qquad -x_1+2\mu x_2=0\]

Dividing (valid since \(x_1,x_2>0\)): \(\dfrac{x_2}{x_1}=\dfrac{x_1}{x_2}\), so \(x_1^{2}=x_2^{2}\) and, with both positive, \(x_1=x_2\). The constraint then gives \(2x_1^{2}=8\), i.e. \(x_1=2\).

From the first equation, \(\mu=\dfrac{x_2}{2x_1}=\dfrac12\ge0\) ✓.

\[\boxed{\mathbf{x}^{*}=(2,2),\quad f^{*}=4,\quad \mu=0.5}\]

Interpretation. The result is the classical one: among all points on a circle of radius \(\sqrt8\), the product \(x_1x_2\) is largest where \(x_1=x_2\), i.e. at \(45°\). The multiplier \(\mu=0.5\) says that enlarging the circle to \(x_1^2+x_2^2\le9\) would raise the maximum by about \(0.5\); exactly, the new maximum is \(9/2=4.5\), an increase of \(0.5\) ✓ — the prediction is exact here because \(f^{*}(b)=b/2\) is linear in \(b\).

Sufficiency check. \(-x_1x_2\) is not convex (its Hessian \(\begin{pmatrix}0&-1\\-1&0\end{pmatrix}\) is indefinite), so the sufficiency theorem does not apply and KKT is only necessary. Here the feasible set is compact and there is a single interior candidate, so the boundary point found is the global maximum — but that had to be argued separately. When convexity fails, KKT gives candidates, not answers.

Problem 5 — KKT and LP duality

Show that the KKT conditions for a linear programme reproduce Unit I's duality results.

Solution. Take the standard LP

\[\text{maximise } \mathbf{c}^{T}\mathbf{x}\quad\text{s.t.}\quad A\mathbf{x}\le\mathbf{b},\ \mathbf{x}\ge\mathbf{0}\]

and convert to minimising \(-\mathbf{c}^{T}\mathbf{x}\) with \(g_1=A\mathbf{x}-\mathbf{b}\le\mathbf{0}\) and \(g_2=-\mathbf{x}\le\mathbf{0}\), with multipliers \(\mathbf{y}\ge\mathbf{0}\) and \(\mathbf{s}\ge\mathbf{0}\).

Stationarity:

\[-\mathbf{c}+A^{T}\mathbf{y}-\mathbf{s}=\mathbf{0}\ \Longrightarrow\ A^{T}\mathbf{y}=\mathbf{c}+\mathbf{s}\ \ge\mathbf{c}\]

That is exactly the dual feasibility condition \(A^{T}\mathbf{y}\ge\mathbf{c}\), \(\mathbf{y}\ge0\) of Lesson 7 — and \(\mathbf{s}\) is the vector of surplus variables in the dual.

Complementary slackness:

\[y_i\,(A\mathbf{x}-\mathbf{b})_i=0\quad\text{and}\quad s_jx_j=0\]

which is precisely Lesson 7's pair of conditions: a constraint with slack has zero dual price, and a variable at zero level has a positive reduced cost.

Strong duality. Multiplying stationarity by \(\mathbf{x}^{T}\) and using complementary slackness:

\[\mathbf{c}^{T}\mathbf{x}=\mathbf{x}^{T}A^{T}\mathbf{y}-\mathbf{x}^{T}\mathbf{s} =\mathbf{y}^{T}(A\mathbf{x})-0=\mathbf{y}^{T}\mathbf{b}\]
\[\boxed{\mathbf{c}^{T}\mathbf{x}^{*}=\mathbf{b}^{T}\mathbf{y}^{*}}\]

— strong duality, obtained in three lines from KKT.

Interpretation. The multipliers \(\mathbf{y}\) of KKT are the shadow prices of Lesson 7, and the simplex method's \(z_j-c_j\) row is the vector \(\mathbf{s}\) of dual surpluses. Everything in Unit I was the linear special case of the theory in this lesson. That unity is worth stating explicitly:

Unit I (LP) Unit IV (NLP)
Dual variable \(y_i\) KKT multiplier \(\mu_i\)
\(y_i\ge0\) for a \(\le\) constraint \(\mu_i\ge0\)
Complementary slackness Condition 4
Reduced cost \(z_j-c_j\) Multiplier on \(x_j\ge0\)
Simplex reaches the optimum in finitely many steps Convexity makes a KKT point global

44.6 Practice Problems

  1. Minimise \(f=x_1^{2}+x_2^{2}\) subject to \(x_1+x_2\ge4\). (Answer: constraint active; \(\mathbf{x}^{*}=(2,2)\), \(f^{*}=8\), \(\mu=4\) after converting to \(-x_1-x_2+4\le0\))
  2. Minimise \(f=(x_1-2)^{2}+(x_2-1)^{2}\) subject to \(x_1+x_2\le2\), \(x_1\ge0\), \(x_2\ge0\). (Answer: \(g_1\) active, \(\mathbf{x}^{*}=(1.5,\ 0.5)\), \(\mu_1=1\), \(f^{*}=0.5\))
  3. For \(f=x_1^{2}+x_2^{2}\) subject to \(x_1+x_2\le6\), show that the constraint is inactive and the optimum is the unconstrained one. (Answer: \((0,0)\) is feasible, so \(\mu=0\) and \(f^{*}=0\))
  4. Enumerate all four active sets for a problem with two inequality constraints and state what must be checked in each case.
  5. Why does a negative multiplier disqualify a candidate? Answer in terms of the direction in which the constraint pushes the solution.

44.7 Summary

  • KKT = stationarity + primal feasibility + \(\mu_i\ge0\) + complementary slackness. It generalises Lagrange multipliers (L43) to inequality constraints.
  • Complementary slackness \(\mu_ig_i=0\): an inactive constraint has \(\mu_i=0\); a positive \(\mu_i\) forces the constraint to be active. This is Lesson 7's condition, in general form.
  • The multiplier sign matters. \(\mu_i\ge0\) because an inequality can be relaxed in only one direction; a negative \(\mu\) means the constraint is pushing the wrong way, and the candidate is rejected even though it is feasible (Problem 2, Case D).
  • Solve by active-set enumeration for small \(m\): assume a set active, solve the equality problem, then check the conditions the assumption did not impose. Try the unconstrained optimum first.
  • KKT is necessary given a constraint qualification (LICQ or Slater), and necessary and sufficient for a global minimum when \(f\) and the \(g_i\) are convex and the \(h_j\) affine.
  • At a boundary optimum \(\nabla f\ne\mathbf{0}\) — which is exactly why Lesson 37's test fails and this theory is needed.
  • LP duality is the linear special case. Dual variables, reduced costs, complementary slackness and strong duality all fall out of KKT in a few lines.

Next lesson: L45 — Quadratic programming: Wolfe's and Beale's methods, and the course capstone.

Practise now: unit4-nlp-search-lab.html → KKT Checker: enter an objective and constraints, enumerate the active sets, and see each candidate accepted or rejected with the failing condition highlighted.