Konjugerad gradientmetod

Den konjugerade gradientmetoden (Fletcher-Reeves-metoden) är en metod för att hitta det lokala extremumet för en funktion baserat på information om dess värden och dess gradient . I fallet med en kvadratisk funktion återfinns minimumet i högst steg. $\mathbb {R} ^{n}$ $n$

Grundläggande begrepp

Låt oss definiera terminologin:

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

Låt oss introducera den objektiva funktionen . $\mathbb{X}$ $f({\vec {x}})\in \mathrm {C^{2}} (\mathbb {X} )$

Vektorer kallas konjugat om: ${\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$

var är den hessiska matrisen . $H$ $f({\vec {x)))$

Sats ( om existens ).
Det finns åtminstone ett system av konjugerade riktningar för matrisen , eftersom själva matrisen (dess egenvektorer ) är ett sådant system.

n

H

H

Motivering av metoden

Noll iteration

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

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

Låt oss bestämma riktningen

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

så att det är förknippat med : ${\displaystyle {\vec {S_{0))))$

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

Expandera i en stadsdel och ersätt : $\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 transponerar det resulterande uttrycket och multiplicerar med till höger: $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 av kontinuiteten hos de andra partiella derivaten . Sedan: $H^{T}=H$

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

Låt oss ersätta det resulterande uttrycket med (3):

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

Använd sedan (1) och (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)

Om , så är gradienten vid punkten vinkelrät mot gradienten vid punkten , så enligt reglerna för den skalära produkten av 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

Med hänsyn till det senare får vi från uttryck (4) den slutliga formeln för beräkning : $\omega$

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

K-te iterationen

Vid den k:te iterationen har vi uppsättningen . ${\vec {S_{0}}},\ldots ,{\vec {S_{k-1}}}$

Därefter beräknas nästa riktning med formeln:

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

Detta uttryck kan skrivas om i en mer bekväm 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}}},

där beräknas direkt vid den k:te iterationen. $\omega_{k}$

Algoritm

Låt vara utgångspunkten, var riktningen för antigradienten och vi försöker hitta minimum av funktionen . Låt oss ställa in och hitta minimum längs riktningen . Låt oss beteckna minimipunkten . ${\vec {x}}_{0}$ ${\vec {r}}_{0}$ $f({\vec {x)))$ ${\vec {S}}_{0}={\vec {r}}_{0}$ ${\vec {S}}_{0}$ ${\vec {x}}_{1}$

Låt oss vid något steg vara vid punkten och vara riktningen för antigradienten. Låt , där man väljer antingen (den vanliga Fletcher-Reeves-algoritmen för kvadratiska funktioner med ) eller ( Polak-Ribière-algoritmen ). Sedan hittar vi minimum i riktningen och betecknar minimipunkten . Om funktionen inte minskar i den beräknade riktningen, måste du glömma den föregående riktningen genom att ställa in och upprepa steget. ${\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 ges av den initiala approximationen och felet: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Beräkna startriktningen: $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}}}$
- Om eller , sluta då. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Annat
  - om , gå sedan till 3; $(j+1)<n$ $j=j+1$
  - annars , gå till 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Fallet med en kvadratisk funktion

Sats.
Om konjugerade riktningar används för att hitta minimum av en kvadratisk funktion, kan den funktionen minimeras i steg, en i varje riktning, och ordningen är inte signifikant.

n

Litteratur

Akulich I. L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre. skola, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa problem med olinjär programmering. — M .: MEPhI, 1982.
Maksimov Yu. A. Linjära och diskreta programmeringsalgoritmer. — M .: MEPhI, 1980.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering