Metoda Piyavsky

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 septembrie 2017; verificarea necesită 1 editare .

Metoda lui Piyavsky este o metodă pentru găsirea minimului ( maximului ) global al unei funcții Lipschitz dată pe o mulțime compactă . Este ușor de implementat și are condiții de convergență destul de simple. Potrivit pentru o clasă largă de funcții a căror derivată, de exemplu, o putem limita.

Ideea metodei

Fie ca funcția definită în satisface condiția Lipschitz: $f(x)$ $\left[a,b\right]$

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

Condițiile Lipschitz implică în mod evident o inegalitate cu două părți care limitează comportamentul așteptat al funcției.

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

unde , punctul în care a fost făcută măsurarea. $f_{i}$

Să facem câteva teste . $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$

Să numim funcția minorant și majorant . $f_{k}^{-}(x)=\max _{{i=\overline {1,k}}}^{{}}\left\{f_{i}-L\|x-x_{i }\|\dreapta\}$ $f_{k}^{+}(x)=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}+L\|x-x_{i }\|\dreapta\}$

Grafic, sunt linii întrerupte, așa că metoda Piyavsky este adesea numită și metoda liniilor întrerupte. Evident, ele limitează funcția din două părți: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Să notăm . Minimul global al unei funcții poate fi estimat: $f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\stânga\{f_{i}\dreapta\}$ $f(x^{*})$ $\min _{{x\in \left[a,b\right]}}^{{}}\left\{f_{k}^{-}(x)\right\}\leq f(x^{ *})\leq f_{k}^{*}$

Făcând „coridorul” indicat mai mic decât cel predeterminat , se poate găsi minimul global al funcției. Metoda lui Piyavsky la fiecare pas efectuează un nou test al funcției , corectând în același timp minoranta și estimarea curentă a minimului global. Testele se efectuează în punctul minim al minorului actual. $\varepsilon$ $f_{{i+1}}$

Algoritm

Setăm (sau evaluăm) constanta Lipschitz , acuratețea și - numărul de încercări inițiale. $L>0$ $\varepsilon >0$ $k_{0}$
Efectuăm aceste teste în orice puncte diferite ale compactului . . $K$ $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\stânga\{f_{i}\dreapta\}$ . Puteți compara pur și simplu cu valoarea din iterația anterioară.
$x_{{k+1}}=arg\min _{{x\in \Pi _{k}}}^{{}}f_{k}^{-}(x)$ , unde . $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\right\}$
Dacă - opriți. Minimul se găsește la punctul . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq \varepsilon$ $x_{{k+1}}$
Se efectuează un test . . Minorul este corectat. Reveniți la pasul 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Teorema de convergență

Să fie compact. - Lipschitz, cu constantă , . Apoi, pentru orice modalitate de plasare a punctelor inițiale , metoda lui Piyavsky se va opri după un număr finit de pași , și . $K$ $f(x)$ $L>0$ $\varepsilon >0$ $x_{1},x_{2},...,x_{k}\în K$ $N(f)$ $f_{k}^{*}-f(x^{*})\leq \varepsilon$

Literatură

Piyavsky S. A. Un algoritm pentru găsirea extremului absolut al funcțiilor // Journal of Computational Mathematics and Mathematical Physics, vol. 12, nr.4 (1972), pp. 885—896.
Norkin V. I. Despre metoda lui Piyavsky pentru rezolvarea unei probleme generale de optimizare globală // Journal of Computational Mathematics and Mathematical Physics, vol. 32, nr.7 (1992), pp. 992—1006.

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ă