Ellipsoid metode

Ellipsoidmetoden er en algoritme til at finde et punkt, der ligger i skæringspunktet mellem konvekse mængder. Udviklet af A. S. Nemirovsky og bragt til den algoritmiske implementering af L. G. Khachiyan ved Computing Center for USSR Academy of Sciences.

Beskrivelse af algoritmen

Først vælges en stor kugle, der indeholder skæringspunktet mellem konvekse sæt. Metoden til at konstruere denne bold afhænger af problemet. Yderligere er der ved hvert trin en ellipsoide specificeret af centrum og vektorer . Ellipsoiden indeholder punkter for hvilke . Bemærk, at den samme ellipsoide kan specificeres på flere måder. Hvis midten af denne ellipsoide tilhører alle konvekse sæt, er det nødvendige punkt fundet. Ellers eksisterer der et hyperplan , der passerer gennem punktet , sådan at et af sættene ligger helt på den ene side af det. Så kan du gå fra det oprindelige grundlag til et andet grundlag , som er parallelle og rettet mod sættet. Lad os nu sætte , , kl . Denne nye ellipsoide indeholder halvdelen af den gamle og har et mindre volumen. Således falder ellipsoidens volumen eksponentielt med en stigning i antallet af trin, og det ønskede punkt vil blive fundet i trin, hvor er volumen af den oprindelige kugle, og er volumen af skæringsområdet. Algoritmens samlede køretid er lig med , hvor er antallet af sæt, er tiden til at kontrollere, om et punkt hører til et sæt. $v$ ${\displaystyle v_{1},v_{2},\dots ,v_{n}\in \mathbb {R} ^{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}\leqslant 1$ $\pi$ $v$ $v_{i}$ $\tau ,w_{2},\dots w_{n}$ $w_{i}$ $\pi$ $\tau$ $v'=v+{\frac {\tau }{n+1}}$ $v'_{1}={\frac {n\tau }{n+1}}$ $v'_{i}=w_{i}{\frac {n}{{\sqrt {n^{2}-1))))$ $i\geq 2$ $O(n^{2}\log(V_{1}/V_{2}))$ $V_{1}$ $V_{2}$ $O(Ntn^{2}\log(V_{1}/V_{2}))$ $N$ $t$

Anvendelse til et lineært programmeringsproblem

Hvis det i et lineært programmeringsproblem var muligt at konstruere en kugle indeholdende den ønskede løsning, så kan det løses ved ellipsoidmetoden. For at gøre dette finder vi først et punkt inde i bolden, der opfylder problemets begrænsninger. Vi tegner et hyperplan igennem det , hvor er den objektive funktion, og finder et punkt i skæringspunktet mellem det oprindelige og det nye hyperplan (startende fra den nuværende ellipsoide). Vi gør det samme med det nyfundne punkt. Processen konvergerer til den optimale løsning med en eksponentiel hastighed (da volumen af ellipsoiden falder med denne hastighed). $u$ $f(x)<f(u)$ $f$

Metodens effektivitet

Den polynomielle algoritme kunne teoretisk set blive den nye standard, men i praksis bør Khachiyan-algoritmen bruges med forsigtighed: der er problemer med en størrelse på 50 variabler, der kræver mere end 24 tusinde iterationer af Khachiyan-metoden, mens antallet af meget simplere iterationer af simplex-metoden i sådanne tilfælde beregnes hundreder eller endda tiere [1] [2] . Der er dog eksempler på problemer, hvor algoritmer af denne klasse arbejder hundredvis af gange mere effektivt end standardimplementeringer af simplex-metoden.

Noter

↑ Nikolenko, 2005 .
↑ Schreiver, 1991 , s. 264.

Litteratur

S.A. Ashmanov. Lineær programmering. - M. : Hovedudgave af fysisk og matematisk litteratur, 1981. - S. 288-289.
A. Schreiver. Teori om lineær og heltalsprogrammering, v1. - M . : "Mir", 1991. - ISBN 5-03-002754-8 .
S. Nikolenko. Teori og praksis om kompleksitet // Computerra. - M . : LLC Journal "Computerra", 2005. - Udgave. 31 .

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering