Полуопределённое программирование (SDP)

1994. Лоран Ловас доказывает: theta-число графа (верхняя оценка независимого множества, задача NP-hard) вычисляется за полиномиальное время через одно SDP. Год спустя Гоеманс и Вильямсон публикуют алгоритм MAX-CUT с гарантией 0.878 от оптимума - он остаётся лучшим полиномиальным алгоритмом для MAX-CUT по сей день. Обе работы используют один трюк: заменить скалярные переменные $y_i \in \{-1, +1\}$ на матрицу $Y \succeq 0$ с диагональю 1 - это SDP relaxation. Расслабление решается точно за полиномиальное время, а рандомное округление возвращает целочисленное решение с доказуемой гарантией. Тот же инструмент используется в SVM kernel learning, в синтезе робастных регуляторов, в верификации нейросетей через Sum-of-Squares.

• **MAX-CUT (Goemans-Williamson):** гарантия 0.878 от оптимума - лучший полиномиальный алгоритм, условно оптимальный под гипотезой UGC
• **Kernel learning (ML):** матрица Грама $K \succeq 0$ - ограничение Мерсера, обучение ядра при дополнительных ограничениях напрямую является SDP
• **LQR и H-infinity синтез (control):** оптимальный регулятор находится через LMI над Lyapunov-матрицей
• **Sum-of-Squares (robotics, verification):** сертификаты безопасности и Lyapunov-функции для нелинейных систем через SDP

Предварительные знания

• KKT-условия и двойственность
• Interior point метод
• Выпуклые конусы

SDP и Linear Matrix Inequality

**1994. Ловас доказывает: задача о независимом множестве (NP-hard) аппроксимируется за полиномиальное время через одно SDP.** Год спустя Гоеманс и Вильямсон публикуют алгоритм MAX-CUT с гарантией 0.878 от оптимума - лучший полиномиальный результат, известный до сих пор. Оба результата используют один инструмент: переменная оптимизации не вектор, а матрица, и ограничение - не $Ax \leq b$, а матричное неравенство $X \succeq 0$.

LP - частный случай оптимизации над векторным конусом $\mathbb{R}^n_+$. SDP обобщает LP: конус заменяется конусом положительно полуопределённых матриц $\mathbb{S}^n_+$. Переменная $X \in \mathbb{S}^n$ - симметричная матрица $n \times n$.

**Стандартная форма SDP:** $$\min_{X \in \mathbb{S}^n} \operatorname{Tr}(CX) \quad \text{s.t.} \quad \operatorname{Tr}(A_i X) = b_i, \; i = 1,\ldots,m, \quad X \succeq 0$$ Здесь $\operatorname{Tr}(CX) = \sum_{ij} C_{ij} X_{ij}$ - скалярное произведение матриц. $X \succeq 0$ означает все собственные значения $\geq 0$. **Linear Matrix Inequality (LMI) - эквивалентная формулировка:** $$F(x) = F_0 + x_1 F_1 + \cdots + x_n F_n \succeq 0$$ Здесь $x \in \mathbb{R}^n$ - вектор переменных, $F_i \in \mathbb{S}^k$ - заданные матрицы. Задача: $\min \, c^T x$ при $F(x) \succeq 0$. **Иерархия конических программ:** $$\text{LP} \subset \text{SOCP} \subset \text{SDP}$$ Каждый LP записывается как SDP: заменить $x_i \geq 0$ на $\operatorname{diag}(x) \succeq 0$.

Типичное применение в ML: обучение ядра (kernel learning). Матрица Грама $K_{ij} = k(x_i, x_j)$ должна быть PSD по теореме Мерсера. Задача - найти $K \succeq 0$, $\operatorname{Tr}(K) \leq 1$, минимизирующую hinge loss. Это SDP по $K$. Ограничение $K \succeq 0$ нельзя записать как LP: конус $\mathbb{S}^n_+$ не является пересечением конечного числа полупространств.

Двойственность и сильная дуальность SDP

Двойственность SDP устроена аналогично LP: прямая задача минимизирует линейную функцию над конусом PSD, двойственная - максимизирует по другому конусу PSD. Разница с LP: сильная двойственность в SDP не гарантирована автоматически - нужно условие Слейтера (существование строго допустимой точки $X \succ 0$).

**Прямая и двойственная SDP:** *Прямая:* $$p^* = \min_{X \succeq 0} \operatorname{Tr}(CX) \quad \text{s.t.} \quad \operatorname{Tr}(A_i X) = b_i, \; i=1,\ldots,m$$ *Двойственная:* $$d^* = \max_{y \in \mathbb{R}^m} b^T y \quad \text{s.t.} \quad C - \sum_{i=1}^m y_i A_i \succeq 0$$ **Слабая двойственность:** $d^* \leq p^*$ всегда. **Сильная двойственность** (при условии Слейтера): если существует $X \succ 0$ с $\operatorname{Tr}(A_i X) = b_i$ и $y$ с $C - \sum y_i A_i \succ 0$, то $p^* = d^*$. **Complementary slackness:** $$\operatorname{Tr}\!\left(\bigl(C - {\textstyle\sum} y_i A_i\bigr) X\right) = 0$$ Произведение двух PSD-матриц равно нулю - они ортогональны в смысле следа. Это аналог условия $\lambda_i (b_i - a_i^T x^*) = 0$ из KKT в LP.

Пример из теории управления: задача стабилизации LTI-системы $\dot{x} = Ax + Bu$. Система стабилизируема обратной связью $u = Kx$, если матрица $A + BK$ устойчива. Через матрицу Ляпунова $P \succ 0$ условие записывается как LMI: $(A + BK)^T P + P(A + BK) \prec 0$. Это SDP-feasibility задача по $P$ и $Y = KP$. Двойственная задача к ней - сертификат неустойчивости.

**Почему SDP строже LP в смысле двойственности:** В LP зазор двойственности $p^* - d^* = 0$ при допустимости обеих задач (без дополнительных условий). В SDP возможен **ненулевой зазор** даже при допустимости обеих сторон, если Slater не выполнен. *Пример-ловушка:* $$\min_{X \succeq 0} X_{11} \quad \text{s.t.} \quad X_{12} = 1$$ Прямая задача: инфимум = 0, но не достигается ($X_{11} > 0$ для любого feasible $X$, так как $X \succeq 0$ и $X_{12} = 1$ требуют $X_{11} X_{22} \geq 1$). Двойственная: $\sup = 0$. Зазор = 0, но оптимум прямой задачи не достигается. Причина: нет $X \succ 0$ с $X_{12} = 1$ и $X_{11} = 0$ одновременно.

SDP relaxation: MAX-CUT и Гоеманс-Вильямсон

MAX-CUT: дан граф $G = (V, E)$ с весами $w_{ij} > 0$. Разбить вершины на два множества $S$ и $\bar{S}$ так, чтобы суммарный вес рёбер между ними был максимален. Формально: найти $y \in \{-1, +1\}^n$, максимизирующее $\frac{1}{4} \sum_{ij} w_{ij}(1 - y_i y_j)$. Это NP-hard. Гоеманс и Вильямсон в 1995 показали: SDP relaxation + рандомное округление даёт 0.878-аппроксимацию.

**MAX-CUT: целочисленная программа и SDP relaxation:** *Целочисленная (NP-hard):* $$\max_{y \in \{-1,+1\}^n} \frac{1}{4} \sum_{(i,j) \in E} w_{ij}(1 - y_i y_j)$$ Замена: $y_i y_j = Y_{ij}$ при условии $Y = yy^T$ (матрица ранга 1). Расслабление: отказаться от ранга 1, сохранить лишь PSD и диагональ: *SDP relaxation:* $$\max_Y \frac{1}{4} \sum_{(i,j)} w_{ij}(1 - Y_{ij}) \quad \text{s.t.} \quad Y \succeq 0, \; Y_{ii} = 1$$ **Рандомное округление (Гоеманс-Вильямсон):** 1. Решить SDP, получить $Y^* \succeq 0$ с $Y^*_{ii} = 1$. 2. Разложить: $Y^* = V^T V$, где $v_i$ - единичные векторы в $\mathbb{R}^n$. 3. Выбрать случайный единичный вектор $r \sim \mathcal{N}(0, I)$, нормировать. 4. Разбиение: $y_i = \operatorname{sign}(v_i^T r)$. **Гарантия:** $\mathbb{E}[\text{CUT}] \geq 0.878 \cdot \text{OPT}$, где $0.878 = \min_{\theta \in (0,\pi)} \frac{2}{\pi} \frac{\theta}{1 - \cos\theta}$.

Зачем 0.878 - лучший результат для полиномиального алгоритма? Под гипотезой Уникальности Игры (Unique Games Conjecture, Хот 2002) алгоритм Гоеманса-Вильямсона оптимален: любой полиномиальный алгоритм аппроксимирует MAX-CUT не лучше чем на 0.878. В данном смысле SDP - структурно оптимальный подход для целого класса комбинаторных задач.

SDP в ML, Sum-of-Squares и теории управления

SDP - не экзотика для комбинаторики. Это рабочий инструмент в обучении с учителем, полиномиальной оптимизации и синтезе регуляторов. Три ключевых приложения: eigenvalue optimization (robustness), Sum-of-Squares (global polynomial bounds), LQR/Lyapunov (optimal control).

**1. Eigenvalue optimization:** $$\min_{x} \lambda_{\max}(A(x)) \quad \Longleftrightarrow \quad \min_{x, t} \; t \quad \text{s.t.} \quad t I - A(x) \succeq 0$$ Это SDP по $(x, t)$, если $A(x) = A_0 + \sum x_i A_i$ линейна по $x$. Применения: устойчивость марковской цепи PageRank, минимакс в робастной оптимизации, $H_\infty$-синтез в control. **2. Sum-of-Squares (SOS):** Полином $p(x) \geq 0$ для всех $x$ $\Leftarrow$ $p(x) = z(x)^T Q z(x)$, где $Q \succeq 0$ и $z(x)$ - вектор мономов. Это SDP-feasibility по $Q$. Применения: верификация нейросетей (neural network Lyapunov), глобальная оптимизация полиномов, сертификаты безопасности в робототехнике. **3. LQR через SDP:** Линейно-квадратичный регулятор: $\min_{u} \int_0^\infty (x^T Q x + u^T R u) \, dt$ для системы $\dot{x} = Ax + Bu$. Оптимальное управление $u = -Kx$, $K = R^{-1} B^T P$, матрица $P$ - решение уравнения Риккати. Через SDP: ищем $P \succ 0$ с $A^T P + PA - PBR^{-1}B^T P + Q \prec 0$ (LMI). Это консервативнее Риккати, но масштабируется на неопределённые и переключаемые системы.

Вычислительная сложность SDP: interior point метод (урок 08) с барьером $-\log \det X$ решает SDP за $O(\sqrt{n} \log(1/\varepsilon))$ итераций, каждая стоит $O(n^3 + mn^2)$. Для больших $n$ это дорого. Практические альтернативы: DSOS (диагонально-доминантные SOS) и SDSOS (масштабированные) заменяют PSD-конус более дешёвыми аппроксимациями, решаемыми как LP или SOCP.

Ключевые идеи

• **SDP:** $\min \operatorname{Tr}(CX)$, $X \succeq 0$, $\operatorname{Tr}(A_i X) = b_i$ - LP над матричным конусом PSD; LMI $F_0 + \sum x_i F_i \succeq 0$ - эквивалентная форма с векторными переменными
• **Двойственность:** $\max b^T y$, $C - \sum y_i A_i \succeq 0$; сильная двойственность при условии Слейтера; complementary slackness $\operatorname{Tr}(S \cdot X) = 0$
• **SDP relaxation MAX-CUT:** заменить $y_i y_j \in \{-1,+1\}$ на $Y_{ij}$, $Y \succeq 0$, $Y_{ii}=1$; рандомное округление через Холецкого + случайная гиперплоскость даёт 0.878 гарантию
• **Eigenvalue optimization:** $\min \lambda_{\max}(A(x)) \Leftrightarrow \min t$ при $tI - A(x) \succeq 0$ - SDP по $(x,t)$
• **Sum-of-Squares:** $p(x) \geq 0$ сертифицируется через $Q \succeq 0$ - достаточное, но не необходимое условие (полином Моцкина - контрпример Гильберта 1888)

Что дальше

SDP - вершина иерархии конических программ. Следующий шаг - декомпозиция и распределённые методы для задач, слишком больших для одного SDP-решателя:

• Декомпозиция двойственности и ADMM — ADMM расщепляет большие SDP на параллельные подзадачи; SCS-решатель CVXPY использует ADMM внутри
• Interior point метод — Барьер -log det X для SDP - матричное обобщение log-барьера LP из урока 08
• KKT-условия — Complementary slackness SDP - прямое обобщение KKT; двойственная задача SDP строится из тех же принципов

Вопросы для размышления

• Гоеманс-Вильямсон даёт 0.878-аппроксимацию MAX-CUT через SDP + рандомное округление. Константа $0.878 = \min_\theta \frac{2}{\pi} \frac{\theta}{1-\cos\theta}$. Что геометрически означает этот минимум - при каком угле между векторами $v_i$ и $v_j$ округление даёт наибольшую потерю?
• Sum-of-Squares даёт достаточный сертификат $p(x) \geq 0$, но не необходимый. Как это связано с тем, что проверка $p(x) \geq 0$ для произвольного полинома NP-hard - можно ли выстроить иерархию всё более точных SDP-релаксаций?
• LQR-регулятор находится аналитически через уравнение Риккати. Зачем тогда SDP-формулировка через LMI? В каких ситуациях LMI-подход даёт что-то, чего не даёт классическое уравнение Риккати?

Связанные уроки

• cvx-08 — Interior point метод - основной решатель SDP; барьер -log det X обобщает log-барьер LP
• cvx-05 — KKT и сильная двойственность - язык SDP duality
• cvx-03 — Конус PSD - частный случай выпуклого конуса
• ml-13-svm — SVM kernel learning = SDP feasibility над матрицей Грама
• la-25-quadratic-forms