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

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

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

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

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

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

${\displaystyle {\min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}{\sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}}$

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

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

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

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

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

${\displaystyle {\min _{X\in \mathbb {S} ^{n}}}\langle C,X\rangle _{\mathbb {S} ^{n}}}$

при условиях ${\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}}}$

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

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

${\displaystyle \min _{X\in \mathbb {S} ^{n}}}\langle C,X\rangle _{\mathbb {S} ^{n}}$

при условиях ${\displaystyle {\begin{array}{ll}\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}}$

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

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

Определения

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

${\displaystyle \min _{X\in \mathbb {S} ^{n}}\langle C,X\rangle _{\mathbb {S} ^{n}}}$

при условиях ${\displaystyle {\begin{array}{ll}\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\X\succeq 0\end{array}}}$

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

${\displaystyle \max _{y\in \mathbb {R} ^{m}}\langle b,y\rangle _{\mathbb {R} ^{m}}}$

при условиях ${\displaystyle {\begin{array}{ll}{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}}$

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

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

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

${\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,}$

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

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

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

(i) Предположим, что прямая задача (P-SDP) ограничена снизу и строго допустима (то есть существуют ${\displaystyle X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0}$, такие, что ${\displaystyle \langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_{i}}$, ${\displaystyle i=1,\ldots ,m}$). Тогда имеется оптимальное решение ${\displaystyle y^{*}}$ для двойственной задачи (D-SDP) и

${\displaystyle \langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}.}$

(ii) Предположим, что двойственная задача (D-SDP) ограничена сверху и строго допустима (то есть ${\displaystyle \sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C}$ для некоторого ${\displaystyle y_{0}\in \mathbb {R} ^{m}}$). Тогда существует оптимальное решение ${\displaystyle X^{*}}$ для прямой задачи (P-SDP) и выполняется равенство из (i).

Примеры

Пример 1

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

${\displaystyle {\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0}$

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

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

при условиях

${\displaystyle -0,2\leq x_{12}\leq -0,1}$

${\displaystyle 0,4\leq x_{23}\leq 0,5}$

${\displaystyle x_{11}=x_{22}=x_{33}=1\ }$

${\displaystyle {\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0}$

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

${\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}$

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

Пример 2

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

минимизировать ${\displaystyle {\frac {(c^{T}x)^{2}}{d^{T}x}}}$

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

где предполагается, что ${\displaystyle d^{T}x>0}$ при ${\displaystyle Ax+b\geq 0}$.

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

минимизировать ${\displaystyle t}$

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

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

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

${\displaystyle {\textbf {diag}}(Ax+b)\geq 0}$,

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

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

${\displaystyle td^{T}x-(c^{T}x)^{2}\geq 0}$

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

${\displaystyle D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]}$

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

${\displaystyle D\succeq 0}$ [1]

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

минимизировать ${\displaystyle t}$

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

Метод пучков

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

Другие

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

Приложения

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

Примечания

1. Boyd, Vandenberghe, 1996.
2. Goemans, Williamson, 1995.
3. Raghavendra, 2008, с. 245-254.

Литература

• Lieven Vandenberghe, Stephen Boyd. Semidefinite Programming // SIAM Review 38. — 1996. — Март. — С. 49—95.
• Monique Laurent, Franz Rendl. Semidefinite Programming and Integer Programming/Report PNA-R0210, CWI, Amsterdam. — 2002. — Апрель.
• E. de Klerk. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. — Kluwer Academic Publishers, 2002. — ISBN 1-4020-0547-4.
• P. Raghavendra. Optimal algorithms and inapproximability results for every CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17–20, 2008). STOC '08. — New York, NY: ACM, 2008. — С. 245-254.
• Robert M. Freund. Introduction to Semidefinite Programming (SDP).
• Michel X. Goemans, David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming // JACM. — 1995. — Ноябрь (т. 42, вып. 6). — С. 1115—1145. — doi:10.1145/227683.227684.

Ссылки

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