對偶間隙

對偶間隙是應用數學中最佳化問題的詞語，是指原始解和對偶解之間的差距。若$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）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的上境圖是原始目標函數的閉凸包）。