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)={\frac{\frac{\partial f}{\partial w_i}{w}_i}{\sum _{k=1}^n\frac{\partial f}{\partial w_k}{w}_k}|}_{w_i=w_i(t)}.$

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