Решение полуопределенных программ за полиномиальное время

17

Мы знаем, что линейные программы (ЛП) могут быть решены точно за полиномиальное время с помощью метода эллипсоидов или метода внутренних точек, таких как алгоритм Кармаркара. Некоторые ЛП с суперполиномиальным (экспоненциальным) числом переменных / ограничений также могут быть решены за полиномиальное время, при условии, что мы можем разработать для них поликлинический оракул разделения времени.

Как насчет полуопределенных программ (SDP)? Какие классы SDP могут быть решены именно за полиномиальное время? Когда SDP не может быть точно решен, можем ли мы всегда разработать FPTAS / PTAS для его решения? Каковы технические условия, при которых это можно сделать? Можем ли мы решить SDP с экспоненциальным числом переменных / ограничений за полиномиальное время, если мы можем разработать для него оракул с полиномиальным разделением времени?

Можем ли мы эффективно решить SDP, возникающие в задачах комбинаторной оптимизации (MAX-CUT, раскраска графа)? Если мы можем решить только с коэффициентом , не повлияет ли это на алгоритмы аппроксимации с постоянным коэффициентом (например, 0,878 для алгоритма Геманса-Уильямсона MAX-CUT)?1+ϵ

Любая хорошая ссылка на это будет высоко оценена.

linear-programming semidefinite-programming convex-optimization Ариндам Пал
источник
3
На самом деле метод работает для выпуклого программирования в целом
Суреш Венкат
8
Есть по крайней мере две причины, по которым вы не можете решить общий SDP за полиномиальное время. (1) Существуют SDP, решение которых имеет экспоненциальный размер. (2) SDP могут кодировать сумму задачи с квадратными корнями, которая, как известно, не является разрешимой за полиномиальное время.
Робин Котари
2
@RobinKothari Для SDP обычно «разрешимое за полиномиальное время» заменяется «попадает в (аддитивную) ОПТ во временном полиноме в 1 / ϵ » IIRC. ps как SDP кодирует сумму квадратных квадратов? ϵ1/ϵ
Суреш Венкат
8
@SureshVenkat: скажем, у нас есть матрица 2x2 с записями [ab; компакт диск]. Предположим, что это положительный полуопределенный и d = 1. Это означает, что b = c и a> = b ^ 2. Таким образом, b ограничено сверху квадратным корнем из a. Теперь мы можем максимизировать сумму нескольких таких b. Оптимальным значением будет сумма квадратных корней соответствующих а.
Робин Котари
2
Это не мультипликативный, а аддитивный. Кроме того, en.wikipedia.org/wiki/Semidefinite_programming#Algorithms
Суреш Венкат

Ответы:

16

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

Полуконечное программирование . Ванденберге и Стивен Бойд, 1996.

Jagadish
источник
Хорошая ссылка на Jagadish.
Ариндам Пал
Хорошая ссылка тоже! Благодарность! Задавался вопросом, говоря, алгоритм полиномиального времени, решающий SDP, алгоритмы, решающие для оптимального решения, точно или приблизительно?
StackExchange для всех