Сильная двойственность
Сильная двойственность — это условие математической оптимизации , при котором основная оптимальная цель и двойная оптимальная цель равны. По определению сильная двойственность имеет место тогда и только тогда, когда разрыв двойственности равен 0. Это противоположность слабой двойственности (оптимальное значение основной задачи меньше или равно двойственной задаче, другими словами, разрыв двойственности больше или равен нулю).
Достаточные условия [ править ]
Для выполнения сильной двойственности достаточно каждого из следующих условий:
- где — функция возмущения, связывающая основную и двойственную задачи, а является двусопряженным (следует из построения разрыва двойственности )
- выпукла и полунепрерывна снизу (эквивалентна первой точке по теореме Фенхеля–Моро )
- основная проблема — это задача линейной оптимизации
- Условие Слейтера для задачи выпуклой оптимизации . [1] [2]
Сильная двойственность сложность вычислительная и
При определенных условиях (называемых «квалификацией ограничений»), если проблема разрешима за полиномиальное время, то она имеет сильную двойственность (в смысле лагранжевой двойственности ). Остается открытым вопрос, справедливо ли и противоположное направление, то есть предполагает ли сильная двойственность разрешимость за полиномиальное время. [3]
См. также [ править ]
Ссылки [ править ]
- ^ Борвейн, Джонатан; Льюис, Адриан (2006). Выпуклый анализ и нелинейная оптимизация: теория и примеры (2-е изд.). Спрингер. ISBN 978-0-387-29570-1 .
- ^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 . Проверено 3 октября 2011 г.
- ^ Маньем, Прабху (2010). «Разрыв двойственности, вычислительная сложность и NP-полнота: обзор». arXiv : 1012.5568 [ math.OC ].