Ellipsoid metod

Ellipsoidmetoden är en algoritm för att hitta en punkt som ligger i skärningspunkten mellan konvexa mängder. Utvecklat av A. S. Nemirovsky och fört till den algoritmiska implementeringen av L. G. Khachiyan vid Computing Center vid USSR Academy of Sciences.

Beskrivning av algoritmen

Först väljs en stor boll som innehåller skärningen av konvexa uppsättningar. Metoden för att konstruera denna boll beror på problemet. Vidare, vid varje steg finns det en ellipsoid specificerad av centrum och vektorer . Ellipsoiden innehåller punkter för vilka . Observera att samma ellipsoid kan specificeras på flera sätt. Om mitten av denna ellipsoid tillhör alla konvexa uppsättningar, hittas den önskade punkten. Annars finns det ett hyperplan som passerar genom punkten , så att en av uppsättningarna ligger helt på ena sidan av den. Sedan kan du gå från den ursprungliga basen till en annan bas som är parallell och riktad mot uppsättningen. Låt oss nu sätta , , vid . Denna nya ellipsoid innehåller hälften av den gamla och har en mindre volym. Således minskar volymen av ellipsoiden exponentiellt med en ökning av antalet steg, och den önskade punkten kommer att hittas i steg, där är volymen av den ursprungliga bollen, och är volymen av skärningsområdet. Algoritmens totala körtid är lika med , där är antalet uppsättningar, är tiden för att kontrollera om en punkt tillhör en uppsättning. $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$

Applikation på ett linjärt programmeringsproblem

Om det i ett linjärt programmeringsproblem var möjligt att konstruera en kula som innehåller den önskade lösningen, så kan det lösas med ellipsoidmetoden. För att göra detta hittar vi först någon punkt inuti bollen som uppfyller begränsningarna för problemet. Vi ritar ett hyperplan genom det , där är den objektiva funktionen, och hittar en punkt i skärningspunkten mellan det ursprungliga och nya hyperplanet (med början från den nuvarande ellipsoiden). Vi gör samma sak med den nyfunna punkten. Processen konvergerar till den optimala lösningen med en exponentiell hastighet (eftersom volymen av ellipsoiden minskar med denna hastighet). $u$ $f(x)<f(u)$ $f$

Metodens effektivitet

Polynomalgoritmen skulle teoretiskt sett kunna bli den nya standarden, men i praktiken bör Khachiyan-algoritmen användas med försiktighet: det finns problem med en storlek på 50 variabler som kräver mer än 24 tusen iterationer av Khachiyan-metoden, medan antalet mycket enklare iterationer av simplexmetoden i sådana fall beräknas hundratals eller till och med tiotals [1] [2] . Det finns dock exempel på problem där algoritmer av denna klass fungerar hundratals gånger mer effektivt än standardimplementationer av simplexmetoden.

Anteckningar

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

Litteratur

S.A. Ashmanov. Linjär programmering. - M. : Huvudupplagan av fysisk och matematisk litteratur, 1981. - S. 288-289.
A. Schreiver. Teori för linjär- och heltalsprogrammering, v1. - M . : "Mir", 1991. - ISBN 5-03-002754-8 .
S. Nikolenko. Teori och praktik om komplexitet // Computerra. - M . : LLC Journal "Computerra", 2005. - Utgåva. 31 .

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering