Duality gap explained

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 always greater than or equal to 0 (for minimization problems). The duality gap is zero if and only if strong duality holds. Otherwise the gap is strictly positive and weak duality holds.^[1]

In general given two dual pairs separated locally convex spaces

\left(X,X ^{*\right)} and \left(Y,Y ^{*\right)} . Then given the function f: X \to R \cup \{ +inf ty\} , we can define the primal problem byinf _{x} f(x). If there are constraint conditions, these can be built into the function f by letting f = f + I _{constraints} where I is the indicator function. Then let F: X x Y \to R \cup \{ +inf ty\} be a perturbation function such that F(x, 0 ) = f(x) . The duality gap is the difference given byinf _{x} [F(x, 0 )] - \sup _{y ^{*} \in Y ^{*}} [ - F ^{*(0,y} ^{*)]} where F ^{*} is the convex conjugate in both variables.^{[2] [3] [4]}

In computational optimization, another "duality gap" is often reported, which is the difference in value between any dual solution and the value of a feasible but suboptimal iterate for the primal problem. This alternative "duality gap" quantifies the discrepancy between the value of a current feasible but suboptimal iterate for the primal problem and the value of the dual problem; the value of the dual problem is, under regularity conditions, equal to the value of the convex relaxation of the primal problem: The convex relaxation is the problem arising replacing a non-convex feasible set with its closed convex hull and with replacing a non-convex function with its convex closure, that is the function that has the epigraph that is the closed convex hull of the original primal objective function.^{[5] [6] [7] [8] [9] [10] [11] [12] [13]}

Notes and References

1. Book: Techniques of Variational Analysis. Borwein. Jonathan. Zhu. Qiji. 2005. Springer. 978-1-4419-2026-3.
2. Book: Duality in Vector Optimization. Radu Ioan Boţ. Gert Wanka. Sorin-Mihai Grad. 2009. Springer. 978-3-642-02885-4.
3. Book: Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Ernö Robert Csetnek. 2010. Logos Verlag Berlin GmbH. 978-3-8325-2503-3.
4. Book: Zălinescu, C.. Convex analysis in general vector spaces. limited. World Scientific Publishing Co. Inc. River Edge, NJ. 2002. 106–113. 981-238-067-1. 1921556.
5. Book: Ahuja, Ravindra K. . Ravindra K. Ahuja . Magnanti, Thomas L. . Thomas L. Magnanti . Orlin, James B. . James B. Orlin . Network Flows: Theory, Algorithms and Applications . Prentice Hall . 1993 . 0-13-617549-X .
6. Book: Bertsekas . Dimitri P. . 1999 . Nonlinear Programming . 2nd . Athena Scientific . 1-886529-00-0 .
7. Book: Bonnans . J. Frédéric . Gilbert . J. Charles . Lemaréchal . Claude . Sagastizábal . Claudia A.. Claudia Sagastizábal . Numerical optimization: Theoretical and practical aspects . Second revised ed. of translation of 1997 French . Universitext . Springer-Verlag . Berlin . 2006 . xiv+490 . 3-540-35445-X . 10.1007/978-3-540-35447-5 . 2265882 . Claude Lemaréchal .
8. Book: Hiriart-Urruty . Jean-Baptiste . Lemaréchal . Claude . Convex analysis and minimization algorithms, Volume I: Fundamentals . Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] . 305 . Springer-Verlag . Berlin . 1993 . xviii+417 . 3-540-56850-6 . 1261420 .
9. Book: Hiriart-Urruty . Jean-Baptiste . Lemaréchal . Claude . XII. Abstract Duality for Practitioners . Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods . 1993 . 10.1007/978-3-662-06409-2_4 . Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] . 306 . Springer-Verlag . Berlin . xviii+346 . 3-540-56852-2 . 1295240. Claude Lemaréchal .
10. Book: Lasdon, Leon S. . Optimization theory for large systems . Dover Publications, Inc. . Mineola, New York . 2002 . Reprint of the 1970 Macmillan . xiii+523 . 1888251 . 978-0-486-41999-2 .
11. Book: Lemaréchal, Claude . Lagrangian relaxation . 112–156 . Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000 . Jünger, Michael . Naddef, Denis . Lecture Notes in Computer Science (LNCS) . 2241 . Springer-Verlag . Berlin . 2001 . 3-540-42877-1 . 1900016 . 10.1007/3-540-45586-8_4 . 9048698 . Claude Lemaréchal .
12. Book: Minoux, Michel . Michel Minoux . Mathematical programming: Theory and algorithms . Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French . A Wiley-Interscience Publication. John Wiley & Sons, Ltd. . Chichester . 1986 . xxviii+489 . 0-471-90170-9 . 868279 . (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. .) .
13. Book: Shapiro, Jeremy F.. Mathematical programming: Structures and algorithms. Wiley-Interscience [John Wiley & Sons]. New York. 1979. xvi+388. 0-471-77886-9. 544669.