Minimizacija v dani smeri

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Minimizacija v dani smeri je eden od dveh osnovnih pristopov k iskanju lokalnih rešitev optimizacijskih problemov (alternativen pristop je metoda omejenega koraka).

Algoritem[uredi | uredi kodo]

Pri iskanju lokalnega minimiuma \mathbf{x}^* namenske funkcije f:\mathbb R^n\to\mathbb R je splošni postopek (prototipni algoritem) naslednji:

i) Postavi števec iteracij k=0 in izberi začetni približek za minimum \mathbf{x}_0.
ii) Izračunaj padajočo smer \mathbf{p}_k.
iii) Izberi \alpha_k, ki približno minimizira \phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k) po \alpha\in\mathbb R.
iv) Postavi \mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k, k \to k+1.
Če je \|\nabla f(\mathbf{x}_k)\|\leq tol, končaj.
Drugače pojdi na ii).

V koraku iii) lahko natančno (v okviru zahtevane natančnosti za minimizacijo v dani smeri) minimiziramo \phi(\alpha), pri čemer približno velja \phi'(\alpha_k)=0. Pri drugem pristopu, ki se pogosteje uporablja v sodobnih postopkih, zahtevamo le zadostno zmanjšanje namenske funkcije glede na določen kriterij. Kriterij mora biti takšen, da je zagotovljena konvergenca algoritma k lokalni rešitvi. Premer ustrezno postavljenega kriterija so Wolfejevi pogoji.

Glej tudi[uredi | uredi kodo]