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

Итерационный метод минимизации выпуклых функций

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

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

История

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

Как алгоритм для решения задач линейного программирования с рациональными данными, алгоритм эллипсоида был изучен Леонидом Хачияном ; достижением Хачияна было доказательство полиномиальной разрешимости линейных программ. Это был заметный шаг с теоретической точки зрения: стандартным алгоритмом для решения линейных задач в то время был симплексный алгоритм , время выполнения которого обычно линейно зависит от размера задачи, но для которого существуют примеры, для которых оно экспоненциально зависит от размера задачи. Таким образом, наличие алгоритма, который гарантированно является полиномиальным для всех случаев, было теоретическим прорывом.

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

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

Описание

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

• Выпуклая функция , которую необходимо минимизировать по вектору (содержащему n переменных); ${\displaystyle f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle x}$
• Выпуклые ограничения-неравенства вида , где функции выпуклы; эти ограничения определяют выпуклое множество . ${\displaystyle f_{i}(x)\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}}}$

Наконец, мы требуем существования оракула разделения для выпуклого множества . При наличии точки оракул должен возвращать один из двух ответов: ^[5] ${\displaystyle Q}$ ${\displaystyle x\in \mathbb {R} ^{n}}$

• «Дело в том », или - ${\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}$

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

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

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

Неограниченная минимизация

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

${\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(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .}$

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

На 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}(x^{*}-x^{(k)})+f_{0}(x^{(k)})-f_{\rm {best}}^{(k)}\leqslant 0}$

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

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

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

Производительность в выпуклых программах

Теоретическая гарантия сложности во время выполнения

Гарантия сложности выполнения метода эллипсоида в реальной модели RAM дается следующей теоремой. ^{[6] : Теорема 8.3.1}

Рассмотрим семейство задач выпуклой оптимизации вида: минимизировать f ( x ) st x is in G , где f — выпуклая функция, а G — выпуклое множество (подмножество евклидова пространства R ⁿ ). Каждая задача p в семействе представлена ​​вектором данных Data( p ), например, действительными коэффициентами в матрицах и векторах, представляющих функцию f и допустимую область G . Размер задачи p , Size( p ), определяется как количество элементов (действительных чисел) в Data( p ). Необходимы следующие предположения:

1. G (допустимая область) равна:
   • Ограниченный;
   • Имеет непустую внутреннюю часть (значит, существует строго достижимая точка);
2. Имея данные Data( p ), можно выполнить вычисления, используя арифметические операции poly(Size(p)):
   • Эллипсоид, содержащий G ;
   • Нижняя граница MinVol(p ) >0 для объема G.
3. При наличии Data( p ) и точки x в R ⁿ можно выполнить вычисления с использованием арифметических операций poly(Size(p)):
   • Оракул разделения для G (то есть: либо утверждает, что x принадлежит G , либо возвращает гиперплоскость, разделяющую x от G ).
   • Оракул первого порядка для f (то есть: вычислить значение f ( x ) и субградиент f' ( x )).

При этих предположениях метод эллипсоида является «R-полиномиальным». Это означает, что существует полином Poly, такой что для каждого экземпляра задачи p и каждого аппроксимационного отношения ε >0 метод находит решение x, удовлетворяющее :

${\displaystyle f(x)-\min _{G}f\leq \varepsilon \cdot [\max _{G}f-\min _{G}f]}$,

используя не более следующего количества арифметических операций над действительными числами:

${\displaystyle Poly(Size(p))\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

где V ( p ) — это величина, зависящая от данных. Интуитивно это означает, что количество операций, требуемых для каждой дополнительной цифры точности, является полиномом Size( p ). В случае метода эллипсоида мы имеем:

${\displaystyle V(p)=\left[{\frac {Vol({\text{initial ellipsoid}})}{Vol(G)}}\right]^{1/n}\leq \left[{\frac {Vol({\text{initial ellipsoid}})}{MinVol(p)}}\right]^{1/n}}$.

Метод эллипсоида требует максимум шагов, и каждый шаг требует арифметических операций Poly(Size(p)). ${\displaystyle 2(n-1)n\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

Практическая эффективность

Метод эллипсоида используется в задачах малой размерности, таких как плоские задачи размещения, где он численно устойчив . Немировски и Бентал ^{[6] : Раздел 8.3.3} говорят, что он эффективен, если число переменных не превышает 20-30; это так даже при наличии тысяч ограничений, поскольку число итераций не зависит от числа ограничений. Однако в задачах со многими переменными метод эллипсоида очень неэффективен, поскольку число итераций растет как O( n ² ).

Даже при решении задач «малого» размера он страдает от численной нестабильности и низкой производительности на практике ^{[ необходима ссылка ]} .

Теоретическая значимость

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

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

Производительность в линейных программах

Леонид Хачиян применил метод эллипсоидов к частному случаю линейного программирования : минимизировать c ^T x st Ax ≤ b , где все коэффициенты в A,b,c являются рациональными числами. Он показал, что линейные программы могут быть решены за полиномиальное время. Вот набросок теоремы Хачияна. ^{[6] : Sec.8.4.2}

Шаг 1: сведение оптимизации к поиску . Теорема двойственности линейного программирования гласит, что мы можем свести указанную выше задачу минимизации к задаче поиска: find x,y st Ax ≤ b ; A ^T y = c ; y ≤ 0 ; c ^T x=b ^T y. Первая задача разрешима тогда и только тогда, когда разрешима вторая задача; в случае, если задача разрешима, x -компоненты решения второй задачи являются оптимальным решением первой задачи. Поэтому с этого момента мы можем считать, что нам нужно решить следующую задачу: find z ≥ 0 st Rz ≤ r . Умножая все рациональные коэффициенты на общий знаменатель, мы можем считать, что все коэффициенты являются целыми числами.

Шаг 2: сведение поиска к проверке осуществимости . Задача поиска z ≥ 0 st Rz ≤ r может быть сведена к задаче бинарного решения: « существует ли z ≥ 0 такое, что Rz ≤ r ? ». Это можно сделать следующим образом. Если ответ на задачу решения «нет», то ответ на задачу поиска «нет», и мы закончили. В противном случае берем первое ограничение неравенства R ₁ z ≤ r ₁ ; заменяем его равенством R ₁ z = r ₁ ; и снова применяем задачу решения. Если ответ «да», мы сохраняем равенство; если ответ «нет», это означает, что неравенство избыточно, и мы можем его удалить. Затем мы переходим к следующему ограничению неравенства. Для каждого ограничения мы либо преобразуем его в равенство, либо удаляем его. Наконец, у нас есть только ограничения равенства, которые можно решить любым методом решения системы линейных уравнений.

Шаг 3 : задачу принятия решения можно свести к другой задаче оптимизации. Определим функцию невязки f(z) := max[(Rz) ₁ -r ₁ , (Rz) ₂ -r ₂ , (Rz) ₃ -r ₃ ,...]. Очевидно, что f ( z )≤0 тогда и только тогда, когда Rz ≤ r . Поэтому для решения задачи принятия решения достаточно решить задачу минимизации: min _z f ( z ). Функция f является выпуклой (она является максимумом линейных функций). Обозначим минимальное значение через f *. Тогда ответ на задачу принятия решения — «да», тогда и только тогда, когда f*≤0.

Шаг 4 : В задаче оптимизации min _z f ( z ) можно предположить, что z находится в поле со стороной 2 ^L , где L — длина бит данных задачи. Таким образом, у нас есть ограниченная выпуклая программа, которая может быть решена с любой точностью ε методом эллипсоида за время, полиномиальное по L .

Шаг 5 : Можно доказать, что если f*>0, то f*>2 ^-poly(L) для некоторого полинома. Поэтому мы можем выбрать точность ε=2 ^-poly(L) . Тогда ε-приближенное решение, найденное методом эллипсоида, будет положительным, если и только если f*>0, если и только если задача принятия решения неразрешима.

Варианты

Метод эллипсоида имеет несколько вариантов, в зависимости от того, какие именно разрезы используются на каждом этапе. ^{[1] : Раздел 3}

Различные разрезы

В методе эллипсоида центрального разреза ^{[1] : 82, 87–94} разрезы всегда проходят через центр текущего эллипсоида. Входными данными являются рациональное число ε >0, выпуклое тело K, заданное слабым оракулом разделения , и число R, такое, что S(0, R ) (шар радиуса R вокруг начала координат) содержит K . Выходными данными является одно из следующих:

• (а) Вектор на расстоянии не более ε от K, или --
• (б) Положительно определенная матрица A и точка a такие, что эллипсоид E( A , a ) содержит K , а объем E( A , a ) не превышает ε .

Число шагов равно , число требуемых цифр точности равно p  := 8 N , а требуемая точность оракула разделения равна d  := 2 ^{- p} . ${\displaystyle N:=\lceil 5n\log(1/\epsilon )+5n^{2}\log(2R)\rceil }$

В методе эллипсоида с глубоким разрезом ^{[1] : 83} разрезы удаляют более половины эллипсоида на каждом шаге. Это ускоряет обнаружение того, что K пуст. Однако, когда K непусто, есть примеры, в которых метод центрального разреза находит допустимую точку быстрее. Использование глубоких разрезов не меняет порядок величины времени выполнения.

В методе неглубокого эллипсоида разрезов [ ^{1] : 83, 94–101} разрезы удаляют менее половины эллипсоида на каждом шаге. Этот вариант не очень полезен на практике, но имеет теоретическое значение: он позволяет доказывать результаты, которые не могут быть получены из других вариантов. Входными данными являются рациональное число ε >0, выпуклое тело K, заданное неглубоким оракулом разделения , и число R, такое что S(0, R ) содержит K . Выходными данными являются положительно определенная матрица A и точка a , такие, что выполняется одно из следующих условий:

• (а) Эллипсоид E( A , a ) был объявлен оракулом «жестким», или -
• (б) K содержится в E( A , a ) и объем E( A , a ) не превышает ε .

Число шагов равно , а число требуемых цифр точности равно p  := 8 N. ${\displaystyle N:=\lceil 5n(n+1)^{2}\log(1/\epsilon )+5n^{2}(n+1)^{2}\log(2R)+\log(n+1)\rceil }$

Разные эллипсоиды

Существует также различие между методами описанного эллипсоида и вписанного эллипсоида: ^[7]

• В методе описанного эллипсоида каждая итерация находит эллипсоид наименьшего объема, содержащий оставшуюся часть предыдущего эллипсоида. Этот метод был разработан Юдиным и Немировским. ^[8]
• В методе вписанного эллипсоида каждая итерация находит эллипсоид наибольшего объема, который содержит оставшуюся часть предыдущего эллипсоида. Этот метод был разработан Тарасовым, Хачяном и Эрлихом. ^[9]

Методы различаются по сложности выполнения (ниже n — количество переменных, а epsilon — точность):

• Описанный метод требует итераций, где каждая итерация состоит из нахождения разделяющей гиперплоскости и нахождения нового описанного эллипсоида. Нахождение описанного эллипсоида требует времени. ${\displaystyle O(n^{2})\ln {\frac {1}{\epsilon }}}$ ${\displaystyle O(n^{2})}$
• Вписанный метод требует итераций, где каждая итерация состоит из поиска разделяющей гиперплоскости и поиска нового вписанного эллипсоида. Нахождение вписанного эллипсоида требует времени для некоторого небольшого . ${\displaystyle O(n)\ln {\frac {1}{\epsilon }}}$ ${\displaystyle O(n^{3.5+\delta })}$ ${\displaystyle \delta >0}$

Относительная эффективность методов зависит от времени, необходимого для нахождения разделяющей гиперплоскости, которое зависит от приложения: если время выполнения составляет , то более эффективен описанный метод, а если , то более эффективен вписанный метод. ^[7] ${\displaystyle O(n^{t})}$ ${\displaystyle t\leq 2.5}$ ${\displaystyle t>2.5}$

Связанные методы

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

Примечания

1. Grötschel, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, МР  1261419
2. Л. Ловас : Алгоритмическая теория чисел, графов и выпуклости , CBMS-NSF Региональная конференция серии по прикладной математике 50, SIAM, Филадельфия, Пенсильвания, 1986.
3. V. Chandru и MRRao, Линейное программирование, Глава 31 в Algorithms and Theory of Computation Handbook , под редакцией MJ Atallah , CRC Press 1999, 31-1 по 31-37.
4. V. Chandru и MRRao, Целочисленное программирование, Глава 32 в Algorithms and Theory of Computation Handbook , под редакцией MJAtallah, CRC Press 1999, 32-1 по 32-45.
5. "MIT 6.854 Весна 2016 Лекция 12: От разделения к оптимизации и обратно; Метод эллипсоида - YouTube". www.youtube.com . Архивировано из оригинала 2021-12-22 . Получено 2021-01-03 .
6. Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .^{[ постоянная мертвая ссылка ]}
7. Newman, DJ; Primak, ME (1992-12-01). "Сложность методов описанного и вписанного эллипсоида для решения равновесных экономических моделей". Прикладная математика и вычисления . 52 (2): 223–231. doi :10.1016/0096-3003(92)90079-G. ISSN  0096-3003.
8. https://elibrary.ru/item.asp?id=38308898 ^{[ пустой URL ]}
9. Примак, М.Е.; Хейфец, Б.Л. (1995-06-01). «Модификация метода вписанного эллипсоида». Математическое и компьютерное моделирование . 21 (11): 69–76. doi :10.1016/0895-7177(95)00080-L. ISSN  0895-7177.

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

• Дмитрис Алеврас и Манфред В. Падберг, Линейная оптимизация и расширения: проблемы и расширения , Universitext, Springer-Verlag, 2001. (Задачи от Падберга с решениями.)
• V. Chandru и MRRao, Линейное программирование, Глава 31 в Справочнике по алгоритмам и теории вычислений , под редакцией MJAtallah, CRC Press 1999, 31-1 по 31-37.
• V. Chandru и 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.
• Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность , исправленное переиздание с новым предисловием, Довер.
• Александр Шрийвер , Теория линейного и целочисленного программирования . Джон Уайли и сыновья, 1998, ISBN 0-471-98232-6 

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

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