Strong duality is a condition in mathematical optimization 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 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 is greater than or equal to zero).
YouTube Encyclopedic
-
1/3Views:10 23159 12830 999
-
Lecture 15 10/18 Linear Programming Duality
-
Lecture 8 | Convex Optimization I (Stanford)
-
LP Duality - Duality Theorem of Linear Programming (General Case)
Transcription
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)
- 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 for a convex optimization problem.[1][2]
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.[3]
See also
References
- ^ Borwein, Jonathan; Lewis, Adrian (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples (2 ed.). Springer. ISBN 978-0-387-29570-1.
- ^ Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 3, 2011.
- ^ Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv:1012.5568 [math.OC].
This page was last edited on 18 September 2023, at 07:33