Piyavského metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. září 2017; ověření vyžaduje 1 úpravu .

Piyavského metoda je metoda pro nalezení globálního minima ( maxima ) Lipschitzovy funkce dané na kompaktní množině . Je snadno implementovatelný a má poměrně jednoduché podmínky konvergence. Vhodné pro širokou třídu funkcí, jejichž derivaci například můžeme omezit.

Metoda nápad

Nechť funkce definovaná na splňuje Lipschitzovu podmínku: $f(x)$ $\left[a,b\right]$

$\mid f(x_{2})-f(x_{1})\mid \leq L\|x_{2}-x_{1}\|$ .

Lipschitzovy podmínky zjevně implikují oboustrannou nerovnost, která omezuje očekávané chování funkce.

$f_{i}-L\|x-x_{i}\|\leq f(x)\leq f_{i}+L\|x-x_{i}\|$ ,

kde , bod, ve kterém bylo měření provedeno. $f_{i}$

Udělejme nějaké testy . $x_{1},x_{2},...,x_{k}\šipka doprava f_{1},f_{2},...,f_{k}$

Nazvěme funkci minorant a majorant . _ $f_{k}^{-}(x)=\max _{{i=\overline {1,k}}}^{{}}\left\{f_{i}-L\|x-x_{i }\|\vpravo\}$ $f_{k}^{+}(x)=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}+L\|x-x_{i }\|\vpravo\}$

Graficky se jedná o přerušované čáry, proto se Piyavského metodě často říká také metoda přerušovaných čar. Je zřejmé, že omezují funkci ze dvou stran: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Označme . Globální minimum funkce lze odhadnout: $f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ $f(x^{*})$ $\min _{{x\in \left[a,b\right]}}^{{}}\left\{f_{k}^{-}(x)\right\}\leq f(x^{ *})\leq f_{k}^{*}$

Tím, že je označený "koridor" menší než předem určený , lze najít globální minimum funkce. Piyavského metoda v každém kroku provádí nový test funkce , přičemž opravuje minoritu a aktuální odhad globálního minima. Zkoušky se provádějí na minimálním bodě současného minoritního stupně. $\varepsilon$ $f_{{i+1}}$

Algoritmus

Nastavíme (nebo vyhodnotíme) Lipschitzovu konstantu , přesnost a - počet počátečních pokusů. $L>0$ $\varepsilon >0$ $k_{0}$
Tyto testy provádíme na různých místech kompaktu . . $K$ $x_{1},x_{2},...,x_{k}\šipka doprava f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ . Můžete jednoduše porovnat s hodnotou v předchozí iteraci.
$x_{{k+1}}=arg\min _{{x\in \Pi _{k}}}^{{}}f_{k}^{-}(x)$ , kde . $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\vpravo\}$
Pokud - stop. Minimum se nachází v bodě . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq \varepsilon$ $x_{{k+1}}$
Probíhá test . . Menšina je opravena. Vraťte se ke kroku 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Věta o konvergenci

Buď kompaktní. - Lipschitz, s konstantní , . Pak pro jakýkoli způsob umístění počátečních bodů se Piyavského metoda zastaví po konečném počtu kroků a . $K$ $f(x)$ $L>0$ $\varepsilon >0$ $x_{1},x_{2},...,x_{k}\in K$ $N(f)$ $f_{k}^{*}-f(x^{*})\leq \varepsilon$

Literatura

Piyavsky S. A. Jeden algoritmus pro nalezení absolutního extrému funkcí // Journal of Computational Mathematics and Mathematical Physics, svazek 12, č. 4 (1972), s. 885—896.
Norkin V. I. O Piyavského metodě pro řešení obecného problému globální optimalizace // Journal of Computational Mathematics and Mathematical Physics, svazek 32, č. 7 (1992), s. 992—1006.

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í