Сильная двойственность
Сильная двойственность — это условие математической оптимизации, при котором основная оптимальная цель и двойная оптимальная цель равны. По определению, сильная двойственность имеет место тогда и только тогда, когда разрыв двойственности равен 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 ].