对偶间隙
对偶间隙是应用数学中最佳化问题的词语,是指原始解和对偶解之间的差距。若是对偶问题解对应的值,而是原始问题最佳解对应的值,则对偶间隙为。针对最小化的最佳化问题,对偶间隙恒大于等于零。对偶间隙为零若且唯若强对偶的条件成立,不然对偶间隙为严格正值,此时即为弱对偶[1]。
一般而言,给定二个对偶对的分隔局部凸空间 及。假定函数,可以定义原始问题为
若有限制条件,可以整合到函数中,方式是令,其中是示性函数。则令是扰动函数使得。则对偶间隙即为以下的差值
在计算最优化中,会提到另一种“对偶间隙”,是对偶解以及原始问题次最佳但是可行解之间的差距。这种对偶间隙反映了目前可行,但可能只是次最佳的迭代解,和对偶问题解之间的差距。对偶问题解是指规律性条件下,等于原始问题凸松弛(convex relaxation)下的解。凸松弛是指将问题中非凸可行集合改为闭凸包,将非凸函数改为凸的闭集(函数的上境图是原始目标函数的闭凸包)[5][6][7][8][9]。
参考资料
- ^ Borwein, Jonathan; Zhu, Qiji. Techniques of Variational Analysis. Springer. 2005. ISBN 978-1-4419-2026-3.
- ^ Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4.
- ^ 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.
- ^ 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.
- ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. Network Flows: Theory, Algorithms and Applications. Prentice Hall. 1993. ISBN 0-13-617549-X.
- ^ Bertsekas, Dimitri P. Nonlinear Programming 2nd. Athena Scientific. 1999. ISBN 1-886529-00-0.
- ^ 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).
- ^ 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.
- ^ 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.