Full search page →

OPT 04 · Duality, KKT Conditions and Certificates

OptimizationAdvanced18 minUpdated Oct 4, 2026

Needs: OPT 03 · Linear, Quadratic, Conic and Geometric Programs

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Change a candidate point and multiplier. A small gap is meaningful only with feasibility.

What you’ll learn

  • Derive a lower bound on a constrained minimization problem from a Lagrangian.
  • Distinguish dual feasibility, weak duality, strong duality and attainment.
  • State the KKT conditions and identify when they certify global optimality.
  • Interpret complementary slackness and sensitivity with the correct multiplier signs.
  • Construct a simple infeasibility certificate and extend dual order to cones.
  • Report residuals and gaps without claiming more than numerical evidence supports.

The big picture

Finding a good feasible answer gives an upper bound on the best possible cost. How do we know that a much better answer is not hidden elsewhere? A dual problem produces lower bounds. When an upper and lower bound meet, they certify the optimum.

Boyd and Vandenberghe’s Chapter 5 [1] connects this idea to geometry, supporting planes, multipliers and numerical algorithms. Duality is useful even when we already know how to solve the primal problem: it verifies an answer, describes the value of limited resources and reveals alternative computational structure.

The guarantee must respect signs and assumptions. A value computed from arbitrary multipliers may not be a lower bound. A small stationarity residual alone is not a complete certificate. Strong duality is not automatic for every convex formulation.

This chapter develops the derivations with explicit domains and uses small examples whose exact answers can be checked. The resulting reasoning extends to large problems, but the implementation details and tolerances remain part of the numerical assessment.

From constraints to the Lagrangian

Plain version. Attach a price to every inequality and equality. Then minimize the priced objective without explicitly enforcing those constraints.

Consider

min⁡x∈Df0(x)subject tofi(x)≤0,hj(x)=0.\min_{x\in D} f_0(x) \quad\text{subject to}\quad f_i(x)\leq0,\quad h_j(x)=0.

xx is the decision vector, DD is the common domain retained during minimization, f0f_0 is the objective, fif_i are inequalities and hjh_j are equalities.

The Lagrangian is

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x).L(x,\lambda,\nu)= f_0(x)+\sum_{i=1}^m\lambda_if_i(x) +\sum_{j=1}^p\nu_jh_j(x).

λi\lambda_i are inequality multipliers and νj\nu_j equality multipliers. For the convention fi≤0f_i\leq0, require λi≥0\lambda_i\geq0. Equality multipliers are unrestricted because equality residuals vanish at feasible points regardless of sign.

At a feasible point, the inequality contribution is nonpositive and the equality contribution zero. Thus L(x,λ,ν)≤f0(x)L(x,\lambda,\nu)\leq f_0(x) for nonnegative λ\lambda.

Calling these multipliers “penalties” can be misleading. This Lagrangian is not simply a large positive cost added to violations during an unconstrained minimization. Its role is to create a lower-bound family, and the sign condition is selected for that purpose.

Define the dual function

g(λ,ν)=inf⁡x∈DL(x,λ,ν).g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu).

gg is the Lagrange dual function; its input is the multiplier pair. It takes the infimum over every point in DD, not just feasible points.

For any feasible xx and nonnegative λ\lambda,

g(λ,ν)≤L(x,λ,ν)≤f0(x).g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x).

The first inequality follows from taking an infimum. The second follows from primal feasibility and multiplier signs. Therefore gg is a lower bound on the primal optimal value.

If the infimum is negative infinity, the bound is valid but uninformative. Dual feasibility includes multipliers with an appropriate finite dual value when we want a useful certificate.

Why the dual problem is concave

Plain version. The lower bound changes with prices. We choose the prices giving the strongest bound, and that maximization has a concave objective.

For each fixed xx, LL is affine in the multipliers. The pointwise infimum of affine functions is concave. Therefore gg is concave even if the original problem is not convex.

The dual problem is

maximize⁡λ,νg(λ,ν)subject toλ≥0.\begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad &g(\lambda,\nu)\\ \text{subject to}\quad &\lambda\geq0. \end{aligned}

Let its optimal value be d∗d^*. Weak duality states d∗≤p∗d^*\leq p^*, where p∗p^* is the primal optimal value. This result does not require convexity, only the lower-bound construction with the correct signs.

A concave maximization is a convex optimization problem in the usual sense. However, evaluating the dual function can itself be difficult if it requires a hard nonconvex minimization. “The dual is concave” does not automatically provide a practical oracle.

The dual also need not have the same dimension as the primal. There is one variable for each explicitly dualized constraint. Retaining some restrictions in DD rather than attaching multipliers changes the written dual representation, while the lower-bound logic remains consistent.

The concavity proof in three lines

The dual is concave because the bound at mixed prices is at least the same mixture of the individual bounds. Let z=(λ,ν)z=(\lambda,\nu) collect the multipliers, and take two allowed choices z1,z2z_1,z_2 and θ∈[0,1]\theta\in[0,1]. Affinity of the Lagrangian in prices gives

g(θz1+(1−θ)z2)=inf⁡x∈D[θL(x,z1)+(1−θ)L(x,z2)]≥θinf⁡x∈DL(x,z1)+(1−θ)inf⁡x∈DL(x,z2)=θg(z1)+(1−θ)g(z2).\begin{aligned} g(\theta z_1+(1-\theta)z_2) &=\inf_{x\in D}[\theta L(x,z_1)+(1-\theta)L(x,z_2)]\\ &\geq\theta\inf_{x\in D}L(x,z_1) +(1-\theta)\inf_{x\in D}L(x,z_2)\\ &=\theta g(z_1)+(1-\theta)g(z_2). \end{aligned}

Here DD is the retained primal domain and gg the dual function; consider finite dual values for this comparison. Each summand at a shared xx is at least its own infimum, which explains the middle inequality. Nothing in that step assumes the primal objective is convex [1].

This distinction matters computationally. For a nonconvex primal, merely finding a local minimum of LL does not evaluate its infimum. That local value can exceed g(z)g(z) and cease to be a valid lower bound. Dual concavity concerns the exact dual function, not any approximate routine called a dual evaluator.

A complete one-dimensional derivation

Plain version. A small example shows how prices, the unconstrained minimizer and the bound fit together.

Minimize 12(x−2)2\frac12(x-2)^2 subject to x≤1x\leq1. Here xx is scalar. The constrained optimizer is x∗=1x^*=1, with cost p∗=1/2p^*=1/2.

Using multiplier λ≥0\lambda\geq0,

L(x,λ)=12(x−2)2+λ(x−1).L(x,\lambda)=\frac12(x-2)^2+\lambda(x-1).

The unconstrained Lagrangian minimizer satisfies x−2+λ=0x-2+\lambda=0, so xλ=2−λx_\lambda=2-\lambda. Substitution yields

g(λ)=λ−12λ2.g(\lambda)=\lambda-\frac12\lambda^2.

xλx_\lambda depends on the selected multiplier and need not be primal feasible. The dual is a concave parabola, maximizing at λ∗=1\lambda^*=1 with g(λ∗)=1/2g(\lambda^*)=1/2. Upper and lower bounds meet.

The optimum multiplier balances the objective’s desire to increase xx against the active upper-bound constraint. If λ\lambda is too small, the Lagrangian minimizer lies outside the allowed region. If it is too large, the bound becomes weaker despite the larger multiplier.

The scalar primal objective on its allowed interval and the concave dual bound touching the optimal value.
Figure 1 — Original analytical derivation for minimizing (x − 2)² / 2 under x ≤ 1. The feasible primal optimizer and the best dual bound both have value 1/2.

Code: verify the gap and all KKT components

This standalone calculation checks primal feasibility, multiplier sign, stationarity, complementary slackness and equality of the two values.

Code · Python · 14 lines
import numpy as np

x, multiplier = 1.0, 1.0
objective = 0.5 * (x - 2)**2
dual_value = multiplier - 0.5 * multiplier**2
constraint = x - 1
stationarity = x - 2 + multiplier
complementarity = multiplier * constraint
assert constraint <= 0 and multiplier >= 0
assert abs(stationarity) < 1e-12
assert abs(complementarity) < 1e-12
assert np.isclose(objective, dual_value)
print("primal value:", objective, "dual value:", dual_value)
print("stationarity:", stationarity, "complementarity:", complementarity)

Strong duality and constraint qualifications

Plain version. Weak duality always gives the ordering. Strong duality says the best lower bound is exact, which needs additional conditions.

Strong duality means d∗=p∗d^*=p^*. It is a statement about optimal values, not automatically about whether optimizers exist. A problem can have a value approached by a sequence without attaining it.

For a convex primal with affine equalities, a standard sufficient condition is Slater’s condition [1, Section 5.2]:

∃x∈relint⁡D:fi(x)<0 for all i,Ax=b.\exists x\in\operatorname{relint}D: f_i(x)<0\ \text{for all }i,\qquad Ax=b.

DD is the common function domain, relint⁡D\operatorname{relint}D its relative interior, and A,bA,b define the affine equality constraints. This says there is a point strictly satisfying inequalities while remaining in the appropriate interior and satisfying equalities.

Under these assumptions, strong duality holds. With a finite optimal value, the dual optimum is also attained. The primal attainment question can still require separate existence reasoning.

There are refined conditions for affine inequalities, so requiring all of them strictly can be stronger than necessary. A failure to find a Slater point does not by itself disprove strong duality. It means this sufficient argument has not been established.

Convexity alone is not enough in every formulation. Domains can be degenerate and constraint qualifications can fail. Rather than saying “convex problems always have zero gap,” state the condition being used or verify a valid matching certificate directly.

Domain restrictions are part of duality

If an objective contains a logarithm or inverse, its domain remains in the Lagrangian minimization. Treating it as a function on all real inputs silently changes the problem.

Alternatively, an extended-value function can encode a domain by assigning positive infinity outside it. This is mathematically convenient, but numerical code should not rely on accidental invalid floating-point values as a modeling convention.

In a conic formulation, domain and cone restrictions can be dualized or retained according to a consistent representation. The choice affects the dual expression and sign conventions. Derive the bound from the stated primal rather than copying a formula with incompatible signs.

Zero gap can coexist with no optimal multiplier

A failed constraint qualification does not force a positive duality gap, but it can remove multiplier attainment. Consider minimizing xx subject to x2≤0x^2\leq0, with scalar x∈Rx\in\mathbb R. The only feasible point is zero, so p∗=0p^*=0. There is no strictly feasible point.

The Lagrangian is L(x,λ)=x+λx2L(x,\lambda)=x+\lambda x^2. Minimizing over xx gives

g(λ)={−1/(4λ),λ>0,−∞,λ=0.g(\lambda)= \begin{cases} -1/(4\lambda),&\lambda>0,\\ -\infty,&\lambda=0. \end{cases}

Here λ≥0\lambda\geq0 prices the quadratic restriction and gg is its dual bound. For positive λ\lambda, the minimizing point is −1/(2λ)-1/(2\lambda). As λ\lambda increases without bound, g(λ)g(\lambda) approaches zero. Thus d∗=p∗=0d^*=p^*=0, yet no finite multiplier attains the dual optimum.

At the primal solution, stationarity would require 1+2λx=01+2\lambda x=0, which becomes 1=01=0. No KKT multiplier exists for this representation. Replacing the equivalent restriction by the equality x=0x=0 gives a multiplier ν=−1\nu=-1. The feasible decision is unchanged, but the regularity and multiplier description improve. This is why OPT 01’s hidden equalities and OPT 07’s initialization deserve attention [1].

KKT optimality conditions

Plain version. KKT combines allowed primal choices, allowed prices, balanced forces and the rule that slack constraints carry no positive price.

For differentiable convex f0,fif_0,f_i and affine equality Ax=bAx=b, the conditions are

fi(x)≤0,Ax=b,λi≥0,λifi(x)=0,∇f0(x)+∑iλi∇fi(x)+A⊤ν=0.\begin{aligned} &f_i(x)\leq0,\qquad Ax=b,\\ &\lambda_i\geq0,\\ &\lambda_if_i(x)=0,\\ &\nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x)+A^\top\nu=0. \end{aligned}

xx is a primal candidate, λ\lambda are inequality multipliers, ν\nu are equality multipliers, and the final row is stationarity of the Lagrangian. These are the Karush–Kuhn–Tucker conditions.

For this convex differentiable problem, satisfying all conditions is sufficient for primal and dual optimality. Nonnegative multipliers make the Lagrangian convex in xx; stationarity makes xx its global minimizer; feasibility and complementary slackness make the Lagrangian value equal the objective.

Under a suitable constraint qualification such as Slater’s condition, optimal points also admit multipliers satisfying KKT. This supplies necessity as well as sufficiency. Keep the two logical directions distinct.

For nonconvex problems, a stationary Lagrangian can be a local maximum or saddle in xx. KKT may be necessary under regularity but does not generally certify a global optimum. A concave quadratic at its interior stationary point is a simple counterexample.

Complementary slackness is one-way information

If fi(x)<0f_i(x)<0, complementary slackness forces λi=0\lambda_i=0. If λi>0\lambda_i>0, the constraint is active: fi(x)=0f_i(x)=0.

An active constraint can nevertheless have zero multiplier. Degeneracy or redundant constraints can make prices nonunique. Therefore “active” and “positive price” are not interchangeable labels.

At a smooth constrained optimum, the negative objective gradient lies in the combination of active constraint normals and equality normals with appropriate signs. This gives a geometric explanation of stationarity: feasible descent directions cannot reduce the objective.

Numerical near-activity is tolerance-dependent. A constraint with a tiny slack and tiny multiplier may be difficult to classify discretely. Report actual values where the distinction matters instead of forcing a confident active/inactive label.

Equality-constrained quadratics

Plain version. For a quadratic objective and linear equalities, the KKT equations form one linear system. This reveals the algebra used by later constrained algorithms.

For objective 12x⊤Qx+c⊤x\frac12x^\top Qx+c^\top x under Ax=bAx=b,

[QA⊤A0][xν]=[−cb].\begin{bmatrix}Q&A^\top\\A&0\end{bmatrix} \begin{bmatrix}x\\\nu\end{bmatrix} =\begin{bmatrix}-c\\b\end{bmatrix}.

QQ is symmetric positive semidefinite, cc is the objective coefficient vector, AA the equality matrix, bb its target, and ν\nu the equality multiplier.

The block matrix is generally indefinite even though the optimization problem is convex. A solver requiring a positive-definite matrix cannot be used blindly on this full KKT system.

If QQ is positive definite and AA has independent rows, the system is nonsingular. More general cases require considering curvature on the equality nullspace and redundant constraints. A pseudoinverse may produce one solution but should not hide the underlying rank issue.

The equality multiplier balances the gradient in directions normal to the feasible affine set. Its sign is unconstrained. Removing a constraint changes both the feasible set and the meaning of its multiplier.

Deriving an LP dual carefully

Plain version. A dual formula is not universal notation. Its signs follow from the exact primal convention.

Take the LP min⁡c⊤x\min c^\top x subject to Ax=b, x≥0Ax=b,\ x\geq0. Retain nonnegativity in the domain. The Lagrangian is c⊤x+ν⊤(Ax−b)c^\top x+\nu^\top(Ax-b).

Taking the infimum over nonnegative xx is finite exactly when c+A⊤ν≥0c+A^\top\nu\geq0. If any coefficient is negative, that coordinate can grow without bound and send the infimum to negative infinity.

Set y=−νy=-\nu. The dual becomes

max⁡yb⊤ysubject toA⊤y≤c.\max_y b^\top y\quad\text{subject to}\quad A^\top y\leq c.

yy is an unrestricted equality-price vector. For any feasible pair,

c⊤x−b⊤y=x⊤(c−A⊤y)≥0.c^\top x-b^\top y=x^\top(c-A^\top y)\geq0.

The gap is the inner product of nonnegative primal coordinates and nonnegative dual slack. This is weak duality in a particularly transparent form.

Using a primal maximization or reversed inequalities changes the dual signs. Rather than memorizing separate tables, deriving the Lagrangian and checking the bound can prevent mistakes.

A fitting dual built from the norm conjugate

Duality can turn a parameter penalty into a residual restriction. Consider sparse linear fitting with objective 12∥Ax−b∥22+λ∥x∥1\frac12\|Ax-b\|_2^2+\lambda\|x\|_1, where A,bA,b are fixed and λ>0\lambda>0. Introduce residual variable r=Ax−br=Ax-b and an unrestricted equality multiplier yy:

L(x,r,y)=12∥r∥22+λ∥x∥1+y⊤(Ax−b−r).L(x,r,y)=\frac12\|r\|_2^2+\lambda\|x\|_1 +y^\top(Ax-b-r).

Here xx is the parameter vector and yy has one coordinate per observation. Minimizing in rr gives r=yr=y and value −∥y∥22/2-\|y\|_2^2/2 for the residual terms. Minimizing in xx is finite exactly when ∥A⊤y∥∞≤λ\|A^\top y\|_\infty\leq\lambda, by the norm-conjugate calculation in OPT 02. The dual is therefore

maximize⁡y−12∥y∥22−b⊤ysubject to∥A⊤y∥∞≤λ.\operatorname{maximize}_y\quad-\frac12\|y\|_2^2-b^\top y \qquad\text{subject to}\quad\|A^\top y\|_\infty\leq\lambda.

Here yy is the dual variable; the norm restriction is dual feasibility. At an optimum it coincides with the fitted residual, while its correlations with the design columns must stay within the penalty threshold. This links the lower-bound construction to the geometry of sparse fitting [1, Chapters 5–6].

For synthetic A=IA=I, b=(2,−0.3,0.1)b=(2,-0.3,0.1) and λ=0.4\lambda=0.4, the primal solution is x=(1.6,0,0)x=(1.6,0,0) and dual candidate y=x−b=(−0.4,0.3,−0.1)y=x-b=(-0.4,0.3,-0.1). Both are feasible for their respective problems and both objective values equal 0.770.77. Matching values certify the fit; observing zero coordinates alone would not.

Sensitivity and the value of a constraint

Plain version. A multiplier measures how the best cost responds to changing a constraint, under specified regularity. Its units depend on the constraint’s units.

Perturb inequalities to fi(x)≤uif_i(x)\leq u_i and equalities to Ax−b=vAx-b=v. Let the best cost be p∗(u,v)p^*(u,v). If strong duality holds at zero perturbation and optimal multipliers exist,

p∗(u,v)≥p∗(0,0)−λ∗⊤u−ν∗⊤v.p^*(u,v)\geq p^*(0,0)-\lambda^{*\top}u-\nu^{*\top}v.

uu and vv are right-side perturbations; λ∗,ν∗\lambda^*,\nu^* are optimal unperturbed multipliers. Positive uiu_i relaxes an inequality under the chosen convention.

The inequality gives a global affine lower bound on the perturbed value. If the value function is differentiable at the original problem, its derivatives are −λ∗-\lambda^* and −ν∗-\nu^*.

Without differentiability, multipliers can describe supporting slopes rather than one unique derivative. A large multiplier signals sensitivity in that local modeling direction, not a universal physical importance score.

A scalar example with a changing bound

Minimize 12(x−2)2\frac12(x-2)^2 under x≤bx\leq b. The best point is min⁡(2,b)\min(2,b) and the value is

p∗(b)=12max⁡(2−b,0)2,λ∗(b)=max⁡(2−b,0).p^*(b)=\frac12\max(2-b,0)^2,\qquad \lambda^*(b)=\max(2-b,0).

bb is the allowed upper bound. Where differentiable, dp∗/db=−λ∗(b)dp^*/db=-\lambda^*(b). Once the bound exceeds the unconstrained target, relaxing it further does not help and the multiplier is zero.

Scaling the constraint changes the multiplier reciprocally. Multiplying x−b≤0x-b\leq0 by a positive factor preserves feasible points but rescales its associated price. Compare sensitivity only after accounting for units and normalization.

The optimal value as an upper bound changes, and its corresponding nonnegative multiplier.
Figure 2 — Original analytical sensitivity example. Relaxing the bound reduces cost while it is binding; after the unconstrained target is allowed, the value and multiplier are zero.

Code: a finite-difference sensitivity check

Code · Python · 12 lines
import numpy as np

value = lambda b: 0.5 * max(2 - b, 0)**2
b, eps = 1.2, 1e-5
multiplier = max(2 - b, 0)
derivative = (value(b + eps) - value(b - eps)) / (2 * eps)
assert np.isclose(derivative, -multiplier, atol=1e-8)
test_bounds = np.linspace(-1, 4, 50)
lower_bound = value(b) - multiplier * (test_bounds - b)
assert np.all([value(t) for t in test_bounds] >= lower_bound - 1e-12)
print("finite-difference derivative:", derivative)
print("negative multiplier:", -multiplier)

Deriving sensitivity from the same lower bound

The sensitivity inequality needs no new principle. Use the original optimal multipliers on the perturbed Lagrangian. For any point feasible under fi(x)≤uif_i(x)\leq u_i and hj(x)=vjh_j(x)=v_j,

f0(x)≥g(λ∗,ν∗)−λ∗⊤u−ν∗⊤v.f_0(x)\geq g(\lambda^*,\nu^*) -{\lambda^*}^\top u-{\nu^*}^\top v.

Here u,vu,v are the perturbation vectors and the starred multipliers are optimal for the unperturbed problem. Taking the infimum over perturbed feasible points and using strong duality at the original problem produces the previously stated value-function bound. The minus sign follows from subtracting the perturbed right-hand sides inside the Lagrangian.

For the scalar bound example at b=1b=1, the value is 1/21/2 and λ∗=1\lambda^*=1. Increasing the bound by δ\delta with 0<δ<10\lt \delta\lt 1 gives actual value (1−δ)2/2(1-\delta)^2/2. Its decrease is δ−δ2/2\delta-\delta^2/2, while the multiplier predicts first-order decrease δ\delta. The lower-bound prediction 1/2−δ1/2-\delta stays below the actual value, with difference δ2/2\delta^2/2.

If the restriction is instead written 10(x−b)≤010(x-b)\leq0, its multiplier is 1/101/10. The derivative of this restriction with respect to bb is −10-10, so its product with the multiplier still predicts slope −1-1. Prices depend on representation; the predicted change in the original cost is consistent [1, Section 5.6].

Infeasibility certificates

Plain version. A valid weighted combination of constraints can prove that no choice satisfies them. That is stronger evidence than an algorithm failing to find a point.

For inequalities Gx≤hGx\leq h, suppose a vector yy satisfies

y≥0,G⊤y=0,h⊤y<0.y\geq0,\qquad G^\top y=0,\qquad h^\top y<0.

G,hG,h define the inequality system and yy is a nonnegative certificate vector. If a feasible xx existed, multiplying and summing would give 0=y⊤Gx≤y⊤h<00=y^\top Gx\leq y^\top h<0, a contradiction.

This is the geometry behind a theorem of alternatives such as the forms discussed in [1, Section 5.8]. It distinguishes a mathematical certificate from an unsuccessful search.

In floating point, the equalities and strict sign must be assessed relative to scale. A nearly zero transpose residual and a tiny negative certificate value may be inconclusive under accumulated errors. Numerical certification requires a suitable tolerance analysis.

Code: incompatible scalar inequalities

The constraints are x≤0x\leq0 and x≥1x\geq1. Their nonnegative sum proves impossibility.

Code · Python · 10 lines
import numpy as np

G = np.array([[1.], [-1.]])
h = np.array([0., -1.])
certificate = np.array([1., 1.])
assert np.all(certificate >= 0)
assert np.allclose(G.T @ certificate, 0)
assert h @ certificate < 0
print("transpose residual:", G.T @ certificate)
print("certificate contradiction:", h @ certificate)

Cones, saddle points and numerical gaps

Plain version. The lower-bound argument extends to cone inequalities by choosing prices from the matching dual cone. A primal–dual solution can also be viewed as a saddle point.

For a cone KK, its dual cone is

K∗={y:y⊤z≥0 for every z∈K}.K^*=\{y:y^\top z\geq0\ \text{for every }z\in K\}.

zz ranges over the original cone and yy is a price vector. When a constraint is expressed as belonging to KK, choose signs so the dual-cone inner product supplies the intended lower bound. Orthants, second-order cones and positive-semidefinite cones have familiar self-dual structures under their usual inner products.

For matrix variables, the inner product is trace: ⟨X,Y⟩=tr⁡(XY)\langle X,Y\rangle=\operatorname{tr}(XY) for symmetric matrices. Complementary slackness is then a trace condition, not entrywise multiplication.

Under the appropriate primal–dual assumptions, a saddle point satisfies

L(x∗,λ,ν)≤L(x∗,λ∗,ν∗)≤L(x,λ∗,ν∗).L(x^*,\lambda,\nu)\leq L(x^*,\lambda^*,\nu^*) \leq L(x,\lambda^*,\nu^*).

x∗x^* and (λ∗,ν∗)(\lambda^*,\nu^*) are optimal primal and dual points; xx ranges over the domain and λ≥0\lambda\geq0. The first side maximizes prices at the feasible point; the second minimizes decisions at the optimal prices.

In practice, an objective difference is a certified gap only when both points are appropriately feasible and the dual value is correctly evaluated. Approximate feasibility can require corrected bounds. A relative gap should use a documented denominator that remains meaningful near zero or with negative objective values.

A complete LP certificate and an invalid near-solution

Consider minimizing x1+3x2x_1+3x_2 subject to x1+x2=1x_1+x_2=1 and x≥0x\geq0. The primal point (1,0)(1,0) has cost one. In the LP dual convention derived above, the scalar dual variable y=1y=1 is feasible because (y,y)≤(1,3)(y,y)\leq(1,3), and its value is one. These matching bounds prove optimality without enumerating every feasible point.

The dual slack is (0,2)(0,2). Its inner product with the primal point is zero, making complementary slackness explicit. The second coordinate is expensive relative to the equality price and receives zero allocation. This interpretation follows from the coefficients and the stated equality; it is not a general feature-importance conclusion.

Now take the approximate point (1.01,−0.01)(1.01,-0.01). It satisfies the equality exactly and has an apparently better objective, 0.98. It violates nonnegativity. Comparing that objective with the dual value produces a negative difference, but does not refute weak duality: the candidate is outside the feasible set.

A routine that displays only equality residual and objective could therefore report a misleading result. Check every bound and cone restriction, including those encoded through a solver’s variable-bound argument rather than an explicit matrix row.

Clipping the negative coordinate gives (1.01,0)(1.01,0), which then violates the equality. A subsequent normalization gives (1,0)(1,0) in this particular example. Neither clipping nor normalization is a universally valid repair procedure for coupled constraints.

Approximate residuals need corrected reasoning

For an approximately feasible LP pair, the algebraic objective difference is

c⊤x−b⊤y=x⊤s+y⊤r,s=c−A⊤y,r=Ax−b.c^\top x-b^\top y=x^\top s+y^\top r,\qquad s=c-A^\top y,\quad r=Ax-b.

x,yx,y are candidate primal and dual vectors, ss the dual slack and rr the primal equality residual. The identity is exact algebra; a nonnegative certified gap additionally needs the required feasibility properties.

If x≥0x\geq0 and s≥0s\geq0 but r≠0r\ne0, the residual term can have either sign. A small residual multiplied by a large price can matter. This is why an absolute equality tolerance by itself is not a universal objective-accuracy guarantee.

If dual slack is only bounded below by −ε-\varepsilon componentwise and x≥0x\geq0, then x⊤s≥−ε∥x∥1x^\top s\geq-\varepsilon\|x\|_1. Here ε≥0\varepsilon\geq0 measures the worst negative slack. Large primal magnitude can amplify a tiny dual violation.

This inequality does not turn the approximate dual objective into a lower bound for every feasible primal point unless a valid bound on those points is also available. An unbounded feasible set makes that correction especially delicate. Avoid describing an arbitrary approximate multiplier as an exact global certificate.

Report primal residuals, negative-slack magnitudes, multiplier norms and objective differences together. If a rigorous certificate is required, use a valid repair, verified error bound or higher-precision check appropriate to the problem structure.

Modern view

Plain version. Modern large-scale methods use primal–dual structure directly, while applications increasingly differentiate through constrained solutions. Both rely on the same certificate and regularity ideas.

Applegate and colleagues’ PDLP report [2], first posted in 2025 and revised in 2026, develops large-scale LP computation with practical primal–dual steps and feasibility polishing. Its relevance here is that a useful system monitors feasibility as well as cost improvement; a low objective error with unusable constraint violations is a different outcome.

Pokutta’s 2024 survey [3] explains primal and dual convergence for Frank–Wolfe methods. A linear minimization over the feasible set gives a first-order gap from the supporting-plane inequality. This is related to a lower-bound certificate, while its assumptions and computation differ from a generic Lagrange multiplier dual.

Agrawal and colleagues’ differentiable convex optimization layers [4] connect structured formulations with differentiation through solutions. The original paper is from 2019; it is included as a foundation for current optimization-layer work, not mislabeled as a new 2026 result. Differentiability and conditioning can fail near degeneracy or active-set changes, so a valid convex solution does not automatically imply a well-behaved gradient.

Current questions include obtaining reliable certificates at very large scale, interpreting uncertainty when constraints are learned, differentiating through nonunique solutions and balancing precision against application latency. Keep optimization accuracy, model validity and learning generalization as separate evaluations.

Key takeaways

  • Feasible primal points provide upper bounds; feasible dual points provide lower bounds.
  • Multiplier signs follow the exact inequality convention.
  • The dual function is concave even when the primal is nonconvex.
  • Strong duality needs suitable conditions or a directly verified matching certificate.
  • KKT is sufficient for convex differentiable problems and needs regularity for necessity.
  • Complementary slackness and sensitivity have precise one-way and sign rules.
  • Numerical residuals and gaps must be interpreted with scale and feasibility.

Exercises

  1. Derive the dual of minimizing 12(x−a)2\frac12(x-a)^2 under x≤bx\leq b, treating a,ba,b as fixed data.
Hint

Minimize the Lagrangian over the scalar variable before maximizing its multiplier.

  1. Give an active inequality with zero multiplier at an optimum.
Hint

A redundant bound at an unconstrained minimizer works.

  1. Derive the LP dual using nonnegative variables retained in the domain.
Hint

The linear coefficient must be nonnegative for a finite infimum.

  1. Explain why KKT stationarity at the origin does not certify minimizing −x2-x^2 on [−1,1][-1,1].
Hint

The origin is a maximum of the objective.

  1. Construct a nonnegative weighted contradiction proving a pair of scalar inequalities infeasible.
Hint

Add an upper bound below a required lower bound.

  1. Rescale an inequality by ten. Derive the corresponding multiplier rescaling and explain why primal sensitivity stays consistent.
Hint

Preserve the Lagrangian product.

References

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Reading: Chapter 5, including duality, KKT, perturbation, alternatives and generalized inequalities. Official book, free PDF.
  2. David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue and Warren Schudy, “PDLP: A Practical First-Order Method for Large-Scale Linear Programming,” arXiv preprint, 2025, revised 2026. Verified paper.
  3. Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024. Open-access survey.
  4. Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond and J. Zico Kolter, “Differentiable Convex Optimization Layers,” NeurIPS, 2019. Official publication page.

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next OPT 05 · Approximation, Statistical Estimation and Experiment Design · 19 min