Gradienttimenetelmiä

Gradienttimenetelmät ovat numeerisia menetelmiä ongelmien ratkaisemiseksi gradientin avulla , jotka rajoittuvat funktion ääripisteiden löytämiseen.

Lausunto yhtälöjärjestelmän ratkaisun ongelmasta optimointimenetelmien kannalta

Tehtävä yhtälöjärjestelmän ratkaisemiseksi :

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\lpisteet &&\\f_{n} (x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.$ (yksi)

c vastaa funktion minimoimisen ongelmaa $n$ $x_{1},x_{2},\ldots ,x_{n}$

$F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2}, ...,x_{n})|^{2}$ (2)

tai jokin muu jäännösarvojen (virheiden) itseisarvojen nouseva funktio , . Muuttujien funktion minimin (tai maksimin) löytämisen ongelma on itsessään erittäin tärkeä käytännön merkitys. $|f_{i}|$ $f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})$ $i=1,2,\ldots ,n$ $n$

Tämän ongelman ratkaisemiseksi iteratiivisilla menetelmillä aloitetaan mielivaltaisilla arvoilla ja muodostetaan peräkkäiset approksimaatiot: $x_{i}^{[0]}(i=1,2,...,n)$

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j] }$

tai koordinaatistossa:

$x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2 ,\ldots ,n,\quad j=0,1,2,\ldots$ (3)

jotka konvergoivat johonkin ratkaisuun . ${\vec {x}}^{[k]}$ ${j\to \infty }$

Eri menetelmät eroavat toisistaan "suunnan" valinnassa seuraavalle vaiheelle eli suhteiden valinnassa

$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

Askelarvo (etäisyys tiettyyn suuntaan ääripäätä etsittäessä) määräytyy arvon minimoivan parametrin arvon funktiona . Tämä funktio on yleensä approksimoitu sen Taylor-laajennuksella tai interpolaatiopolynomilla kolmesta viiteen valitulle arvolle . Viimeinen menetelmä soveltuu taulukkofunktion maksimi - ja minimiarvojen löytämiseen . $\lambda ^{[j]}$ $F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})$ $\lambda ^{[j]}$ $\lambda ^{[j]}$ $F(x_{1},x_{2},...,x_{n})$

Gradient Methods

Menetelmien pääajatuksena on mennä jyrkimmän laskeuman suuntaan, ja tämän suunnan antaa antigradientti : $-\nabla F$

${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^ {[j]})$

missä on valittu: $\lambda ^{[j]}$

vakio, jolloin menetelmä voi poiketa toisistaan;
murto-osa, eli vaiheen pituus laskeutumisprosessissa jaetaan tietyllä luvulla;
nopein laskeutuminen: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({ \vec {x}}^{[j]}))$

Jyrkin laskeutumismenetelmä ( gradienttimenetelmä )

Valitse , jossa kaikki derivaatat lasketaan , ja pienennä askelpituutta lähestyessäsi funktion minimiä . $v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i))}$ $x_{i}=x_{i}^{[j]}$ $\lambda ^{[j]}$ $F$

Analyyttisille funktioille ja pienille arvoille Taylor-laajennus mahdollistaa optimaalisen askelkoon valinnan $F$ $f_{i}$ $F(\lambda ^{[j]})$

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k))})^{2)){ \sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h))}{ \frac {\partial F}{\partial x_{k))}{\frac {\partial F}{\partial x_{h))))}$ (5)

jossa kaikki johdannaiset lasketaan arvolla . Parabolisen funktion interpolointi voi olla kätevämpää. $x_{i}=x_{i}^{[j]}$ $F(\lambda ^{[j]})$

Algoritmi

Alkuproksimaatio ja laskennan tarkkuus asetetaan ${\vec {x}}^{0}\!,\,\epsilon$
Laske missä ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\oikea)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]} \nabla F\left({\vec {x}}^{[j]}\oikea)\oikea)$
Tarkista pysäytystila:
- Jos , siirry vaiheeseen 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon$ $j=j+1$
- Muuten lopeta. ${\vec {x}}={\vec {x}}^{[j+1]}$

Gauss-Seidelin koordinaattilaskumenetelmä

Tämä menetelmä on nimetty analogisesti Gauss-Seidelin menetelmän kanssa lineaarisen yhtälöjärjestelmän ratkaisemiseksi. Parantaa edellistä menetelmää johtuen siitä, että seuraavassa iteraatiossa laskeutuminen suoritetaan asteittain kutakin koordinaattia pitkin, mutta nyt on tarpeen laskea uudet kerran yhdessä vaiheessa. $\lambda \quad n$

Algoritmi

Alkuproksimaatio ja laskennan tarkkuus asetetaan ${\vec {x}}_{0}^{0},\quad \varepsilon$
Laske missä $\left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]} -\lambda _{1}^{[j]}{\frac {\partial F({\vec {x}}_{0}^{[j]})}{\partial x_{1}}}{ \vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1} ^{[j]}-\lambda _{n}^{[j]}{\frac {\partial F({\vec {x))_{n-1}^{[j]})}{\ osittainen x_{n}}}{\vec {e}}_{n}\end{array}}\right.$ $\lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x))_{i-1}^{[j]}-\ lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e }}_{Olen oikea)$
Tarkista pysäytystila:
- Jos , siirry vaiheeseen 2. $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$
- Muuten lopeta. ${\vec {x}}={\vec {x}}_{n}^{[j]}$

Konjugaattigradienttimenetelmä

Konjugaattigradienttimenetelmä perustuu moniulotteisen optimoinnin suoran menetelmän - konjugaattisuuntien menetelmän - käsitteisiin .

Menetelmän soveltaminen toisen asteen funktioihin määrittää minimin portaissa. $\mathbb {R} ^{n}$ $n$

Algoritmi

Ne saadaan alkuperäisen likiarvon ja virheen perusteella: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Laske aloitussuunta: $j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_ {k}^{j}={\vec {x}}_{k}$
${\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j },\quad \lambda =\arg \min _{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j }),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega { \vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})|| ^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}$
- Jos tai , niin lopeta. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Muuten
  - jos , siirry kohtaan 3; ${\näyttötyyli (j+1)<n}$ $j=j+1$
  - muussa tapauksessa siirry kohtaan 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Katso myös

Kirjallisuus

Akulich I.L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. asiantuntija. yliopistot. - M . : Korkeampi. koulu, 1986.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Korshunov Yu.M., Korshunov Yu.M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat, 1972.
Maksimov Yu.A., Filipovskaya E.A. Algoritmit epälineaarisen ohjelmoinnin ongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu.A. Algoritmit lineaariseen ja diskreettiin ohjelmointiin. - M .: MEPhI, 1980.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.

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