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

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

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

История

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

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

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

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

Описание

Основная статья: Выпуклая оптимизация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому мы заключаем, что

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

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

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

где

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

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

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

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

Минимизация

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

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

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

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

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

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

в

сложности во время

Гарантия сложности во время выполнения метода эллипсоида в реальной модели RAM дается следующей теоремой.

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

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

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

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

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

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

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

$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}$.

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

Практическое исполнение

Метод эллипсоида используется для решения задач малой размерности, таких как задачи планарного локации, где он численно стабилен . Немировский и БенТал говорят, что оно эффективно, если число переменных не превышает 20–30; это так, даже если существуют тысячи ограничений, поскольку количество итераций не зависит от количества ограничений. Однако в задачах со многими переменными метод эллипсоида очень неэффективен, так как число итераций растет как O( n ² ).

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

значимость

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

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

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

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

Шаг 1: сведение оптимизации к поиску . Теорема двойственности линейного программирования гласит, что мы можем свести описанную выше задачу минимизации к задаче поиска: найти x,y st Ax ≤ b ; А ^Т у = с; у ≤ 0; с ^Т х=б ^Т й. Первая проблема разрешима тогда и только тогда, когда разрешима вторая задача; в случае, если задача разрешима, x -компоненты решения второй задачи являются оптимальным решением первой задачи. Поэтому с этого момента можно считать, что нам необходимо решить следующую задачу: найти 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 время .

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

Варианты

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

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

В методе эллипсоида центрального сечения разрезы всегда проходят через центр текущего эллипсоида. Входными данными являются рациональное число ε >0, выпуклое тело K, заданное оракулом слабого разделения и число R такое, что S(0, R ) (шар радиуса R вокруг начала координат) содержит K. , Результатом является одно из следующих:

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

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

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

В методе мелкого эллипсоида разрезы удаляют менее половины эллипсоида на каждом этапе. Этот вариант не очень полезен на практике, но имеет теоретическое значение: позволяет доказать результаты, которые невозможно получить из других вариантов. Входными данными являются рациональное число ε >0, выпуклое тело K, оракулом мелкого разделения , и число R такое, что S(0, R ) содержит K. заданное Выходными данными являются положительно определенная матрица A и точка a, для которой выполняется одно из следующих условий:

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

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

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

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

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

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

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

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

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

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

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

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

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

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