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