Technische Samenvatting: Projectievrije Functioneel Gelimiteerde Optimalisatie voor Risicoaversie en Sparsiteitscontrole

1. Probleemformulering

Het artikel behandelt het probleem van functioneel gelimiteerde optimalisatie:
$$\begin{aligned} f^* := \min_{x} \quad & f(x) \\ \text{zodat} \quad & h_i(x) \le 0, \quad i = 1, \dots, m, \\ & x \in X, \end{aligned} \tag{1.1}$$
waarbij $X \subseteq \mathbb{R}^n$ een niet-lege, compacte, convexe verzameling is. De functies $h_i$ zijn proper, onderaanzijdig semicontinu en convex. Het doelwit $f$ wordt onderzocht in twee regimes:

1. Convexe Setting: $f$ is convex (mogelijk niet-glad).
2. Niet-convexe Setting: $f$ is differentieerbaar met Lipschitz-continue gradiënten.

Dit kader modelleert toepassingen waar risicobewuste criteria en sparsiteitsbeperkingen gelijktijdig voorkomen, zoals portefeuilleoptimalisatie (minimaliseren van onderprestatierisico met activa-limieten) en intensiteit-gemoduleerde stralingstherapie (IMRT)-planning (minimaliseren van overdosering/ondodosering met selectie van een spaarzaam aantal stralenbundels).

Uitdaging: Standaard projectie-gebaseerde methoden (bijv. straffunctie, uitgebreide Lagrange, primaal-dual) vereisen herhaalde projecties op $X$, wat computatieel duur kan zijn en de in de oplossing inherente sparsestructuren vernietigt. Bestaande projectievrije methoden behandelen ofwel alleen eenvoudige beperkingen, of hebben complexiteitsgrenzen die afhankelijk zijn van de grootte van de optimale duale Lagrange-multiplicatoren, die willekeurig groot kunnen zijn.

2. Methodologie

De auteurs stellen projectievrije algoritmen voor die projecties vervangen door oproepen aan een Lineaire Minimalisatie-Orakel (LMO) over $X$. De kerninnovatie is een Level-Set Buitenste Lus gecombineerd met een Conditionele Gradiënt-Orakel (CGO) voor zadelpunt-subproblemen.

2.1 Convexe Setting: Level Conditionele Gradiënt (LCG)

Voor het convexe geval wordt het probleem gereduceerd tot het vinden van de wortel van een waardenfunctie $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$.

• Buitenste Lus: Een benaderde Newton-methode updatet de niveau-schatting $l_k$. In plaats van exacte gradiënten, gebruikt deze een ondergrens $L_k$ en een benaderde subgradiënt afgeleid van de binnenste orakel.
• Binnenste Lus (CGO): Een gespecialiseerde Conditionele Gradiënt-Orakel lost het zadelpunt-subprobleem op $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$.
  • De orakel retourneert een primale iteratie $x_k$ en een certificaatinterval $[L_k, U_k]$.
  • Cruciaal is dat de duale verzameling $Z$ de standaard simplex is, wat garandeert dat de methode niet afhankelijk is van de grootte van de optimale Lagrange-multiplicatoren.
  • De gap $U_k - L_k$ drijft de stopregels en niveau-updates.
• Uitbreiding voor niet-gladde functies: Voor gestructureerde niet-gladde functies (max-structuur) hanteert de methode Nesterov-smoothing binnen het CGO-kader, waarbij dezelfde complexiteitsorde wordt behouden.

2.2 Niet-convexe Setting: Onnauwkeurige Proximale Punten LCG (IPP-LCG)

Voor niet-convexe $f$ reduceert de methode het probleem tot een reeks convexe subproblemen via proximale punt-regularisatie:
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{zodat} \quad h_i(x) \le 0.$$

• Mechanisme: De LCG-methode uit de convexe setting wordt gebruikt als een onnauwkeurige solver voor elk proximale subprobleem.
• Output: Het algoritme selecteert de iteratie die de doelwitvermindering over de reeks minimaliseert.
• Garantie: Onder Slater's voorwaarde en gladheidsaannamen berekent de methode een $(\epsilon, \epsilon)$-near-KKT-punt.

3. Belangrijkste Bijdragen

1. LCG voor Convexe Functionele Beperkingen:

   • Stelt de Level Conditionele Gradiënt (LCG)-methode voor.
   • Bereikt een iteratiecomplexiteit van $O(\epsilon^{-2} \log(\epsilon^{-1}))$ voor het verkrijgen van een $\epsilon$-optimale en $\epsilon$-toelaatbare oplossing.
   • Betekenis: De complexiteitsgrens is onafhankelijk van de grootte van de optimale duale Lagrange-multiplicator, een beperking die aanwezig was in eerdere projectievrije werken (bijv. Lan et al., 2021).

2. IPP-LCG voor Gladde Niet-convexe Doelwitten:

   • Ontwikkelt de Onnauwkeurige Proximale Punten LCG (IPP-LCG)-methode.
   • Lost een reeks convexe subproblemen op met LCG, waarbij alle binnenste oplossingen projectievrij blijven.
   • Bereikt een iteratiecomplexiteit van $O(\epsilon^{-3} \log(\epsilon^{-1}))$ voor het berekenen van een $(\epsilon, \epsilon)$-near-KKT-punt.

3. Certificaatmechanisme:

   • De CGO retourneert expliciete onder- en bovencertificaten ($L_k, U_k$) die de level-set-updates en stopregels drijven, waardoor de noodzaak voor exacte zadelpunt-oplossingen wordt vermeden.

4. Numerieke Resultaten

De auteurs evalueren de methoden op twee toepassingsdomeinen:

4.1 Portefeuilleselectie

• Opzet: Risico-averse portefeuilleoptimalisatie met stap-risicodoelwitten (geconvexeerd via CVaR of gladde niet-convexe surrogaten) en sparsiteitsbeperkingen (beperken van het aantal activa).
• Baselines: Vergelijking met CoexDurCG (projectievrij), FISTA, PGD en diverse op sparsiteit gerichte heuristieken (Greedy+Refit, IRL1, etc.) onder een vast wandklok-budget van 5 seconden.
• Vondsten:
  • Convex Model: LCG behaalde de beste toelaatbare out-of-sample stap-risico op 5 van de 6 datasets, terwijl strikt aan de sparsiteitsdoelen werd voldaan.
  • Niet-convex Model: IPP-LCG behaalde de beste toelaatbare stap-risico op 4 van de 6 datasets.
  • Trade-off: De methoden navigeerden succesvol door de nauwkeurigheids-sparsiteits-trade-off, en presteerden vaak beter dan projectie-gebaseerde baselines in toelaatbare risicoreductie binnen hetzelfde tijdsbudget.

4.2 Intensiteit-Gemoduleerde Stralingstherapie (IMRT)

• Opzet: Behandelingsplanning met groep-sparsiteitsbeperkingen (beperken van het aantal stralenbundelhoeken) en klinische dosis-volume-beperkingen.
• Vondsten:
  • Convex: LCG verbeterde de bevrediging van beperkingen vergeleken met CoexDurCG bij vergelijkbare looptijden.
  • Niet-convex: Een "warm-start"-strategie werd getest waarbij een spaarzaam convexe LCG-planning de niet-convexe IPP-LCG-verfijning initialiseerde.
  • Resultaat: De warm-started IPP-LCG verlaagde de maximale beperkingsovertreding aanzienlijk (van 0,8438 naar 0,1675) vergeleken met een cold-start IPP-LCG, terwijl een klinisch spaarzame behandelingsstructuur werd behouden (7 hoeken, 20 aperturen). Cold-start niet-convexe optimalisatie faalde om klinisch levensvatbare plannen te vinden vanwege ernstige ondodosering van het doelwit.

5. Betekenis en Aanspraken

Het artikel stelt dat de primaire bijdrage ligt in het uitbreiden van projectievrije methoden naar algemene functionele beperkingen zonder te vertrouwen op de grootte van duale multiplicatoren voor complexiteitsgaranties. Door een level-set buitenste lus te combineren met een compact zadelpunt-orakel, behouden de auteurs de voordelen van spaarzame representatie van conditionele gradiëntmethoden (iteraties als convexe combinaties van uiterste punten) terwijl ze complexe niet-lineaire beperkingen hanteren.

De numerieke resultaten suggereren dat:

1. LCG effectief is voor convexe risico-sparsiteitsproblemen, met concurrerende of superieure prestaties ten opzichte van bestaande projectievrije en projectie-gebaseerde methoden.
2. IPP-LCG het meest effectief is niet als een standalone solver vanaf een willekeurige start, maar als een verfijningsmechanisme wanneer geïnitieerd met een hoogwaardige spaarzame convexe oplossing.

De auteurs concluderen dat deze methoden bijzonder geschikt zijn voor grootschalige toepassingen waar projecties duur zijn en spaarzame structurele representaties wenselijk zijn. Toekomstige werkrichtingen die zijn geïdentificeerd, omvatten het ontwikkelen van lichtere niet-convexe schema's, het versoepelen van Slater-achtige aannames, en het ontwerpen van toepassingsspecifieke LMO's voor impliciete toelaatbare verzamelingen.