對偶間隙

對偶間隙是應用數學中最佳化問題的詞語，是指原始解和對偶解之間的差距。若$d^{*}$是對偶問題解對應的值，而$p^{*}$是原始問題最佳解對應的值，則對偶間隙為$p^{*}-d^{*}$。針對最小化的最佳化問題，對偶間隙恆大於等於零。對偶間隙為零若且唯若Template:Le的條件成立，不然對偶間隙為嚴格正值，此時即為Template:Le。

一般而言，給定二個Template:Le的分隔Template:Le $(X,X^{*})$及$(Y,Y^{*})$。假定函數$f:X\to ℝ\cup \{+\mathrm{\infty }\}$，可以定義原始問題為

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

若有限制條件，可以整合到函數$f$中，方式是令$f=f+I_{\text{constraints}}$，其中$I$是示性函数。則令$F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$是擾動函數使得$F(x,0)=f(x)$。則對偶間隙即為以下的差值

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

其中$F^{*}$為二個變數的凸共轭。

在計算最优化中，會提到另一種「對偶間隙」，是對偶解以及原始問題次最佳但是可行解之間的差距。這種對偶間隙反映了目前可行，但可能只是次最佳的迭代解，和對偶問題解之間的差距。對偶問題解是指規律性條件下，等於原始問題凸鬆弛（convex relaxation）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的Template:Le是原始目標函數的閉凸包）。