Меня довольно смущает литература по непрерывной оптимизации и литература TCS о том, какие типы (непрерывных) математических программ (МП) могут быть эффективно решены, а какие нет. Сообщество непрерывной оптимизации, кажется, утверждает, что все выпуклые программы могут быть решены эффективно, но я...
Я хотел бы найти алгоритм полиномиального времени, который определяет, содержит ли диапазон данного набора матриц матрицу перестановок. Если кто-нибудь знает, относится ли эта проблема к другому классу сложности, это было бы так же полезно. РЕДАКТИРОВАТЬ: я пометил этот вопрос с помощью линейного...
При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.) Существуют ли хорошие образовательные источники или обзоры, выходящие...
Мы знаем, что линейные программы (ЛП) могут быть решены точно за полиномиальное время с помощью метода эллипсоидов или метода внутренних точек, таких как алгоритм Кармаркара. Некоторые ЛП с суперполиномиальным (экспоненциальным) числом переменных / ограничений также могут быть решены за...
Это продолжение недавнего вопроса, заданного А. Палом: Решение полуопределенных программ за полиномиальное время . Я все еще ломаю голову над фактическим временем выполнения алгоритмов, которые вычисляют решение полуопределенной программы (SDP). Как отметил Робин в своем комментарии к...
Я не смог найти в литературе точную характеристику исчезновения разрыва двойственности СДП. Или когда держится «сильная двойственность»? Например, когда кто-то переходит между Лассерром и SDP SDP, в принципе у него есть пробел в дуальности. Однако, почему-то, кажется, есть какая-то «тривиальная»...
Мне интересно, существуют ли систематические исследования сумм квадратичных форм в квадрате, похожих на квадратичные формы, что практически отражается в разложении по собственным значениям (что имеет огромное практическое значение). Пара примеров связана с важностью вопроса. Анализ основных...
Я знаком с линейными программами в том смысле, что они могут решать задачи с линейными целевыми функциями и линейными ограничениями. Но что может полуопределенное программирование решить, чего не может линейное программирование? Я уже знаю, что полуопределенные программы являются обобщением...