Gradientní metody

Gradientové metody jsou numerické metody pro řešení úloh pomocí gradientu , které jsou redukovány na hledání extrémů funkce.

Sdělení problému řešení soustavy rovnic z hlediska optimalizačních metod

Úkol vyřešit soustavu rovnic :

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n} (x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\vpravo.$ (jeden)

c je ekvivalentní problému minimalizace funkce $n$ $x_{1},x_{2},\ldots ,x_{n}$

$F(x_{1},x_{2},\ldots ,x_{n})\ekviv \součet _{i=1}^{n}|f_{i}(x_{1},x_{2}, ...,x_{n})|^{2}$ (2)

nebo nějaká jiná rostoucí funkce absolutních hodnot reziduí (chyb) , . Problém nalezení minima (nebo maxima) funkce proměnných má sám o sobě velký praktický význam. $|f_{i}|$ $f_{i}=f_{i}(x_{1},x_{2},\ldots,x_{n})$ $i=1,2,\ldots ,n$ $n$

Chcete-li tento problém vyřešit pomocí iteračních metod , je třeba začít s libovolnými hodnotami a konstruovat postupné aproximace: $x_{i}^{[0]}(i=1,2,...,n)$

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j] }$

nebo souřadnicově:

$x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2 ,\ldots ,n,\quad j=0,1,2,\ldots$ (3)

které konvergují k nějakému řešení pro . ${\vec {x}}^{[k]}$ ${j\to \infty }$

Různé metody se liší volbou „směru“ pro další krok, tedy volbou vztahů

$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

Hodnota kroku (vzdálenost, kterou se má posunout daným směrem při hledání extrému) je určena hodnotou parametru, který minimalizuje hodnotu jako funkci . Tato funkce je obvykle aproximována její Taylorovou expanzí nebo interpolačním polynomem přes tři až pět vybraných hodnot . Poslední metoda je použitelná pro nalezení max a min tabulkové funkce . $\lambda ^{[j]}$ $F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})$ $\lambda ^{[j]}$ $\lambda ^{[j]}$ $F(x_{1},x_{2},...,x_{n})$

Gradientní metody

Hlavní myšlenkou metod je jít ve směru nejstrmějšího sestupu a tento směr je dán anti-gradientem : $-\nabla F$

${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^ {[j]})$

kde je vybráno: $\lambda ^{[j]}$

konstantní, v takovém případě se metoda může lišit;
zlomkový krok, to znamená, že délka kroku v procesu sestupu je vydělena určitým číslem;
nejrychlejší sestup: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({ \vec {x}}^{[j]}))$

Metoda nejstrmějšího sestupu ( metoda gradientu )

Vyberte , kde jsou všechny derivace počítány na a snižte délku kroku , jak se blížíte k minimu funkce . $v_{i}^{[j]}=-{\frac {\částečné F}{\částečné x_{i))}$ $x_{i}=x_{i}^{[j]}$ $\lambda ^{[j]}$ $F$

Pro analytické funkce a malé hodnoty umožňuje Taylorova expanze zvolit optimální velikost kroku $F$ $f_{i}$ $F(\lambda ^{[j]})$

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k))})^{2)){ \sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h))}{ \frac {\částečné F}{\částečné x_{k))}{\frac {\částečné F}{\částečné x_{h))))}$ (5)

kde se všechny deriváty počítají na . Vhodnější může být interpolace parabolické funkce . $x_{i}=x_{i}^{[j]}$ $F(\lambda ^{[j]})$

Algoritmus

Je nastavena počáteční aproximace a přesnost výpočtu ${\vec {x}}^{0}\!,\,\epsilon$
Počítej kde ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]} \nabla F\left({\vec {x}}^{[j]}\right)\right)$
Zkontrolujte stav zastavení:
- Pokud ano, přejděte ke kroku 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon$ $j=j+1$
- Jinak přestaň. ${\vec {x}}={\vec {x}}^{[j+1]}$

Gauss-Seidelova metoda souřadnicového sestupu

Tato metoda je pojmenována analogicky s Gauss-Seidelovou metodou pro řešení soustavy lineárních rovnic. Vylepšuje předchozí metodu díky tomu, že při další iteraci se klesání provádí postupně po každé ze souřadnic, ale nyní je nutné jednou v jednom kroku vypočítat nové. $\lambda \quad n$

Algoritmus

Je nastavena počáteční aproximace a přesnost výpočtu ${\vec {x}}_{0}^{0},\quad \varepsilon$
Počítej kde $\left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]} -\lambda _{1}^{[j]}{\frac {\částečné F({\vec {x}}_{0}^{[j]})}{\částečné x_{1}}}{ \vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1} ^{[j]}-\lambda _{n}^{[j]}{\frac {\částečné F({\vec {x)))_{n-1}^{[j]})}{\ částečné x_{n}}}{\vec {e}}_{n}\end{array}}\vpravo.$ $\lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x))_{i-1}^{[j]}-\ lambda ^{[j]}{\frac {\částečné F({\vec {x}}_{i-1}^{[j]})}{\částečné x_{i}}}{\vec {e }}_{i}\right)$
Zkontrolujte stav zastavení:
- Pokud ano, přejděte ke kroku 2. $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$
- Jinak přestaň. ${\vec {x}}={\vec {x}}_{n}^{[j]}$

Metoda konjugovaného gradientu

Metoda konjugovaného gradientu je založena na konceptech přímé metody vícerozměrné optimalizace - metodě konjugovaných směrů .

Použití metody na kvadratické funkce v určuje minimum v krocích. $\mathbb {R} ^{n}$ $n$

Algoritmus

Jsou dány počáteční aproximací a chybou: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Vypočítejte směr startu: $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}}}$
- Pokud nebo , tak přestaňte. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- v opačném případě
  - pokud , přejděte na 3; $(j+1)<n$ $j=j+1$
  - jinak přejděte na 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Viz také

Literatura

Akulich I.L. Matematické programování v příkladech a úlohách: Proc. příspěvek na studentské hospodářství. specialista. vysoké školy. - M .: Vyšší. škola, 1986.
Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. — M .: Energoatomizdat, 1972.
Maksimov Yu.A., Filipovskaya E.A. Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
Maksimov Yu.A. Algoritmy pro lineární a diskrétní programování. — M. : MEPhI, 1980.
Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování