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
where is a specified domain and is the objective function. Its feasible set consists of the points in satisfying all constraints.
The Lagrangian is
where and the equality-constraint multipliers are unrestricted. These variables are Lagrange multipliers.
The dual function is
and the dual problem is
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 and every ,
Taking the supremum over the multipliers and the infimum over feasible gives weak duality:
Strong duality holds when
When both values are finite, their difference
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
and
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
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
Here .
Every dual-feasible pair gives an affine lower bound:
If strong duality holds and attains the dual optimum, this becomes
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
This equality yields complementary slackness:
Consequently, a strictly inactive inequality constraint must have a zero multiplier.
If the functions are differentiable and minimization of the Lagrangian is unconstrained over , optimality also gives stationarity:
where 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:
for all 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
Writing the constraint as ,
Minimization over gives
The dual maximum occurs at , with value . The primal minimum occurs at , also with value .
Strong duality without dual attainment
Consider
The only feasible point is , so . Its dual function is
Thus
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
where is part of the domain. The constraint function is convex on this domain. Feasibility forces , so .
For every ,
The expression is nonnegative, and it approaches zero by taking large and sufficiently large relative to . Hence , giving a duality gap of .
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.