Duality gap

---

title: "Duality gap" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["linear-programming", "convex-optimization"] topic_path: "general/linear-programming" source: "https://en.wikipedia.org/wiki/Duality_gap" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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.

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 \mathbb{R} \cup {+\infty}, we can define the primal problem by :\inf_{x \in X} f(x). , If there are constraint conditions, these can be built into the function f by letting f = f + I_\text{constraints} where I is the indicator function. Then let F: X \times Y \to \mathbb{R} \cup {+\infty} be a perturbation function such that F(x,0) = f(x). The duality gap is the difference given by :\inf_{x \in X} [F(x,0)] - \sup_{y^* \in Y^} [-F^(0,y^)] where F^ is the convex conjugate in both variables.

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.

References

References

1. (2005). "Techniques of Variational Analysis". Springer.
2. (2009). "Duality in Vector Optimization". Springer.
3. Ernö Robert Csetnek. (2010). "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". Logos Verlag Berlin GmbH.
4. Zălinescu, C.. (2002). "Convex analysis in general vector spaces". World Scientific Publishing Co. Inc.
5. (1993). "Network Flows: Theory, Algorithms and Applications". Prentice Hall.
6. (1999). "Nonlinear Programming". Athena Scientific.
7. (2006). "Numerical optimization: Theoretical and practical aspects". Springer-Verlag.
8. (1993). "Convex analysis and minimization algorithms, Volume I: Fundamentals". Springer-Verlag.
9. (1993). "Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods". Springer-Verlag.
10. Lasdon, Leon S.. (2002). "Optimization theory for large systems". Dover Publications, Inc..
11. Lemaréchal, Claude. (2001). "Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000". Springer-Verlag.
12. Minoux, Michel. (1986). "Mathematical programming: Theory and algorithms". A Wiley-Interscience Publication. John Wiley & Sons, Ltd..
13. Shapiro, Jeremy F.. (1979). "Mathematical programming: Structures and algorithms". Wiley-Interscience [John Wiley & Sons].

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::