Когда разрыв в двойственности полуопределенного программирования (SDP) равен нулю?

10

Я не смог найти в литературе точную характеристику исчезновения разрыва двойственности СДП. Или когда держится «сильная двойственность»?

Например, когда кто-то переходит между Лассерром и SDP SDP, в принципе у него есть пробел в дуальности. Однако, почему-то, кажется, есть какая-то «тривиальная» причина, почему этого разрыва нет.

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

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual gradstudent
источник

10

Для SDP существует более сложная теория двойственности, которая является точной: не существует «дополнительного условия», подобного условию Слейтера. Это связано с Раманой . (Еще один рассказ об SOS см. В [KS12] .) Честно говоря, я никогда не пытался понять эти документы и был бы счастлив, если бы кто-то их ошарашил.

Одним заметным следствием этой работы является то, что проблема проверки того, является ли данный SDP выполнимым, заключается в NP, если и только если он находится в coNP. (Тем не менее, я думаю, что эксперты ожидают, что проблема ни в одном. Лучшая известная верхняя граница - это PSPACE.)

Райан О'Доннелл
источник

Большое спасибо за очень полезный ответ! Дай мне посмотреть! (Какое совпадение, что в течение последних недель я также пытался проработать вашу статью с Дэниелом Кейном о нижних границах глубоких сетей! Это такая поучительная статья! Мне было интересно, если то, что вы делаете для LTF, происходит и для большего реалистичные активации, такие как ReLU.)

gradstudent

9

min {t r (C^{T} X) : t r (A_{1}^{T} X) = b_{1}, \dots, t r (A_{m}^{T} X) = b_{m}, X ⪰ 0},

$\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},$

X ≻ 0

$X\succ 0$

t r (A_{i}^{T} X) = b_{i}

$\mathrm{tr}(A_i^T X) = b_i$

{X : X_{1, 1} = 1, \dots, X_{n, n} = 1, X ⪰ 0}

$\{X: X_{1,1} = 1, \ldots, X_{n,n} = 1, X\succeq 0\}$

Что касается иерархии Лассерра / Сумма квадратов, Лассерр показал, что если допустимое множество, определяемое полиномиальными ограничениями, имеет внутреннюю точку, то здесь нет пробела в двойственности. Вы можете найти более слабое условие в этой статье .

Сашо Николов
источник

Большое спасибо за ссылки! Так является ли условие трансформированного Слейтера также необходимым условием для СДП? Или есть другие необходимые условия? (Я скоро собираюсь просмотреть документы, на которые вы ссылались, но мне было интересно, не могли бы вы сказать что-то о том, что вы имели в виду под «более слабым условием»? Вы имеете в виду, что условие во втором документе все еще является достаточным условием, а не необходимым условие, но проще, чем достаточное условие в первой статье?)

gradstudent

Это стандартное условие Слейтера, я только что специализировался на SDP, что упрощает вопросы, потому что все ограничения являются аффинными, за исключением ограничения PSD. Это условие не обязательно. Я не думаю, что какое-либо из условий SoS также необходимо, но «более слабое» не требует наличия внутренней точки, так что это может быть легче проверить.

Сашо Николов

Спасибо! Таким образом, необходимое условие не известно?

выпускник

1

Есть хорошая (я думаю ....) характеристика того, когда сильная двойственность имеет место или не подходит для {\ em всех} целевых функций.

Мы говорим, что полуопределенная {\ em система}

$(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$

$c$

$\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$

$c.$

$(P_{SD})$ $c$

$(P_{SD})$

https://arxiv.org/pdf/1709.02423.pdf

Документ скоро выйдет в SIAM Review. Надеюсь, людям это понравится :)

Район № 9
источник

Когда разрыв в двойственности полуопределенного программирования (SDP) равен нулю?

Ответы: