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

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

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

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

Начальная мотивация

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

${\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}k\\\end{array}}$

где $c_{i,j},a_{i,j,k}$и $b_{k}$ являются действительными числами и $x^{i}\cdot x^{j}$ является произведением скалярным $x^{i}$ и $x^{j}$.

Эквивалентные составы

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

Обозначим через $\mathbb {S} ^{n}$ пространство всего $n\times n$ действительные симметричные матрицы. Пространство оснащено внутренним продуктом (где ${\rm {trace}}$ обозначает след ):

$\langle A,B\rangle :={\rm {trace}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.$

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

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle \leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}$

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

Обратите внимание, что если мы соответствующим образом добавим слабые переменные , этот SDP можно преобразовать к эквациональной форме :

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}$

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

Связь с другими задачами оптимизации

Пространство полуопределенных матриц представляет собой выпуклый конус . Следовательно, SDP — это частный случай конической оптимизации , которая является частным случаем выпуклой оптимизации.

Когда матрица C диагональна, скалярные произведения < , X > эквивалентны векторному произведению диагонали C и диагонали X. C Аналогично, когда матрицы A _k диагональны, соответствующие скалярные произведения эквивалентны векторным произведениям. В этих векторных произведениях используются только диагональные элементы X , поэтому мы можем добавить ограничения, приравнивающие недиагональные элементы X к 0. Условие $X\succeq 0$ тогда эквивалентно условию, что все диагональные элементы X неотрицательны. Затем полученная SDP становится линейной программой , в которой переменные являются диагональными элементами X .

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

Определения

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

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{i},X\rangle =b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}$

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

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&b^{T}y\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}$

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

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

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

$\langle C,X\rangle -b^{T}y=\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 удовлетворяет строгой двойственности; в общем случае значение двойного SDP может лежать строго ниже значения основного, а P-SDP и D-SDP удовлетворяют следующим свойствам:

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

$\langle C,X^{*}\rangle =b^{T}y^{*}.$

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

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

Примеры

Пример 1

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

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

Эта матрица называется корреляционной матрицей . Предположим, что мы знаем из некоторых предварительных знаний (например, эмпирических результатов эксперимента), что $-0.2\leq \rho _{AB}\leq -0.1$ и $0.4\leq \rho _{BC}\leq 0.5$. Задача определения наименьшего и наибольшего значений, которые $\rho _{AC}\$ можно взять:

${\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end{array}}$

Мы устанавливаем $\rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}$ чтобы получить ответ. Это может быть сформулировано СДП. Мы справляемся с ограничениями-неравенствами, дополняя матрицу переменных и вводя слабые переменные , например

$\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 дает минимальное и максимальное значения $\rho _{AC}=x_{13}\$ как $-0.978$ и $0.872$ соответственно.

Пример 2

Рассмотрите проблему

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

при условии $Ax+b\geq 0$

где мы предполагаем, что $d^{T}x>0$ в любое время $Ax+b\geq 0$.

Введение вспомогательной переменной $t$ проблему можно переформулировать:

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

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

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

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

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

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

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

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

Определение $D$ следующее

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

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

$D\succeq 0$

(Бойд и Ванденберге, 1996 г.)

Полуопределенная программа, связанная с этой задачей, имеет вид

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

при условии $\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 (алгоритм аппроксимации максимального разреза Гоеманса – Вильямсона)

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

Максимизировать $\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},$ такой, что каждый $v_{i}\in \{1,-1\}$.

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

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

Для максимального разреза самое естественное расслабление — это

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

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

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

Другие приложения

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

Сложность во время выполнения

Полуопределенная задача осуществимости (SDF) — это следующая проблема принятия решения : учитывая SDP, решите, имеет ли она хотя бы одно допустимое решение. Точная сложность этой проблемы во время выполнения неизвестна (по состоянию на 1997 год). Однако Рамана доказал следующее:

• В модели машины Тьюринга SDF находится в NP тогда и только тогда, когда она находится в co-NP. Следовательно, SDF не является NP-полной, если NP = coNP.
• В модели машины Блюма – Шуба – Смейла SDF находится на пересечении NP и co-NP.

Алгоритмы решения СДП

Существует несколько типов алгоритмов решения SDP. Эти алгоритмы выводят значение SDP с точностью до аддитивной ошибки. $\epsilon$ за время, полиномиальное по размеру описания программы и $\log(1/\epsilon )$.

Эллипсоидный метод

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

${\begin{array}{rl}{\displaystyle \max _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}$

Пусть L — аффинное подпространство матриц в S ^н удовлетворение m эквациональных ограничений; поэтому SDP можно записать как: $\max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0$. Предположим, что все коэффициенты в SDP являются рациональными числами. Пусть R — явно заданная верхняя граница максимальной нормы Фробениуса допустимого решения, а ε> 0 — константа. Матрица X в S ^н называется ε-глубокой , если каждая матрица Y из L с расстоянием Фробениуса не более ε от X удовлетворяет условию выполнимости $Y\succeq 0$. Обозначим $v_{deep}:=\sup\{\langle C,X\rangle :X{\text{ is }}\epsilon {\text{-deep}}\}$. Эллипсоид возвращает один из следующих выходных данных:

• Матрица X* в L (т. е. точно удовлетворяющая всем ограничениям линейного равенства), такая, что расстояние Фробениуса между X* и некоторым допустимым решением не превышает ε (т. е. приблизительно удовлетворяет ограничению-неравенству $X\succeq 0$), и $\langle C,X^{*}\rangle \geq v_{deep}-\epsilon$ (то есть приблизительно оптимальное целевое значение).
• Свидетельство о том, что задача не имеет ε-глубинных решений (т. е. задача приближенно неразрешима).

Время выполнения является полиномиальным в двоичной кодировке входных данных и в log(R/ ε ) в модели машины Тьюринга .

Обратите внимание, что, вообще говоря, R может быть дважды экспоненциальным по n. В этом случае гарантия времени выполнения метода эллипсоида является экспоненциальной по n . Но в большинстве приложений R не так уж велик. В этих случаях метод эллипсоида является единственным известным методом, который гарантирует полиномиальное время выполнения в модели машины Тьюринга. Но на практике его производительность не так хороша.

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

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

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

Методы первого порядка конической оптимизации позволяют избежать вычисления, хранения и факторизации большой матрицы Гессе и масштабируются для решения гораздо более серьезных задач, чем методы внутренней точки, за счет некоторой потери точности. Метод первого порядка реализован в решателе расщепляющегося конуса (SCS). Другим методом первого порядка является метод множителей переменного направления (ADMM). Этот метод требует на каждом шаге проецирования на конус полуопределенных матриц.

Пакетный метод

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

Другие методы решения

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

Приблизительные методы

Также были предложены алгоритмы, позволяющие приближенно решать задачи SDP. Основная цель таких методов — добиться снижения сложности в приложениях, где приближенных решений достаточно, а сложность должна быть минимальной. Известным методом, который использовался для обнаружения данных в беспроводных системах с несколькими входами и множеством выходов (MIMO), является треугольная аппроксимационная полуопределенная релаксация (TASER), который работает с факторами разложения Холецкого полуопределенной матрицы вместо полуопределенной матрицы. Этот метод вычисляет приближенные решения для задачи типа max-cut, которые часто сравнимы с решениями точных решателей, но всего за 10-20 итераций алгоритма. Хазан разработал приближенный алгоритм решения СДП с дополнительным ограничением, заключающимся в том, что след матрицы переменных должен быть равен 1.

Алгоритмы предварительной обработки

Алгоритмы уменьшения лица — это алгоритмы, используемые для предварительной обработки проблем SDP путем проверки ограничений проблемы. Их можно использовать для

• Обнаружить отсутствие строгого технико-экономического обоснования;
• Удалить лишние строки и столбцы;
• Уменьшите размер переменной матрицы.

См. также

• Проблема суммы квадратного корня - частный случай проблемы осуществимости SDP.

Ссылки

• Ливен Ванденберге, Стивен Бойд, «Полуопределенное программирование», SIAM Review 38, март 1996 г., стр. 49–95. PDF
• Моник Лоран, Франц Рендл, «Полуопределенное программирование и целочисленное программирование», отчет PNA-R0210, CWI, Амстердам, апрель 2002 г., оптимизация онлайн.
• Э. де Клерк, «Аспекты полуопределенного программирования: алгоритмы внутренних точек и избранные приложения», Kluwer Academic Publishers, март 2002 г., ISBN   1-4020-0547-4 .
• Роберт М. Фройнд, «Введение в полуопределенное программирование (SDP), SDP-Введение

Внешние ссылки

• Ссылки на презентации и события в этой области
• Конспект лекций Ласло Ловаса по полуопределенному программированию