An inexact infeasible arc-search interior-point method for linear optimization problems

Technische Samenvatting: Een Inexacte Infeasible Arc-Search Interior-Point Methode voor Lineaire Optimalisatieproblemen

Probleemstelling
Het artikel behandelt de oplossing van Lineaire Optimalisatieproblemen (LOP's) met behulp van Interior-Point Methoden (IPM's). Specifiek richt het zich op inexacte infeasible IPM's (II-IPM's), wat varianten zijn die ontworpen zijn om LOP's op te lossen vanaf een inefficiënt beginpunt en de Newton-systemen inexact op te lossen (bijvoorbeeld via iteratieve solvers zoals de Conjugate Gradient-methode). Hoewel inexacte solvers de computationele kosten per iteratie voor grootschalige problemen verminderen, lijden bestaande inexacte infeasible line-search methoden onder een aanzienlijk nadeel: de accumulatie van linearisatiefouten (van het benaderen van het centrale pad) en inexactheidfouten (van de solver) langs een rechte zoekrichting. Deze accumulatie dwingt het algoritme om zeer kleine stapgroottes te nemen, wat resulteert in een relatief zwakke worst-case iteratiecomplexiteit-begrenzing van $O(n^2 L)$, waarbij $n$ het aantal variabelen is en $L$ de binaire lengte van de invoergegevens.

Methodologie
De auteurs stellen een nieuwe methode voor genaamd II-arc (Inexact Infeasible Arc-Search Interior-Point Method). De kerninnovatie ligt in het vervangen van de standaard rechte lijn-zoekstrategie door een ellipsoïdale arc-search strategie.

1. Arc-Search Framework: In plaats van langs een rechte lijn te bewegen, benadert de methode het centrale pad met een ellipsoïdale boog gedefinieerd door een tweede-orde Taylor-expansie. De volgende iteratie $(x_{k+1}, y_{k+1}, s_{k+1})$ wordt berekend als:
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (en vergelijkbaar voor $y$ en $s$), waarbij $\dot{x}, \ddot{x}$ de eerste en tweede afgeleiden van het centrale pad zijn.
2. Inexact Oplossen: De methode lost de Newton-systemen voor de eerste afgeleide ($\dot{x}, \dot{y}, \dot{s}$) en de tweede afgeleide ($\ddot{x}, \ddot{y}, \ddot{s}$) inexact op. De auteurs maken gebruik van de Modified Normal Equation System (MNES) formulering voor theoretische analyse om de residu-vereisten te versoepelen, hoewel numerieke experimenten de standaard Normal Equation System (NES) gebruiken met een Jacobi-preconditioner vanwege waargenomen numerieke instabiliteit in MNES-implementaties voor grootschalige problemen.
3. Selectie van Stapgrootte: De stapgrootte $\alpha$ wordt gekozen om specifieke buurtcondities te voldoen (om ervoor te zorgen dat de iteratie binnen een specifieke regio van het centrale pad blijft) en een Armijo-achtige conditie om voldoende reductie in de dualiteitskloof te garanderen.
4. Theoretische Analyse: De auteurs bewijzen dat het gebogen traject van de arc-search de linearisatiefout effectiever onderdrukt dan een rechte lijn. Dit maakt het mogelijk dat de stapgrootte groter blijft, zelfs wanneer de Newton-systemen met aanzienlijke inexactheid worden opgelost.

Belangrijkste Bijdragen

• Eerste Inexact Arc-Search IPM: Naar weten van de auteurs is dit de eerste paper die een inexact IPM binnen het arc-search framework bespreekt.
• Verbeterde Complexiteit-begrenzing: Het artikel stelt een polynomiale iteratiecomplexiteit-begrenzing van $O(n^{1.5} L)$ vast voor de voorgestelde II-arc methode. Dit vertegenwoordigt een theoretische verbetering ten opzichte van de best bekende begrenzing voor bestaande inexact infeasible line-search methoden ($O(n^2 L)$) met een factor $n^{0.5}$.
• Mitigatie van Foutaccumulatie: De auteurs demonstreren dat de arc-search strategie de accumulatie van linearisatie- en inexactheidfouten mitigeert, wat de primaire bottleneck is in bestaande inexact infeasible methoden.

Numerieke Resultaten
De auteurs hebben numerieke experimenten uitgevoerd op grootschalige problemen uit de NETLIB benchmark collectie (inclusief DFL001, QAP15, STOCFOR3, en Kennington problemen) met behulp van een Python-implementatie met Preconditioned Conjugate Gradient (CG) als de lineaire solver.

• Vergelijking: De voorgestelde II-arc methode (specifiek de variant die het initiële punt van Yang's heuristiek gebruikt, "II-arc-Yang") werd vergeleken met een bestaande inexact infeasible line-search methode ("II-line-Yang").
• Prestaties:
  • Iteraties: II-arc-Yang vereiste consistent minder iteraties dan II-line-Yang. Voor bijna 25% van de testproblemen had de line-search methode twee keer of meer iteraties nodig dan de arc-search methode.
  • Computationele Tijd: II-arc-Yang verminderde de totale computationele tijd voor 75% van de problemen. De reductie in iteraties compenseerde voor de extra kosten van het oplossen van het tweede afgeleide systeem.
  • Robuustheid: De methode loste 17 van de 18 testproblemen succesvol op, wat duidt op numerieke stabiliteit.
• Initiële Punten: De studie vergeleek ook een constant initieel punt met het initiële punt van Yang's heuristiek, waarbij werd vastgesteld dat de heuristische aanpak (II-arc-Yang) over het algemeen betere prestaties leverde in termen van zowel iteraties als tijd.

Betekenis en Claims
Het artikel claimt dat de voorgestelde II-arc methode een bewijsbaar nauwere worst-case iteratie-begrenzing biedt dan bestaande inexact infeasible line-search methoden. De betekenis van dit werk ligt in het overbruggen van de kloof tussen de theoretische voordelen van arc-search (betere benadering van het centrale pad) en de praktische noodzaak van inexacte solvers voor grootschalige problemen.

De auteurs merken bescheiden op dat hoewel de theoretische complexiteit is verbeterd, het primaire doel was om het framework voor te stellen en de convergentie te bespreken. Zij erkennen dat de numerieke prestaties verder verbeterd kunnen worden door:

• De methode te implementeren in snellere talen (bijv. C++, Julia).
• Meer geavanceerde inexacte lineaire system solvers en preconditioners te onderzoeken.
• Combinaties te verkennen met Nesterov's restarting strategie of feasible IPM's.

Het artikel concludeert dat de ellipsoïdale arc-benadering grotere stapgroottes toestaat in aanwezigheid van inexactheid, wat leidt tot zowel een theoretische reductie in iteratiecomplexiteit als praktische verbeteringen bij het oplossen van grootschalige lineaire optimalisatieproblemen.