G2 Master’s thesis, polytechnic Master’s thesis
Proksimaaliset kimppumenetelmät rajoittamattomassa epäsileässä
konveksissa optimoinnissa
Authors: Joki Kaisa
Publisher: University of Turku
Publishing place: Turku
Publication year: 2013
Abstract
Epäsileissä optimointitehtävissä funktioiden ei tarvitse olla differentioituvia. Näin ollen klassista optimointiteoriaa tai sileitä gradienttiin perustuvia menetelmiä ei voida hyödyntää. Tässä pro gradu -tutkielmassa esitelläänkin epäsileiden optimointitehtävien ratkaisemiseen kehitettyjä kimppumenetelmiä. Erityisesti keskitytään tarkastelemaan rajoittamattomia epäsileitä konvekseja optimointitehtäviä, sillä tällöin käytetyt merkinnät pysyvät yksinkertaisempina ja kimppumenetelmien perusidea pystytään esittämään selkeämmin.
Tutkielmassa perehdytään ensin kimppumenetelmien tunnusomaisiin piirteisiin esittelemällä yleisen kimppumenetelmän toimintaperiaate. Yleisen kimppumenetelmän tarkastelu aloitetaan määrittelemällä kimppumenetelmien kannalta tärkeitä käsitteitä kuten kimppu, linearisointivirhe ja leikkaustasomalli. Keskeisessä osassa on myös hakusuunnan määräämisessä käytetty suunnanetsimistehtävä ja sen ratkaisulle saatavat tulokset. Yleisen kimppumenetelmän algoritmin ja askelpituuden määrityksen lisäksi tässä yhteydessä käydään läpi lopetusehtoja sekä aligradientin yhdistämismenetelmä.
Yleisen kimppumenetelmän jälkeen esitellään tarkemmin kolme erilaista proksimaalista kimppumenetelmää, joista jokaisessa hyödynnetään proksimaalista stabilointitermiä. Jokaisen valitun menetelmän toimintaan ja algoritmiin perehdytään ensinnäkin kattavasti, ja tämän lisäksi keskitytään todistamaan yksityiskohtaisesti menetelmien konvergenssit. Ensimmäinen näistä menetelmistä on melko tyypillinen proksimaalinen kimppumenetelmä, jossa hyödynnetään paloittain lineaarista leikkaustasomallia. Toisena esitelty proksimaalinen kimppumenetelmä taas eroaa ensimmäisestä erityisesti askelpituuden määrityksen suhteen. Viimeisessä kimppumenetelmässä käytetään paloittain lineaarisen leikkaustasomallin sijasta paloittain kvadraattista mallia.
Epäsileissä optimointitehtävissä funktioiden ei tarvitse olla differentioituvia. Näin ollen klassista optimointiteoriaa tai sileitä gradienttiin perustuvia menetelmiä ei voida hyödyntää. Tässä pro gradu -tutkielmassa esitelläänkin epäsileiden optimointitehtävien ratkaisemiseen kehitettyjä kimppumenetelmiä. Erityisesti keskitytään tarkastelemaan rajoittamattomia epäsileitä konvekseja optimointitehtäviä, sillä tällöin käytetyt merkinnät pysyvät yksinkertaisempina ja kimppumenetelmien perusidea pystytään esittämään selkeämmin.
Tutkielmassa perehdytään ensin kimppumenetelmien tunnusomaisiin piirteisiin esittelemällä yleisen kimppumenetelmän toimintaperiaate. Yleisen kimppumenetelmän tarkastelu aloitetaan määrittelemällä kimppumenetelmien kannalta tärkeitä käsitteitä kuten kimppu, linearisointivirhe ja leikkaustasomalli. Keskeisessä osassa on myös hakusuunnan määräämisessä käytetty suunnanetsimistehtävä ja sen ratkaisulle saatavat tulokset. Yleisen kimppumenetelmän algoritmin ja askelpituuden määrityksen lisäksi tässä yhteydessä käydään läpi lopetusehtoja sekä aligradientin yhdistämismenetelmä.
Yleisen kimppumenetelmän jälkeen esitellään tarkemmin kolme erilaista proksimaalista kimppumenetelmää, joista jokaisessa hyödynnetään proksimaalista stabilointitermiä. Jokaisen valitun menetelmän toimintaan ja algoritmiin perehdytään ensinnäkin kattavasti, ja tämän lisäksi keskitytään todistamaan yksityiskohtaisesti menetelmien konvergenssit. Ensimmäinen näistä menetelmistä on melko tyypillinen proksimaalinen kimppumenetelmä, jossa hyödynnetään paloittain lineaarista leikkaustasomallia. Toisena esitelty proksimaalinen kimppumenetelmä taas eroaa ensimmäisestä erityisesti askelpituuden määrityksen suhteen. Viimeisessä kimppumenetelmässä käytetään paloittain lineaarisen leikkaustasomallin sijasta paloittain kvadraattista mallia.
UTU Research Portal