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

Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

18.03.2021

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

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

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

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

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

min x 1 , … , x n ∈ R n ∑ i , j ∈ [ n ] c i , j ( x i ⋅ x j ) {displaystyle {min _{x^{1},ldots ,x^{n}in mathbb {R} ^{n}}}{sum _{i,jin [n]}c_{i,j}(x^{i}cdot x^{j})}} при условиях ∑ i , j ∈ [ n ] a i , j , k ( x i ⋅ x j ) ≤ b k ∀ k . {displaystyle {sum _{i,jin [n]}a_{i,j,k}(x^{i}cdot x^{j})leq b_{k}qquad forall k}.}

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

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

Обозначим через S n {displaystyle mathbb {S} ^{n}} пространство всех n × n {displaystyle n imes n} вещественных симметричных матриц. В этом пространстве имеется скалярное произведение ⟨ A , B ⟩ S n = t r ( A T B ) = ∑ i = 1 , j = 1 n A i j B i j . {displaystyle langle A,B angle _{mathbb {S} ^{n}}={ m {tr}}(A^{T}B)=sum _{i=1,j=1}^{n}A_{ij}B_{ij}.} (где t r {displaystyle { m {tr}}} означает след)

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

min X ∈ S n ⟨ C , X ⟩ S n {displaystyle {min _{Xin mathbb {S} ^{n}}}langle C,X angle _{mathbb {S} ^{n}}} при условиях ⟨ A k , X ⟩ S n ≤ b k , k = 1 , … , m X ⪰ 0 {displaystyle {egin{array}{ll}{displaystyle langle A_{k},X angle _{mathbb {S} ^{n}}leq b_{k},quad k=1,ldots ,m}Xsucceq 0end{array}}}

где элемент i , j {displaystyle i,j} матрицы C {displaystyle C} равно c i , j {displaystyle c_{i,j}} из предыдущей секции, а A k {displaystyle A_{k}} — n × n {displaystyle n imes n} матрица, имеющая в качестве элемента i , j {displaystyle i,j} матрицы значение a i , j , k {displaystyle a_{i,j,k}} из предыдущей секции.

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

min X ∈ S n ⟨ C , X ⟩ S n {displaystyle min _{Xin mathbb {S} ^{n}}}langle C,X angle _{mathbb {S} ^{n}} при условиях ⟨ A k , X ⟩ S n = b k , k = 1 , … , m X ⪰ 0 {displaystyle {egin{array}{ll}langle A_{k},X angle _{mathbb {S} ^{n}}=b_{k},quad k=1,ldots ,mXsucceq 0end{array}}}

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

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

Определения

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

min X ∈ S n ⟨ C , X ⟩ S n {displaystyle min _{Xin mathbb {S} ^{n}}langle C,X angle _{mathbb {S} ^{n}}} при условиях ⟨ A i , X ⟩ S n = b i , i = 1 , … , m X ⪰ 0 {displaystyle {egin{array}{ll}langle A_{i},X angle _{mathbb {S} ^{n}}=b_{i},quad i=1,ldots ,mXsucceq 0end{array}}}

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

max y ∈ R m ⟨ b , y ⟩ R m {displaystyle max _{yin mathbb {R} ^{m}}langle b,y angle _{mathbb {R} ^{m}}} при условиях ∑ i = 1 m y i A i ⪯ C {displaystyle {egin{array}{ll}{displaystyle sum _{i=1}^{m}}y_{i}A_{i}preceq Cend{array}}}

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

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

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

⟨ C , X ⟩ − ⟨ b , y ⟩ = ⟨ C , X ⟩ − ∑ i = 1 m y i b i = ⟨ C , X ⟩ − ∑ i = 1 m y i ⟨ A i , X ⟩ = ⟨ C − ∑ i = 1 m y i A i , X ⟩ ≥ 0 , {displaystyle langle C,X angle -langle b,y angle =langle C,X angle -sum _{i=1}^{m}y_{i}b_{i}=langle C,X angle -sum _{i=1}^{m}y_{i}langle A_{i},X angle =langle C-sum _{i=1}^{m}y_{i}A_{i},X angle geq 0,}

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

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

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

(i) Предположим, что прямая задача (P-SDP) ограничена снизу и строго допустима (то есть существуют X 0 ∈ S n , X 0 ≻ 0 {displaystyle X_{0}in mathbb {S} ^{n},X_{0}succ 0} , такие, что ⟨ A i , X 0 ⟩ S n = b i {displaystyle langle A_{i},X_{0} angle _{mathbb {S} ^{n}}=b_{i}} , i = 1 , … , m {displaystyle i=1,ldots ,m} ). Тогда имеется оптимальное решение y ∗ {displaystyle y^{*}} для двойственной задачи (D-SDP) и

⟨ C , X ∗ ⟩ S n = ⟨ b , y ∗ ⟩ R m . {displaystyle langle C,X^{*} angle _{mathbb {S} ^{n}}=langle b,y^{*} angle _{mathbb {R} ^{m}}.}

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

Примеры

Пример 1

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

( 1 ρ A B ρ A C ρ A B 1 ρ B C ρ A C ρ B C 1 ) ⪰ 0 {displaystyle {egin{pmatrix}1& ho _{AB}& ho _{AC} ho _{AB}&1& ho _{BC} ho _{AC}& ho _{BC}&1end{pmatrix}}succeq 0}

Предположим, что из каких-то источников (например, из эмпирических или экспериментальных данных) мы знаем, что − 0 , 2 ≤ ρ A B ≤ − 0 , 1 {displaystyle -0,2leq ho _{AB}leq -0,1} и 0 , 4 ≤ ρ B C ≤ 0 , 5 {displaystyle 0,4leq ho _{BC}leq 0,5} . Задачу определения наименьшего и наибольшего значений ρ A C   {displaystyle ho _{AC} } можно выписать в виде:

минимизировать/максимизировать x 13 {displaystyle x_{13}} при условиях − 0 , 2 ≤ x 12 ≤ − 0 , 1 {displaystyle -0,2leq x_{12}leq -0,1} 0 , 4 ≤ x 23 ≤ 0 , 5 {displaystyle 0,4leq x_{23}leq 0,5} x 11 = x 22 = x 33 = 1   {displaystyle x_{11}=x_{22}=x_{33}=1 } ( 1 x 12 x 13 x 12 1 x 23 x 13 x 23 1 ) ⪰ 0 {displaystyle {egin{pmatrix}1&x_{12}&x_{13}x_{12}&1&x_{23}x_{13}&x_{23}&1end{pmatrix}}succeq 0}

Здесь мы принимаем ρ A B = x 12 ,   ρ A C = x 13 ,   ρ B C = x 23 {displaystyle ho _{AB}=x_{12}, ho _{AC}=x_{13}, ho _{BC}=x_{23}} . Задачу можно сформулировать как задачу SDP. Мы дополняем неравенства путём расширения матрицы переменных и введения дополнительных переменных, например

t r ( ( 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 ) ⋅ ( 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 ) ) = x 12 + s 1 = − 0 , 1 {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 получим минимум и максимум значений ρ A C = x 13   {displaystyle ho _{AC}=x_{13} } ( − 0 , 978 {displaystyle -0,978} и 0 , 872 {displaystyle 0,872} соответственно).

Пример 2

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

минимизировать ( c T x ) 2 d T x {displaystyle {frac {(c^{T}x)^{2}}{d^{T}x}}} при условиях A x + b ≥ 0 {displaystyle Ax+bgeq 0} ,

где предполагается, что d T x > 0 {displaystyle d^{T}x>0} при A x + b ≥ 0 {displaystyle Ax+bgeq 0} .

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

минимизировать t {displaystyle t} при условиях A x + b ≥ 0 , ( c T x ) 2 d T x ≤ t {displaystyle Ax+bgeq 0,,{frac {(c^{T}x)^{2}}{d^{T}x}}leq t}

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

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

diag ( A x + b ) ≥ 0 {displaystyle { extbf {diag}}(Ax+b)geq 0} ,

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

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

t d T x − ( c T x ) 2 ≥ 0 {displaystyle td^{T}x-(c^{T}x)^{2}geq 0}

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

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

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

D ⪰ 0 {displaystyle Dsucceq 0}

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

минимизировать t {displaystyle t} при условиях [ diag ( A x + b ) 0 0 0 t c T x 0 c T x d T x ] ⪰ 0 {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 (Аппроксимационный алгоритм Гоеманса — Уильямсона MAX CUT)

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

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

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

  • Ослабляем целочисленную задачу квадратичного программирования до задачи SDP.
  • Решаем задачу SDP (с любой произвольно малой ошибкой ϵ {displaystyle epsilon } ).
  • Округляем решение задачи SDP для получения приближённого решения исходной задачи целочисленного квадратичного программирования.
  • Для задачи MAX CUT наиболее естественным ослаблением является

    max ∑ ( i , j ) ∈ E 1 − ⟨ v i , v j ⟩ 2 , {displaystyle max sum _{(i,j)in E}{frac {1-langle v_{i},v_{j} angle }{2}},} для ‖ v i ‖ 2 = 1 {displaystyle lVert v_{i} Vert ^{2}=1} , где максимизация осуществляется по векторам { v i } {displaystyle {v_{i}}} , а не скалярным целым переменным.

    Задача является задачей SDP, поскольку и целевая функция, и ограничения являются линейными функциями от скалярных произведений векторов. Решение задачи SDP даёт набор единичных векторов в R n {displaystyle mathbf {R^{n}} } . Поскольку вектора не обязательно коллинеарны, значение ослабленной задачи может быть только больше значения исходной целочисленной задачи квадратичного программирования. Конечная процедура округления необходима, чтобы получить разбиение. Гоеманс и Уильямсон выбирают случайную гиперплоскость (используя равномерное распределение), проходящую через начало координат и разбивают вершины в зависимости от расположения относительно этой плоскости. Непосредственный анализ показывает, что эта процедура обеспечивает ожидаемый аппроксимационный коэффициент 0,87856 - ε. (Математическое ожидание значения разреза равно сумме по всем рёбрам вероятностей, что ребро входит в разрез и это ожидание пропорционально углу cos − 1 ⁡ ⟨ v i , v j ⟩ {displaystyle cos ^{-1}langle v_{i},v_{j} angle } между векторами в конечных вершинах ребра. Если сравнивать эту вероятность с ( 1 − ⟨ v i , v j ⟩ ) / 2 {displaystyle (1-langle v_{i},v_{j} angle )/{2}} , математическое ожидание отношения всегда будет не меньшим 0,87856.) В предположении верности гипотезы уникальной игры можно показать, что аппроксимационный коэффициент этой аппроксимации, главным образом, оптимален.

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

    Алгоритмы

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

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

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

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

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

    Метод пучков

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

    Другие

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

    Приложения

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


    Имя:*
    E-Mail:
    Комментарий: