Полуопределенное программирование (SDP): теория линейных матричных неравенств

Математически стандартная форма SDP заключается в минимизации следа матрицы $C \bullet X = \text{tr}(CX)$ при условиях $A_i \bullet X = b_i$ и $X \succeq 0$, где запись $X \succeq 0$ означает, что симметричная матрица $X$ положительно полуопределена (все ее собственные значения неотрицательны). Эквивалентная формулировка использует линейные матричные неравенства (Linear Matrix Inequalities, LMI) вида $F_0 + x_1 F_1 + \dots + x_n F_n \succeq 0$. Важность LMI состоит в том, что множество решений такого неравенства всегда образует замкнутое выпуклое множество. Благодаря теореме Шура о дополнении (Schur Complement), огромный класс нелинейных выпуклых ограничений может быть точно переписан в форме LMI.

Один из величайших триумфов SDP в дискретной математике связан с аппроксимацией NP-трудных задач комбинаторной оптимизации. В 1995 году Мишель Гоманс и Дэвид Уильямсон предложили алгоритм на базе SDP для задачи максимального разреза графа (MAX-CUT). Суть их гениального подхода заключалась в замене булевых переменных $x_i \in \{-1, 1\}$, соответствующих вершинам графа, на векторы $v_i$ на единичной сфере в $n$-мерном пространстве. Расслабление дискретной задачи до непрерывного поиска оптимальной матрицы скалярных произведений (матрицы Грама $X$) превратило нерешаемую задачу в задачу SDP, которая решается за полиномиальное время. Использование случайного гиперплоскостного округления для полученных векторов позволило Гомансу и Уильямсону получить феноменальную гарантированную оценку аппроксимации в 0.87856 от абсолютного оптимума.

В классической теории управления и робастной стабильности систем LMI стали универсальным языком. Поиск функции Ляпунова, доказывающей устойчивость нелинейной или дифференциальной системы управления, математически сводится к решению системы линейных матричных неравенств. Если SDP-решатель находит допустимую матрицу $P \succeq 0$, система гарантированно устойчива. Это перевело сложнейшие аналитические доказательства стабильности в разряд рутинных вычислительных операций, выполняемых компьютерами.

Алгоритмически задачи SDP решаются методами внутренней точки (Primal-Dual Interior-Point Methods). Хотя они обладают полиномиальной сложностью, вычисления на каждой итерации требуют формирования и обращения матриц больших размеров, что накладывает ограничения на размерность разрешимых задач. Современные исследования в области алгоритмов первого порядка (ADMM, проксимальные методы) и использования структуры разреженности хордовых графов направлены на преодоление этого барьера, позволяя внедрять полуопределенную оптимизацию в гигантские задачи машинного обучения и квантовой химии.

Список литературы:
1. Vandenberghe L., Boyd S. Semidefinite Programming. — SIAM Review, 1996.
2. Goemans M.X., Williamson D.P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. — JACM, 1995.
3. Немировский А.С. Линейные матричные неравенства в теории управления. — М.: ФАЗИС, 1998.