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

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

Полуопределенное программирование - относительно новая область оптимизации, которая вызывает растущий интерес по нескольким причинам. Многие практические задачи исследования операций и комбинаторной оптимизации могут быть смоделированы или аппроксимированы как задачи полуопределенного программирования. В теории автоматического управления 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 \ \\ конец {массив}}}$

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

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

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

Обозначим через пространство всех действительных симметрических матриц. Пространство оборудовано внутренним продуктом (где обозначает след ) ${\ Displaystyle \ mathbb {S} ^ {п}}$${\ Displaystyle п \ раз п}$${\ displaystyle {\ rm {tr}}}$${\ displaystyle \ langle A, B \ rangle _ {\ mathbb {S} ^ {n}} = {\ rm {tr}} (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 _ {\ mathbb {S} ^ { n}} \\ {\ text {при условии}} & \ langle A_ {k}, X \ rangle _ {\ mathbb {S} ^ {n}} \ leq b_ {k}, \ quad k = 1, \ ldots, m \\ & X \ successq 0. \ end {array}}}$

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

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

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {при условии}} & \ langle A_ {k}, X \ rangle _ {\ mathbb {S} ^ {n}} = b_ {k}, \ quad k = 1, \ ldots , m \\ & X \ successq 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 О (п ^ {3})}$

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

Определения

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

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {при условии}} & \ langle A_ {i}, X \ rangle _ {\ mathbb {S} ^ {n}} = b_ {i}, \ quad i = 1, \ ldots , m \\ & X \ successq 0 \ end {array}}}$

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

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ max _ {y \ in \ mathbb {R} ^ {m}}} & \ langle b, y \ rangle _ {\ mathbb {R} ^ { m}} \\ {\ text {при условии}} & {\ displaystyle \ sum _ {i = 1} ^ {m}} y_ {i} A_ {i} \ prevq C \ end {array}}}$

где для любых двух матриц и , значит . ${\ displaystyle P}$${\ displaystyle Q}$${\ Displaystyle P \ successq Q}$${\ Displaystyle PQ \ successq 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) ограничена снизу и строго допустима (т. е. существует такая, что , ). Тогда есть оптимальное решение для (D-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 я = 1, \ ldots, м}$${\ displaystyle y ^ {*}}$

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

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

Примеры

Пример 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}} \ successq 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 {\ begin {pmatrix} 1 & x_ {12} & x_ {13} \\ x_ {12} & 1 & x_ {23} \\ x_ {13} & x_ {23} & 1 \ end {pmatrix}} \ successq 0.}$

Мы приступили к получению ответа. Это можно сформулировать с помощью 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 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0} \ end \ 0 & 0 & 0} \ end \ 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 дает минимальное и максимальное значения as и соответственно. ${\ 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 \ successq 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 \ конец {массив}} \ right] \ successq 0}$

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

Полуопределенные программы являются важными инструментами для разработки алгоритмов аппроксимации для NP-сложных задач максимизации. Алгоритм первого приближения, основанный на SDP, был разработан Мишелем Гоэмансом и Дэвидом П. Уильямсоном (JACM, 1995). Они изучили задачу о максимальном разрезе : для данного графа 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 применялись для разработки многочисленных алгоритмов аппроксимации. Недавно Прасад Рагхавендра разработал общую схему для задач удовлетворения ограничений, основанную на гипотезе уникальных игр .

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

использованная литература

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

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

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