Minimizacija v dani smeri

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

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 $\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

• Optimizacija
• Nelinearno programiranje
• Minimizacija
• Metoda omejenega koraka
• Metoda aktivne množice