Trust region -optimointialgoritmi

Abstract

Trust region- eli luottamusaluealgoritmit ovat iteratiivisiä optimointialgoritmeja. Niiden toiminta perustuu siihen, että minimoitavaa funktiota approksimoidaan kvadraattisella mallifunktiolla jonkin luottamusalueen sisällä. Mallifunktio pyritään minimoimaan luottamusalueen sisällä ja saatu ratkaisu hyväksytään uudeksi iteraatioaskeleeksi, mikäli se tuottaa riittävästi vähenemää funktiossa. Samalla myös luottamusalueen kokoa muutetaan.

Mallifunktion minimointia luottamusalueella kutsutaan algoritmin osaongelmaksi. Tässä työssä käsitellään kahta ratkaisutapaa, Cauchyn pistettä sekä dog-leg -metodia, jotka hakevat approksimoidun ratkaisun osaongelmalle, sekä lisäksi eksaktin ratkaisun etsimistä. Myös algoritmin suppeneminen näitä tapoja käyttäen todistetaan.

Työssä myös toteutettiin itse MATLAB-ohjelmistolla luottamusaluealgoritmi, jonka toimintaa testattiin minimoimalla sillä Rosenbrockin funktiota. Algoritmin toimintaa iteraatioprosessin aikana tutkittiin ja vertailun vuoksi sama optimointitehtävä ratkaistiin myös viivahakuun perustuvalla algoritmilla.