对偶间隙

对偶间隙是应用数学中最佳化问题的词语，是指原始解和对偶解之间的差距。若${\displaystyle d^{*}}$是对偶问题解对应的值，而${\displaystyle p^{*}}$是原始问题最佳解对应的值，则对偶间隙为${\displaystyle p^{*}-d^{*}}$。针对最小化的最佳化问题，对偶间隙恒大于等于零。对偶间隙为零当且仅当强对偶（英语：strong duality）的条件成立，不然对偶间隙为严格正值，此时即为弱对偶（英语：weak duality）^[1]。

一般而言，给定二个对偶对（英语：dual pair）的分隔局部凸空间（英语：locally convex space） ${\displaystyle \left(X,X^{*}\right)}$及${\displaystyle \left(Y,Y^{*}\right)}$。假定函数${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$，可以定义原始问题为

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

若有限制条件，可以整合到函数${\displaystyle f}$中，方式是令${\displaystyle f=f+I_{\text{constraints}}}$，其中${\displaystyle I}$是示性函数。则令${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$是扰动函数使得${\displaystyle F(x,0)=f(x)}$。则对偶间隙即为以下的差值

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

其中${\displaystyle F^{*}}$为二个变数的凸共轭^[2][3][4]。

在计算最优化中，会提到另一种“对偶间隙”，是对偶解以及原始问题次最佳但是可行解之间的差距。这种对偶间隙反映了目前可行，但可能只是次最佳的迭代解，和对偶问题解之间的差距。对偶问题解是指规律性条件下，等于原始问题凸松弛（convex relaxation）下的解。凸松弛是指将问题中非凸可行集合改为闭凸包，将非凸函数改为凸的闭集（函数的上境图（英语：epigraph (mathematics)）是原始目标函数的闭凸包）^{[5][6][7][8][9]}。