Еліпсоїдні методи - лексикон математики
Лексикон математики: еліпсоїдні методи
Еліпсоїдні методи - це клас методів вирішення лінійних (і опуклих) задач оптимізації. Основна ідея полягає в наступному: По-перше, проблема оптимізації переформулюється як проблема рішення, чи багатогранник \ beginP = \\ end не є порожнім. Це робиться шляхом застосування теореми подвійності лінійної оптимізації.
Первинна задача \ begin ^ \ cdot v \ to \ min \, \, \, E \ cdot v \ ge f, \, \, v \ ge 0 \ end і пов'язана з цим подвійна задача \ begin ^ \ cdot y \ to \ max \, \, \, ^ \ cdot y \ le c, \, \, y \ ge 0 \ кінець до системи \ begin-E \ cdot v \ le -f, -v \ le 0, \\ ^ \ cdot y \ le c, -y \ le 0, \\ ^ \ cdot v - ^ \ cdot y \ le 0 \ end об'єднані. Це дає систему A.
Еквівалентність завдання пошуку реальної точки для цієї задачі до вихідної задачі оптимізації випливає з того факту, що розрив подвійності c T * x - b T * y зникає лише в крайніх точках, але в іншому випадку є позитивним.
Фактична процедура тепер починається з побудови спеціального еліпсоїда E0 = (z0, B0). Підмножина E (z, B) називається des ℝ n - (спеціальний) еліпсоїд із центром z ∈ ℝ n, якщо він має форму \ begin \ >> ^ | ^ \ cdot ^ \ cdot (x-z) \ le 1 \> \ end можна записати. Тут B - позитивно визначена (n, n) матриця. Перший еліпсоїд E0 обраний таким чином, щоб він містив точку розчину P у випадку P ≠ ∅ (див. Нижче).
Побудова нового еліпсоїда
Процес триває до тих пір, поки не буде знайдена середня точка z ∈ P, або можна гарантувати, що P = ∅. Останнє досягається порівнянням об’єму еліпсоїдів Ei з оцінкою мінімального об’єму P ∩ E0.
Еліпсоїдний метод має велике історичне значення, оскільки він був першим методом поліноміального часу для лінійного програмування в моделі Тьюрінга. При цьому розглядаються проблеми, що складаються лише з раціональних вхідних даних. Тут без обмежень можна припустити, що початкова система складається лише з цілочисельних даних (чого можна досягти, помноживши систему на загальний основний знаменник усіх раціональних даних).
Замість A ⋅ x ≤ b, розглянемо систему суворих нерівностей \ beginA \ cdot x \ lt b + ^ \ cdot e, \ end, де e = (1,…, 1) T, а L позначає бітовий розмір початкової задачі. Нова система може бути вирішена точно, якщо вона була старою. Цей взаємозв'язок між цими двома системами по суті заснований на цілочисельному характері вхідних даних та можливої оцінки (вгору) розрядності певних рішень за допомогою правила Крамера. З одного боку, відповідний вихідний еліпсоїд E0 з (P ≠ ∅ ⇒ E0 ∩ P ≠ ∅) можна знайти з вихідних даних; з іншого боку, можна встановити нижню межу для об'єму V перетину E0 із набором розв'язків \ (\ mathop
\ межі ^ \) від A ⋅ x - L · e. Тепер процедура застосована до \ (\ mathop
\ обмежує ^ \) і повторює, поки \ begin \ text (_) \ le ^ \ cdot \ text (_) \ lt V \ end (що через λ m × n> дає кількість арифметичних операцій відомі еліпсоїдні методи обмежені вгору. Тому еліпсоїдні методи не є поліномами в алгебраїчних моделях обчислення (результат Трауба та Возняковського (1982)).