Approaches to accelerate methods for solving systems of equations arising in nonlinear optimization
Tid: Fr 2020-12-18 kl 10.00
Plats: via Zoom, https://kth-se.zoom.us/j/63180134076, Stockholm (English)
Ämnesområde: Tillämpad matematik och beräkningsmatematik, Optimeringslära och systemteori
Respondent: David Ek , Optimeringslära och systemteori
Opponent: Professor Jacek Gondzio, School of Mathematics, University of Edinburgh, Scotland, UK
Handledare: Professor Anders Forsgren, Optimeringslära och systemteori
Abstract
Metoder för att lösa ickelinjära optimeringsproblem involverar vanligtvis lösning av ekvationssystem. Denna avhandling handlar om strategier för att accelerera några av dessa metoder. I vårt ramverk innebär acceleration att hitta en avvägning mellan beräkningskostnaden för en iteration och kvaliteten av den beräknade sökriktningen. Vi utformar strategier för vilka teoretiska resultat i ideala omgivningar härleds. Vi undersöker också strategiernas praktiska prestanda inom och utanför gränserna för de teoretiska omgivningarna med numeriska simuleringar.
Artikel A behandlar metoder för att lösa strikt konvexa kvadratiska optimeringsproblem utan bivillkor. Detta motsvarar att lösa linjära ekvationssystem där matriserna är symmetriska och positivt definita. Huvudfokus är kvasi-Newtonmetoder, med exakt linjesökning och begränsat minne, som genererar sökriktningar parallella med de i konjugerade gradientmetoden. Vi ger en klass av kvasi-Newtonmetoder med begränsat minne. Dessutom föreslår vi ett dynamiskt ramverk för att konstruera dessa metoder. Metoderna är avsedda att vara särskilt användbara för att lösa sekvenser av relaterade linjära ekvationssystem. Sådana sekvenser förekommer vanligtvis då metoder för att lösa ickelinjära ekvationssystem konvergerar.
Artikel B handlar om att lösa ickelinjära ekvationssystem som uppstår i inre-punktsmetoder för ickelinjär optimering med begränsade variabler. Till-ämpning av Newtons metod ger sekvenser av linjära ekvationssystem. Vi föreslår partiella och fullständiga approximativa lösningar till Newton-systemen. De partiella approximativa lösningarna är beräkningsmässigt billiga, medan varje fullständig approximativ lösning vanligtvis kräver att ett reducerat Newton-system löses. Dessutom föreslår vi två Newton-liknande strategier, som baseras på de föreslagna partiella approximativa lösningarna, för att lösa de ickelinjära ekvationssystemen.
Artikel C berör inre-punktsmetoder för kvadratisk optimering med linjära olikhetsbivillkor. Vi föreslår en strukturerad modifierad Newton-strategi för att lösa de ickelinjära ekvationssystemen som uppstår. De modifierade Jakobianerna är sammansatta av en tidigare Jakobian, samt en uppdateringsmatris av låg rang per efterföljande iteration. För en given rangbegränsning konstruerar vi en uppdateringsmatris av låg rang sådan att den modifierade Jakobianen blir närmast den nuvarande Jakobianen, i både 2-norm och Frobenious-norm. Strategin är strukturerad i avseendet att den bevarar Jakobianens gleshetsstruktur.
Strategierna som föreslås i Artikel B och Artikel C motiveras med asymptotiska resultat i ideala teoretiska omgivningar. Särskilt visas det att strategierna blir alltmer exakta då primal-duala inre-punktsmetoder konvergerar. En undersökning av deras praktiska prestanda ges genom numeriska resultat. Resultaten illustrerar de föreslagna strategiernas praktiska prestanda samt deras begränsningar.
Vi föreställer oss att strategierna i Artikel A, Artikel B och Artikel C kan vara användbara parallellt, eller i kombination, med befintliga lösare för att accelerera metoder.
Artikel D är mer pedagogisk i sin natur. Vi ger en härledning av konjugerade gradientsmetoden i ett optimeringsramverk. Resultatet i sig är välkänt men härledningen har, såvitt vi vet, inte presenterats tidigare.