Konjugaattigradienttimenetelmä

Konjugaattigradienttimenetelmä (Fletcher-Reeves-menetelmä) on menetelmä funktion paikallisen ääripään löytämiseksi sen arvoja ja gradienttia koskevien tietojen perusteella . Kvadraattisen funktion tapauksessa minimi löytyy enintään askeleelta. $\mathbb {R} ^{n}$ $n$

Peruskäsitteet

Määritellään terminologia:

Anna . ${\vec {S_{1}}},\ldots ,{\vec {S_{n}}}\in \mathbb {X} \subset \mathbb {R} ^{n}$

Esitellään tavoitefunktio . $\mathbb{X}$ $f({\vec {x}})\in \mathrm {C^{2}} (\mathbb {X} )$

Vektoreita kutsutaan konjugaateiksi , jos: ${\displaystyle {\vec {S_{1))},\ldots ,{\vec {S_{n))))$

${\vec {S_{i))}^{T}H{\vec {S_{j))}=0,\quad i\neq j,\quad i,j=1,\ldots ,n$
${\vec {S_{i}}}^{T}H{\vec {S_{i}}}\geqslant 0,\quad i=1,\ldots ,n$

missä on Hessenin matriisi . $H$ $f({\vec {x)))$

Lause ( olemassaolosta ).
Matriisille on olemassa ainakin yksi konjugaattisuunnan järjestelmä , koska itse matriisi (sen ominaisvektorit ) on tällainen järjestelmä.

n

H

H

Menetelmän perustelu

Nolla iteraatiota

Päästää ${\vec {S_{0}}}=-\nabla f({\vec {x_{0}}})\qquad (1)$

Sitten . ${\vec {x_{1}}}={\vec {x_{0}}}+\lambda _{1}{\vec {S_{0}}}\qquad$

Päätetään suunta

${\vec {S_{1}}}=-\nabla f({\vec {x_{1}}})+\omega _{1}{\vec {S_{0}}}\ \qquad (2)$

niin, että se liittyy : ${\displaystyle {\vec {S_{0))))$

{\vec {S_{0}}}^{T}H{\vec {S_{1}}}=0\qquad (3)

Laajenna naapurustossa ja korvaa : $\nabla f({\vec {x)))$ ${\displaystyle {\vec {x_{0))))$ ${\vec {x}}={\vec {x_{1}}}$

\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}})=H\,({\vec {x_{1}}}- {\vec {x_{0}}}}=\lambda _{1}H{\vec {S_{0}}}

Transponoimme tuloksena olevan lausekkeen ja kerromme oikealla: $H^{{-1}}$

(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}H^{-1}=\lambda _ {1}{\vec {S_{0}}}^{T}H^{T}H^{-1}

Toisen osittaisen derivaatan jatkuvuuden vuoksi . Sitten: $H^{T}=H$

{\vec {S_{0}}}^{T}={\frac {(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0 )))))^{T}H^{-1}}{\lambda _{1}}}

Korvataan tuloksena oleva lauseke (3):

{\frac {(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}H^{-1} H{\vec {S_{1}}}}{\lambda _{1}}}=0

Sitten käyttämällä (1) ja (2):

(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}(-\nabla f({\vec { x_{1}}})-\omega _{1}\nabla f({\vec {x_{0}}})))=0\qquad (4)

Jos , niin pisteen gradientti on kohtisuorassa pisteen gradienttiin nähden, niin vektoreiden skalaaritulon sääntöjen mukaan : $\lambda =\arg \min _{\lambda }f({\vec {x_{0}}}+\lambda {\vec {S_{0}}})$ ${\vec {x_{1}}}={\vec {x_{0}}}+\lambda {\vec {S_{0}}}$ ${\displaystyle {\vec {x_{0))))$

(\nabla f({\vec {x_{0}}}),\nabla f({\vec {x_{1}}}))=0

Kun otetaan huomioon jälkimmäinen, saadaan lausekkeesta (4) lopullinen laskentakaava : $\omega$

\omega _{1}={\frac {||\nabla f({\vec {x_{1}}})||^{2}}{||\nabla f({\vec {x_ {0}}})||^{2}}}

K. iteraatio

K:nnessä iteraatiossa meillä on joukko . ${\vec {S_{0}}},\ldots ,{\vec {S_{k-1}}}$

Sitten seuraava suunta lasketaan kaavalla:

{\vec {S_{k))}=-\nabla f({\vec {x_{k))})-\|\nabla f({\vec {x_{k))})\| ^{2}{\cdot }\left({\frac {\nabla f({\vec {x}}_{k-1})}{\|\nabla f({\vec {x}}_{ k-1})\|^{2))}+\ldots +{\frac {\nabla f({\vec {x_{0))})}{\|\nabla f({\vec {x} }_{0})\|^{2}}}\oikea)

Tämä lauseke voidaan kirjoittaa uudelleen kätevämpään iteratiiviseen muotoon:

{\vec {S_{k}}}=-\nabla f({\vec {x_{k}}})+\omega _{k}{\vec {S}}_{k-1} ,\qquad \omega _{i}={\frac {\|\nabla f({\vec {x_{i))})\|^{2)){\|\nabla f({\vec {x }}_{i-1})\|^{2}}},

jossa lasketaan suoraan k. iteraatiossa. $\omega_{k}$

Algoritmi

Olkoon lähtökohta, antigradientin suunta ja yritämme löytää funktion minimin . Asetetaan ja etsitään minimi suuntaa pitkin . Merkitään minimipiste . ${\vec {x}}_{0}$ ${\vec {r}}_{0}$ $f({\vec {x)))$ ${\vec {S}}_{0}={\vec {r}}_{0}$ ${\vec {S}}_{0}$ ${\vec {x}}_{1}$

Olkoon jossain vaiheessa olemme pisteessä , ja olla antigradientin suunta. Olkoon , jossa valitaan joko (standardi Fletcher-Reeves-algoritmi neliöfunktioille, joissa on ) tai ( Polak-Ribière -algoritmi ). Sitten löydämme suunnan minimin ja merkitsemme minimipisteen . Jos toiminto ei laske laskettuun suuntaan, sinun on unohdettava edellinen suunta asettamalla ja toistamalla vaihe. ${\vec {x}}_{k}$ ${\vec {r}}_{k}$ ${\vec {S}}_{k}={\vec {r}}_{k}+\omega _{k}{\vec {S}}_{k-1}$ $\omega_{k}$ ${\frac {({\vec {r}}_{k},{\vec {r}}_{k})}{({\vec {r}}_{k-1},{ \vec {r}}_{k-1})}}$ $H>0$ $\max(0,{\frac {({\vec {r}}_{k},{\vec {r}}_{k}-{\vec {r}}_{k-1} )}{({\vec {r}}_{k-1},{\vec {r}}_{k-1}))))$ ${\displaystyle {\vec {S_{k))))$ ${\vec {x}}_{k+1}$ $\omega _{k}=0$

Formalisointi

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$

Neliöfunktion tapaus

Lause.
Jos neliöfunktion minimin löytämiseen käytetään konjugaattisuuntia, niin tämä funktio voidaan minimoida portaittain, yksi kumpaankin suuntaan, eikä järjestys ole merkittävä.

n

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., Filippovskaya EA Algoritmit epälineaarisen ohjelmoinnin ongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineaariset ja diskreetit ohjelmointialgoritmit. - 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