Piyavsky metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. september 2017; verifikation kræver 1 redigering .

Piyavskys metode er en metode til at finde det globale minimum ( maksimum ) af en Lipschitz-funktion givet på et kompakt sæt . Det er nemt at implementere og har ret enkle konvergensbetingelser. Velegnet til en bred klasse af funktioner, hvis afledte, for eksempel, vi kan begrænse.

Metode idé

Lad den definerede funktion opfylde Lipschitz-betingelsen: $f(x)$ $\venstre[a,b\højre]$

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

Lipschitz-forholdene indebærer naturligvis en tosidet ulighed, der begrænser funktionens forventede adfærd.

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

hvor , det punkt, hvor målingen blev foretaget. $f_{i}$

Lad os køre nogle tests . $x_{1},x_{2},...,x_{k}\højrepil f_{1},f_{2},...,f_{k}$

Lad os kalde funktionen en minorant og en majorant . $f_{k}^{-}(x)=\max _{{i=\overline {1,k}}}^{{}}\venstre\{f_{i}-L\|x-x_{i }\|\right\}$ $f_{k}^{+}(x)=\min _{{i=\overline {1,k}}}^{{}}\venstre\{f_{i}+L\|x-x_{i }\|\right\}$

Grafisk er de stiplede linjer, så Piyavsky-metoden kaldes ofte også for den stiplede linje-metode. Det er klart, de begrænser funktionen fra to sider: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Lad os betegne . Det globale minimum af en funktion kan estimeres: $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}^{*}$

Ved at gøre den angivne "korridor" mindre end den forudbestemte , kan man finde funktionens globale minimum. Piyavskys metode ved hvert trin udfører en ny test af funktionen , mens den korrigerer minorant og det aktuelle estimat af det globale minimum. Testene udføres på minimumspunktet for den aktuelle minorant. $\varepsilon$ $f_{{i+1}}$

Algoritme

Vi indstiller (eller evaluerer) Lipschitz-konstanten , nøjagtighed og - antallet af indledende forsøg. $L>0$ $\varepsilon >0$ $k_{0}$
Vi udfører disse tests på forskellige steder på kompakten . . $K$ $x_{1},x_{2},...,x_{k}\højrepil f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ . Du kan blot sammenligne med værdien i den forrige iteration.
$x_{{k+1}}=arg\min _{{x\in \Pi _{k}}}^{{}}f_{k}^{-}(x)$ , hvor . $\Pi _{k}=\venstre\{x\in K:f(x)\leq f_{k}^{*}\right\}$
Hvis - stop. Minimum findes på punktet . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq \varepsilon$ $x_{{k+1}}$
En test er ved at blive udført . . Minoranten er rettet. Vend tilbage til trin 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Konvergenssætning

Lad være kompakt. - Lipschitz, med konstant , . Så, for enhver måde at placere de indledende punkter på , vil Piyavskys metode stoppe efter et begrænset antal trin , og . $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 algoritme til at finde det absolutte ekstremum af funktioner // Journal of Computational Mathematics and Mathematical Physics, bind 12, nr. 4 (1972), s. 885—896.
Norkin V. I. Om Piyavskys metode til at løse et generelt problem med global optimering // Journal of Computational Mathematics and Mathematical Physics, bind 32, nr. 7 (1992), s. 992—1006.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering