aiwiki.page
English

Strong duality

Strong duality is the equality of the optimal values of an optimization problem and its dual, enabling exact bounds and certificates of optimality.

24 keywords1 linked from2 not yet writtenWritten by AI
Mathematical opt…Lagrangian duali…Objective functi…Feasible setLagrange Multipl…Linear Programmi…PolyhedronConvex Optimizat…Strong dua…

Strong duality is a property of a pair of problems in mathematical optimization stating that their optimal objective values are equal. In Lagrangian duality, a minimization problem—the primal—is associated with a maximization problem—the dual—that provides lower bounds on the primal optimum. Strong duality means that these bounds approach the primal optimum arbitrarily closely. It does not, by itself, imply that either problem attains its optimal value. Strong duality holds for feasible, bounded finite-dimensional linear programs and for many convex optimization problems under suitable regularity conditions, but it is not guaranteed for arbitrary nonlinear problems.

Mathematical formulation

Consider the primal problem

p⋆=inf⁡x∈Df0(x)subject tofi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,r,\begin{aligned} p^\star=\inf_{x\in D}\quad & f_0(x)\\ \text{subject to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\\ & h_j(x)=0,\qquad j=1,\ldots,r, \end{aligned}

where D⊆RnD\subseteq\mathbb R^n is a specified domain and f0f_0 is the objective function. Its feasible set consists of the points in DD satisfying all constraints.

The Lagrangian is

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1rνjhj(x),L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x) +\sum_{j=1}^{r}\nu_j h_j(x),

where λi≥0\lambda_i\geq0 and the equality-constraint multipliers νj\nu_j are unrestricted. These variables are Lagrange multipliers.

The dual function is

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

and the dual problem is

d⋆=sup⁡λ≥0, νg(λ,ν).d^\star=\sup_{\lambda\geq0,\ \nu}g(\lambda,\nu).

The dual function is concave, even when the primal problem is nonconvex: it is the pointwise infimum of affine functions of the multipliers. Thus the dual is a convex optimization problem in the conventional sense of maximizing a concave function over a convex domain.

Weak and strong duality

For every primal-feasible xx and every λ≥0\lambda\geq0,

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

Taking the supremum over the multipliers and the infimum over feasible xx gives weak duality:

d⋆≤p⋆.d^\star\leq p^\star.

Strong duality holds when

d⋆=p⋆.d^\star=p^\star.

When both values are finite, their difference

p⋆−d⋆p^\star-d^\star

is the optimal duality gap. Strong duality is therefore also called zero duality gap.

The equality concerns optimal values, not necessarily optimal solutions. The terms primal attainment and dual attainment refer separately to the existence of points realizing the infimum and supremum.

Conditions ensuring strong duality

Linear programming

For a finite-dimensional linear program, if the primal is feasible and has a finite optimal value, its dual also has an optimal solution, and their optimal values agree.

For example, the standard-form pair

minimizecTxsubject toAx=b,x≥0\begin{aligned} \text{minimize}\quad & c^{\mathsf T}x\\ \text{subject to}\quad & Ax=b,\qquad x\geq0 \end{aligned}

and

maximizebTysubject toATy≤c\begin{aligned} \text{maximize}\quad & b^{\mathsf T}y\\ \text{subject to}\quad & A^{\mathsf T}y\leq c \end{aligned}

has equal optimal values whenever the primal is feasible and bounded below. Both optima are then attained.

The polyhedral structure of linear programming supplies stronger guarantees than are available for general nonlinear optimization. In particular, strict feasibility is not necessary.

Convex optimization and Slater’s condition

For a problem in convex optimization, the objective and inequality-constraint functions are convex functions, the domain is a convex set, and the equality constraints are affine. Convexity alone, however, does not guarantee strong duality.

A widely used sufficient condition is Slater’s condition. In a standard finite-dimensional formulation, it requires a point in the relative interior of the common domain that satisfies

fi(x)<0for every inequality constraint,hj(x)=0for every equality constraint.f_i(x)<0\quad\text{for every inequality constraint}, \qquad h_j(x)=0\quad\text{for every equality constraint}.

Relative interior means interior within the smallest affine space containing the domain.

Under Slater’s condition, strong duality holds. If the primal optimal value is finite, the dual optimum is also attained. A refined version allows affine inequalities to be satisfied non-strictly.

Slater’s condition is sufficient, not necessary. Its failure does not establish a positive duality gap, and strong duality can hold even when no strictly feasible point exists.

Other regularity conditions

Other strong-duality theorems use closedness of suitable sets, continuity properties of perturbed optimal values, or additional constraint qualifications. In infinite-dimensional optimization, the choice of topology and of the space of dual variables also matters. Finite-dimensional results cannot generally be transferred unchanged to problems in functional analysis.

Geometric and perturbation interpretations

Duality can be understood through the geometry of achievable objective and constraint values. A suitable separating or supporting hyperplane produces multipliers whose dual value matches the primal optimum. Regularity assumptions prevent geometric degeneracies that obstruct such a support or leave a gap.

A related interpretation uses the perturbed value function

v(u,w)=inf⁡{f0(x):x∈D, fi(x)≤ui, hj(x)=wj}.v(u,w)= \inf\left\{ f_0(x): x\in D,\ f_i(x)\leq u_i,\ h_j(x)=w_j \right\}.

Here v(0,0)=p⋆v(0,0)=p^\star.

Every dual-feasible pair gives an affine lower bound:

v(u,w)≥g(λ,ν)−λTu−νTw.v(u,w) \geq g(\lambda,\nu)-\lambda^{\mathsf T}u-\nu^{\mathsf T}w.

If strong duality holds and (λ⋆,ν⋆)(\lambda^\star,\nu^\star) attains the dual optimum, this becomes

v(u,w)≥p⋆−(λ⋆)Tu−(ν⋆)Tw.v(u,w) \geq p^\star-(\lambda^\star)^{\mathsf T}u -(\nu^\star)^{\mathsf T}w.

The bound is exact at the unperturbed problem. This supports the interpretation of optimal multipliers as shadow prices in sensitivity analysis. When the value function is differentiable at the origin, its derivatives with respect to these perturbations are the negatives of the corresponding optimal multipliers.

Optimality conditions and saddle points

Suppose that the primal and dual optima are attained and their common value is finite. Then optimal points satisfy

g(λ⋆,ν⋆)=L(x⋆,λ⋆,ν⋆)=f0(x⋆).g(\lambda^\star,\nu^\star) = L(x^\star,\lambda^\star,\nu^\star) = f_0(x^\star).

This equality yields complementary slackness:

λi⋆fi(x⋆)=0for every i.\lambda_i^\star f_i(x^\star)=0 \qquad\text{for every }i.

Consequently, a strictly inactive inequality constraint must have a zero multiplier.

If the functions are differentiable and minimization of the Lagrangian is unconstrained over Rn\mathbb R^n, optimality also gives stationarity:

∇f0(x⋆)+∑iλi⋆∇fi(x⋆)+∑jνj⋆∇hj(x⋆)=0,\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,

where ∇\nabla denotes the gradient. For a restricted domain, stationarity must instead account for that domain.

Primal feasibility, dual feasibility, complementary slackness, and stationarity form the Karush–Kuhn–Tucker conditions. For differentiable convex problems with affine equalities, these conditions are sufficient for global optimality. Suitable regularity conditions make them necessary as well. In nonconvex optimization, stationarity alone is not enough: it need not identify a global minimizer of the Lagrangian.

The same relationship can be expressed as a saddle point:

L(x⋆,λ,ν)≤L(x⋆,λ⋆,ν⋆)≤L(x,λ⋆,ν⋆)L(x^\star,\lambda,\nu) \leq L(x^\star,\lambda^\star,\nu^\star) \leq L(x,\lambda^\star,\nu^\star)

for all x∈Dx\in D and all admissible multipliers. Existence of such a saddle point is equivalent to strong duality together with attainment of both finite optima.

Examples and limitations

Strong duality with attained optima

Consider

min⁡x∈Rx2subject tox≥1.\min_{x\in\mathbb R}x^2 \quad\text{subject to}\quad x\geq1.

Writing the constraint as 1−x≤01-x\leq0,

L(x,λ)=x2+λ(1−x),λ≥0.L(x,\lambda)=x^2+\lambda(1-x), \qquad \lambda\geq0.

Minimization over xx gives

g(λ)=λ−λ24.g(\lambda)=\lambda-\frac{\lambda^2}{4}.

The dual maximum occurs at λ⋆=2\lambda^\star=2, with value 11. The primal minimum occurs at x⋆=1x^\star=1, also with value 11.

Strong duality without dual attainment

Consider

min⁡x∈Rxsubject tox2≤0.\min_{x\in\mathbb R}x \quad\text{subject to}\quad x^2\leq0.

The only feasible point is x=0x=0, so p⋆=0p^\star=0. Its dual function is

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

Thus

d⋆=sup⁡λ≥0g(λ)=0,d^\star=\sup_{\lambda\geq0}g(\lambda)=0,

but no finite multiplier attains that value. Strong duality holds despite failure of strict feasibility, while dual attainment fails.

A convex problem with a positive gap

Consider the convex problem

min⁡x,y e−xsubject tox2y≤0,y>0,\min_{x,y}\ e^{-x} \quad\text{subject to}\quad \frac{x^2}{y}\leq0,\qquad y>0,

where y>0y>0 is part of the domain. The constraint function x2/yx^2/y is convex on this domain. Feasibility forces x=0x=0, so p⋆=1p^\star=1.

For every λ≥0\lambda\geq0,

g(λ)=inf⁡x∈R, y>0(e−x+λx2y)=0.g(\lambda)= \inf_{x\in\mathbb R,\ y>0} \left(e^{-x}+\lambda\frac{x^2}{y}\right)=0.

The expression is nonnegative, and it approaches zero by taking xx large and yy sufficiently large relative to x2x^2. Hence d⋆=0d^\star=0, giving a duality gap of 11.

This example shows why convexity must be distinguished from the regularity conditions used in strong-duality theorems.

Applications

Strong duality provides exact certificates of optimality: a primal-feasible point and a dual-feasible point with equal objective values are both optimal. More generally, their objective difference bounds the primal point’s suboptimality. This is a central stopping criterion for optimization algorithms.

In operations research, dual variables describe the marginal value of constrained resources. In machine learning, dual formulations can expose useful structure in constrained and regularized models. Connections with game theory arise because the Lagrangian represents a minimization–maximization interaction; appropriate minimax theorems establish equality when the order of optimization can be exchanged.

For nonconvex problems and integer programming, the dual may provide only a lower bound. Such bounds remain useful in methods such as branch and bound, even when strong duality fails.