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 ${𝐱}^{*}$ namenske funkcije $f:{ℝ}^n\to ℝ$ je splošni postopek (prototipni algoritem) naslednji:

i) Postavi števec iteracij $k=0$ in izberi začetni približek za minimum ${𝐱}_0$.

ii) Izračunaj padajočo smer ${𝐩}_k$.

iii) Izberi ${\alpha }_k$, ki približno minimizira $\varphi (\alpha )=f({𝐱}_k+\alpha {𝐩}_k)$ po $\alpha \in ℝ$.

iv) Postavi ${𝐱}_{k+1}={𝐱}_k+{\alpha }_k{𝐩}_k$, $k\to k+1$.

Če je $\Vert \mathrm{\nabla }f({𝐱}_k)\Vert \le 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 $\varphi (\alpha )$, pri čemer približno velja ${\varphi }^{\prime }({\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