Promotie: Snellere GPS

21 september 2009

Navigatiesystemen in auto's bepalen met behulp van niet-lineaire optimalisering de positie op basis van ontvangen satellietsignalen, terwijl met behulp van lineaire optimalisering een kortste reisroute wordt berekend. Hiervoor zijn optimaliseringsalgoritmen nodig. Op 18 september promoveerde Gu op deze algoritmen aan de Technische Universiteit Delft binnen het Vrije Competitie project van Kees Roos.

Er bestaan twee grote klassen optimaliseringsalgoritmen (zeg A en B) van zeer efficiënte inwendige punt algoritmen. Volgens de theorie zijn de algoritmen in klasse A efficiënter (dus sneller) dan die in klasse B. In de praktijk doet zich echter het omgekeerde voor: dan blijken de algoritmen in klasse B sneller te zijn dan die in klasse A. In de praktijk worden daarom uitsluitend algoritmen uit klasse B gebruikt. Fundamenteel is een nieuw idee dat leidt tot het vinden van algoritmen in klasse B die theoretisch even efficiënt zijn als die in klasse A en in de praktijk nog sneller dan de snelste algoritmen van vandaag. De promotor van Gu, Kees Roos, presenteerde en analyseerde een Ontoelaatbare Inwendige Punt Methode (OIPM) voor Lineaire Optimalisering (LO). Dit is een primaal-duale homotopie methode die zich onderscheidt van de klassieke methoden doordat alleen volle Newton stappen worden gebruikt, waarbij geen lijnzoekmethoden nodig zijn.

Gu begint zijn proefschrift met een verbeterde volle-Newton-stap OIPM voor LO. Vervolgens, gebruikmakend van de eigenschappen van Euclidische Jordan algebras, generaliseert hij de verbeterde OIPM voor LO naar een volle Nesterov-Todd-stap OIPM voor Symmetrische Optimalisering (SO). Omdat de analyse van deze methode een kwadratisch convergentie resultaat gebruikt voor toelaatbare IPMn, kijkt hij eerst naar primaal-duale toelaatbare IPMn met volle stappen. Ofschoon de bedachte OIPMn de best bekende iteratiegrens hebben, zijn zij vanuit praktisch oogpunt inefficiënt, doordat hun praktische performance niet veel beter is dan de theoretische slechtse-geval performance. Dit komt doordat de theorie slechts kleine reducties van de zogenaamde barrière parameter toelaat. Als remedie stelt hij een agressievere (adaptieve) aanpassingstrategie voor.

Tenslotte is de volle NT-stap OIPM voor SO geïmplementeerd met zowel standaard als adaptieve aanpassingen van de barrière parameter. De hierdoor te bereiken verbetering in performance van de adaptive strategie ten opzichte van de standaard strategie wordt aan de hand van een voorbeeld duidelijk gemaakt. Het algoritme met de adaptieve strategie is ook gebruikt om problemen op te lossen uit de welbekende bibliotheek SDPLIB van testproblemen. De gepresenteerde resultaten zijn veelbelovend, en tot op zekere hoogte vergelijkbaar met die van de veelgebruikte solver SDPT3.