對偶間隙

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

一般而言，給定二個對偶對的分隔局部凸空間 ${\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）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的上境圖是原始目標函數的閉凸包）[5][6][7][8][9]。