Что может быть решено с помощью полуопределенного программирования, которое не может быть решено с помощью линейного программирования?

9

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

Кроме того, как распознать проблему, которая может быть решена с помощью полуопределенного программирования? Какова типичная проблема, для которой используется полуопределенное программирование, которая не может быть решена с помощью линейного программирования?

Большое спасибо за любой ответ.

linear-programming convex-optimization semidefinite-programming user11094
источник
2
Может быть, вы можете уточнить свой вопрос? В конце концов, линейное программированиеP-полное.
Кристоффер Арнсфельт Хансен
5
@KristofferArnsfeltHansen Я никогда не перестаю удивляться, почему люди продолжают поднимать этот факт в подобных дискуссиях. P-полнота не имеет значения, если только мы не говорим об отделении P от L или NC - если мы говорим о политизме, все в P является «P-полным». Чтобы предложить ответ на OP: после того, как вы исправите линейное кодирование проблемы (т.е. напишите как оптимизацию линейного функционала по многограннику), имеет смысл задать вопрос, может ли полизированный LP / SDP решить проблему.
Сашо Николов

Ответы:

18

Типичная проблема - MaxCut: выведите срез на график, который (приблизительно) максимизирует количество срезов ребер. Геманс и Уильямсон показали, что SDP приближает значение MaxCut с точностью до коэффициента не менее 0,878. Недавно Чан, Ли, Рагхавендра и Стойрер показали, что для естественного линейного кодирования задачи MaxCut все LP с полиномиальным размером достигают аппроксимации не лучше, чем 0,5.

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

Посмотрите книги Гертнера и Матоусека , главы 6 и 13 книги Виллимсона и Шмоя , обзор Ловаша .

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

Для многих задач комбинаторной оптимизации (например, Max-Cut) полуопределенное программирование дает гораздо более сильные релаксации, чем LP-релаксация IP-формулировок. Это позволяет создавать алгоритмы аппроксимации и точные алгоритмы, которые более эффективны, чем их линейные аналоги, благодаря лучшему качеству границ. Примеры можно найти в дипломной работе Кристофа Хельмберга , в этом обзоре и на этой странице курса .

Другой недавней последовательностью впечатляющих результатов, использующих полуопределенное программирование, является применение алгебр Разборова- флага для доказательства результатов по проблемам типа Туран (см. Этот обзор и флагманский проект ).

Томас Калиновский
источник