對偶間隙

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

一般而言，給定二個對偶對（英语：dual pair）的分隔局部凸空間（英语：locally convex space） ${\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 \}}$是擾動函數（英语：perturbation function）使得${\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）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的上境圖（英语：epigraph (mathematics)）是原始目標函數的閉凸包）^{[5][6][7][8][9]}。

參考資料

1. Borwein, Jonathan; Zhu, Qiji. Techniques of Variational Analysis. Springer. 2005. ISBN 978-1-4419-2026-3. 
2. Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4. 
3. Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3. 
4. Zălinescu, C. Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing Co. Inc. 2002: 106–113. ISBN 981-238-067-1. MR 1921556. 
5. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. Network Flows: Theory, Algorithms and Applications. Prentice Hall. 1993. ISBN 0-13-617549-X. 
6. Bertsekas, Dimitri P. Nonlinear Programming 2nd. Athena Scientific. 1999. ISBN 1-886529-00-0. 
7. Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. Numerical optimization: Theoretical and practical aspects. Universitext Second revised ed. of translation of 1997 Optimisation numérique : Aspects théoriques et pratiques (French). Berlin: Springer-Verlag. 2006: xiv+490 [2020-07-12]. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5. （原始内容于2013-07-19）. 
8. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude. Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 305. Berlin: Springer-Verlag. 1993: xviii+417. ISBN 3-540-56850-6. MR 1261420. 
9. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude. XII. Abstract Duality for Practitioners. Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 306. Berlin: Springer-Verlag. 1993: xviii+346. ISBN 3-540-56852-2. MR 1295240. doi:10.1007/978-3-662-06409-2_4.