Эллипсоидный метод

Итерация метода эллипсоида

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

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

История [ править ]

Эллипсоидный метод имеет долгую историю. В качестве итеративного метода предварительная версия была представлена Наумом З. Шором . В 1972 г. приближенный алгоритм для реальной выпуклой минимизации был изучен Аркадием Немировским и Давидом Б. Юдиным (Юдин). В качестве алгоритма для решения задач линейного программирования с рациональными данными алгоритм эллипсоида изучал Леонид Хачиян : достижением Хачияна было доказательство полиномиальной разрешимости линейных программ.

После работы Хачияна метод эллипсоидов был единственным алгоритмом для решения линейных программ, время выполнения которых было доказано как полиномиальное до появления алгоритма Кармаркара . Однако на практике метод внутренней точки Кармаркара и варианты симплексного алгоритма намного быстрее, чем метод эллипсоида. Алгоритм Кармаркара в худшем случае также работает быстрее.

Однако эллипсоидальный алгоритм позволяет теоретикам сложности достигать (в худшем случае) границ, которые зависят от размерности проблемы и размера данных, но не от количества строк, поэтому он оставался важным в теории комбинаторной оптимизации для многих. годы. ^{[1] [2] [3] [4]} Только в 21 веке появились алгоритмы внутренней точки с аналогичными свойствами сложности. ^{[ необходима цитата ]}

Описание [ править ]

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

• Выпуклая функция , чтобы свести к минимуму над вектором (содержащего п переменных);${\ displaystyle f_ {0} (x): \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle x}$
• Выпуклые ограничения-неравенства вида , где функции выпуклые; эти ограничения определяют выпуклое множество .${\ Displaystyle f_ {я} (х) \ leqslant 0}$${\ displaystyle f_ {i}}$ ${\ displaystyle Q}$
• Ограничения линейного равенства формы .${\ displaystyle h_ {i} (х) = 0}$

Нам также дан начальный эллипсоид, определяемый как${\ Displaystyle {\ mathcal {E}} ^ {(0)} \ subset \ mathbb {R} ^ {n}}$

${\ Displaystyle {\ mathcal {E}} ^ {(0)} = \ left \ {z \ in \ mathbb {R} ^ {n} \: \ (z-x_ {0}) ^ {T} P_ { (0)} ^ {- 1} (z-x_ {0}) \ leqslant 1 \ right \}}$

содержащий минимизатор , где и является центром . ${\ displaystyle x ^ {*}}$${\ Displaystyle P _ {(0)} \ succ 0}$${\ displaystyle x_ {0}}$${\ displaystyle {\ mathcal {E}}}$

Наконец, мы требуем существования оракула отсекающей плоскости (также называемого оракулом разделения ) для выпуклого множества . Если задан балл , оракул должен вернуть один из двух ответов: ^[5]${\ displaystyle Q}$${\ Displaystyle х \ в \ mathbb {R} ^ {п}}$

• «Дело в », или -${\ displaystyle x}$${\ displaystyle Q}$
• «Дело в том, что не в , и более того, здесь гиперплоскость, которая отделяется от », то есть вектор такой, что для всех .${\ displaystyle x}$${\ displaystyle Q}$${\ displaystyle x}$${\ displaystyle Q}$${\ displaystyle c}$${\ Displaystyle с \ cdot х <с \ cdot y}$${\ displaystyle y \ in Q}$

Одним из примеров оракула отсекающей плоскости является субградиент g функции f . ^{[ требуется разъяснение ]}

Приложение к линейному программированию [ править ]

В контексте линейного программирования все ограничения линейны и представляют собой выпуклый многогранник . Тогда оракул разделения можно легко реализовать следующим образом. ^[5] Учитывая ограничения и точку , оракул просто вычисляет :${\ displaystyle Q}$${\ Displaystyle Q = \ {х | Ax \ leq b \}}$${\ Displaystyle х \ в \ mathbb {R} ^ {п}}$${\ displaystyle Ax}$

• Если результат не больше , значит, есть ;${\ displaystyle b}$${\ displaystyle x}$${\ displaystyle Q}$
• В противном случае, существует, по крайней мере , один ряд из A , таким образом, что больше , чем соответствующее значение в ; эта строка дает нам разделяющую гиперплоскость.${\ displaystyle c}$${\ displaystyle c \ cdot x}$${\ displaystyle b}$${\ displaystyle c}$

Этот оракул работает за полиномиальное время, пока количество ограничений полиномиально. В некоторых задачах линейной оптимизации, даже если количество ограничений экспоненциально, все же можно написать собственный оракул разделения, который работает за полиномиальное время. Вот два примера: ^[6]

• Задача древовидности минимальной стоимости : для данного взвешенного ориентированного графа и вершины r в нем найти подграф минимальной стоимости, содержащий ориентированный путь из r в любую другую вершину. Задачу можно представить в виде LP с ограничением для каждого подмножества вершин, которое представляет собой экспоненциальное количество ограничений. Однако оракул разделения можно реализовать, используя n -1 приложений процедуры минимального отсечения .
• Максимальное независимое множество проблем. Его можно аппроксимировать ЛП с ограничением для каждого цикла нечетной длины. Хотя таких циклов экспоненциально много, оракул разделения, работающий за полиномиальное время, можно реализовать, просто найдя нечетный цикл минимальной длины.

Результатом метода эллипсоида является либо:

• Любая точка многогранника (т. Е. Любая допустимая точка), или -${\ displaystyle Q}$
• Доказательство, которое пусто.${\ displaystyle Q}$

Минимизация с учетом неравенства функции, которая всюду равна нулю, соответствует задаче простого определения любой допустимой точки. Оказывается, любую задачу линейного программирования можно свести к задаче линейной выполнимости (например, минимизировать нулевую функцию с учетом некоторых ограничений линейного неравенства и равенства). Один из способов сделать это - объединить прямую и двойную линейные программы вместе в одну программу и добавить дополнительное (линейное) ограничение, согласно которому значение основного решения не хуже, чем значение двойного решения. Другой способ - рассматривать цель линейной программы как дополнительное ограничение и использовать двоичный поиск для поиска оптимального значения. ^{[ необходима цитата ]}

Неограниченная минимизация [ править ]

На k -й итерации алгоритма мы имеем точку в центре эллипсоида${\ Displaystyle х ^ {(к)}}$

${\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(x-x^{(k)}\right)^{T}P_{(k)}^{-1}\left(x-x^{(k)}\right)\leqslant 1\right\}.}$

Мы запрашиваем у оракула отсекающей плоскости вектор, такой что${\displaystyle g^{(k+1)}\in \mathbb {R} ^{n}}$

${\displaystyle g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.}$

Таким образом, мы заключаем, что

${\displaystyle x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\ :\ g^{(k+1)T}\left(z-x^{(k)}\right)\leqslant 0\right\}.}$

Мы устанавливаем эллипсоид минимального объема, содержащий полуэллипсоид, описанный выше, и вычисляем . Обновление предоставлено${\displaystyle {\mathcal {E}}^{(k+1)}}$${\displaystyle x^{(k+1)}}$

${\displaystyle {\begin{aligned}x^{(k+1)}&=x^{(k)}-{\frac {1}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}\\P_{(k+1)}&={\frac {n^{2}}{n^{2}-1}}\left(P_{(k)}-{\frac {2}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}{\tilde {g}}^{(k+1)T}P_{(k)}\right)\end{aligned}}}$

куда

${\displaystyle {\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}.}$

Критерий остановки задается тем свойством, что

${\displaystyle {\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f\left(x^{(k)}\right)-f\left(x^{*}\right)\leqslant \epsilon .}$

Примерная последовательность итераций

${\displaystyle k=0}$	${\displaystyle k=1}$	${\displaystyle k=2}$
${\displaystyle k=3}$	${\displaystyle k=4}$	${\displaystyle k=5}$

Минимизация с ограничениями по неравенству [ править ]

На k-й итерации алгоритма ограниченной минимизации мы, как и раньше , имеем точку в центре эллипсоида . Мы также должны поддерживать список значений, фиксирующих наименьшее объективное значение возможных итераций на данный момент. В зависимости от того, выполнима эта точка или нет , мы выполняем одну из двух задач:${\displaystyle x^{(k)}}$${\displaystyle {\mathcal {E}}^{(k)}}$${\displaystyle f_{\rm {best}}^{(k)}}$${\displaystyle x^{(k)}}$

• Если это возможно, выполните по существу то же обновление, что и в случае без ограничений, выбрав субградиент , удовлетворяющий${\displaystyle x^{(k)}}$${\displaystyle g_{0}}$

${\displaystyle g_{0}^{T}\left(x^{*}-x^{(k)}\right)+f_{0}\left(x^{(k)}\right)-f_{\rm {best}}^{(k)}\leqslant 0}$

• Если это невозможно и нарушает j -ое ограничение, обновите эллипсоид с разрезом выполнимости. Наша осуществимость разрез может быть субградиент из которых должен удовлетворять${\displaystyle x^{(k)}}$${\displaystyle g_{j}}$${\displaystyle f_{j}}$

${\displaystyle g_{j}^{T}\left(z-x^{(k)}\right)+f_{j}\left(x^{(k)}\right)\leqslant 0}$

для всех возможных z .

Производительность [ править ]

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

Однако метод эллипсоидов - важный теоретический метод комбинаторной оптимизации . В теории сложности вычислений алгоритм эллипсоида привлекателен тем, что его сложность зависит от количества столбцов и цифрового размера коэффициентов, но не от количества строк. В 21 веке появились алгоритмы внутренней точки с похожими свойствами ^{[ ссылка ]} .

Примечания [ править ]

Дальнейшее чтение [ править ]

• Дмитрис Алеврас и Манфред В. Падберг, Линейная оптимизация и расширения: проблемы и расширения , Universitext, Springer-Verlag, 2001. (Проблемы Падберга с решениями).
• В. Чандру и М.Р.Рао, Линейное программирование, Глава 31 в Справочнике по алгоритмам и теории вычислений , под редакцией М.Дж. Аталлаха, CRC Press 1999, с 31-1 по 31-37.
• В. Чандру и MRRao, Целочисленное программирование, глава 32 в Справочнике по алгоритмам и теории вычислений , под редакцией MJAtallah, CRC Press 1999, с 32-1 по 32-45.
• Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Springer-Verlag.
• Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: теория и расширения . Springer-Verlag.
• Л. Ловас : Алгоритмическая теория чисел, графиков и выпуклости , серия региональных конференций CBMS-NSF по прикладной математике 50, SIAM, Филадельфия, Пенсильвания, 1986
• Каттта Г. Мурти, Линейное программирование , Wiley, 1983.
• М. Падберг , Линейная оптимизация и расширения , второе издание, Springer-Verlag, 1999.
• Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность , исправленное переиздание с новым предисловием, Dover.
• Александр Шрайвер , Теория линейного и целочисленного программирования . Джон Уайли и сыновья, 1998, ISBN 0-471-98232-6 

Внешние ссылки [ править ]

• EE364b , домашняя страница Стэнфордского курса