Duality gap

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

${\displaystyle \underset{x\in X}{inf}f(x).}$

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

${\displaystyle \underset{x\in X}{inf}[F(x,0)]-\underset{y^{\ast }\in Y^{\ast }}{sup}[-F^{\ast }(0,y^{\ast })]}$

where ${\displaystyle F^{\ast }}$ 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.