Metoda gradientului conjugat

Metoda gradientului conjugat (metoda Fletcher-Reeves) este o metodă de găsire a extremului local al unei funcții pe baza informațiilor despre valorile și gradientul acesteia . În cazul unei funcții pătratice, minimul se găsește în cel mult pași. $\mathbb {R} ^{n}$ $n$

Concepte de bază

Să definim terminologia:

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

Să introducem funcția obiectiv . $\mathbb{X}$ $f({\vec {x}})\in \mathrm {C^{2}} (\mathbb {X} )$

Vectorii se numesc conjugați dacă: ${\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$

unde este matricea hessiană . $H$ $f({\vec {x)))$

Teorema ( despre existență ).
Există cel puțin un sistem de direcții conjugate pentru matrice , deoarece matricea în sine (vectorii ei proprii ) este un astfel de sistem.

n

H

H

Justificarea metodei

Iterație zero

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

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

Să stabilim direcția

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

astfel încât este asociat cu : ${\vec {S_{0}})$

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

Extindeți -vă într-un cartier și înlocuiți : $\nabla f({\vec {x}))$ ${\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}}}

Transpunem expresia rezultată și înmulțim cu în dreapta: $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}

Datorită continuităţii derivatelor a doua parţiale . Apoi: $H^{T}=H$

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

Să înlocuim expresia rezultată în (3):

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

Apoi, folosind (1) și (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)

Dacă , atunci gradientul în punctul este perpendicular pe gradientul în punctul , atunci conform regulilor produsului scalar al vectorilor : $\lambda =\arg \min _{\lambda }f({\vec {x_{0}}}+\lambda {\vec {S_{0}}})$ ${\vec {x_{1}}}={\vec {x_{0}}}+\lambda {\vec {S_{0}}}$ ${\vec {x_{0)})$

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

Ținând cont de acestea din urmă, obținem din expresia (4) formula finală de calcul : $\omega$

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

K-a iterație

La a k-a iterație, avem setul . ${\vec {S_{0}}},\ldots ,{\vec {S_{k-1}}}$

Apoi următoarea direcție este calculată cu formula:

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

Această expresie poate fi rescrisă într-o formă iterativă mai convenabilă:

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

unde se calculează direct la a k-a iterație. $\omega_{k}$

Algoritm

Să fie punctul de plecare, să fie direcția antigradientului și încercăm să găsim minimul funcției . Să stabilim și să găsim minimul de-a lungul direcției . Să notăm punctul minim . ${\vec {x}}_{0}$ ${\vec {r}}_{0}$ $f({\vec {x)))$ ${\vec {S}}_{0}={\vec {r}}_{0}$ ${\vec {S}}_{0}$ ${\vec {x}}_{1}$

Să fim la un pas la punctul , și să fim direcția antigradientului. Fie , unde se alege fie (algoritmul standard Fletcher-Reeves pentru funcții pătratice cu ) fie ( algoritmul Polak-Ribière ). Apoi găsim minimul în direcția și notăm punctul minim . Dacă funcția nu scade în direcția calculată, atunci trebuie să uitați direcția anterioară setând și repetând pasul. ${\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}))))$ ${\vec {S_{k}})$ ${\vec {x}}_{k+1}$ $\omega _{k}=0$

Formalizare

Ele sunt date de aproximarea inițială și eroare: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Calculați direcția de pornire: $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}}}$
- Dacă sau , atunci opriți. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- In caz contrar
  - dacă , atunci treceți la 3; $(j+1)<n$ $j=j+1$
  - în caz contrar , treceți la 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Cazul unei funcții pătratice

Teorema.
Dacă direcțiile conjugate sunt folosite pentru a găsi minimul unei funcții pătratice, atunci acea funcție poate fi minimizată în pași, câte unul în fiecare direcție, iar ordinea nu este semnificativă.

n

Literatură

Akulich I. L. Programare matematică în exemple și sarcini: Proc. indemnizație pentru economia studenților. specialist. universități. - M .: Mai sus. scoala, 1986.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Maksimov Yu. A. Algoritmi de programare liniară și discretă. — M .: MEPhI, 1980.
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică