Strong duality is a condition in
mathematical optimization in which the primal optimal objective and the
dual optimal objective are equal. This is as opposed to
weak duality In applied mathematics, weak duality is a concept in optimization which states that the duality gap is always greater than or equal to 0. That means the solution to the dual (minimization) problem is ''always'' greater than or equal to the solution ...
(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).
Characterizations
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.
Sufficient conditions
Sufficient conditions comprise:
*
where
is the
perturbation function In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form ...
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
In convex analysis, the Fenchel–Moreau theorem (named after Werner Fenchel and Jean Jacques Moreau) or Fenchel biconjugation theorem (or just biconjugation theorem) is a theorem which gives necessary and sufficient conditions for a function to b ...
)
* 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
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 pr ...
References
{{Reflist
Linear programming
Convex optimization