Kiintopistealgoritmi.html

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.