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 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.{{cite book|title=Techniques of Variational Analysis|last1=Borwein|first1=Jonathan|last2=Zhu|first2=Qiji|year=2005|publisher=Springer|isbn=978-1-4419-2026-3}}

In general given two dual pairs separated locally convex spaces $\backslash left(X,X^*\backslash right)$ and $\backslash left(Y,Y^*\backslash right)$. Then given the function $f:\; X\; \backslash to\; \backslash mathbb\{R\}\; \backslash cup\; \backslash \{+\backslash infty\backslash \}$, we can define the primal problem by

:$\backslash inf\_\{x\; \backslash in\; X\}\; f(x).\; \backslash ,$

If there are constraint conditions, these can be built into the function $f$ by letting $f\; =\; f\; +\; I\_\backslash text\{constraints\}$ where $I$ is the indicator function. Then let $F:\; X\; \backslash times\; Y\; \backslash to\; \backslash mathbb\{R\}\; \backslash cup\; \backslash \{+\backslash infty\backslash \}$ be a perturbation function such that $F(x,0)\; =\; f(x)$. The duality gap is the difference given by

:$\backslash inf\_\{x\; \backslash in\; X\}\; [F(x,0)]\; -\; \backslash sup\_\{y^*\; \backslash in\; Y^*\}\; [-F^*(0,y^*)]$

where $F^*$ is the convex conjugate in both variables.{{cite book|title=Duality in Vector Optimization|author1=Radu Ioan Boţ|author2=Gert Wanka|author3=Sorin-Mihai Grad|year=2009|publisher=Springer|isbn=978-3-642-02885-4}}{{cite book|title=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|author=Ernö Robert Csetnek|year=2010|publisher=Logos Verlag Berlin GmbH|isbn=978-3-8325-2503-3}}{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|url=https://archive.org/details/convexanalysisge00zali_934|url-access=limited|publisher=World Scientific Publishing Co. Inc|location=River Edge, NJ|year= 2002|pages=[https://archive.org/details/convexanalysisge00zali_934/page/n126 106]–113|isbn=981-238-067-1|mr=1921556}}

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.{{cite book |author1=Ahuja, Ravindra K. |author-link=Ravindra K. Ahuja |author2=Magnanti, Thomas L. |author2-link=Thomas L. Magnanti |author3=Orlin, James B. |author3-link=James B. Orlin |title=Network Flows: Theory, Algorithms and Applications |publisher=Prentice Hall |year=1993 |isbn=0-13-617549-X }}{{cite book |last1=Bertsekas |first1=Dimitri P. |year=1999 |title=Nonlinear Programming |edition=2nd |publisher=Athena Scientific |isbn=1-886529-00-0 }}{{cite book |last1=Bonnans |first1=J. Frédéric |last2=Gilbert |first2=J. Charles |last3=Lemaréchal |first3=Claude |last4=Sagastizábal |first4=Claudia A.|author4-link= Claudia Sagastizábal |title=Numerical optimization: Theoretical and practical aspects |url=https://www.springer.com/mathematics/applications/book/978-3-540-35445-1 |edition=Second revised ed. of translation of 1997 French |series=Universitext |publisher=Springer-Verlag |location=Berlin |year=2006 |pages=xiv+490 |isbn=3-540-35445-X |doi=10.1007/978-3-540-35447-5 |mr=2265882 |authorlink3=Claude Lemaréchal }}{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |last2=Lemaréchal |first2=Claude |title=Convex analysis and minimization algorithms, Volume I: Fundamentals |series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] |volume=305 |publisher=Springer-Verlag |location=Berlin |year=1993 |pages=xviii+417 |isbn=3-540-56850-6 |mr=1261420 }}{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |last2=Lemaréchal |first2=Claude |chapter=XII. Abstract Duality for Practitioners |title=Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods |year=1993 |doi=10.1007/978-3-662-06409-2_4 |series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] |volume=306 |publisher=Springer-Verlag |location=Berlin |pages=xviii+346 |isbn=3-540-56852-2 |mr=1295240|authorlink2=Claude Lemaréchal }}{{cite book |last=Lasdon |first=Leon S. |title=Optimization theory for large systems |publisher=Dover Publications, Inc. |location=Mineola, New York |year=2002 |orig-year=Reprint of the 1970 Macmillan |pages=xiii+523 |mr=1888251 |isbn=978-0-486-41999-2 }}{{cite book |last=Lemaréchal |first=Claude |chapter=Lagrangian relaxation |pages=112–156 |title=Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000 |editor=Jünger, Michael |editor2=Naddef, Denis |series=Lecture Notes in Computer Science (LNCS) |volume=2241 |publisher=Springer-Verlag |location=Berlin |year=2001 |isbn=3-540-42877-1 |mr=1900016 |doi=10.1007/3-540-45586-8_4 |s2cid=9048698 |author-link=Claude Lemaréchal }}{{cite book |last=Minoux |first=Michel |author-link=Michel Minoux |title=Mathematical programming: Theory and algorithms |others= Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French |publisher=A Wiley-Interscience Publication. John Wiley & Sons, Ltd. |location=Chichester |year=1986 |pages=xxviii+489 |isbn=0-471-90170-9 |mr=868279 |id=(2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. . ) }}{{cite book|last=Shapiro|first=Jeremy F.|title=Mathematical programming: Structures and algorithms|publisher=Wiley-Interscience [John Wiley & Sons]|location=New York|year=1979|pages=[https://archive.org/details/mathematicalprog0000shap/page/ xvi+388]|isbn=0-471-77886-9|mr=544669|url=https://archive.org/details/mathematicalprog0000shap/page/}}