Метод эллипсоида

редактировать

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

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

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

Содержание

1 История
2 Описание
3 Неограниченная минимизация
4 Минимизация с учетом неравенства
- 4.1 Применение в линейном программировании
5 Производительность
6 Примечания
7 Дополнительная литература
8 Внешние ссылки

История

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

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

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

Описание

Задача выпуклой минимизации состоит из выпуклой функции $f 0 ( x): R n → R {\ displaystyle f_ {0} (x): \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ $f_ {0} (x): {\ mathbb {R}} ^ {n} \ to {\ mathbb {R}}$ для минимизации по переменной x, выпуклый ограничения неравенства вида $fi (x) ⩽ 0 {\ displaystyle f_ {i} (x) \ leqslant 0}$ ${\ displaystyle f_ {i} (x) \ leqslant 0}$ , где функции $fi {\ displaystyle f_ {i}}$ $f_ {i}$ являются выпуклыми, и ограничения линейного равенства вида $hi (x) = 0 {\ displaystyle h_ {i} (x) = 0}$ $h_ {i} (x) = 0$ . Нам также дан начальный эллипсоид $E (0) ⊂ R n {\ displaystyle {\ mathcal {E}} ^ {(0)} \ subset \ mathbb {R} ^ {n} }$ ${\ mathcal {E}} ^ {{(0)}} \ subset {\ mathbb {R}} ^ {n}$ определяется как

E (0) = {z ∈ R n: (z - x 0) TP (0) - 1 (z - x 0) ⩽ 1} {\ displaystyle {\ mathcal {E}} ^ {(0)} = \ left \ {z \ in \ mathbb {R} ^ {n} \: \ (z-x_ {0}) ^ {T} P _ {(0)} ^ { -1} (z-x_ {0}) \ leqslant 1 \ right \}}

{\ displaystyle {\ mathcal {E}} ^ {(0)} = \ left \ {z \ in \ mathbb {R} ^ {n} \: \ (z-x_ {0}) ^ {T} P _ {(0)} ^ {- 1} (z-x_ {0}) \ leqslant 1 \ right \}}

, содержащий минимизатор $x ∗ {\ displaystyle x ^ {*}}$ $x ^ {*}$ , где $P (0) ≻ 0 {\ displaystyle P _ {(0)} \ succ 0}$ ${\ displaystyle P _ {(0)} \ succ 0}$ и $x 0 {\ displaystyle x_ {0}}$ $x_{0}$ является центром $E {\ displaystyle {\ mathcal {E}}}$ ${\ mathcal {E}}$ . Наконец, мы требуем существования оракула секущей плоскости для функции f. Один пример плоскости отсечения дается субградиентом g f.

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

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

E (k) = {x ∈ R n: (x - x (k)) TP (k) - 1 (x - x (k)) ⩽ 1}. {\ 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 {\ mathcal {E}} ^ {(k)} = \ left \ {x \ in \ mathbb {R} ^ {n} \: \ \ left (xx ^ {(k)} \ right) ^ {T} P _ {(k)} ^ {- 1} \ left (xx ^ {(k)} \ right) \ leqslant 1 \ right \}.}

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

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

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

Отсюда заключаем, что

x ∗ ∈ E (k) ∩ {z: g (k + 1) T (z - x (k)) ⩽ 0}. {\ Displaystyle х ^ {*} \ in {\ mathcal {E}} ^ {(k)} \ cap \ left \ {z \: \ g ^ {(k + 1) T} \ left (zx ^ {( k)} \ right) \ leqslant 0 \ right \}.}

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

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

x (k + 1) = x (k) - 1 n + 1 P (k) g ~ (k + 1) P (k + 1) = n 2 n 2 - 1 (P (к) - 2 N + 1 п (к) г ~ (к + 1) г ~ (к + 1) TP (к)) {\ Displaystyle {\ begin {выровнено} х ^ {(к + 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)} {

{\ 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}}}

где

g ~ (k + 1) = (1 g (k + 1) TP (k) g (k + 1)) g (k + 1). {\ Displaystyle {\ тильда {g}} ^ {(k + 1)} = \ left ({\ frac {1} {\ sqrt {g ^ {(k + 1) T} P _ {(k)} g ^ {(k + 1)}}}} \ right) g ^ {(k + 1)}.}

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

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

g (k) TP (k) g (k) ⩽ ϵ ⇒ f (x (k)) - f (x ∗) ⩽ ϵ. {\ 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 {\ sqrt {g ^ {(k) T} P _ {(k)} g ^ {(k)}}} \ leqslant \ epsilon \ quad \ Rightarrow \ quad f \ left (x ^ {(k)} \ right) -f \ left (x ^ {*} \ right) \ leqslant \ epsilon.}

Пример последовательности итераций
$k = 0 {\ displaystyle k = 0}$ $k = 0$	$k = 1 { \ displaystyle k = 1}$ $k = 1$	$k = 2 {\ displaystyle k = 2}$ $k = 2$
$k = 3 {\ displaystyle k = 3}$ $k = 3$	$k = 4 {\ displaystyle k = 4}$ $k = 4$	$k = 5 {\ displaystyle k = 5}$ $k = 5$

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

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

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

g 0 T (x ∗ - x (k)) + f 0 (x (k)) - fbest (k) ⩽ 0 {\ displaystyle g_ {0} ^ {T} \ left (x ^ {*} - x ^ {(k)} \ right) + f_ {0} \ left (x ^ {(k)} \ right) -f _ {\ rm {best}} ^ {(k)} \ leqslant 0}

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

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

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

{\ displaystyle g_ {j} ^ {T} \ left (zx ^ { (к)} \ вправо) + f_ {j} \ влево (х ^ {(к)} \ вправо) \ leqslant 0}

для всех допустимых z.

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

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

Производительность

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

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

Примечания

^М. Грётшель, Л. Ловас, А. Schrijver : Геометрические алгоритмы и комбинаторная оптимизация, Springer, 1988.
^Л. Ловас : Алгоритмическая теория чисел, графиков и выпуклости, Серия региональных конференций CBMS-NSF по прикладной математике 50, SIAM, Филадельфия, Пенсильвания, 1986.
^V. Чандру и М.Р. Рао, Линейное программирование, глава 31 в Справочнике по алгоритмам и теории вычислений, под редакцией М. Дж. Аталлах, CRC Press 1999, с 31-1 по 31-37.
^В. Чандру и М. Р. Рао, Целочисленное программирование, глава 32 в Справочнике по алгоритмам и теории вычислений, под редакцией М. Дж. Аталлаха, CRC Press 1999, с 32-1 по 32-45.

Дополнительная литература

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

Внешние ссылки

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