Toistettu kvadraattinen optimointi ja Maratos-efekti - Ekman, Arvo (My University, 2023)
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ä.
Keywords: Toistettu kvadraattinen optimointi, SQP, Maratos-efekti, Karush–Kuhn– Tucker