Полуопределённое программирование

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Полуопределённое программирование (или SDP от англ. Semidefinite programming) — подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.

Полуопределённое программирование является относительно новой областью оптимизации, интерес к которой растёт по нескольким причинам. Много практических задач в областях исследования операций и комбинаторной оптимизации можно смоделировать или аппроксимировать как задачи полуопределённого программирования. В теории автоматического управления задачи SDP используются в контексте линейных матричных неравенств. Задачи SDP, фактически, являются частным случаем конического программирования[англ.] и могут быть эффективно решены методом внутренней точки. Все задачи линейного программирования могут быть выражены как задачи SDP, а с помощью иерархий задач SDP могут быть аппроксимированы решения задач полиномиальной оптимизации. Полуопределённое программирование используется при оптимизации сложных систем. В последние годы некоторые задачи сложности квантовых запросов были сформулированы в терминах полуопределённого программирования.

Мотивация и определение

[править | править код]

Исходные мотивации

[править | править код]

Задача линейного программирования — это задача, в которой нужно максимизировать или минимизировать линейную целевую функцию от вещественных переменных на многограннике. В полуопределённом программировании, вместо этого мы используем вещественные вектора и нам позволено использовать скалярное произведение векторов. Условие неотрицательности вещественных переменных задачи ЛП заменяется ограничениями полуопределённости на матрице переменных задачи SDP. В частности, общая задача полуопределённого программирования может быть определена как любая задача математического программирования вида

при условиях

Эквивалентные формулировки

[править | править код]

Говорят, что матрица положительно полуопределённа, если она является матрицей Грама некоторых векторов (т.е. если существуют вектора , такие, что для всех ). Если это выполняется, мы обозначим это как . Заметим, что существуют некоторые другие эквивалентные определения положительной полуопределённости, например, положительно полуопределённые матрицы имеют только неотрицательные собственные значения и имеет положительно полуопределённый квадратный корень.

Обозначим через пространство всех вещественных симметричных матриц. В этом пространстве имеется скалярное произведение (где означает след)

Мы можем переписать задачу математического программирования из предыдущей секции в эквивалентном виде

при условиях

где элемент матрицы равно из предыдущей секции, а матрица, имеющая в качестве элемента матрицы значение из предыдущей секции.

Заметим, что если мы добавим дополнительные переменные[англ.] должным образом, эта задача SDP может быть преобразована к виду

при условиях

Для удобства задача SDP может быть определена слегка в другой, но эквивалентной форме. Например, линейные выражения, использующие неотрицательные скалярные переменные могут быть добавлены в спецификацию задачи. Задача остаётся SDP, поскольку каждая переменная может быть включена в матрицу как диагональный элемент ( для некоторого ). Чтобы обеспечить , можно добавить ограничения для всех . В качестве другого примера, заметим, что для любой положительной полуопределённой матрицы , существует набор векторов , таких, что элемент , матрицы равен , скалярному произведению векторов и . Таким образом, задачи SDP часто формулируются в терминах линейных выражений от скалярных произведений векторов. Если дано решение задачи SDP в стандартном виде, вектора могут быть восстановлены за время (например, с помощью неполного разложения Холецкого матрицы X).

Теория двойственности

[править | править код]

Определения

[править | править код]

Аналогично линейному программированию, если задана общая задача SDP в виде

при условиях

(прямая задача, или P-SDP), мы определим двойственную полуопределённую задачу (D-SDP) как

при условиях

Где для любых двух матриц и , означает .

Слабая двойственность

[править | править код]

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

где последнее неравенство отражает факт положительной полуопределённости обеих матриц. Значение этой функции иногда называется двойственным зазором.

Сильная двойственность

[править | править код]

При условии, известном как условие Слейтера, значения прямой и двойственной SDP-задач равны. Это называется сильной двойственностью. В отличие от задач линейного программирования, не всякая задача SDP обладает строгой двойственностью. В общем случае значение двойственной задачи SDP может быть строго меньше значения прямой задачи.

(i) Предположим, что прямая задача (P-SDP) ограничена снизу и строго допустима (то есть существуют , такие, что , ). Тогда имеется оптимальное решение для двойственной задачи (D-SDP) и

(ii) Предположим, что двойственная задача (D-SDP) ограничена сверху и строго допустима (то есть для некоторого ). Тогда существует оптимальное решение для прямой задачи (P-SDP) и выполняется равенство из (i).

Рассмотрим три случайные переменные , и . По определению, их коэффициенты корреляции допустимы тогда и только тогда, когда

Предположим, что из каких-то источников (например, из эмпирических или экспериментальных данных) мы знаем, что и . Задачу определения наименьшего и наибольшего значений можно выписать в виде:

минимизировать/максимизировать
при условиях

Здесь мы принимаем . Задачу можно сформулировать как задачу SDP. Мы дополняем неравенства путём расширения матрицы переменных и введения дополнительных переменных[англ.], например

После решения этой задачи SDP получим минимум и максимум значений ( и соответственно).

Рассмотрим задачу

минимизировать
при условиях ,

где предполагается, что при .

Введя дополнительную переменную , перепишем задачу в виде:

минимизировать
при условиях

В этой формулировке целевая функция является линейной функцией от двух переменных ().

Первое ограничение можно переписать в виде

,

где матрица является квадратной матрицей со значениями на диагонали, равными элементам вектора .

Второе ограничение можно записать в виде

Определим матрицу следующим образом

Мы можем использовать теорию дополнения Шура, чтобы показать, что

[1]

Задача полуоределённого программирования для этой задачи будет иметь вид

минимизировать
при условиях

Пример 3 (Аппроксимационный алгоритм Гоеманса — Уильямсона MAX CUT)

[править | править код]

Полуопределённое программирование является важным инструментом для создания аппроксимационных алгоритмов для NP-трудных задач максимизации. Первый аппроксимационный алгоритм, основанный на SDP, предложили Михель Гоеманс и Дэвид Уильямсон[2]. Они изучали задачу MAX CUT: Дан граф G = (V, E), требуется разбить вершины V на две части так, чтобы максимизировать число рёбер соединяющих эти две части. Задачу можно представить как задачу целочисленного квадратичного программирования:

Максимизировать при условии для любого .

Если только не P = NP, мы не можем решить эту задачу эффективно. Однако Гоеманс и Уильямсон наметили трёхшаговую процедуру для атаки такого рода задач:

  1. Ослабляем целочисленную задачу квадратичного программирования до задачи SDP.
  2. Решаем задачу SDP (с любой произвольно малой ошибкой ).
  3. Округляем решение задачи SDP для получения приближённого решения исходной задачи целочисленного квадратичного программирования.

Для задачи MAX CUT наиболее естественным ослаблением является

для , где максимизация осуществляется по векторам , а не скалярным целым переменным.

Задача является задачей SDP, поскольку и целевая функция, и ограничения являются линейными функциями от скалярных произведений векторов. Решение задачи SDP даёт набор единичных векторов в . Поскольку вектора не обязательно коллинеарны, значение ослабленной задачи может быть только больше значения исходной целочисленной задачи квадратичного программирования. Конечная процедура округления необходима, чтобы получить разбиение. Гоеманс и Уильямсон выбирают случайную гиперплоскость (используя равномерное распределение), проходящую через начало координат и разбивают вершины в зависимости от расположения относительно этой плоскости. Непосредственный анализ показывает, что эта процедура обеспечивает ожидаемый аппроксимационный коэффициент 0,87856 - ε. (Математическое ожидание значения разреза равно сумме по всем рёбрам вероятностей, что ребро входит в разрез и это ожидание пропорционально углу между векторами в конечных вершинах ребра. Если сравнивать эту вероятность с , математическое ожидание отношения всегда будет не меньшим 0,87856.) В предположении верности гипотезы уникальной игры[англ.] можно показать, что аппроксимационный коэффициент этой аппроксимации, главным образом, оптимален.

Со времени появления статья Гоеманса и Уильямсона задачи SDP были применены для разработки большого количества аппроксимационных алгоритмов. Не так давно Прасад Рагхавендра разработал общую схему для задач удовлетворения ограничений, основанную на гипотезе уникальной игры[англ.][3].

Имеется несколько видов алгоритмов для решения задач SDP. Результат работы этих алгоритмов является значение задачи SDP с точностью до , которое получается за время, полиномиально зависящее от размера задачи и .

Методы внутренней точки

[править | править код]

Большинство систем решения базируются на методе внутренней точки (CSDP, SeDuMi, SDPT3, DSDP, SDPA), робастном и эффективном для линейных задач SDP общего вида. Подход ограничен в использовании тем фактом, что алгоритмы являются методами второго порядка и требуют запоминания и разложения больших (и, зачастую, плотных) матриц.

Методы первого порядка

[править | править код]

Методы первого порядка для конической оптимизации[англ.] избегают запоминания и разложения больших матриц Гессе и применимы к существенно большим по размеру задачам, чем методы внутренней точки, за счёт потери в точности. Метод реализован в системе «SCS solver».

Метод пучков

[править | править код]

Задача SDP формулируется как задача негладкой оптимизации и решается методом спектрального пучка. Этот подход очень эффективен для частных классов линейных задач SDP.

Алгоритмы, основанные на методе обобщённого лагранжиана[англ.] (PENSDP), близки по поведению к методам внутренней точки и могут быть приспособлены для некоторых очень больших задач. Другие алгоритмы используют низкоуровневую информацию и переформулировку задачи SDP как задачи нелинейного программирования (SPDLR).

Приложения

[править | править код]

Полуопределённое программирование было использовано для поиска приближённых решений задач комбинаторной оптимизации, таких как решение задачи максимального разреза c аппроксимационным коэффициентом 0,87856. Задачи SDP используется также в геометрии для определения тенсегрити-графов, и появляются в теории управления как линейные матричные неравенства.

Примечания

[править | править код]

Литература

[править | править код]
  • Lieven Vandenberghe, Stephen Boyd. Semidefinite Programming // SIAM Review 38. — 1996. — Март. — С. 49—95.
  • Monique Laurent, Franz Rendl. Semidefinite Programming and Integer Programming/Report PNA-R0210, CWI, Amsterdam. — 2002. — Апрель.
  • E. de Klerk. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. — Kluwer Academic Publishers, 2002. — ISBN 1-4020-0547-4.
  • P. Raghavendra. Optimal algorithms and inapproximability results for every CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17–20, 2008). STOC '08. — New York, NY: ACM, 2008. — С. 245-254.
  • Robert M. Freund. Introduction to Semidefinite Programming (SDP).
  • Michel X. Goemans, David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming // JACM. — 1995. — Ноябрь (т. 42, вып. 6). — С. 1115—1145. — doi:10.1145/227683.227684.