Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Technisches Resümee: Immunität gegenüber steigenden Konditionszahlen von Linearer Superiorisierung gegenüber Linearer Programmierung

Problemstellung
Die Arbeit befasst sich mit der vergleichenden Leistungsfähigkeit von Algorithmen der Linearen Programmierung (LP) und der Methodik der Linearen Superiorisierung (LinSup) bei der Anwendung auf lineare Programmierprobleme, die durch steigende Konditionszahlen charakterisiert sind. Während die klassische LP darauf abzielt, einen optimalen Punkt zu finden (Minimierung der Zielfunktion unter Nebenbedingungen), zielt LinSup darauf ab, einen zulässigen Punkt mit einem „überlegenen“ (reduzierten, wenn auch nicht notwendigerweise minimalen) Zielfunktionswert zu finden. Das zentrale untersuchte Problem ist die Sensitivität beider Ansätze gegenüber schlechter Gestelltheit (Ill-Posedness), insbesondere wie steigende Konditionszahlen der Beschränkungsmatrix die Laufzeit, das Erreichen der Zulässigkeit und die Reduktion der Zielfunktion dieser Algorithmen beeinflussen.

Methodik
Die Autoren führten eine kontrollierte experimentelle Studie durch, in der sie LinSup gegen etablierte LP-Solver testeten.

• Problemgenerierung: Die Forscher konstruierten lineare Programmierprobleme der Form $\min \langle c, x \rangle$ unter den Nebenbedingungen $Ax \le b$ und $\ell \le x \le u$. Um eine strukturelle Ähnlichkeit über verschiedene Konditionszahlen hinweg zu gewährleisten, nutzten sie die Singulärwertzerlegung (SVD). Sie generierten zufällige semi-orthogonale Matrizen $U$ und $V$ und konstruierten diagonale Matrizen $\Sigma_\kappa$ mit Singulärwerten, die so verteilt waren, dass spezifische Konditionszahlen $\kappa$ (reichend von gut konditioniert bis hochgradig schlecht konditioniert) erreicht wurden. Die Matrixgrößen reichten von $80 \times 100$ bis $4000 \times 5000$.
• Getestete Algorithmen:
  • LinSup: Implementiert unter Verwendung der Agmon-Motzkin-Schönberg (AMS) Projektionsmethode als Basis-Algorithmus zur Suche nach Zulässigkeit. Perturbationen wurden mittels des normierten negativen Gradienten der Zielfunktion eingeführt. Der Algorithmus verwendete beschränkte Perturbationen und zyklische Projektionen mit spezifischen Schrittweiten-Schedules und Neustart-Mechanismen.
  • LP-Solver: Die Studie verglich LinSup mit scipy.simplex, scipy.revised simplex, scipy.interior-point und gurobi.primal simplex.
• Experimentelles Protokoll: Um einen fairen Vergleich zu gewährleisten, legten die Autoren ein einheitliches Abbruchkriterium basierend auf einem festen Inzulässigkeitsschwellenwert ($\varepsilon = 10^{-8}$) fest.
  • LinSup wurde ausgeführt, bis dieser Schwellenwert erreicht war.
  • Die LP-Solver wurden unter demselben Schwellenwert ausgeführt. Falls ein LP-Solver den Schwellenwert innerhalb der Zeit $T_{sup}$ (der Zeit, die LinSup zur Terminierung benötigte) nicht erreichte, wurde er bei $T_{sup}$ gestoppt, und sein aktueller Iterationswert wurde aufgezeichnet.
  • Aufgenommene Metriken waren Laufzeit, Zielfunktionswerte und maximale Beschränkungsverletzungen (Inzulässigkeit) bei Terminierung und während der Iterationen.

Wesentliche Beiträge und Ergebnisse
Die Studie liefert empirische Belege für die Robustheit von LinSup im Vergleich zu klassischen LP-Solvern unter variierenden Problemkomplexitäten:

1. Leistung bei steigenden Dimensionen (festes $\kappa$):

   • Bei kleinen Dimensionen waren Simplex-basierte Solver schneller.
   • Mit zunehmenden Problemdimensionen (bis zu $4000 \times 5000$) stieg die Laufzeit der Simplex-Implementierungen (einschließlich Gurobi) signifikant an. In hohen Dimensionen terminierte LinSup schneller als die Simplex-Solver.
   • Bemerkenswerterweise erreichte LinSup in den größten getesteten Dimensionen den Zulässigkeitsschwellenwert, noch bevor die Simplex-Algorithmen überhaupt Zulässigkeit erlangten.

2. Immunität gegenüber steigenden Konditionszahlen (feste Dimensionen):

   • Simplex-Methoden: Mit steigender Konditionszahl zeigten die scipy-Simplex-Implementierungen eine schwere Degradation. Sie terminierten oft vorzeitig mit suboptimalen Zielfunktionswerten und „ergaben sich“ effektiv der Schwierigkeit des Problems.
   • Interior-Point-Methode: Obwohl diese Methode offenbar schnell niedrige Zielfunktionswerte fand, hatte sie Schwierigkeiten, bei hohen Konditionszahlen das erforderliche Maß an Zulässigkeit zu erreichen, was zu hohen Inzulässigkeitswerten (bis zu $10^1$) führte.
   • LinSup: Die Superiorisierungsmethode demonstrierte eine bemerkenswerte Stabilität. Ihre Laufzeit blieb unabhängig von der Konditionszahl relativ konsistent, und sie erreichte über alle getesteten Konditionszahlen hinweg konsistent den Ziel-Zulässigkeitswert ($\varepsilon = 10^{-8}$).
   • Zielfunktion: LinSup produzierte am Punkt der Terminierung konsistent bessere (niedrigere) Zielfunktionswerte im Vergleich zu den Simplex-Methoden in schlecht konditionierten Szenarien.

3. Proximity-Target-Analyse:

   • Plots der Inzulässigkeit gegenüber dem Zielfunktionswert (Proximity-Target-Kurven) bestätigten, dass LinSup einen stetigen Pfad zur Zulässigkeit beibehielt, während es gleichzeitig die Zielfunktion reduzierte. Im Gegensatz dazu zeigte die Interior-Point-Methode eine Diskrektion zwischen dem Finden eines niedrigen Zielfunktionswertes und der Erfüllung der Beschränkungen in schlecht konditionierten Settings.

Bedeutung und Behauptungen
Das Paper behauptet, dass die Lineare Superiorisierung einen deutlichen Vorteil gegenüber klassischen LP-Solvern bietet, wenn es um schlecht konditionierte lineare Systeme geht, insbesondere in großskaligen Szenarien.

• Robustheit: Die Autoren kommen zu dem Schluss, dass LinSup weniger von hohen Konditionszahlen betroffen ist als die getesteten LP-Solver. Sie führen dies auf die Natur des Algorithmus zurück: LinSup führt individuelle Projektionen auf Halbräume durch, anstatt das gesamte System simultan zu lösen, und die „Resilienz gegenüber beschränkten Perturbationen“ des Basis-Algorithmus kann dabei helfen, Rechenfehler zu absorbieren, die durch schlechte Konditionierung andernfalls verstärkt würden.
• Praktischer Nutzen: Die Studie legt nahe, dass LinSup für Anwendungen, bei denen das Finden eines zulässigen Punktes mit einem reduzierten Zielfunktionswert ausreichend ist (ein „Satisficing“-Ansatz statt strikter Optimalität), ein zuverlässigeres und effizienteres Werkzeug für schlecht gestellte Probleme darstellt.
• Moderater Umfang: Die Autoren geben explizit an, dass ihre Ergebnisse auf spezifischen experimentellen Setups und Problemgrößen basieren. Sie äußern Vertrauen, dass die beobachteten Trends auch für größere Instanzen gelten werden, beanspruchen aber nicht, dass LinSup LP-Solver für alle Optimierungsaufgaben ersetzt. Sie merken an, dass LinSup kein LP-Solver ist und nicht auf eine eingeschränkte Optimalität abzielt, sondern auf einen „überlegenen“ zulässigen Punkt.
• Zukünftige Arbeit: Das Paper legt nahe, dass die beobachtete Robustheit von LinSup in linearen Settings eine Untersuchung in nichtlinearen Settings rechtfertigt, insbesondere dort, wo Interior-Point-Methoden bekanntlich Schwierigkeiten mit schlechter Konditionierung haben (z. B. intensitätsmodulierte Strahlentherapie).