Kiintopistealgoritmi

Kiintopistealgoritmit ovat matemaattisia algoritmeja, joita sovelletaan esimerkiksi simuloinnissa, optimoinnissa, tieteellisessä laskennassa ja koneoppimisessa ja signaalinkäsittelyssä.

Kiintopistealgoritmi (Fixed Point Algorithm, FP) on muotoa

$x(t+1)=F[x(t)].$

Jos se konvergoi, se toteuttaa kiintopistelauseen

$x=F(x).$

Tyypillisesti kiintopistelause saadaan asettamalla optimointifunktion derivaatta nollaksi. Esimerkiksi jos optimoitava funktio on

$R(w)=f(w)+\lambda (1-\sum _{i=1}^{n}w_{i}),$

niin tämän derivaatta on

${\frac {\partial R}{\partial w_{i}}}={\frac {\partial f}{\partial w_{i}}}-\lambda .$

Asettamalla derivaatta nollaksi, saadaan

$\lambda =\lambda \sum _{i=1}^{n}w_{i}=\sum _{i=1}^{n}w_{i}{\frac {\partial f}{\partial w_{i}}},$

jolloin

${\frac {\partial R}{\partial w_{i}}}={\frac {\partial f}{\partial w_{i}}}-\sum _{k=1}^{n}{\frac {\partial f}{\partial w_{k}}}w_{k}.$

Tällöin esimerkiksi saadaan lause

$w_{i}(t+1)=\left.{\frac {{\frac {\partial f}{\partial w_{i}}}w_{i}}{\sum _{k=1}^{n}{\frac {\partial f}{\partial w_{k}}}w_{k}}}\right|_{w_{i}=w_{i}(t)}.$

Jos $f(w)$ on kasvava ja konkaavi funktio, niin esimerkiksi tämä algoritmi on kiintopistealgoritmi.