对偶间隙

对偶间隙应用数学最佳化问题的词语,是指原始解和对偶解之间的差距。若是对偶问题解对应的值,而是原始问题最佳解对应的值,则对偶间隙为。针对最小化的最佳化问题,对偶间隙恒大于等于零。对偶间隙为零当且仅当强对偶英语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.