Minimizacija v dani smeri

Iz Wikipedije, proste enciklopedije

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

[uredi] Algoritem

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 α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 φ(α), pri čemer približno velja φ'(α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.

[uredi] Glej tudi

V drugih jezikih