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

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

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

На початку вибирається велика куля, що містить перетин опуклих множин. Спосіб побудови цієї кулі залежить від задачі. Далі на кожному кроці є еліпсоїд, заданий центром $v$ та векторами $v_1,v_2,\dots ,v_n\in {ℝ}^n$. Еліпсоїду належать точки $v+c_1{v}_1+c_2{v}_2+\cdots +c_n{v}_n$, для яких $c_1^2+c_2^2+\cdots +c_n^2⩽1$ . Зазначимо, що той самий еліпсоїд можна задати декількома способами. Якщо центр цього еліпсоїда належить усім опуклим множинам, то точку знайдено. Інакше існує гіперплощина $\pi$, що проходить через точку $v$, така, що одна з множин повністю лежить по один бік від неї. Тоді можна перейти від початкового базису $v_i$ до іншого базису $\tau ,w_2,\dots w_n$ такого, що $w_i$ паралельні $\pi$, а $\tau$ спрямований у бік множини. Покладемо тепер $v^{\prime }=v+\frac{\tau }{n+1}$, $v{\text{'}}_1=\frac{n\tau }{n+1}$, $v{\text{'}}_i=w_i\frac{n}{\sqrt{n^2-1}}$ при $i\ge 2$ . Цей новий еліпсоїд містить половину старого і має менший об'єм. Таким чином, об'єм еліпсоїда зменшується експоненційно зі зростанням числа кроків і шукану точку буде знайдено за $O(n^2\log (V_1/V_2))$ кроків, де $V_1$ — об'єм початкової кулі, а $V_2$ — об'єм області перетину. Загальний час роботи алгоритму виходить рівним $O(Nt{n}^2\log (V_1/V_2))$, де $N$ — число множин, $t$ — час перевірки належності точки множині.

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

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

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

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

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття