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

редактировать

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

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

Содержание

1 Мотивация и определение
- 1.1 Исходная мотивация
- 1.2 Эквивалентные формулировки
2 Теория двойственности
- 2.1 Определения
- 2.2 Слабая двойственность
- 2.3 Сильная двойственность
3 Примеры
- 3.1 Пример 1
- 3.2 Пример 2
- 3.3 Пример 3 (алгоритм аппроксимации максимального разреза Гоэманса – Вильямсона)
4 Алгоритмы
- 4.1 Методы внутренней точки
- 4.2 Методы первого порядка
- 4.3 Пакетный метод
- 4.4 Другие методы решения
5 Приложения
6 Ссылки
7 Внешние ссылки

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

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

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

min x 1,…, xn ∈ R n ∑ i, j ∈ [n] ci, j (xi ⋅ xj) при условии ∑ я, j ∈ [n] ai, j, k (xi ⋅ xj) ≤ bk для всех k {\ 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 {\ 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}}}

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

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

An $n × n {\ displaystyle n \ times n}$ $n \ times n$ матрица $M {\ displaystyle M}$ $M$ - это называется положительно полуопределенным, если это матрица Грамиана некоторых векторов (т.е. если существуют векторы $x 1,…, xn {\ displaystyle x ^ {1}, \ ldots, x ^ {n}}$ $x ^ {1}, \ ldots, x ^ {n}$ такие, что $mi, j = xi ⋅ xj { \ displaystyle m_ {i, j} = x ^ {i} \ cdot x ^ {j}}$ $m _ {{i, j}} = x ^ {i} \ cdot x ^ {j}$ для всех $i, j {\ displaystyle i, j}$ $i, j$ ). В таком случае мы обозначаем это как $M ⪰ 0 {\ displaystyle M \ successq 0}$ $M \ successq 0$ . Обратите внимание, что есть несколько других эквивалентных определений положительного полуопределенного значения, например, положительно полуопределенные матрицы - это самосопряженные матрицы, которые имеют только неотрицательные собственные значения.

. Обозначим как $S n {\ displaystyle \ mathbb {S} ^ {n}}$ $\ mathbb {S} ^ n$ пространство всех $n × n {\ displaystyle n \ times n}$ $n \ times n$ реальных симметричных матриц. Пространство снабжено внутренним продуктом (где $tr {\ displaystyle {\ rm {tr}}}$ ${{\ rm {tr}}}$ обозначает след ) $A, B⟩ S n = tr (ATB) = ∑ i = 1, j = 1 n A ij B ij. {\ displaystyle \ langle A, B \ rangle _ {\ mathbb {S} ^ {n}} = {\ rm {tr}} (A ^ {T} B) = \ sum _ {i = 1, j = 1 } ^ {n} A_ {ij} B_ {ij}.}$ $\ langle A, B \ rangle _ {{{\ mathbb { S}} ^ {n}}} = {{\ rm {tr}}} (A ^ {T} B) = \ sum _ {{i = 1, j = 1}} ^ {n} A _ {{ij }} B _ {{ij}}.$

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

min X ∈ S n ⟨C, X⟩ S n при условии ⟨A К, Икс⟩ S N ≤ BK, К знак равно 1,…, м Икс ⪰ 0 {\ Displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n} }} \ langle C, X \ rangle _ {\ mathbb {S} ^ {n}} \\ {\ text {subject to}} \ langle A_ {k}, X \ rangle _ {\ mathbb {S} ^ {n}} \ leq b_ {k}, \ quad k = 1, \ ldots, m \\ X \ successq 0 \ end {array}}}

{\ begin {array} {rl} {\ Displaystyle \ мин _ {{Х \ в {\ 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}}

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

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

min X ∈ S n ⟨C, X⟩ S n при условии ⟨A К, Икс⟩ S N знак равно BK, К знак равно 1,…, м Икс ⪰ 0. {\ Displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n }}} \ langle C, X \ rangle _ {\ mathbb {S} ^ {n}} \\ {\ text {subject to}} \ langle A_ {k}, X \ rangle _ {\ mathbb {S } ^ {n}} = b_ {k}, \ quad k = 1, \ ldots, m \\ X \ successq 0. \ end {array}}}

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

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

Определения

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

min X ∈ S n ⟨C, X⟩ S n с учетом ⟨A я, Икс⟩ S N знак равно би, я = 1,…, м Икс ⪰ 0 {\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ { n}}} \ langle C, X \ rangle _ {\ mathbb {S} ^ {n}} \\ {\ text {subject to}} \ langle A_ {i}, X \ rangle _ {\ mathbb { S} ^ {n}} = b_ {i}, \ quad i = 1, \ ldots, m \\ X \ successq 0 \ end {array}}}

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

max y ∈ R m ⟨b, y⟩ R m при условии ∑ i = 1 myi A i ⪯ C {\ displaystyle {\ begin { массив} {rl} {\ displaystyle \ max _ {y \ in \ mathbb {R} ^ {m}}} \ langle b, y \ rangle _ {\ mathbb {R} ^ {m}} \\ {\ текст {подчиняется}} {\ displaystyle \ sum _ {i = 1} ^ {m}} y_ {i} A_ {i} \ prevq C \ end {array}}}

{\ begin {array} {rl} {\ displaystyle \ max _ {{y \ in {\ mathbb {R) }} ^ {m}}}} \ langle b, y \ rangle _ {{{\ mathbb {R}} ^ {m}}} \\ {\ text {subject to}} {\ displaystyle \ sum _ {{i = 1}} ^ {m}} y_ {i} A_ {i} \ prevq C \ end {array}}

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

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

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

⟨C, X⟩ - ⟨b, y⟩ = ⟨C, X⟩ - ∑ i = 1 myibi = ⟨C, X⟩ - ∑ i = 1 myi ⟨A i, X⟩ = ⟨C - ∑ я знак равно 1 myi A я, Икс⟩ ≥ 0, {\ 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,}

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

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

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

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

Примеры

Пример 1

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

(1 ρ AB ρ AC ρ AB 1 ρ BC ρ AC ρ BC 1) ⪰ 0, {\ displaystyle {\ begin {pmatrix} 1 \ rho _ {AB} \ rho _ {AC} \\\ rho _ {AB} 1 \ rho _ {BC} \\\ rho _ {AC} \ rho _ {BC} 1 \ end {pmatrix}} \ successq 0,}

{\ displaystyle {\ begin {pmatrix} 1 \ rho _ {AB} \ rho _ {AC} \\\ rho _ {AB} 1 \ rho _ {BC} \\\ rho _ {AC} \ rho _ {BC} 1 \ end {pmatrix}} \ successq 0,}

, и в этом случае эта матрица называется корреляционной матрицей. Предположим, что мы знаем из некоторых предварительных знаний (например, эмпирических результатов эксперимента), что $- 0,2 ≤ ρ AB ≤ - 0,1 {\ displaystyle -0.2 \ leq \ rho _ {AB} \ leq -0.1}$ $-0.2 \ leq \ rho _ {{AB}} \ leq -0.1$ и $0,4 ≤ ρ BC ≤ 0,5 {\ displaystyle 0,4 \ leq \ rho _ {BC} \ leq 0,5}$ $0,4 \ leq \ rho _ {{BC}} \ leq 0,5$ . Задача определения наименьшего и наибольшего значений, которые может принимать $ρ AC {\ displaystyle \ rho _ {AC} \}$ $\ rho _ {{AC} } \$ , задается следующим образом:

минимизировать / максимизировать

x 13 { \ displaystyle x_ {13}}

x _ {{13}}

при условии

- 0,2 ≤ x 12 ≤ - 0,1 {\ displaystyle -0.2 \ leq x_ {12} \ leq -0.1}

-0.2 \ leq x _ {{12} } \ leq -0.1

0,4 ​​≤ x 23 ≤ 0,5 {\ displaystyle 0.4 \ leq x_ {23} \ leq 0.5}

0.4 \ leq x _ {{23}} \ leq 0.5

(1 x 12 x 13 x 12 1 x 23 x 13 x 23 1) ⪰ 0. {\ displaystyle {\ begin {pmatrix} 1 x_ {12} x_ { 13} \\ x_ {12} 1 x_ {23} \\ x_ {13} x_ {23} 1 \ end {pmatrix}} \ successq 0.}

{\ displaystyle {\ begin {pmatrix} 1 x_ {12} x_ {13} \\ x_ {12} 1 x_ {23} \\ x_ {13} x_ {23} 1 \ end {pmatrix}} \ successq 0.}

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

$tr ((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 с 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 ({\ 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} \ 12 x_ {0 x_ {0 x_ {0 x_) } 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 0 s_ {3} \ end {array}} = right) x_ {12} + s_ {1} = - 0,1}$ ${\ 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 0 \\ 0 0 0 0 \\ 0 0 0 0 \\ 0 0 0 0 {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) \ справа) = x _ {{12}} + s _ {{1}} = - 0,1$

Решение этого SDP дает минимальное и максимальное значения $ρ AC = x 13 {\ displaystyle \ rho _ {AC} = x_ {13} \}$ $\ rho _ {{AC}} = x _ {{13}} \$ как $- 0,978 {\ displaystyle -0.978}$ $-0.978$ и $0,872 {\ displaystyle 0.872}$ $0.872$ соответственно.

Пример 2

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

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

(c T x) 2 d T x {\ displaystyle {\ frac {(c ^ {T} x) ^ { 2}} {d ^ {T} x}}}

{\ frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}}

с учетом

A x + b ≥ 0 {\ displaystyle Ax + b \ geq 0}

Ax + b \ geq 0

где мы предполагаем, что $d T x>0 {\ displaystyle d ^ {T} x>0}$ $d^{T}x>0$ всякий раз, когда $A x + b ≥ 0 {\ displaystyle Ax + b \ geq 0}$ $Ax + b \ geq 0$ .

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

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

t {\ displaystyle t}

t

при условии

A x + b ≥ 0, (c T x) 2 d T x ≤ t { \ displaystyle Ax + b \ geq 0, \, {\ frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}} \ leq t}

Ax + b \ geq 0, \, {\ frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}} \ leq t

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

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

diag (A x + b) ≥ 0 {\ displaystyle {\ textbf {diag }} (Ax + b) \ geq 0}

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

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

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

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

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

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

D = [tc T xc T xd T x] {\ displaystyle D = \ left [{ \ begin {array} {cc} t c ^ {T} x \\ c ^ {T} x d ^ {T} x \ end {array}} \ right]}

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

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

D ⪰ 0 {\ displaystyle D \ successq 0}

D \ successq 0

(Boyd and Vandenberghe, 1996)

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

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

t {\ displaystyle t}

t

с учетом

[diag (A x + b) 0 0 0 tc T x 0 c T xd T x] ⪰ 0 {\ 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] \ successq 0}

\ 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] \ successq 0

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

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

Максимизировать

∑ (i, j) ∈ E 1 - vivj 2, {\ displaystyle \ sum _ {(i, j) \ in E} { \ frac {1-v_ {i} v_ {j}} {2}},}

\ sum _ {{(i, j) \ in E}} {\ frac {1-v _ {{i}} v _ {{j}}} {2}},

такой, что каждый

vi ∈ {1, - 1} {\ displaystyle v_ {i} \ in \ {1, -1 \}}

v_ {i} \ in \ {1, -1 \}

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

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

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

max ∑ (i, j) ∈ E 1 - ⟨vi, vj⟩ 2, {\ displaystyle \ max \ sum _ {(i, j) \ in E} {\ frac {1- \ langle v_ {i}, v_ {j} \ rangle} {2 }},}

\ max \ sum _ {{(i, j) \ in E}} {\ frac {1- \ langle v _ {{i}}, v _ {{j}} \ rangle} {2}},

такие, что

‖ vi ‖ 2 = 1 {\ displaystyle \ lVert v_ {i} \ rVert ^ {2} = 1}

\ lVert v_ {i} \ rVert ^ {2} = 1

, где максимизация по векторам

{vi} {\ displaystyle \ {v_ {i} \}}

\ {v_ {i} \}

вместо целочисленных скаляров.

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

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

Алгоритмы

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

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

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

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

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

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

Bundle method

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

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

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

Приложения

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

Ссылки

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

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

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