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

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

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

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

${\displaystyle {\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{при условии}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ для всех }}k\\\end{array}}}$

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

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

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

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

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

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

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

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

${\displaystyle {\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, поскольку каждая переменная может быть включена в матрицу как диагональная запись ( для некоторых ). Чтобы гарантировать, что , ограничения могут быть добавлены для всех . В качестве другого примера отметим, что для любой положительной полуопределенной матрицы , существует набор векторов, такой что , запись является скалярным произведением и . Поэтому SDP часто формулируются в терминах линейных выражений на скалярных произведениях векторов. Учитывая решение SDP в стандартной форме, векторы могут быть восстановлены со временем (например, с помощью неполного разложения Холецкого X).${\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}}$${\displaystyle \{v_{i}\}}$${\displaystyle O(n^{3})}$

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

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

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

${\displaystyle {\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) как

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

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

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

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

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

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

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

Рассмотрим три случайные величины , и . Заданный набор коэффициентов корреляции возможен тогда и только тогда, когда${\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 {\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}}}$

Мы устанавливаем , чтобы получить ответ. Это может быть сформулировано с помощью SDP. Мы обрабатываем ограничения неравенства, увеличивая переменную матрицу и вводя переменные слэка , например${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}}$

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

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

минимизировать${\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}$

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

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

минимизировать${\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Также были предложены алгоритмы, которые решают SDP приближенно. Основной целью таких методов является достижение меньшей сложности в приложениях, где приближенные решения достаточны, а сложность должна быть минимальной. Известным методом, который использовался для обнаружения данных в беспроводных системах с несколькими входами и несколькими выходами (MIMO), является метод треугольной аппроксимации SEmidefinite Relaxation (TASER) ^[12] , который работает с коэффициентами разложения Холецкого полуопределенной матрицы вместо полуопределенной матрицы. Этот метод вычисляет приближенные решения для задачи типа максимального разреза, которые часто сопоставимы с решениями точных решателей, но всего за 10-20 итераций алгоритма. Хазан ^[13] разработал приближенный алгоритм для решения SDP с дополнительным ограничением, что след матрицы переменных должен быть равен 1.

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

• Выявить отсутствие строгой осуществимости;
• Удалить лишние строки и столбцы;
• Уменьшить размер переменной матрицы. ^[14]

• Задача о сумме квадратных корней — частный случай задачи осуществимости SDP.

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

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