查看“︁對偶間隙”︁的源代码

'''對偶間隙'''是[[應用數學]]中[[最佳化問題]]的詞語，是指[[對偶性 (最佳化)#對偶問題|原始解和對偶解]]之間的差距。若<math>d^*</math>是對偶問題解對應的值，而<math>p^*</math>是原始問題最佳解對應的值，則對偶間隙為<math>p^* - d^*</math>。針對最小化的最佳化問題，對偶間隙恆大於等於零。對偶間隙為零若且唯若{{le|強對偶|strong duality}}的條件成立，不然對偶間隙為嚴格正值，此時即為{{le|弱對偶|weak duality}}<ref>{{cite book|title=Techniques of Variational Analysis|url=https://archive.org/details/techniquesofvari0000borw|last1=Borwein|first1=Jonathan|last2=Zhu|first2=Qiji|year=2005|publisher=Springer|isbn=978-1-4419-2026-3}}</ref>。

一般而言，給定二個{{le|對偶對|dual pair}}的[[豪斯多夫空间|分隔]]{{le|局部凸空間|locally convex space}} <math>\left(X,X^*\right)</math>及<math>\left(Y,Y^*\right)</math>。假定函數<math>f: X \to \mathbb{R} \cup \{+\infty\}</math>，可以定義原始問題為
:<math>\inf_{x \in X} f(x). \,</math>
若有限制條件，可以整合到函數<math>f</math>中，方式是令<math>f = f + I_\text{constraints}</math>，其中<math>I</math>是[[示性函数 (凸分析)|示性函数]]。則令<math>F: X \times Y \to \mathbb{R} \cup \{+\infty\}</math>是[[擾動函數]]使得<math>F(x,0) = f(x)</math>。則對偶間隙即為以下的差值
:<math>\inf_{x \in X} [F(x,0)] - \sup_{y^* \in Y^*} [-F^*(0,y^*)]</math>
其中<math>F^*</math>為二個變數的[[凸共轭]]<ref name="BWG">{{cite book|title=Duality in Vector Optimization|author1=Radu Ioan Boţ|author2=Gert Wanka|author3=Sorin-Mihai Grad|year=2009|publisher=Springer|isbn=978-3-642-02885-4}}</ref><ref>{{cite book|title=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|author=Ernö Robert Csetnek|year=2010|publisher=Logos Verlag Berlin GmbH|isbn=978-3-8325-2503-3}}</ref><ref name="Zalinescu">{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|url=https://archive.org/details/convexanalysisge00zali_934|publisher=World Scientific Publishing Co. Inc|location=River Edge, NJ|year= 2002|pages=[https://archive.org/details/convexanalysisge00zali_934/page/n126 106]–113|isbn=981-238-067-1|mr=1921556}}</ref>。

在計算[[最优化]]中，會提到另一種「對偶間隙」，是對偶解以及原始問題次最佳但是可行解之間的差距。這種對偶間隙反映了目前可行，但可能只是次最佳的迭代解，和對偶問題解之間的差距。對偶問題解是指規律性條件下，等於原始問題凸鬆弛（convex relaxation）下的解。凸鬆弛是指將問題中非凸可行集合改為閉[[凸包]]，將非凸函數改為凸的[[半連續性|閉集]]（函數的{{le|上境圖|epigraph (mathematics)}}是原始目標函數的閉凸包）<ref>{{cite book |author1=Ahuja, Ravindra K. |author2=Magnanti, Thomas L. |author3=Orlin, James B.  |title=Network Flows: Theory, Algorithms and Applications |url=https://archive.org/details/networkflowstheo0000ahuj |publisher=Prentice Hall |year=1993 |isbn=0-13-617549-X }}</ref><ref>{{cite book |last1=Bertsekas |first1=Dimitri P. |year=1999 |title=Nonlinear Programming |edition=2nd |publisher=Athena Scientific |isbn=1-886529-00-0 }}</ref><ref>{{cite book |last1=Bonnans |first1=J.&nbsp;Frédéric |last2=Gilbert |first2=J.&nbsp;Charles |last3=Lemaréchal |first3=Claude |last4=Sagastizábal |first4=Claudia&nbsp;A. |title=Numerical optimization: Theoretical and practical aspects |url=https://www.springer.com/mathematics/applications/book/978-3-540-35445-1 |edition=Second revised ed. of translation of 1997 ''Optimisation numérique : Aspects théoriques et pratiques'' (French) |series=Universitext |publisher=Springer-Verlag |location=Berlin |year=2006 |pages=xiv+490 |isbn=3-540-35445-X |doi=10.1007/978-3-540-35447-5 |mr=2265882 |ref=harv |access-date=2020-07-12 |archive-date=2013-07-19 |archive-url=https://web.archive.org/web/20130719050442/http://www.springer.com/mathematics/applications/book/978-3-540-35445-1 |dead-url=no }}</ref><ref>{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |last2=Lemaréchal |first2=Claude |title=Convex analysis and minimization algorithms, Volume&nbsp;I: Fundamentals |series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] |volume=305 |publisher=Springer-Verlag |location=Berlin |year=1993 |pages=xviii+417 |isbn=3-540-56850-6 |mr=1261420 }}</ref><ref>{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |last2=Lemaréchal |first2=Claude |chapter=XII. Abstract Duality for Practitioners |title=Convex analysis and minimization algorithms, Volume&nbsp;II: Advanced theory and bundle methods |year=1993 |doi=10.1007/978-3-662-06409-2_4 |series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] |volume=306 |publisher=Springer-Verlag |location=Berlin |pages=xviii+346 |isbn=3-540-56852-2 |mr=1295240 }}</ref>。

==參考資料==
{{reflist|30em}}

[[Category:線性規劃]]
[[Category:凸最佳化]]