Quant Academy Math · Probability · Quant Finance
Phase 10 - Lesson 10.3

Lagrangian Duality and the KKT Conditions

Turning constraints into prices, bounding the optimum, and certifying it.

⏱ 55 min● Advanced🔗 Prereqs: 10.2
↖ Phase 10 hub
Builds on: 10.2 gave optimality over convex feasible sets.
Leads to: 10.4 solves the resulting systems; 10.5 uses KKT for portfolios.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Key Vocabulary

Lagrangian
The function \(L(x,\lambda,\nu)=f_0(x)+\sum_i\lambda_i f_i(x)+\sum_j\nu_j(a_j^\top x-b_j)\) folding constraints into the objective.
Dual function
The infimum \(g(\lambda,\nu)=\inf_x L(x,\lambda,\nu)\); concave, and a lower bound on the optimum.
Weak duality
Always: \(g(\lambda,\nu)\le p^\star\) for \(\lambda\ge0\); the best such bound is the dual optimum \(d^\star\le p^\star\).
Strong duality
When \(d^\star=p^\star\) (zero gap); holds for convex problems under a constraint qualification.
Slater's condition
A strictly feasible point exists (\(f_i(x)\lt 0\), equalities met); guarantees strong duality for convex problems.
KKT conditions
Stationarity, primal & dual feasibility, and complementary slackness - necessary and (convex case) sufficient for optimality.

Intuition & Motivation

Intuition
Every constraint has a ‘price’: how much the optimal value would improve if you relaxed it a little. The Lagrangian buys off each constraint at a price \(\lambda_i\) and folds it into the objective. Minimizing over \(x\) for fixed prices gives a guaranteed lower bound on the true optimum (weak duality). For convex problems with a strictly feasible point, the best price choice makes the bound tight (strong duality), and the resulting KKT equations pin down the solution exactly.

The Lagrangian and dual function

Start from standard form (10.3). Attach a multiplier \(\lambda_i\ge0\) to each inequality and \(\nu_j\) to each equality:

\[L(x,\lambda,\nu)=f_0(x)+\sum_{i}\lambda_i f_i(x)+\sum_j\nu_j(a_j^\top x-b_j).\] (10.5)

The dual function \(g(\lambda,\nu)=\inf_x L(x,\lambda,\nu)\) is a pointwise infimum of affine functions of \((\lambda,\nu)\), hence always concave even when the primal is not convex.

Theorem - Weak duality
For any \(\lambda\ge0\) and any \(\nu\), \(g(\lambda,\nu)\le p^\star\), where \(p^\star\) is the primal optimum. Maximizing the bound gives the dual problem with value \(d^\star\), and always \(d^\star\le p^\star\). The nonnegative difference \(p^\star-d^\star\) is the duality gap.
Proof
For feasible \(x\) (so \(f_i(x)\le0,\ a_j^\top x=b_j\)) and \(\lambda\ge0\), the added terms are \(\le0\), hence \(L(x,\lambda,\nu)\le f_0(x)\). Taking the inf over \(x\) on the left only lowers it: \(g(\lambda,\nu)\le f_0(x)\) for every feasible \(x\), so \(g\le p^\star\).
Theorem - Strong duality & Slater
If the primal is convex and satisfies Slater's condition - there exists a strictly feasible \(x\) with \(f_i(x)\lt 0\) for all nonaffine \(f_i\) and \(Ax=b\) - then strong duality holds: \(d^\star=p^\star\), and the dual optimum is attained.
Definition - KKT conditions
For differentiable \(f_i\), a primal-dual pair \((x^\star,\lambda^\star,\nu^\star)\) is optimal (under strong duality) iff:
  1. Stationarity: \(\nabla f_0(x^\star)+\sum_i\lambda_i^\star\nabla f_i(x^\star)+\sum_j\nu_j^\star a_j=0\).
  2. Primal feasibility: \(f_i(x^\star)\le0\), \(Ax^\star=b\).
  3. Dual feasibility: \(\lambda_i^\star\ge0\).
  4. Complementary slackness: \(\lambda_i^\star f_i(x^\star)=0\) for all \(i\).

For convex problems the KKT conditions are sufficient as well as necessary - solve them and you have the global optimum.

Worked Example - KKT for an equality-constrained quadratic
1
Problem: \(\min\ \tfrac12 x^\top Q x\) s.t. \(a^\top x=1\), \(Q\succ0\). Only an equality, so multiplier \(\nu\).
2
Lagrangian \(L=\tfrac12 x^\top Q x+\nu(a^\top x-1)\). Stationarity: \(Qx+\nu a=0\Rightarrow x=-\nu Q^{-1}a\).
3
Feasibility \(a^\top x=1\): \(-\nu\,a^\top Q^{-1}a=1\Rightarrow\nu=-1/(a^\top Q^{-1}a)\).
4
So \(x^\star=\dfrac{Q^{-1}a}{a^\top Q^{-1}a}\) - exactly the min-variance portfolio weights you meet in 10.5 (with \(a=\mathbf1\)). The multiplier \(\nu^\star\) is the marginal cost of the budget constraint.

Predict the shadow price

Predict first: If tightening a constraint by one unit worsens the optimal value by 3, what is the corresponding Lagrange multiplier (its shadow price), approximately?
Common Mistakes to Avoid
  • Allowing \(\lambda_i\lt 0\). Inequality multipliers must be \(\ge0\); only equality multipliers \(\nu\) are free.
  • Forgetting complementary slackness: an inactive constraint (\(f_i\lt 0\)) forces \(\lambda_i=0\), and vice versa.
  • Assuming strong duality without checking a constraint qualification (Slater). Nonconvex or degenerate problems can have a positive gap.
  • Using KKT as sufficient for nonconvex problems - there it is only necessary.
Quant Practitioner Tips
  • The dual is always concave, so the dual problem is always convex - sometimes far easier than the primal.
  • Complementary slackness is a powerful solver: guess which constraints are active, set their \(\lambda_i\gt 0\), the rest to 0, and solve the reduced system.
  • Read multipliers as prices: \(\lambda_i^\star\) is the sensitivity of the optimum to constraint \(i\) - directly meaningful in risk budgeting.

Knowledge Check

Q1 Medium
Weak duality states that for \(\lambda\ge0\):
\(g(\lambda,\nu)\ge p^\star\)
\(g(\lambda,\nu)\le p^\star\)
\(g=p^\star\) always
\(d^\star\gt p^\star\)
Q2 Medium
Which condition guarantees strong duality for a convex problem?
The objective is bounded
Slater's condition (a strictly feasible point exists)
All constraints are equalities
The Hessian is diagonal
Q3 Medium
Complementary slackness says:
\(\lambda_i^\star=f_i(x^\star)\)
\(\lambda_i^\star f_i(x^\star)=0\)
\(\lambda_i^\star\gt 0\) always
\(f_i(x^\star)=0\) always

Practical Exercise

Solve \(\min\ x_1^2+x_2^2\) s.t. \(x_1+x_2\ge2\) using KKT. (a) Form the Lagrangian. (b) Apply stationarity and complementary slackness. (c) Give \(x^\star\) and \(\lambda^\star\).

▶ Show full solution

(a) Rewrite \(f_1(x)=2-x_1-x_2\le0\). \(L=x_1^2+x_2^2+\lambda(2-x_1-x_2)\), \(\lambda\ge0\).

(b) Stationarity: \(2x_1-\lambda=0,\ 2x_2-\lambda=0\Rightarrow x_1=x_2=\lambda/2\). If the constraint were inactive, \(\lambda=0\) gives \(x=0\), which violates \(x_1+x_2\ge2\). So it is active: \(x_1+x_2=2\).

(c) \(\lambda/2+\lambda/2=2\Rightarrow\lambda^\star=2\), \(x^\star=(1,1)\). Check \(\lambda^\star=2\ge0\) and complementary slackness holds (constraint tight). The shadow price 2 means relaxing the constraint to \(\ge1.9\) would lower the optimum by \(\approx0.2\).

After the reveal, answer for yourself: How did complementary slackness let you avoid checking both active/inactive branches blindly?

Lesson Summary

Lagrangian duality prices each constraint with a multiplier, giving a dual function \(g\) that is always concave and always lower-bounds the primal optimum (weak duality). For convex problems satisfying Slater's condition the gap closes (strong duality), and the KKT conditions - stationarity, primal/dual feasibility, complementary slackness - are necessary and sufficient. Multipliers are shadow prices: marginal sensitivities of the optimum to each constraint.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: List the four KKT conditions.
A: Stationarity (\(\nabla_x L=0\)), primal feasibility, dual feasibility (\(\lambda\ge0\)), and complementary slackness (\(\lambda_i f_i=0\)).
Q: What does Slater's condition guarantee and for what class?
A: For convex problems, existence of a strictly feasible point guarantees strong duality (zero duality gap) and attainment of the dual optimum.

Completion Checklist

Confidence / mastery rating
Personal notes
← 10.2Next: 10.4 →