Какие классы математических программ могут быть решены точно или приблизительно за полиномиальное время?

31

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

Этот вопрос очень беспокоил меня в последние несколько лет, и я не могу найти четкого ответа на него. Я надеюсь, что вы могли бы помочь мне решить это раз и навсегда: какие классы членов парламента могут быть решены точно за полиномиальное время и какими средствами; а что известно об аппроксимации оптимального решения МП, которое мы не можем решить точно за полиномиальное время?

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

Все мы знаем, что линейное программирование может быть решено точно за полиномиальное время, запустив метод эллипсоида или метод внутренней точки, а затем выполнив некоторую процедуру округления. Линейное программирование может даже быть решено во временном полиноме по количеству переменных при столкновении с семейством LP с любым сверхбольшим количеством линейных ограничений, при условии, что можно обеспечить «оракул разделения» для него: алгоритм, который, учитывая точку либо определяет, является ли эта точка достижимой, либо выводит гиперплоскость, которая отделяет точку от многогранника возможных точек. Аналогично, линейное программирование по полиному времени по количеству ограничений при столкновении с семейством LP с любым сверхбольшим количеством переменных, если кто-то предоставляет алгоритм разделения для двойников этих LP.

Метод эллипсоидов также способен решать квадратичные программы за полиномиальное время, если матрица в целевой функции положительно (полу?) Определена. Я подозреваю, что, используя трюк с разделением оракула, мы можем в некоторых случаях сделать это, если имеем дело с невероятным количеством ограничений. Это правда?

В последнее время полуопределенное программирование (SDP) приобрело большую популярность в сообществе TCS. Их можно решить с произвольной точностью, используя методы внутренних точек или метод эллипсоидов. Я думаю, что SDP не могут быть решены точно из-за проблемы, что квадратные корни не могут быть вычислены точно. (?) Было бы тогда правильно, если я скажу, что есть FPTAS для SDP? Я нигде не видел, что заявлено, так что это, вероятно, не правильно. Но почему?

Мы можем точно решать LP и SDP с произвольной точностью. А как насчет других классов конических программ? Можем ли мы решать программы конусов второго порядка с произвольной точностью, используя метод эллипсоидов? Я не знаю.

На каких классах членов парламента мы можем использовать метод эллипсоидов? Какими свойствами должен удовлетворять такой МП, чтобы можно было дать ответ с произвольной точностью, и какие дополнительные свойства нам нужны, чтобы получить точное решение за полиномиальное время? Те же вопросы для внутренних методов.

Да, и наконец, что заставляет постоянных оптимизаторов говорить, что выпуклые программы могут быть эффективно решены? Правда ли, что ответ произвольной точности на выпуклую программу может быть найден за полиномиальное время? Я не верю, поэтому в каких аспектах их определение «эффективный» отличается от нашего?

Любой вклад приветствуется! Заранее спасибо.

ds.algorithms optimization linear-programming semidefinite-programming polynomial-time Барт
источник
6
Название этого вопроса слишком широкое; кажется, что вы действительно хотите знать, могут ли выпуклые программы действительно быть решены за полиномиальное время.
Питер Шор
Откомандирован. Барт, может быть, вы можете разбить вещи на конкретные вопросы?
Суреш Венкат
Петр и Суреш, спасибо за эти предложения. Из того, что я написал, предполагается, что меня интересует не только вопрос о том, могут ли выпуклые программы быть решены или аппроксимированы за многократное время. Меня в основном интересуют пределы методов эллипсоидов и внутренних точек, и я надеюсь, что кто-то точно знает, над какими классами депутатов они работают эффективно. Я спрашиваю об этом, потому что текущая литература по этому вопросу не ясно (для меня).
Барт
Лично я думаю, что было бы хорошо иметь хороший обзор этого в одном месте (например, как ответ на этот вопрос об обмене стека). Также мне кажется, что это довольно сложный вопрос. Тем не менее, поскольку я новичок в stackexchannge, я не знаком с культурой и этикой здесь ... поэтому, если вы настаиваете, я постараюсь выяснить, как разделить этот вопрос на несколько небольших вопросов.
Барт
1
Я думаю, что объем этого вопроса слишком широк, чтобы иметь ответ. Ограничения методов эллипсоида и внутренней точки были бы хорошим вопросом, и что можно сделать для выпуклых программ - хороший вопрос, но если вы не укажете тип алгоритма или тип программы, вы в основном задаете вопрос для краткого изложения всей области непрерывной оптимизации в вашем ответе, и это практически невозможно. Это не маленькое поле. Однако, если вы оставите свой вопрос как есть, вполне возможно, что вы получите еще один хороший частичный ответ.
Питер Шор

Ответы:

18

Я могу ответить на эту часть:

Тогда будет ли правильно, если я скажу, что есть FPTAS для SDP? Я нигде не видел, что заявлено, так что это, вероятно, не правильно. Но почему?

Утверждение верно, но мы не часто видим его, потому что более сильное утверждение имеет место и более важно, чем это более слабое утверждение.

FPTAS - это алгоритм полиномиального времени, который, учитывая проблему и параметр точности 1 k , выводит (1 + 1 / k ) -приближенное решение.

Но для SDP метод эллипсоида и метод внутренней точки предоставляют алгоритмы полиномиального времени, которые, учитывая проблему и параметр точности 1 k , выдают (1 + 2 - k ) -приближенное решение. Обратите внимание, что коэффициент аппроксимации намного лучше, чем требуется для FPTAS.

Цуёси Ито
источник
Это требует большей осторожности, поскольку метод эллипсоида и методы внутренней точки требуют дополнительных условий для выполнения за полиномиальное время.
Ёсио Окамото
Спасибо за это, Tsuyoshi! Ёсио, не могли бы вы уточнить, что вы имеете в виду под этим? Вы действительно имеете в виду, что существуют определенные условия для конкретного SDP, потому что иначе SDP не может быть аппроксимировано таким же образом в поли-времени? Для меня это сюрприз, и мне было бы интересно узнать об этих условиях. Спасибо.
Барт
@Bart: Например, если вы посмотрите лекционные заметки Ловаша cs.elte.hu/~lovasz/semidef.ps , вы можете найти теорему 3.7 (стр. 19), в которой говорится об ограничении времени выполнения метода эллипсоидов для выпуклой минимизации , Там налагаются некоторые технические предположения.
Ёсио Окамото
4
@Bart: посмотрите на заметки, которые очень хороши, но просто чтобы поставить их здесь: условия в основном состоят в том, что допустимая область содержит шар радиуса , содержится в шаре радиусаrRlog⁡R/r
Большое спасибо за это. Это отвечает на очень большую часть моего вопроса. Кажется, что это знание может быть очень полезным инструментом для теоретических компьютерных ученых, хотя мне все же кажется, что оно совсем не известно и заявлено почти нигде. Weird.
Барт