Меню Главная Случайная статья Настройки Разрыв двойственности Материал из https://ru.wikipedia.org Разрыв двойственности — это разница между прямым и двойственным решениями. Если ${\displaystyle d^{*}}$ является оптимальным значением двойственной задачи, а ${\displaystyle p^{*}}$ является оптимальным значением прямой задачи, то разрыв двойственности равен ${\displaystyle p^{*}-d^{*}}$. Это значение всегда больше либо равно нулю (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен, и имеет место слабая двойственность[1]. Содержание 1 Описание 2 Альтернативы 3 Примечания 4 Литература Описание В общем случае пусть дана двойственная пара[англ.] разделённых локально выпуклых пространств ${\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 I}$ на ограничениях — ${\displaystyle f=f+I}$. Тогда пусть ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ будет функцией возмущений[англ.], такой что ${\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]. Альтернативы В вычислительной оптимизации часто упоминается другой «разрыв двойственности», который равен разности значений между любым решением и значением допустимого, но подоптимального значения прямой задачи. Этот альтернативный «разрыв двойственности» количественно выражает расхождение между значением текущего допустимого, но подоптимального значения прямой задачи, и значением двойственной задачи. Значение двойственной задачи, по условиям регулярности, равно значению выпуклой релаксации прямой задачи. Выпуклая релаксация — это задача, которая получается путём замены невыпуклого множества допустимых решений на его замкнутую выпуклую оболочку и заменой невыпуклой функции на её выпуклое замыкание, то есть на функцию, надграфик которой является замкнутой выпуклой оболочкой надграфика исходной целевой функции прямой задачи [5][6][7][8][9][10][11][12][13]. Примечания Borwein, Zhu, 2005. Bo, Wanka, Grad, 2009. Csetnek, 2010. Zlinescu, 2002, с. 106–113. Ahuja, Magnanti, Orlin, 1993. Bertsekas, 1999. Bonnans, Gilbert, Lemarchal, Sagastizbal, 2006, с. xiv+490. Hiriart-Urruty, Lemarchal, 1993, с. xviii+417. Hiriart-Urruty, Lemarchal, 1993, с. xviii+346. Lasdon, 2002, с. xiii+523. Lemarchal, 2001, с. 112–156. Minoux, 1986, с. xxviii+489. Shapiro, 1979, с. xvi+388. Литература Jonathan Borwein, Qiji Zhu. Techniques of Variational Analysis. — Springer, 2005. — ISBN 978-1-4419-2026-3.