Piyavsky-metoden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 september 2017; verifiering kräver 1 redigering .

Piyavskys metod är en metod för att hitta det globala minimum ( maximum ) för en Lipschitz-funktion som ges på en kompakt uppsättning . Det är lätt att implementera och har ganska enkla konvergensvillkor. Lämplig för en bred klass av funktioner vars derivata, till exempel, vi kan begränsa.

Metodidé

Låt funktionen som definieras på uppfyller Lipschitz-villkoret: $f(x)$ $\vänster[a,b\höger]$

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

Lipschitz-förhållandena innebär uppenbarligen en tvåsidig ojämlikhet som begränsar funktionens förväntade beteende.

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

där , punkten där mätningen gjordes. $f_{i}$

Låt oss köra några tester . $x_{1},x_{2},...,x_{k}\högerpil f_{1},f_{2},...,f_{k}$

Låt oss kalla funktionen för en minorant och en majorant . $f_{k}^{-}(x)=\max _{{i=\överlinje {1,k}}}^{{}}\left\{f_{i}-L\|x-x_{i }\|\right\}$ $f_{k}^{+}(x)=\min _{{i=\överlinje {1,k}}}^{{}}\left\{f_{i}+L\|x-x_{i }\|\right\}$

Grafiskt sett är de streckade linjer, så Piyavsky-metoden kallas ofta också för bruten linje-metoden. Uppenbarligen begränsar de funktionen från två sidor: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Låt oss beteckna . Det globala minimumet för en funktion kan uppskattas: $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}^{*}$

Genom att göra den angivna "korridoren" mindre än den förutbestämda kan man hitta funktionens globala minimum. Piyavskys metod vid varje steg utför ett nytt test av funktionen , samtidigt som det korrigerar minorant och den nuvarande uppskattningen av det globala minimumet. Testerna utförs vid minimipunkten för den aktuella minoranten. $\varepsilon$ $f_{{i+1}}$

Algoritm

Vi ställer in (eller utvärderar) Lipschitz-konstanten , noggrannhet och - antalet initiala försök. $L>0$ $\varepsilon >0$ $k_{0}$
Vi utför dessa tester på olika ställen på kompakten . . $K$ $x_{1},x_{2},...,x_{k}\högerpil f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ . Du kan helt enkelt jämföra med värdet i föregående iteration.
$x_{{k+1}}=arg\min _{{x\in \Pi _{k}}}^{{}}f_{k}^{-}(x)$ , var . $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\right\}$
Om - sluta. Minimum finns vid punkten . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq \varepsilon$ $x_{{k+1}}$
Ett test genomförs . . Minoranten korrigeras. Gå tillbaka till steg 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Konvergenssats

Låt vara kompakt. - Lipschitz, med konstant , . Sedan, för alla sätt att placera de initiala punkterna , kommer Piyavskys metod att sluta efter ett ändligt antal steg , och . $K$ $f(x)$ $L>0$ $\varepsilon >0$ $x_{1},x_{2},...,x_{k}\i K$ $N(f)$ $f_{k}^{*}-f(x^{*})\leq \varepsilon$

Litteratur

Piyavsky S. A. En algoritm för att hitta funktioners absoluta extremum // Journal of Computational Mathematics and Mathematical Physics, vol. 12, nr 4 (1972), s. 885—896.
Norkin V. I. Om Piyavskys metod för att lösa ett allmänt problem med global optimering // Journal of Computational Mathematics and Mathematical Physics, vol. 32, nr 7 (1992), s. 992—1006.

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 Powells 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