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

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

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

История

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

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

Эллипсоидальный алгоритм позволяет теоретикам сложности достичь (в худшем случае) границ, которые зависят от размерности проблемы и размера данных, но не от количества строк, поэтому он оставался важным в теории комбинаторной оптимизации в течение многих лет. Только в 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} (x) = 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}}}$

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

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

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

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

В контексте линейного программирования все ограничения линейны и представляют собой выпуклый многогранник . Тогда оракул разделения можно легко реализовать следующим образом. Учитывая ограничения и точку , оракул просто вычисляет : ${\ 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}$

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

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

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

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

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

Безусловная минимизация

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

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

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

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

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

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

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

${\ displaystyle {\ begin {align} 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 {align}}}$

где

${\ Displaystyle {\ тильда {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 х ^ {(к)}}$${\ Displaystyle {\ mathcal {E}} ^ {(к)}}$${\ displaystyle f _ {\ rm {лучший}} ^ {(k)}}$${\ Displaystyle х ^ {(к)}}$

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

${\ displaystyle g_ {0} ^ {T} \ left (x ^ {*} - x ^ {(k)} \ right) + f_ {0} \ left (x ^ {(k)} \ right) -f_ {\ rm {лучший}} ^ {(k)} \ leqslant 0}$

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

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

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

Представление

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

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

Заметки

дальнейшее чтение

• Дмитрис Алеврас и Манфред В. Падберг, Линейная оптимизация и расширения: проблемы и расширения , Universitext, Springer-Verlag, 2001. (Проблемы Падберга с решениями).
• В. Чандру и MRRao, Линейное программирование, глава 31 в Справочнике по алгоритмам и теории вычислений , под редакцией MJAtallah, 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 , домашняя страница Стэнфордского курса