對偶間隙

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

一般而言,給定二個對偶對英語dual pair分隔局部凸空間英語locally convex space 。假定函數,可以定義原始問題為

若有限制條件,可以整合到函數中,方式是令,其中示性函數。則令擾動函數英語perturbation function使得。則對偶間隙即為以下的差值

其中為二個變數的凸共軛[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.