Елипсоидни методи - Лексикон за математика
Лексикон по математика: елипсоидни методи
Елипсоидните методи се класа на методи за решавање на линеарни (и конвексни) проблеми со оптимизација. Основната идеја е како што следува: Прво, проблемот со оптимизација е преформулиран како проблем за одлука дали полиедронот \ startP = \\ крајот не е празен. Ова се прави со примена на теоремата за двојност на линеарно оптимизирање.
Примарен проблем \ започне ^ \ cdot v \ до \ min \, \, \, E \ cdot v \ ge f, \, \, v \ ge 0 \ крај и придружниот двоен проблем \ започне ^ \ cdot y \ до \ max \, \, \, ^ \ cdot y \ le c, \, \, y \ ge 0 \ крај на системот \ start-E \ cdot v \ le -f, -v \ le 0, \\ ^ \ cdot y \ le c, -y \ le 0, \\ ^ \ cdot v - ^ \ cdot y \ le 0 \ крај комбинирано. Ова го дава системот што ги дефинира P x ≤ b (со x: = (v, y) и соодветната дефиниција на A и b).
Еквивалентноста на задачата за наоѓање на изводлива точка за овој проблем на оригиналната задача за оптимизација произлегува од фактот дека јазот на двојност c T * x - b T * y исчезнува само во екстремни точки, но инаку е позитивен.
Вистинската постапка сега започнува со изградба на специјален елипсоид E0 = (z0, B0). Подмножеството Е (z, B) се нарекува des ℝ n е (специјален) елипсоид со центар z ℝ n ако е во форма \ започнете \ >> ^ | ^ \ cdot ^ \ cdot (x-z) \ le 1 \> \ крајот се пишува. Овде Б е позитивно дефинитивна (n, n) матрица. Првиот елипсоид E0 е избран така што содржи точка на раствор на P во случајот P ≠ see (види подолу).
Изградба на новиот елипсоид
Процесот продолжува сè додека не се најде средна точка z ∈ P или некој може да гарантира дека P =. Вториот се постигнува со споредување на волуменот на елипсоидите Ei со проценка на минималниот волумен на P ∩ E0.
Елипсоидниот метод е од големо историско значење затоа што тоа беше првиот метод за полиномното време за линеарно програмирање во моделот Туринг. Притоа, се разгледуваат проблеми што се состојат само од рационални влезни податоци. Без ограничување, тука се претпоставува дека почетниот систем се состои само од цели податоци (што може да се постигне по множење на системот со заеднички главен именител на сите рационални податоци).
Сега, наместо A ⋅ x ≤ b, размислете за систем на строги нееднаквости \ startA \ cdot x \ lt b + ^ \ cdot e, \ end каде e = (1, ..., 1) T и L ја означува големината на битот на почетниот проблем. Новиот систем може да се реши точно ако беше стариот. Овој однос помеѓу двата система е во основа заснован на интегралниот карактер на влезните податоци и можната проценка (нагоре) на големината на битот на одредени решенија користејќи го правилото на Крамер. Од една страна, од излезните податоци може да се најде соодветен почетен елипсоид E0 со (P ≠ ∅ ⇒ E0 ∩ P ≠ ∅); од друга страна, може да се постави долна граница за волуменот V на пресекот на E0 со множеството на решенија \ (\ mathop
\ граници ^ \) од A ⋅ x - L · e. Постапката сега се применува на \ (\ mathop
\ ограничува ^ \) и се повторува се додека не започне \ текст (_) \ le ^ \ cdot \ текст (_) \ lt V \ крај (што бидејќи λ m × n> дава број на аритметички операции од познатите елипсоидни методи се ограничени нагоре. Елипсоидните методи не се полином во алгебарските модели за пресметка (резултат од Трауб и Возниаковски (1982)).