Metode elipsoidale - Lexicon de matematică
Lexicon de matematică: metode elipsoidale
Metodele elipsoide sunt o clasă de metode pentru rezolvarea problemelor de optimizare liniară (și convexă). Ideea de bază este următoarea: În primul rând, problema de optimizare este reformulată ca o problemă de decizie dacă un poliedru \ beginP = \\ end este ne-gol. Acest lucru se realizează prin aplicarea teoremei dualității optimizării liniare.
O problemă primară \ begin ^ \ cdot v \ to \ min \, \, \, E \ cdot v \ ge f, \, \, v \ ge 0 \ end și problema dublă asociată \ begin ^ \ cdot y \ to \ max \, \, \, ^ \ cdot y \ le c, \, \, y \ ge 0 \ end to the system \ begin-E \ cdot v \ le -f, -v \ le 0, \\ ^ \ cdot y \ le c, -y \ le 0, \\ ^ \ cdot v - ^ \ cdot y \ le 0 \ end combinat. Aceasta dă sistemul care definește P x ≤ b (cu x: = (v, y) și definiția corespunzătoare a lui A și b).
Echivalența sarcinii de a găsi un punct fezabil pentru această problemă la sarcina inițială de optimizare rezultă din faptul că decalajul de dualitate c T * x - b T * y dispare doar în puncte extreme, dar este altfel pozitiv.
Procedura actuală începe acum cu construirea unui elipsoid special E0 = (z0, B0). Un subset E (z, B) se numește des ℝ n este un elipsoid (special) cu centrul z ∈ ℝ n dacă este în forma \ begin \ >> ^ | ^ \ cdot ^ \ cdot (x-z) \ le 1 \> \ end se poate scrie. Aici B este o matrice definită pozitiv (n, n). Primul elipsoid E0 este ales astfel încât să conțină un punct de soluție P în cazul P ≠ ∅ (vezi mai jos).
Construcția noului elipsoid
Procesul continuă până când se găsește fie un punct de mijloc z ∈ P, fie se poate garanta că P = ∅. Acesta din urmă se realizează prin compararea volumului elipsoidelor Ei cu o estimare a volumului minim de P ∩ E0.
Metoda elipsoidă are o mare importanță istorică, deoarece a fost prima metodă polinomială de timp pentru programarea liniară în modelul Turing. Procedând astfel, se analizează problemele care constau doar din date de intrare raționale. Fără restricții, se presupune aici că sistemul inițial constă doar din date întregi (care pot fi realizate după înmulțirea sistemului cu numitorul principal comun al tuturor datelor raționale).
Acum, în loc de A ⋅ x ≤ b, luați în considerare un sistem de inegalități stricte \ beginA \ cdot x \ lt b + ^ \ cdot e, \ end unde e = (1, ..., 1) T și L denotă dimensiunea de biți a problemei inițiale. Noul sistem poate fi rezolvat exact dacă a fost cel vechi. Această relație dintre cele două sisteme se bazează în esență pe natura întregă a datelor de intrare și o posibilă estimare (în sus) a dimensiunii de biți a anumitor soluții prin intermediul regulii lui Cramer. Astfel, pe de o parte, un elipsoid de pornire adecvat E0 cu (P ≠ ∅ ⇒ E0 ∩ P ≠ ∅) poate fi găsit din datele de ieșire; pe de altă parte, se poate seta o limită inferioară pentru volumul V al intersecției lui E0 cu soluția setată \ (\ mathop
\ limits ^ \) din A ⋅ x - L · e. Procedura este acum aplicată la \ (\ mathop
\ limits ^ \) și iterează până când \ begin \ text (_) \ le ^ \ cdot \ text (_) \ lt V \ end (care datorită λ m × n> oferă numărul de operații aritmetice dintre metodele de elipsoid cunoscute sunt limitate în sus. Prin urmare, metodele elipsoidelor nu sunt polinomiale în modelele de calcul algebric (rezultat din Traub și Wozniakowski (1982)).