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

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

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

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

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

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

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

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

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

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

Обозначим через ${displaystyle mathbb {S} ^{n}}$ пространство всех ${displaystyle n imes n}$ вещественные симметричные матрицы. Помещение оборудовано внутренний продукт (куда ${displaystyle {m {tr}}}$ обозначает след )${displaystyle langle A,Bangle _{mathbb {S} ^{n}}={m {tr}}(A^{T}B)=sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}$

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

${displaystyle {egin{array}{rl}{displaystyle min _{Xin mathbb {S} ^{n}}}&langle C,Xangle _{mathbb {S} ^{n}}{ ext{subject to}}&langle A_{k},Xangle _{mathbb {S} ^{n}}leq b_{k},quad k=1,ldots ,m&Xsucceq 0end{array}}}$

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

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

${displaystyle {egin{array}{rl}{displaystyle min _{Xin mathbb {S} ^{n}}}&langle C,Xangle _{mathbb {S} ^{n}}{ ext{subject to}}&langle A_{k},Xangle _{mathbb {S} ^{n}}=b_{k},quad k=1,ldots ,m&Xsucceq 0.end{array}}}$

Для удобства SDP может быть указан в несколько иной, но эквивалентной форме. Например, линейные выражения с неотрицательными скаляр переменные могут быть добавлены в спецификацию программы. Это остается SDP, потому что каждая переменная может быть включена в матрицу. ${displaystyle X}$ как диагональный вход (${displaystyle X_{ii}}$ для некоторых ${displaystyle i}$). Чтобы гарантировать, что ${displaystyle X_{ii}geq 0}$, ограничения ${displaystyle X_{ij}=0}$ можно добавить для всех ${displaystyle jeq 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 {egin{array}{rl}{displaystyle min _{Xin mathbb {S} ^{n}}}&langle C,Xangle _{mathbb {S} ^{n}}{ ext{subject to}}&langle A_{i},Xangle _{mathbb {S} ^{n}}=b_{i},quad i=1,ldots ,m&Xsucceq 0end{array}}}$

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

${displaystyle {egin{array}{rl}{displaystyle max _{yin mathbb {R} ^{m}}}&langle b,yangle _{mathbb {R} ^{m}}{ ext{subject to}}&{displaystyle sum _{i=1}^{m}}y_{i}A_{i}preceq Cend{array}}}$

где для любых двух матриц ${displaystyle P}$ и ${displaystyle Q}$, ${displaystyle Psucceq Q}$ средства ${displaystyle P-Qsucceq 0}$.

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

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

${displaystyle langle C,Xangle -langle b,yangle =langle C,Xangle -sum _{i=1}^{m}y_{i}b_{i}=langle C,Xangle -sum _{i=1}^{m}y_{i}langle A_{i},Xangle =langle C-sum _{i=1}^{m}y_{i}A_{i},Xangle 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}angle _{mathbb {S} ^{n}}=b_{i}}$, ${displaystyle i=1,ldots ,m}$Тогда есть оптимальное решение ${displaystyle y^{*}}$ в (D-SDP) и

${displaystyle langle C,X^{*}angle _{mathbb {S} ^{n}}=langle b,y^{*}angle _{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 ho _{AB}, ho _{AC},ho _{BC}}$ действительны тогда и только тогда, когда

${displaystyle {egin{pmatrix}1&ho _{AB}&ho _{AC}ho _{AB}&1&ho _{BC}ho _{AC}&ho _{BC}&1end{pmatrix}}succeq 0,}$

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

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

при условии

${displaystyle -0.2leq x_{12}leq -0.1}$

${displaystyle 0.4leq x_{23}leq 0.5}$

${displaystyle {egin{pmatrix}1&x_{12}&x_{13}x_{12}&1&x_{23}x_{13}&x_{23}&1end{pmatrix}}succeq 0.}$

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

${displaystyle mathrm {tr} left(left({egin{array}{cccccc}0&1&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&0end{array}}ight)cdot left({egin{array}{cccccc}1&x_{12}&x_{13}&0&0&0x_{12}&1&x_{23}&0&0&0x_{13}&x_{23}&1&0&0&0�&0&0&s_{1}&0&0�&0&0&0&s_{2}&0�&0&0&0&0&s_{3}end{array}}ight)ight)=x_{12}+s_{1}=-0.1}$

Решение этого SDP дает минимальные и максимальные значения ${displaystyle ho _{AC}=x_{13} }$ в качестве ${displaystyle -0.978}$ и ${displaystyle 0.872}$ соответственно.

Пример 2

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

свести к минимуму ${displaystyle {frac {(c^{T}x)^{2}}{d^{T}x}}}$

при условии ${displaystyle Ax+bgeq 0}$

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

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

свести к минимуму ${displaystyle t}$

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

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

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

${displaystyle { extbf {diag}}(Ax+b)geq 0}$

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

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

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

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

${displaystyle D=left[{egin{array}{cc}t&c^{T}xc^{T}x&d^{T}xend{array}}ight]}$

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

${displaystyle Dsucceq 0}$

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

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

свести к минимуму ${displaystyle t}$

при условии ${displaystyle left[{egin{array}{ccc}{ extbf {diag}}(Ax+b)&0&0�&t&c^{T}x�&c^{T}x&d^{T}xend{array}}ight]succeq 0}$

Пример 3 (алгоритм аппроксимации максимального разреза Гоэманса – Вильямсона)

Полуопределенные программы - важные инструменты для разработки приближенных алгоритмов для NP-сложных задач максимизации. Алгоритм первого приближения на основе SDP обусловлен Мишель Гоэманс и Дэвид П. Уильямсон (JACM, 1995). Они изучили проблема максимальной резки: Учитывая график грамм = (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}angle }{2}},}$ такой, что ${displaystyle lVert v_{i}Vert ^{2}=1}$, где максимизация идет по векторам ${displaystyle {v_{i}}}$ вместо целочисленных скаляров.

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Примерные методы

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

Приложения

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

Рекомендации

1. Рагхавендра, П. 2008. Оптимальные алгоритмы и результаты неприблизимости для каждого CSP?. В материалах 40-го ежегодного симпозиума ACM по теории вычислений (Виктория, Британская Колумбия, Канада, 17–20 мая 2008 г.). STOC '08. ACM, Нью-Йорк, штат Нью-Йорк, 245–254.
2. Чжу, Юйцзысюань; Патаки, Габор; Тран-Динь, Куок (2019), «Sieve-SDP: простой алгоритм сокращения лица для предварительной обработки полуопределенных программ», Математическое программирование вычислений, 11 (3): 503–586, arXiv:1710.08954, Дои:10.1007 / s12532-019-00164-4, ISSN  1867-2949, S2CID  53645581
3. Брендан О'Донохью, Эрик Чу, Нил Парих, Стивен Бойд, «Коническая оптимизация с помощью расщепления оператора и однородного самодуального вложения», Журнал теории оптимизации и приложений, 2016, стр 1042-1068,https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.
4. Вэнь, Зайвэнь, Дональд Гольдфарб и Вотао Инь. «Переменные направления дополняют методы Лагранжа для полуопределенного программирования». Математическое программирование вычислений 2.3-4 (2010): 203-230.
5. Монтейро, Ренато Д. С.; Бюрер, Самуэль (2003), "Алгоритм нелинейного программирования для решения полуопределенных программ с помощью факторизации низкого ранга", Математическое программирование, 95 (2): 329–357, CiteSeerX  10.1.1.682.1520, Дои:10.1007 / s10107-002-0352-8, ISSN  1436-4646, S2CID  7691228
6. Castañeda, O .; Гольдштейн, Т .; Студер, К. (декабрь 2016 г.). «Обнаружение данных в больших беспроводных системах с множеством антенн с помощью приближенной полуопределенной релаксации». IEEE Transactions on Circuits and Systems I: Regular Papers. 63 (12): 2334–2346. Дои:10.1109 / TCSI.2016.2607198. ISSN  1558-0806.

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

внешняя ссылка

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