Елипсоидни методи - лексикон на математиката
Лексикон на математиката: Елипсоидни методи
Елипсоидните методи са клас методи за решаване на линейни (и изпъкнали) задачи за оптимизация. Основната идея е следната: Първо, проблемът с оптимизацията се преформулира като проблем за решение дали многогранник \ beginP = \\ end не е празен. Това се прави чрез прилагане на теоремата за двойствеността на линейната оптимизация.
Основен проблем \ begin ^ \ cdot v \ to \ min \, \, \, E \ cdot v \ ge f, \, \, v \ ge 0 \ end и свързаният двоен проблем \ begin ^ \ cdot y \ до \ 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 комбинирани. Това дава системата, дефинираща P x ≤ b (с x: = (v, y) и съответната дефиниция на A и b).
Еквивалентността на задачата за намиране на осъществима точка за този проблем на първоначалната задача за оптимизация произтича от факта, че разликата в двойствеността 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 означава битовия размер на първоначалния проблем. Новата система може да бъде решена точно, ако е била старата. Тази връзка между двете системи се основава по същество на цялостния характер на входните данни и възможна оценка (нагоре) на битовия размер на определени решения, използвайки правилото на Cramer. От една страна, от изходните данни може да се намери подходящ изходен елипсоид E0 с (P ≠ ∅ ⇒ E0 found P ≠ ∅); от друга страна, може да се определи долна граница за обема V на пресечната точка на E0 с набора от решения \ (\ mathop
\ граници ^ \) на A ⋅ x - L · e. Сега процедурата е приложена към \ (\ mathop
\ ограничения ^ \) и итерации до \ begin \ text (_) \ le ^ \ cdot \ text (_) \ lt V \ end (което поради λ m × n> дава броя на аритметичните операции от известните елипсоидни методи са ограничени нагоре. Следователно елипсоидните методи не са полином в алгебричните модели за изчисление (резултат от Трауб и Возняковски (1982)).