Введение
Полуопределенное программирование (SDP) - это подполе математического программирования, которое занимается оптимизацией линейной объективной функции (функции, указанной пользователем, которую пользователь хочет минимизировать или максимизировать) над пересечением конуса положительных полуопределенных матриц с аффинным пространством, то есть спектраэдром. Полуопределенное программирование - относительно новая область оптимизации, которая представляет растущий интерес по нескольким причинам. Многие практические проблемы в исследовании операций и комбинаторной оптимизации могут быть смоделированы или приближены как полуопределенные проблемы программирования. В теории автоматического управления SDP используются в контексте неравенств линейной матрицы. SDPs являются, по сути, особым случаем конусового программирования и могут быть эффективно решены методами внутренней точки. Все линейные программы и (выпуклые) квадратные программы могут быть выражены как SDP, и через иерархию SDP решения проблем оптимизации полиномов могут быть приближены. Полуопределенное программирование используется в оптимизации сложных систем. В последние годы некоторые проблемы сложности квантовых запросов были сформулированы в терминах полуопределенных программ.
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive semidefinite matrices with an affine space, i. e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs.
Первоначальная мотивация
Линейная задача программирования - это задача, в которой мы хотим максимизировать или минимизировать линейную объективную функцию реальных переменных над политопом. В полуопределенном программировании мы вместо этого используем реальные оцененные векторы и можем принимать точечное произведение векторов; ограничения на неотрицательность для реальных переменных в LP (линейное программирование) заменяются ограничениями на полуопределенность для матричных переменных в SDP (полуопределенное программирование). В частности, общая полуопределенная задача программирования может быть определена как любая математическая проблема программирования формы, где , и являются реальными числами и является точечным произведением и .
where the , and the are real numbers and is the dot product of and .
Связь с другими задачами оптимизации
Пространство полуопределенных матриц представляет собой выпуклый конус. Поэтому SDP является специальным случаем конической оптимизации, которая является специальным случаем выпуклой оптимизации. Когда матрица C диагональная, внутренние произведения <C,X> эквивалентны векторному произведению диагонали C и диагонали X. Аналогично, когда матрицы Ak диагональны, соответствующие внутренние произведения эквивалентны векторным произведениям. В этих векторных произведениях используются только диагональные элементы X, поэтому мы можем добавить ограничения, приравнивающие недиагональные элементы X к 0. Условие тогда эквивалентно условию, что все элементы диагонали X являются неотрицательными. Затем полученная SDP становится линейной программой, в которой переменные являются элементами диагонали X.
Слабая дуальность
Теорема слабой дуальности утверждает, что значение первичного SDP равно по меньшей мере значению двойного SDP. Поэтому любое возможное решение двойного SDP снижает первичное значение SDP, и наоборот, любое возможное решение первичного SDP снижает верхнее значение SDP. Это происходит потому, что где последнее неравенство, потому что обе матрицы являются положительными полуопределенными, и результат этой функции иногда называют двойственным разрывом.
where the last inequality is because both matrices are positive semidefinite, and the result of this function is sometimes referred to as duality gap.
Пример 1
Рассмотрим три случайных переменных , , и данный набор корреляционных коэффициентов возможен , если и только если эта матрица называется корреляционной матрицей . Предположим, что мы знаем из некоторых предварительных знаний (эмпирических результатов эксперимента, например), что и Проблема определения наименьших и наибольших значений, которые могут принимать, дается: Мы задали, чтобы получить ответ. Это может быть сформулировано в ПДР. Мы обрабатываем ограничения неравенства, увеличивая переменную матрицу и вводя переменные слак, например, Решение этого SDP дает минимальные и максимальные значения соответственно as и .
This matrix is called the correlation matrix. Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that and The problem of determining the smallest and largest values that can take is given by:
We set to obtain the answer. This can be formulated by an SDP. We handle the inequality constraints by augmenting the variable matrix and introducing slack variables, for example
Solving this SDP gives the minimum and maximum values of as and respectively.
Пример 3 (алгоритм приближения максимального разреза GoemansWilliamson)
Полуопределенные программы являются важными инструментами для разработки алгоритмов приближения для NP-трудных задач максимизации. Первый алгоритм приближения, основанный на SDP, разработан Мишелем Гомансом и Дэвидом П. Уильямсоном (JACM, 1995).
Другие применения
Полуопределенное программирование применяется для поиска приблизительных решений проблем комбинаторной оптимизации, таких как решение проблемы максимального разреза с коэффициентом приближения 0,87856. SDP также используются в геометрии для определения графиков тенсегритности и возникают в теории управления как LMI, а в проблемах с обратными эллиптическими коэффициентами как выпуклые, нелинейные, ограничения полуопределенности. Он также широко используется в физике для ограничения конформных теорий поля с помощью конформной загрузки.
Сложность времени выполнения
Проблема полуопределенной осуществимости (SDF) - это следующая проблема принятия решения: с учетом SDP, решите, есть ли у него по крайней мере одно осуществимое решение. Точная сложность выполнения этой задачи неизвестна (по состоянию на 1997 год). Однако Рамана доказал следующее:
Методы первого порядка
Методы первого порядка для конической оптимизации избегают вычисления, хранения и разбивки на факторы большой гессианской матрицы и масштабируют до гораздо более крупных проблем, чем методы внутренней точки, при некоторой стоимости точности. В расщепляющемся конусе (SCS) реализован метод первого порядка. Другим методом первого порядка является метод чередующегося направления множителей (ADMM). Этот метод требует в каждом шаге проекции на конусе полуопределенных матриц.
Метод пакета
Код ConicBundle формулирует задачу SDP как задачу негладкой оптимизации и решает ее методом негладкой оптимизации Spectral Bundle. Этот подход очень эффективен для особого класса линейных задач SDP.
Другие методы решения
Алгоритмы, основанные на расширенном лагранжианском методе (PENSDP), похожи по поведению на методы внутренней точки и могут быть специализированы на некоторых очень крупномасштабных проблемах. Другие алгоритмы используют низкоуровневую информацию и переформулирование SDP как нелинейную задачу программирования (SDPLR, ManiSDP).
Приблизительные методы
Также были предложены алгоритмы, которые приблизительно решают SDP. Основная цель таких методов - достижение более низкой сложности в приложениях, где приблизительные решения являются достаточными, а сложность должна быть минимальной. Известный метод, который использовался для обнаружения данных в многократно вводимых многократно выводимых (MIMO) беспроводных системах, - это треугольная приближенная полуопределенная релаксация (TASER), которая работает на факторах расщепления Чоллески полуопределенной матрицы вместо полуопределенной матрицы. Этот метод вычисляет приблизительные решения для максимальной разреза, как проблемы, которые часто сопоставимы с решениями от точных решений, но только в 10 20 алгоритм итераций. Хазан разработал приблизительный алгоритм решения SDP с дополнительным ограничением, что трасса матрицы переменных должна быть равна 1.