Теория двойственности в коническом программировании: геометрия конусов и условия Слейтера

Математическая постановка прямой задачи конического программирования имеет вид: минимизировать $c^T x$ при условии $Ax = b$ и $x \in K$, где $K$ — замкнутый выпуклый конус. Для построения двойственной задачи вводится понятие двойственного конуса $K^*$, который состоит из всех векторов $y$, образующих неотрицательное скалярное произведение с любым вектором из исходного конуса $K$ ($y^T x \ge 0$ для всех $x \in K$). Двойственная задача формулируется так: максимизировать $b^T y$ при условии $c - A^T y \in K^*$. Красота этой формулировки заключается в ее абсолютной симметрии с классической теорией двойственности линейного программирования.

Для самодвойственных конусов, таких как неотрицательный ортант, конус Лоренца (конус второго порядка) и конус положительно полуопределенных матриц, двойственный конус $K^*$ в точности совпадает с прямым конусом $K$. Это свойство критически важно для создания эффективных вычислительных алгоритмов, в частности, методов внутренней точки. Однако, в отличие от линейного программирования, где слабая и сильная двойственность выполняются почти безусловно, в произвольном коническом программировании сильная двойственность (равенство оптимумов прямой и двойственной задач) не гарантирована. Может возникать так называемый "разрыв двойственности" (Duality Gap), когда супремум двойственной задачи строго меньше инфимума прямой.

Для обеспечения нулевого разрыва двойственности необходимо выполнение условий регулярности, самым известным из которых является условие Слейтера (Slater's Condition). В контексте конического программирования оно требует существования хотя бы одной строго допустимой точки, то есть такой точки $x$, для которой $Ax=b$, а вектор $x$ лежит строго во внутренности конуса $K$ ($x \in \text{int} K$). Если условие Слейтера выполняется для прямой задачи, сильная двойственность гарантирована, а двойственная задача обязательно достигает своего оптимума. Если условие выполняется для обеих задач, то оптимумы достигаются обеими задачами, и разрыв равен нулю.

Экономический смысл двойственных переменных $y$ остается неизменным — они представляют собой теневые цены ресурсов. В приложениях полуопределенного программирования (SDP), которые являются частным случаем конического, двойственность позволяет строить строгие нижние оценки для сложных комбинаторных задач. Например, в знаменитом алгоритме Гоманса-Уильямсона для задачи MAX-CUT переход к двойственной полуопределенной задаче позволяет мгновенно оценить качество приближенного решения. Понимание геометрии двойственных конусов необходимо для глубокого анализа устойчивости систем и разработки робастных инженерных моделей, где ограничения задаются через нормы и матричные неравенства.

Список литературы:
1. Boyd S., Vandenberghe L. Convex Optimization. — Cambridge University Press, 2004.
2. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization. — SIAM, 2001.
3. Нестеров Ю.Е. Введение в выпуклую оптимизацию. — М.: МЦНМО, 2010.