对偶间隙

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

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

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

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

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

其中$F^{*}$为二个变数的凸共轭。

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