Smer padanja

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

Pri optimizaciji je smer padanja funkcije oziroma padajoča smer v točki \mathbf{x}\in\mathbb R^n vektor \mathbf{p}\in\mathbb R^n, za katerega velja, da vrednost namenske funkcije f:\mathbb R^n\to\mathbb R v tej smeri »lokalno pada«.

Bolj natančno to pomeni, da lahko najdemo takšen skalar \epsilon >0 , da velja

\alpha>0 \and  \alpha < \epsilon \Rightarrow f(\mathbf{x} + \alpha \mathbf{p}) < f(\mathbf{x}) , je

Če gradient funkcije ni enak nič ( \nabla f(\mathbf{x} \ne 0) ), je \mathbf{p} smer padanja funkcije f natanko takrat, ko je

\langle\mathbf{p}_k,\nabla f(\mathbf{x}_k)\rangle < 0,

kjer  \langle , \rangle označuje skalarni produkt.

Pri optimizacijskih algoritmih je iskanje padajočih smeri namenske funkcije pomembno, ker lahko funkcijo v takšni smeri zagotovo zmanjšamo, če uporabimo dovolj majhen korak. Negativen neničelen gradient funkcije je vedno padajoča smer, saj velja

 \langle -\nabla f(\mathbf{x}_k), \nabla f(\mathbf{x}_k) \rangle = -\langle \nabla f(\mathbf{x}_k), \nabla f(\mathbf{x}_k) \rangle < 0 .

To dejstvo uporabimo pri metodi najstrmejšega padca, kjer funkcijo zaporedoma minimiziramo v smeri negativnega gradienta. Obstajajo še druge metode za izračun smeri padanja, na primer metoda konjugiranih gradientov. Ta metoda se uporablja pogosteje od metode najstrmejšega padca, ki v resnici ni učinkovita, kar se intuitivno zdi v nasprotju z dejstvom, da funkcija v smeri negativnega gradienta najhitreje pada.

Glej tudi[uredi | uredi kodo]