Метод еліпсоїдів

Метод еліпсоїдів — алгоритм знаходження точки, що лежить у перетині опуклих множин. Розробив ^[en], до алгоритмічної реалізації ловів ^[en] у ^[ru].

Опис алгоритму

На початку вибирається велика куля, що містить перетин опуклих множин. Спосіб побудови цієї кулі залежить від задачі. Далі на кожному кроці є еліпсоїд, заданий центром ${\displaystyle v}$ та векторами ${\displaystyle v_{1},v_{2},\dots ,v_{n}\in \mathbb {R} ^{n}}$. Еліпсоїду належать точки ${\displaystyle v+c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}}$, для яких ${\displaystyle c_{1}^{2}+c_{2}^{2}+\cdots +c_{n}^{2}\leqslant 1}$ . Зазначимо, що той самий еліпсоїд можна задати декількома способами. Якщо центр цього еліпсоїда належить усім опуклим множинам, то точку знайдено. Інакше існує гіперплощина ${\displaystyle \pi }$, що проходить через точку ${\displaystyle v}$, така, що одна з множин повністю лежить по один бік від неї. Тоді можна перейти від початкового базису ${\displaystyle v_{i}}$ до іншого базису ${\displaystyle \tau ,w_{2},\dots w_{n}}$ такого, що ${\displaystyle w_{i}}$ паралельні ${\displaystyle \pi }$, а ${\displaystyle \tau }$ спрямований у бік множини. Покладемо тепер ${\displaystyle v'=v+{\frac {\tau }{n+1}}}$, ${\displaystyle v'_{1}={\frac {n\tau }{n+1}}}$, ${\displaystyle v'_{i}=w_{i}{\frac {n}{\sqrt {n^{2}-1}}}}$ при ${\displaystyle i\geq 2}$ . Цей новий еліпсоїд містить половину старого і має менший об'єм. Таким чином, об'єм еліпсоїда зменшується експоненційно зі зростанням числа кроків і шукану точку буде знайдено за ${\displaystyle O(n^{2}\log(V_{1}/V_{2}))}$ кроків, де ${\displaystyle V_{1}}$ — об'єм початкової кулі, а ${\displaystyle V_{2}}$ — об'єм області перетину. Загальний час роботи алгоритму виходить рівним ${\displaystyle O(Ntn^{2}\log(V_{1}/V_{2}))}$, де ${\displaystyle N}$ — число множин, ${\displaystyle t}$ — час перевірки належності точки множині.

Застосування до задачі лінійного програмування

Якщо в задачі лінійного програмування вдалося побудувати кулю, що містить шуканий розв'язок, її можна розв'язати методом еліпсоїдів. Для цього спочатку знаходимо якусь точку ${\displaystyle u}$ всередині кулі, що задовольняє обмеження задачі. Проводимо через неї гіперплощину ${\displaystyle f(x)<f(u)}$, де ${\displaystyle f}$ — цільова функція, і знаходимо точку в перетині початкових та нової гіперплощин (починаючи з поточного еліпсоїда). З новою знайденою точкою проробляємо те саме. Процес збігається до оптимального розв'язку з експоненційною швидкістю (оскільки з цією швидкістю зменшується об'єм еліпсоїда).

Ефективність методу

Поліноміальний алгоритм теоретично міг би стати новим стандартом, однак, на практиці алгоритм Хачіяна застосовувати слід обережно: існують задачі розміром 50 змінних, для яких знадобиться понад 24 тис. ітерацій методу Хачіяна, а кількість істотно простіших ітерацій симплекс-методу в таких випадках обчислюється сотнями чи навіть десятками. Однак є приклади задач, для яких алгоритми цього класу працюють у сотні разів ефективніше за стандартні реалізації симплекс-методу.

Примітки

1. Николенко, 2005.
2. Схрейвер, 1991, с. 264.

Література

• С.А. Ашманов. Линейное программирование. — М. : Главная редакция физико-математической литературы, 1981. — С. 288—289.
• А. Схрейвер. Теория линейного и целочисленного программирования, т1. — М. : Мир, 1991. — .
• С. Николенко. Теория и практика сложности // Компьютерра. — М. : ООО Журнал «Компьютерра», 2005. — Вип. 31.