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

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

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

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

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

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

$\underset{x^1,\dots ,x^n\in {ℝ}^n}{\min }\sum _{i,j\in [n]}{c}_{i,j}(x^i\cdot x^j)$

при условиях $\sum _{i,j\in [n]}{a}_{i,j,k}(x^i\cdot x^j)\le b_k\mathrm{\forall }k.$

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

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

Обозначим через ${𝕊}^n$ пространство всех $n\times n$ вещественных симметричных матриц. В этом пространстве имеется скалярное произведение $⟨A,B{⟩}_{{𝕊}^n}=\mathrm{t}\mathrm{r}(A^{T}B)=\sum _{i=1,j=1}^n{A}_{ij}{B}_{ij}.$ (где $\mathrm{t}\mathrm{r}$ означает след)

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

$\underset{X\in {𝕊}^n}{\min }⟨C,X{⟩}_{{𝕊}^n}$

при условиях $\begin{array}{c}⟨A_k,X{⟩}_{{𝕊}^n}\le b_k,k=1,\dots ,m\\ X⪰0\end{array}$

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

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

$\underset{X\in {𝕊}^n}{\min }⟨C,X{⟩}_{{𝕊}^n}$

при условиях $\begin{array}{c}⟨A_k,X{⟩}_{{𝕊}^n}=b_k,k=1,\dots ,m\\ X⪰0\end{array}$

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

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

Определения

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

$\underset{X\in {𝕊}^n}{\min }⟨C,X{⟩}_{{𝕊}^n}$

при условиях $\begin{array}{c}⟨A_i,X{⟩}_{{𝕊}^n}=b_i,i=1,\dots ,m\\ X⪰0\end{array}$

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

$\underset{y\in {ℝ}^m}{\max }⟨b,y{⟩}_{{ℝ}^m}$

при условиях $\begin{array}{c}\sum _{i=1}^m{y}_i{A}_i⪯C\end{array}$

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

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

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

$⟨C,X⟩-⟨b,y⟩=⟨C,X⟩-\sum _{i=1}^m{y}_i{b}_i=⟨C,X⟩-\sum _{i=1}^m{y}_i⟨A_i,X⟩=⟨C-\sum _{i=1}^m{y}_i{A}_i,X⟩\ge 0,$

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

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

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

(i) Предположим, что прямая задача (P-SDP) ограничена снизу и строго допустима (то есть существуют $X_0\in {𝕊}^n,X_0\succ 0$, такие, что $⟨A_i,X_0{⟩}_{{𝕊}^n}=b_i$, $i=1,\dots ,m$). Тогда имеется оптимальное решение $y^{*}$ для двойственной задачи (D-SDP) и

$⟨C,X^{*}{⟩}_{{𝕊}^n}=⟨b,y^{*}{⟩}_{{ℝ}^m}.$

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

Примеры

Пример 1

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

$\left(\begin{array}{ccc}1& {\rho }_{AB}& {\rho }_{AC}\\ {\rho }_{AB}& 1& {\rho }_{BC}\\ {\rho }_{AC}& {\rho }_{BC}& 1\end{array}\right)⪰0$

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

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

при условиях

$-0,2\le x_{12}\le -0,1$

$0,4\le x_{23}\le 0,5$

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

$\left(\begin{array}{ccc}1& x_{12}& x_{13}\\ x_{12}& 1& x_{23}\\ x_{13}& x_{23}& 1\end{array}\right)⪰0$

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

$\mathrm{t}\mathrm{r}(\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))=x_{12}+s_1=-0,1$

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

Пример 2

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

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

при условиях $Ax+b\ge 0$,

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

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

минимизировать $t$

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

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

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

$\mathbf{\text{diag}}(Ax+b)\ge 0$,

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

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

$t{d}^{T}x-(c^{T}x{)}^2\ge 0$

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

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

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

$D⪰0$ Шаблон:Sfn

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

минимизировать $t$

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

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

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

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

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

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

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

$\max \sum _{(i,j)\in E}\frac{1-⟨v_i,v_j⟩}{2},$ для $\Vert v_i{\Vert }^2=1$, где максимизация осуществляется по векторам $\{v_i\}$, а не скалярным целым переменным.

Задача является задачей SDP, поскольку и целевая функция, и ограничения являются линейными функциями от скалярных произведений векторов. Решение задачи SDP даёт набор единичных векторов в ${𝐑}^{𝐧}$. Поскольку вектора не обязательно коллинеарны, значение ослабленной задачи может быть только больше значения исходной целочисленной задачи квадратичного программирования. Конечная процедура округления необходима, чтобы получить разбиение. Гоеманс и Уильямсон выбирают случайную гиперплоскость (используя равномерное распределение), проходящую через начало координат и разбивают вершины в зависимости от расположения относительно этой плоскости. Непосредственный анализ показывает, что эта процедура обеспечивает ожидаемый аппроксимационный коэффициент 0,87856 - ε. (Математическое ожидание значения разреза равно сумме по всем рёбрам вероятностей, что ребро входит в разрез и это ожидание пропорционально углу ${\cos }^{-1}⟨v_i,v_j⟩$ между векторами в конечных вершинах ребра. Если сравнивать эту вероятность с $(1-⟨v_i,v_j⟩)/2$, математическое ожидание отношения всегда будет не меньшим 0,87856.) В предположении верности Шаблон:Не переведено 5 можно показать, что аппроксимационный коэффициент этой аппроксимации, главным образом, оптимален.

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

Алгоритмы

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

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

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

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

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

Метод пучков

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

Другие

Алгоритмы, основанные на Шаблон:Не переведено 5 (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