Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Technische Samenvatting: Immuniteit voor toenemende conditiegetallen van Lineaire Superiorisatie versus Lineaire Programmering

Probleemstelling
Het artikel behandelt de vergelijkende prestaties van algoritmen voor Lineaire Programmering (LP) en de Lineaire Superiorisatie (LinSup) methodologie wanneer deze worden toegepast op lineaire programmeerproblemen die gekenmerkt worden door toenemende conditiegetallen. Terwijl klassieke LP streeft naar het vinden van een optimaal punt (het minimaliseren van de doelfunctie onder restricties), streeft LinSup naar het vinden van een haalbaar punt met een "superieure" (gereduceerde, maar niet noodzakelijkerwijs minimale) waarde van de doelfunctie. Het centrale probleem dat wordt onderzocht is de gevoeligheid van beide benaderingen voor slecht gestelde problemen (ill-posedness), specifiek hoe toenemende conditiegetallen van de restrictiematrix de runtime, het bereiken van haalbaarheid en de reductie van de doelfunctie van deze algoritmen beïnvloeden.

Methodologie
De auteurs voerden een gecontroleerde experimentele studie uit waarbij LinSup werd vergeleken met gevestigde LP-solvers.

• Probleemgeneratie: De onderzoekers construeerden lineaire programmeerproblemen van de vorm $\min \langle c, x \rangle$ onder de voorwaarden $Ax \le b$ en $\ell \le x \le u$. Om structurele gelijkenis te garanderen over verschillende conditiegetallen, gebruikten zij Singular Value Decomposition (SVD). Zij genereerden willekeurige semi-orthogonale matrices $U$ en $V$ en construeerden diagonale matrices $\Sigma_\kappa$ met singuliere waarden verdeeld om specifieke conditiegetallen $\kappa$ te bereiken (variërend van goed geconditioneerd tot sterk slecht geconditioneerd). De matrixgroottes varieerden van $80 \times 100$ tot $4000 \times 5000$.
• Geteste Algoritmen:
  • LinSup: Geïmplementeerd met de Agmon-Motzkin-Schönberg (AMS) projectiemethode als het basisalgoritme voor het zoeken naar haalbaarheid. Perturbaties werden geïntroduceerd met behulp van de genormaliseerde negatieve gradiënt van de doelfunctie. Het algoritme maakte gebruik van begrensde perturbaties en cyclische projecties met specifieke stapgrootte-schema's en restart-mechanismen.
  • LP Solvers: De studie vergeleek LinSup met scipy.simplex, scipy.revised simplex, scipy.interior-point, en gurobi.primal simplex.
• Experimenteel Protocol: Om een eerlijke vergelijking te waarborgen, hanteerden de auteurs een verenigd stopcriterium gebaseerd op een vaste onhaalbaarheidsdrempel ($\varepsilon = 10^{-8}$).
  • LinSup werd uitgevoerd totdat deze drempel werd bereikt.
  • LP-solvers werden onder dezelfde drempel uitgevoerd. Indien een LP-solver de drempel niet bereikte binnen de tijd $T_{sup}$ (de tijd die LinSup nodig had om te termineren), werd deze gestopt bij $T_{sup}$, en werd de huidige iteratie geregistreerd.
  • Geregistreerde metrieken waren runtime, waarden van de doelfunctie en maximale restrictie-overtredingen (onhaalbaarheid) bij terminatie en gedurende de iteraties.

Belangrijkste Bijdragen en Resultaten
De studie levert empirisch bewijs voor de robuustheid van LinSup vergeleken met klassieke LP-solvers onder variërende probleemcomplexiteiten:

1. Prestaties bij toenemende dimensies (vaste $\kappa$):

   • Voor kleine dimensies waren simplex-gebaseerde solvers sneller.
   • Naarmate de probleemdimensies toenamen (tot $4000 \times 5000$), nam de runtime van simplex-implementaties (inclusclusief Gurobi) significant toe. In hoge dimensies termineerde LinSup sneller dan de simplex-solvers.
   • Opvallend genoeg bereikte LinSup in de grootste geteste dimensies de haalbaarheidsdrempel voordat de simplex-algoritmen zelfs maar haalbaarheid hadden bereikt.

2. Immuniteit voor toenemende conditiegetallen (vaste dimensies):

   • Simplex-methoden: Naarmate het conditiegetal toenam, vertoonden de scipy simplex-implementaties een ernstige degradatie. Ze stopten vaak voortijdig met suboptimale doelfunctiewaarden, waarbij ze effectief "opgaven" vanwege de moeilijkheid van het probleem.
   • Interior Point Methode: Hoewel deze methode snel lage doelfunctiewaarden leek te vinden, worstelde zij met het bereiken van het vereiste niveau van haalbaarheid voor hoge conditiegetallen, wat resulteerde in hoge onhaalbaarheidswaarden (tot $10^1$).
   • LinSup: De superiorisatiemethode vertoonde een opmerkelijke stabiliteit. De runtime bleef relatief consistent, ongeacht het conditiegetal, en het bereikte consistent het beoogde haalbaarheidsniveau ($\varepsilon = 10^{-8}$) over alle geteste conditiegetallen.
   • Doelfunctie: LinSup produceerde consequent betere (lagere) doelfunctiewaarden op het punt van terminatie vergeleken met de simplex-methoden in slecht geconditioneerde scenario's.

3. Proximity-Target Analyse:

   • Plots van onhaalbaarheid versus doelfunctiewaarde (proximity-target curves) bevestigden dat LinSup een stabiel pad naar haalbaarheid handhaafde terwijl de doelfunctie werd gereduceerd. In tegen tegenstelling hiertoe vertoonde de interior-point methode een disconnect tussen het vinden van een lage doelfunctiewaarde en het voldoen aan de restricties in slecht geconditioneerde settings.

Betekenis en Claims
Het artikel claimt dat Lineaire Superiorisatie een duidelijk voordeel biedt ten opzichte van klassieke LP-solvers bij het werken met slecht geconditioneerde lineaire systemen, met name in grootschalige scenario's.

• Robuustheid: De auteurs concluderen dat LinSup minder wordt beïnvloed door hoge conditiegetallen dan de geteste LP-solvers. Zij schrijven dit toe aan de aard van het algoritme: LinSup voert individuele projecties uit op halfruimten in plaats van het volledige systeem simultaan op te lossen, en de "begrensde perturbatie-resistentie" van het basisalgoritme kan helpen computationele fouten te absorberen die anders door slechte conditionering zouden worden versterkt.
• Praktisch Nut: De studie suggereert dat voor toepassingen waar het vinden van een haalbaar punt met een gereduceerde doelfunctiewaarde voldoende is (een "satisficing" benadering in plaats van strikte optimaliteit), LinSup een betrouwbaarder en efficiënter instrument is voor slecht gestelde problemen.
• Bescheiden Reikwijdte: De auteurs geven expliciet aan dat hun resultaten gebaseerd zijn op specifieke experimentele opstellingen en probleemgroottes. Zij uiten vertrouwen dat de geobserveerde trends zullen standhouden voor grotere instanties, maar beweren niet dat LinSup LP-solvers voor alle optimalisatietaken vervangt. Zij merken op dat LinSup geen LP-solver is en niet streeft naar geconstraineerde optimaliteit, maar naar een "superieur" haalbaar punt.
• Toekomstig Werk: Het artikel suggereert dat de geobserveerde robuustheid van LinSup in lineaire settings onderzoek verdient in niet-lineaire settings, met name waar interior-point methoden bekend staan om hun moeite met slechte conditionering (bijv. intensiteits-gemoduleerde radiotherapie).