Konjugeret gradientmetode

Den konjugerede gradientmetode (Fletcher-Reeves-metoden) er en metode til at finde det lokale ekstremum af en funktion baseret på information om dens værdier og dens gradient . I tilfælde af en kvadratisk funktion findes minimumet i ikke mere end trin. $\mathbb {R} ^{n}$ $n$

Grundlæggende begreber

Lad os definere terminologien:

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

Lad os introducere den objektive funktion . $\mathbb{X}$ $f({\vec {x}})\in \mathrm {C^{2}} (\mathbb {X} )$

Vektorer kaldes konjugeret , hvis: ${\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$

hvor er den hessiske matrix . $H$ $f({\vec {x)))$

Sætning ( om eksistensen ).
Der er mindst et system af konjugerede retninger for matrixen , fordi selve matrixen (dens egenvektorer ) er sådan et system.

n

H

H

Begrundelse for metoden

Nul iteration

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

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

Lad os bestemme retningen

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

så det er forbundet med : ${\displaystyle {\vec {S_{0))))$

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

Udvid i et kvarter og erstat : $\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}}}

Vi transponerer det resulterende udtryk og multiplicerer med til højre: $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}

På grund af kontinuiteten af den anden partielle derivater . Derefter: $H^{T}=H$

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

Lad os erstatte det resulterende udtryk i (3):

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

Brug derefter (1) og (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)

Hvis , så er gradienten i punktet vinkelret på gradienten i punktet , så i henhold til reglerne for det skalære produkt af vektorer : $\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

Under hensyntagen til sidstnævnte får vi fra udtryk (4) den endelige formel til beregning : $\omega$

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

K-te iteration

Ved den kth iteration har vi sættet . ${\vec {S_{0}}},\ldots ,{\vec {S_{k-1}}}$

Derefter beregnes den næste retning med formlen:

{\vec {S_{k))}=-\nabla f({\vec {x_{k))})-\|\nabla f({\vec {x_{k))})\| ^{2}{\cdot }\venstre({\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}}}\right)

Dette udtryk kan omskrives i en mere bekvem iterativ form:

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

hvor er direkte beregnet ved den kth iteration. $\omega_{k}$

Algoritme

Lad være udgangspunktet, være retningen af antigradienten, og vi forsøger at finde minimum af funktionen . Lad os sætte og finde minimum langs retningen . Lad os betegne minimumspunktet . ${\vec {x}}_{0}$ ${\vec {r}}_{0}$ $f({\vec {x)))$ ${\vec {S}}_{0}={\vec {r}}_{0}$ ${\vec {S}}_{0}$ ${\vec {x}}_{1}$

Lad os på et eller andet trin være ved punktet , og være retningen af antigradienten. Lad , hvor man vælger enten (standard Fletcher-Reeves-algoritmen for kvadratiske funktioner med ) eller ( Polak-Ribière-algoritmen ). Så finder vi minimum i retningen og betegner minimumspunktet . Hvis funktionen ikke falder i den beregnede retning, skal du glemme den forrige retning ved at indstille og gentage trinnet. ${\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$

Formalisering

De er givet ved den indledende tilnærmelse og fejl: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Beregn startretningen: $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}}}$
- Hvis eller , så stop. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Ellers
  - hvis , så gå til 3; $(j+1)<n$ $j=j+1$
  - ellers gå til 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Sagen for en kvadratisk funktion

Sætning.
Hvis konjugerede retninger bruges til at finde minimum af en kvadratisk funktion, så kan denne funktion minimeres i trin, en i hver retning, og rækkefølgen er ikke signifikant.

n

Litteratur

Akulich I. L. Matematisk programmering i eksempler og opgaver: Proc. godtgørelse for studerendes økonomi. specialist. universiteter. - M . : Højere. skole, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Om. fra engelsk. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Matematiske grundlag for kybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer til løsning af problemer med ikke-lineær programmering. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineære og diskrete programmeringsalgoritmer. — M .: MEPhI, 1980.
Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering