Сильная двойственность
-
Определение сильной двойственности
- Сильная двойственность подразумевает равенство основной и двойной оптимальных целей.
- Разрыв в двойственности равен нулю при сильной двойственности.
-
Противопоставление слабой двойственности
- Слабая двойственность предполагает, что разрыв в двойственности может быть больше или равен нулю.
-
Достаточные условия сильной двойственности
- Функция возмущения F должна быть выпуклой и нижней полунепрерывной.
- Основная задача должна быть задачей линейной оптимизации.
- Условие Слейтера для задачи выпуклой оптимизации является необходимым условием.
-
Связь с вычислительной сложностью
- При определенных условиях сильная двойственность подразумевает разрешимость задачи за полиномиальное время.
- Вопрос о том, является ли сильная двойственность необходимым условием для полиномиальной разрешимости, остается открытым.
-
Ссылки
- Статья упоминает выпуклую оптимизацию как связанную тему.
- В статье есть рекомендации для дальнейшего чтения.