Skip to content
nonconvexcard

Lagrangian Duality and the KKT Conditions

Weak and strong duality, Slater's condition, and the five KKT conditions — set up so that the SVM derivation is a direct application.

Advanced OptimizationAdvanced⏱ 3 hours13 min readdualitylagrangiankktslatercomplementary slackness
4 problems →
AssumesConvex Sets, Convex Functions, Smoothness and Strong Convexity

The primal problem and its Lagrangian

Consider

p⋆=min⁡x∈Rdf0(x)subject tofi(x)≤0 (i=1,…,m),hj(x)=0 (j=1,…,r).p^\star = \min_{x\in\R^d} f_0(x) \quad\text{subject to}\quad f_i(x)\le0\ (i=1,\dots,m), \quad h_j(x)=0\ (j=1,\dots,r).
DefinitionLagrangian and dual function

The Lagrangian is

L(x,α,ν)=f0(x)+∑i=1mαifi(x)+∑j=1rνjhj(x),\mathcal{L}(x,\alpha,\nu) = f_0(x) + \sum_{i=1}^m \alpha_i f_i(x) + \sum_{j=1}^r \nu_j h_j(x),

with α∈R≥0m\alpha \in \R^m_{\ge0} and ν∈Rr\nu\in\R^r. The dual function is

g(α,ν)=inf⁡xL(x,α,ν),g(\alpha,\nu) = \inf_{x}\mathcal{L}(x,\alpha,\nu),

and the dual problem is d⋆=max⁡α≥0,νg(α,ν)d^\star = \max_{\alpha\ge0,\nu} g(\alpha,\nu).

PropositionThe dual function is always concave

gg is concave on R≥0m×Rr\R^m_{\ge0}\times\R^r, regardless of any property of f0,fi,hjf_0, f_i, h_j. It may take the value −∞-\infty.

Key idea

This is remarkable and is the practical reason duality matters: the dual of an arbitrarily nasty problem is a concave maximisation, hence a convex problem. Sometimes the dual is tractable when the primal is not, and sometimes — as in the SVM — the dual is where the interesting structure (kernels, support vectors) becomes visible.

TheoremWeak duality

d⋆≤p⋆d^\star \le p^\star, with no assumptions on f0,fi,hjf_0,f_i,h_j.

TheoremStrong duality under Slater's condition

Suppose f0,…,fmf_0,\dots,f_m are convex, the hjh_j are affine, and there exists a strictly feasible point: some x~\tilde x in the relative interior of the domain with fi(x~)<0f_i(\tilde x)<0 for all ii with fif_i not affine, and hj(x~)=0h_j(\tilde x)=0. Then d⋆=p⋆d^\star = p^\star, and if p⋆p^\star is finite the dual optimum is attained.

Quoted from Boyd–Vandenberghe, where it is proved via a separating-hyperplane argument applied to the set {(u,v,s):∃x, fi(x)≤ui, hj(x)=vj, f0(x)≤s}\{(u,v,s) : \exists x,\ f_i(x)\le u_i,\ h_j(x)=v_j,\ f_0(x)\le s\}. Slater's condition is mild and is satisfied by every problem in this laboratory that uses duality — in particular by the soft-margin SVM, where any ξi\xi_i large enough is strictly feasible.

The KKT conditions

TheoremKarush–Kuhn–Tucker conditions

Suppose f0,fi,hjf_0,f_i,h_j are differentiable and strong duality holds with both optima attained, at x⋆x^\star and (α⋆,ν⋆)(\alpha^\star,\nu^\star). Then

(1) primal feasibility:fi(x⋆)≤0,hj(x⋆)=0;(2) dual feasibility:αi⋆≥0;(3) complementary slackness:αi⋆fi(x⋆)=0  ∀i;(4) stationarity:∇f0(x⋆)+∑iαi⋆∇fi(x⋆)+∑jνj⋆∇hj(x⋆)=0.\begin{aligned} &\text{(1) primal feasibility:} && f_i(x^\star)\le0,\quad h_j(x^\star)=0;\\ &\text{(2) dual feasibility:} && \alpha_i^\star\ge0;\\ &\text{(3) complementary slackness:} && \alpha_i^\star f_i(x^\star)=0 \ \ \forall i;\\ &\text{(4) stationarity:} && \nabla f_0(x^\star) + \sum_i\alpha_i^\star\nabla f_i(x^\star) + \sum_j\nu_j^\star\nabla h_j(x^\star)=0 . \end{aligned}

Conversely, if the problem is convex and (x,α,ν)(x,\alpha,\nu) satisfies (1)–(4), then xx is primal optimal, (α,ν)(\alpha,\nu) is dual optimal, and the duality gap is zero.

CorollaryComplementary slackness

At an optimum, for each ii,

αi⋆>0  ⟹  fi(x⋆)=0andfi(x⋆)<0  ⟹  αi⋆=0.\alpha_i^\star>0 \implies f_i(x^\star)=0 \qquad\text{and}\qquad f_i(x^\star)<0 \implies \alpha_i^\star=0 .

Key idea

Complementary slackness is the mathematical origin of sparsity in the dual. In the SVM the constraints are yi(w⊤xi+b)≥1y_i(w^\top x_i + b)\ge1, one per training point. Complementary slackness says αi>0\alpha_i > 0 only for points with yi(w⊤xi+b)=1y_i(w^\top x_i+b)=1 — the points exactly on the margin. Every other point has αi=0\alpha_i = 0 and drops out of the solution entirely. "Support vector" is not a heuristic notion; it is the name for a constraint with a non-zero multiplier.

Worked example: the dual of a quadratic program

Dual of min ½xᵀQx + cᵀx subject to Ax ≤ b, with Q ≻ 0

  1. L(x,α)=12x⊤Qx+c⊤x+α⊤(Ax−b).\mathcal{L}(x,\alpha) = \tfrac12x^\top Qx + c^\top x + \alpha^\top(Ax - b).

    Form the Lagrangian with multiplier α ≥ 0 for the inequality constraints.

  2. ∇xL=Qx+c+A⊤α=0⟹x⋆(α)=−Q−1(c+A⊤α).\nabla_x\mathcal{L} = Qx + c + A^\top\alpha = 0 \quad\Longrightarrow\quad x^\star(\alpha) = -Q^{-1}(c + A^\top\alpha).

    Q ≻ 0 makes the Lagrangian strictly convex in x, so the inner minimisation is solved by setting the gradient to zero.

  3. g(α)=−12(c+A⊤α)⊤Q−1(c+A⊤α)−b⊤α.g(\alpha) = -\tfrac12(c+A^\top\alpha)^\top Q^{-1}(c+A^\top\alpha) - b^\top\alpha .

    Substitute back. The quadratic evaluates to minus half the squared Q-inverse norm of the combined linear term.

  4. d⋆=max⁡α≥0 {−12α⊤AQ−1A⊤α−α⊤(AQ−1c+b)−12c⊤Q−1c}.d^\star = \max_{\alpha\ge0}\ \left\{-\tfrac12\alpha^\top AQ^{-1}A^\top\alpha - \alpha^\top(AQ^{-1}c + b) - \tfrac12 c^\top Q^{-1}c\right\}.

    The dual problem is a maximisation of a concave quadratic over the non-negative orthant — itself a quadratic program, but with the inequality constraints replaced by simple sign constraints.

  5. x⋆=−Q−1(c+A⊤α⋆)x^\star = -Q^{-1}(c + A^\top\alpha^\star).

    Slater's condition holds whenever some x satisfies Ax < b, so the gap is zero and the primal solution is recovered from the dual optimum through the stationarity map of step 2.

Note the structural change: the primal has mm general linear inequality constraints; the dual has only α≥0\alpha\ge0. The constraint complexity has moved into the quadratic form AQ−1A⊤AQ^{-1}A^\top. That trade is exactly what the SVM dual exploits, where AQ−1A⊤AQ^{-1}A^\top becomes the kernel matrix.

Problems

Weak duality holds without convexityProof · Beginner · 15 min Derive the dual of a quadratic programProof · Intermediate · 30 min Complementary slackness and active constraintsProof · Intermediate · 30 min A convex problem with a duality gapProof · Advanced · 30 min

References

  • BookStephen Boyd and Lieven Vandenberghe (2004). Convex OptimizationChapter 5 is the standard treatment; Slater's theorem is proved there and quoted here.
  • BookR. Tyrrell Rockafellar (1970). Convex AnalysisThe foundational reference for conjugate duality.
  • BookDimitri P. Bertsekas (2016). Nonlinear Programming

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

  • TheoremWeak dualityproof includedThe dual optimum never exceeds the primal optimum, with no convexity assumed.
  • PropositionThe dual function is always concaveproof includedThe dual is a pointwise infimum of affine functions, hence concave regardless of the primal problem.
  • TheoremStrong duality under Slater's conditionFor a convex problem with a strictly feasible point the duality gap is zero.
  • TheoremKarush–Kuhn–Tucker conditionsproof includedUnder strong duality the five KKT conditions are necessary, and for convex problems they are also sufficient.
  • CorollaryComplementary slacknessproof includedAt optimum, every inactive constraint has zero multiplier and every nonzero multiplier marks an active constraint.

Problems (4)

All problems

Papers that use this mathematics