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

алгоритм знаходження точки, що лежить у перетині опуклих множин

Метод еліпсоїдів — алгоритм знаходження точки, що лежить у перетині опуклих множин. Розробив Немирівський Аркадій Семенович[en], до алгоритмічної реалізації ловів Л. Г. Хачіян[en] у ОЦ АН СРСР[ru].

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

ред.

На початку вибирається велика куля, що містить перетин опуклих множин. Спосіб побудови цієї кулі залежить від задачі. Далі на кожному кроці є еліпсоїд, заданий центром   та векторами  . Еліпсоїду належать точки  , для яких   . Зазначимо, що той самий еліпсоїд можна задати декількома способами. Якщо центр цього еліпсоїда належить усім опуклим множинам, то точку знайдено. Інакше існує гіперплощина  , що проходить через точку  , така, що одна з множин повністю лежить по один бік від неї. Тоді можна перейти від початкового базису   до іншого базису   такого, що   паралельні  , а   спрямований у бік множини. Покладемо тепер  ,  ,   при   . Цей новий еліпсоїд містить половину старого і має менший об'єм. Таким чином, об'єм еліпсоїда зменшується експоненційно зі зростанням числа кроків і шукану точку буде знайдено за   кроків, де   — об'єм початкової кулі, а   — об'єм області перетину. Загальний час роботи алгоритму виходить рівним  , де   — число множин,   — час перевірки належності точки множині.

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

ред.

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

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

ред.

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

Примітки

ред.

Література

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