Konjugált gradiens módszer

A konjugált gradiens módszer (Fletcher-Reeves módszer) egy módszer egy függvény lokális szélsőértékének megtalálására az értékeire és a gradiensére vonatkozó információk alapján . Másodfokú függvény esetén a minimum legfeljebb lépésekben található meg. $\mathbb {R} ^{n}$ $n$

Alapfogalmak

Határozzuk meg a terminológiát:

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

Mutassuk be a célfüggvényt . $\mathbb{X}$ $f({\vec {x}})\in \mathrm {C^{2}} (\mathbb {X} )$

A vektorokat konjugáltnak nevezzük, ha: ${\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$

hol van a hesseni mátrix . $H$ $f({\vec {x)))$

Tétel ( a létezésről ).
A mátrixhoz legalább egy konjugált irányrendszer létezik , mert maga a mátrix ( sajátvektorai ) egy ilyen rendszer.

n

H

H

A módszer indoklása

Nulla iteráció

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

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

Határozzuk meg az irányt

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

így társítva van : ${\displaystyle {\vec {S_{0))))$

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

Bővítse ki a környéket , és helyettesítse : $\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}}}

Transzponáljuk a kapott kifejezést, és megszorozzuk a jobb oldalon: $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}

A második parciális deriváltak folytonossága miatt . Akkor: $H^{T}=H$

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

Helyettesítsük be a kapott kifejezést (3)-ba:

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

Ezután az (1) és (2) használatával:

(\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)

Ha , akkor a pontban lévő gradiens merőleges a pont gradiensére , akkor a vektorok skaláris szorzatának szabályai szerint : $\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

Ez utóbbit figyelembe véve a (4) kifejezésből megkapjuk a számítás végső képletét : $\omega$

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

K-edik iteráció

A k-adik iterációnál megvan a halmaz . ${\vec {S_{0}}},\ldots ,{\vec {S_{k-1}}}$

Ezután a következő képlettel számítjuk ki a következő irányt:

{\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}}}\jobbra)

Ez a kifejezés kényelmesebb iteratív formában átírható:

{\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}}},

ahol a k-edik iterációnál közvetlenül számítják ki. $\omega_{k}$

Algoritmus

Legyen a kiindulópont, legyen az antigradiens iránya és megpróbáljuk megtalálni a függvény minimumát . Állítsuk be és keressük meg a minimumot az irány mentén . Jelöljük a minimum pontot . ${\vec {x}}_{0}$ ${\vec {r}}_{0}$ $f({\vec {x)))$ ${\vec {S}}_{0}={\vec {r}}_{0}$ ${\vec {S}}_{0}$ ${\vec {x}}_{1}$

Legyen egy lépésnél a pontban , és legyen az antigradiens iránya. Legyen , ahol vagy (a szabványos Fletcher-Reeves algoritmus másodfokú függvényekhez -vel ) vagy ( Polak-Ribière algoritmus ) választhat. Ezután megkeressük az irány minimumát , és jelöljük a minimum pontot . Ha a függvény nem csökken a számított irányba, akkor az előző irányt el kell felejtenie a lépés beállításával és megismétlésével. ${\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$

Formalizálás

Ezeket a kezdeti közelítés és hiba adja meg: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Számítsa ki a kiindulási irányt: $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}}}$
- Ha vagy , akkor hagyja abba. $||{\vec {S}}_{k}^{j+1}||<\varepszilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepszilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Másképp
  - ha , akkor lépjen a 3-ra; $(j+1)<n$ $j=j+1$
  - ellenkező esetben lépjen a 2-re. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Másodfokú függvény esete

Tétel.
Ha konjugált irányokat használunk egy másodfokú függvény minimumának meghatározásához, akkor ez a függvény lépésenként minimalizálható, minden irányban egy-egy, és a sorrend nem szignifikáns.

n

Irodalom

Akulich I. L. Matematikai programozás példákban és feladatokban: Proc. diákgazdasági juttatás. szakember. egyetemek. - M . : Feljebb. iskola, 1986.
Gill F., Murray W., Wright M. Gyakorlati optimalizálás. Per. angolról. - M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
Maksimov Yu. A. Lineáris és diszkrét programozási algoritmusok. — M. : MEPhI, 1980.
Korn G., Korn T. Matematikai kézikönyv tudósok és mérnökök számára. - M . : Nauka, 1970. - S. 575-576.

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás