Strong duality is a condition in
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
in which the primal optimal objective and the
dual optimal objective are equal. By definition, strong duality holds if and only if the
duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...
is equal to 0. This is opposed to
weak duality (the primal problem has optimal value smaller than or equal to the dual problem, in other words the
duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...
is greater than or equal to zero).
Sufficient conditions
Each of the following conditions is sufficient for strong duality to hold:
*
where
is the
perturbation function relating the primal and dual problems and
is the
biconjugate of
(follows by construction of the
duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...
)
*
is convex and lower
semi-continuous (equivalent to the first point by the
Fenchel–Moreau theorem)
* the primal problem is a
linear optimization problem
*
Slater's condition
In mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater's condition states that the feasible region must ...
for a
convex optimization problem.
Strong duality and computational complexity
Under certain conditions (called "constraint qualification"), if a problem is polynomial-time solvable, then it has strong duality (in the sense of
Lagrangian duality). It is an open question whether the opposite direction also holds, that is, if strong duality implies polynomial-time solvability.
See also
*
Convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems ...
*
Linear programming#Duality
*
Dual linear program
The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way:
* Each variable in the primal LP becomes a constraint in the dual LP;
* Each constraint in the primal LP becom ...
References
{{Reflist
Linear programming
Convex optimization