對偶間隙

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

一般而言，給定二個的分隔 及。假定函數，可以定義原始問題為

若有限制條件，可以整合到函數中，方式是令，其中是示性函数。則令是使得。則對偶間隙即為以下的差值

其中為二個變數的凸共轭。

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

參考資料

線性規劃
凸最佳化