Ellipsoidi menetelmä

Ellipsoidimenetelmä on algoritmi, jolla etsitään kupera joukkojen leikkauspisteessä oleva piste. Sen on kehittänyt A. S. Nemirovsky , ja L. G. Khachiyan toi algoritmiseen toteutukseen Neuvostoliiton tiedeakatemian laskentakeskuksessa.

Algoritmin kuvaus

Ensin valitaan suuri pallo, joka sisältää kuperoiden sarjojen leikkauspisteen. Tämän pallon rakentamismenetelmä riippuu ongelmasta. Lisäksi jokaisessa vaiheessa on ellipsoidi, jonka määrittelevät keskusta ja vektorit . Ellipsoidi sisältää pisteitä , joille . Huomaa, että sama ellipsoidi voidaan määrittää useilla tavoilla. Jos tämän ellipsoidin keskipiste kuuluu kaikkiin kuperajoukkoon, niin vaadittu piste löytyy. Muuten on olemassa hypertaso , joka kulkee pisteen läpi siten , että yksi joukoista on kokonaan sen toisella puolella. Sitten voit siirtyä alkuperäisestä kannasta toiseen kantaan , joka on yhdensuuntainen ja suunnattu joukkoa kohti. Laitetaan nyt ,, $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))))$ osoitteessa . Tämä uusi ellipsoidi sisältää puolet vanhasta ja sen tilavuus on pienempi. Siten ellipsoidin tilavuus pienenee eksponentiaalisesti askelmäärän kasvaessa, ja haluttu piste löytyy portaittain, missä on alkuperäisen pallon tilavuus ja leikkausalueen tilavuus. Algoritmin kokonaisajoaika on yhtä suuri kuin , missä on joukkojen lukumäärä, on aika tarkistaa, kuuluuko piste joukkoon. $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$

Sovellus lineaariseen ohjelmointiongelmaan

Jos lineaarisessa ohjelmointitehtävässä pystyttiin rakentamaan halutun ratkaisun sisältävä pallo, niin se voidaan ratkaista ellipsoidimenetelmällä. Tätä varten löydämme ensin pallon sisältä pisteen, joka täyttää ongelman rajoitukset. Piirrämme sen läpi hypertason , jossa on tavoitefunktio, ja löydämme pisteen alkuperäisen ja uuden hypertason leikkauspisteestä (alkaen nykyisestä ellipsoidista). Teemme samoin uuden löydetyn pisteen kanssa. Prosessi konvergoi optimaaliseen ratkaisuun eksponentiaalisella nopeudella (koska ellipsoidin tilavuus pienenee tällä nopeudella). $u$ $f(x)<f(u)$ $f$

Menetelmän tehokkuus

Polynomialgoritmista voisi teoriassa tulla uusi standardi, mutta käytännössä Khachiyan-algoritmia tulee käyttää varoen: 50 muuttujan koon kanssa on ongelmia, jotka vaativat yli 24 tuhatta Khachiyan-menetelmän iteraatiota, kun taas useiden Simplex-menetelmän yksinkertaisemmat iteraatiot lasketaan tällaisissa tapauksissa satoja tai jopa kymmeniä [1] [2] . On kuitenkin esimerkkejä ongelmista, joissa tämän luokan algoritmit toimivat satoja kertoja tehokkaammin kuin simplex-menetelmän standarditoteutukset.

Muistiinpanot

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

Kirjallisuus

S.A. Ašmanov. Lineaarinen ohjelmointi. - M. : Fysikaalisen ja matemaattisen kirjallisuuden pääpainos, 1981. - S. 288-289.
A. Schreiver. Lineaarisen ja kokonaislukuohjelmoinnin teoria, v1. - M . : "Mir", 1991. - ISBN 5-03-002754-8 .
S. Nikolenko. Monimutkaisuuden teoria ja käytäntö // Computerra. - M . : LLC Journal "Computerra", 2005. - Numero. 31 .

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi