Toistettu kvadraattinen optimointi ja Maratos-efekti
Ekman, Arvo (2023-03-31)
Toistettu kvadraattinen optimointi ja Maratos-efekti
(31.03.2023)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2023040334693
https://urn.fi/URN:NBN:fi-fe2023040334693
Tiivistelmä
Työn tarkoituksena on esitellä tehokas Newtonin menetelmään perustuva toistetun kvadraattisen optimoinnin algoritmi eli SQP. Algoritmilla voidaan ratkaista epälineaarisia rajoitteellisia optimointiongelmia differentioituvilla kohde- ja rajoitefunktioilla. Ensimmäisen version toistetun kvadraattisen optimoinnin menetelmästä esitti R. B.Wilson väitöskirjassaan vuonna 1963. Myöhemmin S.P. Han ja M.J.D. Powell tehostivat algoritmia käyttämällä aina positiividefniittiä approksimaatiota suunnanvalintatehtävän Hessen matriisista, sekä ratkaisemalla askelpituuden käyttämällä hyväksi sakkofunktiota.
Tutkielman alussa esitellään olennaisia määritelmiä ja todistetaan tärkeä aputulos Gordanin lemma, jota käytetään todistamaan, että lokaalissa optimipisteessä toteutuvat Fritz John -ehdot ja edelleen Karush–Kuhn–Tuckerin ehdot (KKT). Tämän jälkeen esitellään SQP-algoritmi, joka perustuu Newtonin menetelmällä tehtyyn approksimaatioon hakusuunnasta kohti ratkaistavan optimointiongelman KKT-pistettä.
Epälineaariset yhtälörajoitteet ja yksinkertainen sakkofunktio tuottavat SQP-algoritmille konvergenssivaikeuksia. N. Maratos nosti ongelman esiin väitöskirjassaan vuonna 1978. Puuttuvan parantavan suunnan ilmiötä kutsutaankin hänen mukaansa Maratos-efektiksi. Viimeinen kappale käsittelee menetelmiä, joiden avulla voidaan
ratkaista Maratos-efektistä kärsiviä minimointitehtäviä.
Tutkielman alussa esitellään olennaisia määritelmiä ja todistetaan tärkeä aputulos Gordanin lemma, jota käytetään todistamaan, että lokaalissa optimipisteessä toteutuvat Fritz John -ehdot ja edelleen Karush–Kuhn–Tuckerin ehdot (KKT). Tämän jälkeen esitellään SQP-algoritmi, joka perustuu Newtonin menetelmällä tehtyyn approksimaatioon hakusuunnasta kohti ratkaistavan optimointiongelman KKT-pistettä.
Epälineaariset yhtälörajoitteet ja yksinkertainen sakkofunktio tuottavat SQP-algoritmille konvergenssivaikeuksia. N. Maratos nosti ongelman esiin väitöskirjassaan vuonna 1978. Puuttuvan parantavan suunnan ilmiötä kutsutaankin hänen mukaansa Maratos-efektiksi. Viimeinen kappale käsittelee menetelmiä, joiden avulla voidaan
ratkaista Maratos-efektistä kärsiviä minimointitehtäviä.