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

Полуопределённое программирование (или SDP от англ. Semidefinite programming) — подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.

Полуопределённое программирование является относительно новой областью оптимизации, интерес к которой растёт по нескольким причинам. Много практических задач в областях исследования операций и комбинаторной оптимизации можно смоделировать или аппроксимировать как задачи полуопределённого программирования. В теории автоматического управления задачи SDP используются в контексте линейных матричных неравенств. Задачи SDP, фактически, являются частным случаем конического программирования и могут быть эффективно решены методом внутренней точки. Все задачи линейного программирования могут быть выражены как задачи SDP, а с помощью иерархий задач SDP могут быть аппроксимированы решения задач полиномиальной оптимизации. Полуопределённое программирование используется при оптимизации сложных систем. В последние годы некоторые задачи сложности квантовых запросов были сформулированы в терминах полуопределённого программирования.

Мотивация и определение

Исходные мотивации

Задача линейного программирования — это задача, в которой нужно максимизировать или минимизировать линейную целевую функцию от вещественных переменных на многограннике. В полуопределённом программировании, вместо этого мы используем вещественные вектора и нам позволено использовать скалярное произведение векторов. Условие неотрицательности вещественных переменных задачи ЛП заменяется ограничениями полуопределённости на матрице переменных задачи SDP. В частности, общая задача полуопределённого программирования может быть определена как любая задача математического программирования вида

[math]\displaystyle{ {\min_{x^1, \ldots, x^n \in \mathbb{R}^n}}{\sum_{i,j \in [n]} c_{i,j} (x^i \cdot x^j)} }[/math]

при условиях [math]\displaystyle{ {\sum_{i,j \in [n]} a_{i,j,k} (x^i \cdot x^j) \leq b_k \qquad \forall k}. }[/math]

Эквивалентные формулировки

Говорят, что [math]\displaystyle{ n \times n }[/math] матрица [math]\displaystyle{ M }[/math] положительно полуопределённа, если она является матрицей Грама некоторых векторов (т.е. если существуют вектора [math]\displaystyle{ x^1, \ldots, x^n }[/math], такие, что [math]\displaystyle{ m_{i,j}=x^i \cdot x^j }[/math] для всех [math]\displaystyle{ i,j }[/math]). Если это выполняется, мы обозначим это как [math]\displaystyle{ M \succeq 0 }[/math]. Заметим, что существуют некоторые другие эквивалентные определения положительной полуопределённости, например, положительно полуопределённые матрицы имеют только неотрицательные собственные значения и имеет положительно полуопределённый квадратный корень.

Обозначим через [math]\displaystyle{ \mathbb{S}^n }[/math] пространство всех [math]\displaystyle{ n \times n }[/math] вещественных симметричных матриц. В этом пространстве имеется скалярное произведение [math]\displaystyle{ \langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n A_{ij}B_{ij}. }[/math] (где [math]\displaystyle{ {\rm tr} }[/math] означает след)

Мы можем переписать задачу математического программирования из предыдущей секции в эквивалентном виде

[math]\displaystyle{ {\min_{X \in \mathbb{S}^n}} \langle C, X \rangle_{\mathbb{S}^n} }[/math]

при условиях [math]\displaystyle{ \begin{array}{ll} {\displaystyle \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m} \\ X \succeq 0 \end{array} }[/math]

где элемент [math]\displaystyle{ i,j }[/math] матрицы [math]\displaystyle{ C }[/math] равно [math]\displaystyle{ c_{i,j} }[/math] из предыдущей секции, а [math]\displaystyle{ A_k }[/math] — [math]\displaystyle{ n \times n }[/math] матрица, имеющая в качестве элемента [math]\displaystyle{ i,j }[/math] матрицы значение [math]\displaystyle{ a_{i,j,k} }[/math] из предыдущей секции.

Заметим, что если мы добавим дополнительные переменные должным образом, эта задача SDP может быть преобразована к виду

[math]\displaystyle{ \min_{X \in \mathbb{S}^n}} \langle C, X \rangle_{\mathbb{S}^n }[/math]

при условиях [math]\displaystyle{ \begin{array}{ll} \langle A_k, X \rangle_{\mathbb{S}^n} = b_k, \quad k = 1,\ldots,m \\ X \succeq 0 \end{array} }[/math]

Для удобства задача SDP может быть определена слегка в другой, но эквивалентной форме. Например, линейные выражения, использующие неотрицательные скалярные переменные могут быть добавлены в спецификацию задачи. Задача остаётся SDP, поскольку каждая переменная может быть включена в матрицу [math]\displaystyle{ X }[/math] как диагональный элемент ([math]\displaystyle{ X_{ii} }[/math] для некоторого [math]\displaystyle{ i }[/math]). Чтобы обеспечить [math]\displaystyle{ X_{ii} \geq 0 }[/math], можно добавить ограничения [math]\displaystyle{ X_{ij} = 0 }[/math] для всех [math]\displaystyle{ j \neq i }[/math]. В качестве другого примера, заметим, что для любой положительной полуопределённой матрицы [math]\displaystyle{ X }[/math], существует набор векторов [math]\displaystyle{ \{ v_i \} }[/math], таких, что элемент [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math] матрицы [math]\displaystyle{ X }[/math] равен [math]\displaystyle{ X_{ij} = (v_i, v_j) }[/math], скалярному произведению векторов [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ v_j }[/math]. Таким образом, задачи SDP часто формулируются в терминах линейных выражений от скалярных произведений векторов. Если дано решение задачи SDP в стандартном виде, вектора [math]\displaystyle{ \{ v_i \} }[/math] могут быть восстановлены за время [math]\displaystyle{ O(n^3) }[/math] (например, с помощью неполного разложения Холецкого матрицы X).

Теория двойственности

Определения

Аналогично линейному программированию, если задана общая задача SDP в виде

[math]\displaystyle{ \min_{X \in \mathbb{S}^n} \langle C, X \rangle_{\mathbb{S}^n} }[/math]

при условиях [math]\displaystyle{ \begin{array}{ll} \langle A_i, X \rangle_{\mathbb{S}^n} = b_i, \quad i = 1,\ldots,m \\ X \succeq 0 \end{array} }[/math]

(прямая задача, или P-SDP), мы определим двойственную полуопределённую задачу (D-SDP) как

[math]\displaystyle{ \max_{y \in \mathbb{R}^m} \langle b, y \rangle_{\mathbb{R}^m} }[/math]

при условиях [math]\displaystyle{ \begin{array}{ll}{\displaystyle\sum_{i=1}^m} y_i A_i \preceq C \end{array} }[/math]

Где для любых двух матриц [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math], [math]\displaystyle{ P \succeq Q }[/math] означает [math]\displaystyle{ P-Q \succeq 0 }[/math].

Слабая двойственность

Теорема о слабой двойственности утверждает, что прямая задача SDP имеет значение, не меньшее значения двойственной SDP. Таким образом, любое допустимое решение двойственной задачи SDP ограничивает снизу значение прямой SDP, и наоборот, любое допустимое значение прямой задачи SDP ограничивает сверху значение двойственной SDP. Это происходит потому, что

[math]\displaystyle{ \langle C, X \rangle - \langle b, y \rangle = \langle C, X \rangle - \sum_{i=1}^m y_i b_i = \langle C, X \rangle - \sum_{i=1}^m y_i \langle A_i, X \rangle = \langle C - \sum_{i=1}^m y_i A_i, X \rangle \geq 0, }[/math]

где последнее неравенство отражает факт положительной полуопределённости обеих матриц. Значение этой функции иногда называется двойственным зазором.

Сильная двойственность

При условии, известном как условие Слейтера, значения прямой и двойственной SDP-задач равны. Это называется сильной двойственностью. В отличие от задач линейного программирования, не всякая задача SDP обладает строгой двойственностью. В общем случае значение двойственной задачи SDP может быть строго меньше значения прямой задачи.

(i) Предположим, что прямая задача (P-SDP) ограничена снизу и строго допустима (то есть существуют [math]\displaystyle{ X_0\in\mathbb{S}^n, X_0\succ 0 }[/math], такие, что [math]\displaystyle{ \langle A_i,X_0\rangle_{\mathbb{S}^n} = b_i }[/math], [math]\displaystyle{ i=1,\ldots,m }[/math]). Тогда имеется оптимальное решение [math]\displaystyle{ y^* }[/math] для двойственной задачи (D-SDP) и

[math]\displaystyle{ \langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}. }[/math]

(ii) Предположим, что двойственная задача (D-SDP) ограничена сверху и строго допустима (то есть [math]\displaystyle{ \sum_{i=1}^m (y_0)_i A_i \prec C }[/math] для некоторого [math]\displaystyle{ y_0\in\R^m }[/math]). Тогда существует оптимальное решение [math]\displaystyle{ X^* }[/math] для прямой задачи (P-SDP) и выполняется равенство из (i).

Примеры

Пример 1

Рассмотрим три случайные переменные [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] и [math]\displaystyle{ C }[/math]. По определению, их коэффициенты корреляции [math]\displaystyle{ \rho_{AB}, \ \rho_{AC}, \rho_{BC} }[/math] допустимы тогда и только тогда, когда

[math]\displaystyle{ \begin{pmatrix} 1 & \rho_{AB} & \rho_{AC} \\ \rho_{AB} & 1 & \rho_{BC} \\ \rho_{AC} & \rho_{BC} & 1 \end{pmatrix} \succeq 0 }[/math]

Предположим, что из каких-то источников (например, из эмпирических или экспериментальных данных) мы знаем, что [math]\displaystyle{ -0,2 \leq \rho_{AB} \leq -0,1 }[/math] и [math]\displaystyle{ 0,4 \leq \rho_{BC} \leq 0,5 }[/math]. Задачу определения наименьшего и наибольшего значений [math]\displaystyle{ \rho_{AC} \ }[/math] можно выписать в виде:

минимизировать/максимизировать [math]\displaystyle{ x_{13} }[/math]

при условиях

[math]\displaystyle{ -0,2 \leq x_{12} \leq -0,1 }[/math]

[math]\displaystyle{ 0,4 \leq x_{23} \leq 0,5 }[/math]

[math]\displaystyle{ x_{11} = x_{22} = x_{33} = 1 \ }[/math]

[math]\displaystyle{ \begin{pmatrix} 1 & x_{12} & x_{13} \\ x_{12} & 1 & x_{23} \\ x_{13} & x_{23} & 1 \end{pmatrix} \succeq 0 }[/math]

Здесь мы принимаем [math]\displaystyle{ \rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} }[/math]. Задачу можно сформулировать как задачу SDP. Мы дополняем неравенства путём расширения матрицы переменных и введения дополнительных переменных, например

[math]\displaystyle{ \mathrm{tr}\left(\left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right)\cdot\left(\begin{array}{cccccc} 1 & x_{12} & x_{13} & 0 & 0 & 0\\ x_{12} & 1 & x_{23} & 0 & 0 & 0\\ x_{13} & x_{23} & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & s_{1} & 0 & 0\\ 0 & 0 & 0 & 0 & s_{2} & 0\\ 0 & 0 & 0 & 0 & 0 & s_{3}\end{array}\right)\right)=x_{12} + s_{1}=-0,1 }[/math]

После решения этой задачи SDP получим минимум и максимум значений [math]\displaystyle{ \rho_{AC} = x_{13} \ }[/math] ([math]\displaystyle{ -0,978 }[/math] и [math]\displaystyle{ 0,872 }[/math] соответственно).

Пример 2

Рассмотрим задачу

минимизировать [math]\displaystyle{ \frac{(c^T x)^2}{d^Tx} }[/math]

при условиях [math]\displaystyle{ Ax +b\geq 0 }[/math],

где предполагается, что [math]\displaystyle{ d^Tx\gt 0 }[/math] при [math]\displaystyle{ Ax+b\geq 0 }[/math].

Введя дополнительную переменную [math]\displaystyle{ t }[/math], перепишем задачу в виде:

минимизировать [math]\displaystyle{ t }[/math]

при условиях [math]\displaystyle{ Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t }[/math]

В этой формулировке целевая функция является линейной функцией от двух переменных ([math]\displaystyle{ x,t }[/math]).

Первое ограничение можно переписать в виде

[math]\displaystyle{ \textbf{diag}(Ax+b)\geq 0 }[/math],

где матрица [math]\displaystyle{ \textbf{diag}(Ax+b) }[/math] является квадратной матрицей со значениями на диагонали, равными элементам вектора [math]\displaystyle{ Ax+b }[/math].

Второе ограничение можно записать в виде

[math]\displaystyle{ td^Tx-(c^Tx)^2\geq 0 }[/math]

Определим матрицу [math]\displaystyle{ D }[/math] следующим образом

[math]\displaystyle{ D=\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right] }[/math]

Мы можем использовать теорию дополнения Шура, чтобы показать, что

[math]\displaystyle{ D \succeq 0 }[/math]

Задача полуоределённого программирования для этой задачи будет иметь вид

минимизировать [math]\displaystyle{ t }[/math]

при условиях [math]\displaystyle{ \left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right] \succeq 0 }[/math]

Пример 3 (Аппроксимационный алгоритм Гоеманса — Уильямсона MAX CUT)

Полуопределённое программирование является важным инструментом для создания аппроксимационных алгоритмов для NP-трудных задач максимизации. Первый аппроксимационный алгоритм, основанный на SDP, предложили Михель Гоеманс и Дэвид Уильямсон. Они изучали задачу MAX CUT: Дан граф G = (V, E), требуется разбить вершины V на две части так, чтобы максимизировать число рёбер соединяющих эти две части. Задачу можно представить как задачу целочисленного квадратичного программирования:

Максимизировать [math]\displaystyle{ \sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2}, }[/math] при условии [math]\displaystyle{ v_i\in\{1,-1\} }[/math] для любого [math]\displaystyle{ i }[/math].

Если только не P = NP, мы не можем решить эту задачу эффективно. Однако Гоеманс и Уильямсон наметили трёхшаговую процедуру для атаки такого рода задач:

1. Ослабляем целочисленную задачу квадратичного программирования до задачи SDP.
2. Решаем задачу SDP (с любой произвольно малой ошибкой [math]\displaystyle{ \epsilon }[/math]).
3. Округляем решение задачи SDP для получения приближённого решения исходной задачи целочисленного квадратичного программирования.

Для задачи MAX CUT наиболее естественным ослаблением является

[math]\displaystyle{ \max \sum_{(i,j) \in E} \frac{1-\langle v_{i}, v_{j}\rangle}{2}, }[/math] для [math]\displaystyle{ \lVert v_i\rVert^2 = 1 }[/math], где максимизация осуществляется по векторам [math]\displaystyle{ \{v_i\} }[/math], а не скалярным целым переменным.

Задача является задачей SDP, поскольку и целевая функция, и ограничения являются линейными функциями от скалярных произведений векторов. Решение задачи SDP даёт набор единичных векторов в [math]\displaystyle{ \mathbf{R^n} }[/math]. Поскольку вектора не обязательно коллинеарны, значение ослабленной задачи может быть только больше значения исходной целочисленной задачи квадратичного программирования. Конечная процедура округления необходима, чтобы получить разбиение. Гоеманс и Уильямсон выбирают случайную гиперплоскость (используя равномерное распределение), проходящую через начало координат и разбивают вершины в зависимости от расположения относительно этой плоскости. Непосредственный анализ показывает, что эта процедура обеспечивает ожидаемый аппроксимационный коэффициент 0,87856 - ε. (Математическое ожидание значения разреза равно сумме по всем рёбрам вероятностей, что ребро входит в разрез и это ожидание пропорционально углу [math]\displaystyle{ \cos^{-1}\langle v_{i}, v_{j}\rangle }[/math] между векторами в конечных вершинах ребра. Если сравнивать эту вероятность с [math]\displaystyle{ (1-\langle v_{i}, v_{j}\rangle)/{2} }[/math], математическое ожидание отношения всегда будет не меньшим 0,87856.) В предположении верности гипотезы уникальной игры можно показать, что аппроксимационный коэффициент этой аппроксимации, главным образом, оптимален.

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

Алгоритмы

Имеется несколько видов алгоритмов для решения задач SDP. Результат работы этих алгоритмов является значение задачи SDP с точностью до [math]\displaystyle{ \epsilon }[/math], которое получается за время, полиномиально зависящее от размера задачи и [math]\displaystyle{ \log (1/\epsilon) }[/math].

Методы внутренней точки

Большинство систем решения базируются на методе внутренней точки (CSDP, SeDuMi, SDPT3, DSDP, SDPA), робастном и эффективном для линейных задач SDP общего вида. Подход ограничен в использовании тем фактом, что алгоритмы являются методами второго порядка и требуют запоминания и разложения больших (и, зачастую, плотных) матриц.

Методы первого порядка

Методы первого порядка для конической оптимизации избегают запоминания и разложения больших матриц Гессе и применимы к существенно большим по размеру задачам, чем методы внутренней точки, за счёт потери в точности. Метод реализован в системе «SCS solver».

Метод пучков

Задача SDP формулируется как задача негладкой оптимизации и решается методом спектрального пучка. Этот подход очень эффективен для частных классов линейных задач SDP.

Другие

Алгоритмы, основанные на методе обобщённого лагранжиана (PENSDP), близки по поведению к методам внутренней точки и могут быть приспособлены для некоторых очень больших задач. Другие алгоритмы используют низкоуровневую информацию и переформулировку задачи SDP как задачи нелинейного программирования (SPDLR).

Приложения

Полуопределённое программирование было использовано для поиска приближённых решений задач комбинаторной оптимизации, таких как решение задачи максимального разреза c аппроксимационным коэффициентом 0,87856. Задачи SDP используется также в геометрии для определения тенсегрити-графов, и появляются в теории управления как линейные матричные неравенства.

Ссылки

• Links to introductions and events in the field
• Lecture notes from László Lovász on Semidefinite Programming