Piyavsky menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1. syyskuuta 2017 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Piyavskyn menetelmä on menetelmä, jolla löydetään kompaktissa joukossa annetun Lipschitz-funktion globaali minimi ( maksimi ) . Se on helppo toteuttaa ja siinä on melko yksinkertaiset konvergenssiehdot. Sopii laajalle luokalle funktioita, joiden derivaatta voimme esimerkiksi rajoittaa.

Menetelmäidea

Olkoon määritetty funktio , että se täyttää Lipschitzin ehdon: $f(x)$ $\vasen[a,b\oikea]$

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

Lipschitzin ehdot ilmeisesti merkitsevät kaksipuolista epäyhtälöä, joka rajoittaa funktion odotettua käyttäytymistä.

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

missä piste, jossa mittaus tehtiin. $f_{i}$

Suoritetaan joitain testejä . $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$

Kutsutaan funktiota minorantiksi ja majorantiksi . _ $f_{k}^{-}(x)=\max _{{i=\overline {1,k}}}^{{}}\left\{f_{i}-L\|x-x_{i }\|\oikea\}$ $f_{k}^{+}(x)=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}+L\|x-x_{i }\|\oikea\}$

Graafisesti ne ovat katkoviivoja, joten Piyavsky-menetelmää kutsutaan usein myös katkoviivamenetelmäksi. Ilmeisesti ne rajoittavat toimintoa kahdelta puolelta: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Merkitään . Funktion globaali minimi voidaan arvioida: $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}^{*}$

Tekemällä osoitetusta "käytävästä" pienempi kuin ennalta määrätty , voidaan löytää funktion globaali minimi. Pijavskin menetelmä jokaisessa vaiheessa suorittaa funktion uuden testin , samalla kun korjaa minorantin ja nykyisen globaalin minimin estimaatin. Testit suoritetaan nykyisen minorantin minimipisteessä. $\varepsilon$ $f_{{i+1}}$

Algoritmi

Asetamme (tai arvioimme) Lipschitzin vakion , tarkkuuden ja - alkukokeiden lukumäärän. $L>0$ $\varepsilon > 0$ $k_{0}$
Suoritamme nämä testit kompaktin eri kohdissa . . $K$ $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ . Voit yksinkertaisesti verrata edellisen iteraation arvoon.
$x_{{k+1}}=arg\min _{{x\in \Pi _{k}}}^{{}}f_{k}^{-}(x)$ , missä . $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\oikea\}$
Jos - lopeta. Minimi löytyy kohdasta . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq \varepsilon$ $x_{{k+1}}$
Testi suoritetaan . . Alamomentti on korjattu. Palaa vaiheeseen 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Konvergenssilause

Olkoon kompakti. - Lipschitz, vakio , . Sitten millä tahansa tavalla aloituspisteet sijoitetaan , Pijavskin menetelmä pysähtyy rajallisen määrän askelten jälkeen ja . $K$ $f(x)$ $L>0$ $\varepsilon > 0$ $x_{1},x_{2},...,x_{k}\in K$ $N(f)$ $f_{k}^{*}-f(x^{*})\leq \varepsilon$

Kirjallisuus

Piyavsky S. A. Yksi algoritmi funktioiden absoluuttisen ääripään löytämiseksi // Journal of Computational Mathematics and Mathematical Physics, osa 12, nro 4 (1972), s. 885-896.
Norkin V. I. Pijavskin menetelmästä globaalin optimoinnin yleisen ongelman ratkaisemiseksi // Journal of Computational Mathematics and Mathematical Physics, osa 32, nro 7 (1992), s. 992-1006.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi