Technische Samenvatting: Schaalbare Deep Unfolding van Conische Optimalisaties

Probleemstelling

Deep Unfolding (DU) is effectief gebleken voor het versnellen van iteratieve optimalisaties in diverse domeinen, waaronder compressed sensing en robotica. Het uitbreiden van DU naar grootschalige semidefiniete programma's (SDP's)—veelvoorkomend in robotica-toepassingen zoals covariance steering—is echter gehinderd door twee specifieke obstakels bij het uitrollen van full-update ADMM-gebaseerde conische solvers (bijv. COSMO):

1. Geheugenbottleneck in Lineaire Systeemoplossingen: Backpropagatie door de lineaire systeemoplossing in elke iteratie vereist doorgaans het expliciet vormen van de coëfficiëntmatrix. Voor ADMM houdt dit de term $A^\top A$ in. Zelfs als de beperkingsmatrix $A$ ijl (sparse) is, is $A^\top A$ vaak dicht (dense), wat leidt tot een geheugencomplexiteit van $O(n^2)$. Dit verhindert schaling naar grote probleemgroottes waarbij directe factorisatie het geheugen doet vollopen.
2. Numerieke Instabiliteit in PSD-projecties: De projectie op de positief semidefiniete (PSD) kegel vereist een eigendecompositie. Standaard backpropagatie door deze operatie omvat termen van de vorm $1/(\lambda_i - \lambda_j)$ in de gradiënt. Wanneer eigenwaarden samenvallen (een veelvoorkomend fenomeen tijdens training, vooral bij isotrope covariantiedoelen), veroorzaken deze termen numerieke instabiliteit of ongedefinieerde gradiënten (NaNs).

Methodologie

De auteurs stellen een deep unfolding-framework voor de COSMO-solver voor dat deze twee obstakels aanpakt via aangepaste backward rules, waardoor het mogelijk wordt om hyperparameter-policies en warm-starts te leren voor grootschalige conische problemen.

1. Matrix-vrije Impliciete Differentiatie voor Lineaire Systemen

Om de $O(n^2)$ geheugenkosten van het expliciet vormen van de dichte $A^\top A$-matrix te vermijden, gebruiken de auteurs een matrix-vrije impliciete differentiatierule voor de conjugate gradient (CG) gebaseerde lineaire systeemoplossing.

• Forward Pass: De solver gebruikt de indirecte modus, waarbij de gereduceerde normale vergelijkingen $(P + \sigma I + A^\top D(\rho)A)\tilde{x} = \xi$ worden opgelost met behulp van CG, wat uitsluitend steunt op matrix-vectorproducten (matvecs).
• Backward Pass: In plaats van de CG-iteraties uit te rollen of de dichte Jacobiaan te vormen, leiden de auteurs een regel af op basis van het adjoint systeem. Door het adjoint systeem $M\tilde{\lambda} = -\nabla_{\tilde{x}}L$ op te lossen met dezelfde CG-methode, wordt de gradiënt met betrekking tot de hyperparameters $\rho$ berekend als $\nabla_\rho L = (A\tilde{\lambda}) \odot (A\tilde{x})$.
• Resultaat: Deze aanpak vormt nooit expliciet de dichte coëfficiëntmatrix, wat de geheugencomplexiteit vermindert van $O(n^2)$ naar $O(n + \text{nnz}(A))$ en backpropagatie mogelijk maakt op schalen waar voorheen gebruikte methoden falen.

2. Stabiele Backward Rule voor PSD-projectie

Om de instabiliteit van eigendecompositie-gradiënten bij herhaalde eigenwaarden op te lossen, vervangen de auteurs de standaard autograd door een backward rule gebaseerd op de Dalečii–Krein (DK) representatie van de Fréchet-afgeleide.

• Mechanisme: De PSD-projectie wordt behandeld als een primaire matrixfunctie $T = U f(\Lambda) U^\top$ met $f(x) = \max(x, 0)$. De DK-stelling biedt een formule voor de afgeleide waarbij de enkelvoudige term $1/(\lambda_j - \lambda_i)$ wordt vermenigvuldigd met een teller $f(\lambda_j) - f(\lambda_i)$.
• Stabiliteit: Wanneer eigenwaarden samenvallen ($\lambda_i = \lambda_j$), verdwijnt de teller met dezelfde snelheid als de noemer, wat resulteert in een verwijderbare singulariteit die wordt gedefinieerd door de limiet $f'(\lambda_i)$. Dit zorgt ervoor dat de gradiënt eindig en goed gedefinieerd blijft, zelfs met herhaalde eigenwaarden.
• Efficiëntie: Deze regel hergebruikt de in de forward pass berekende eigendecompositie en brengt geen extra asymptotische computationele kosten met zich mee vergeleken met naïeve benaderingen, in tegenstelling tot alternatieven zoals het uitrollen van Newton-Schulz iteraties.

Belangrijkste Bijdragen

1. Schaalbare Lineaire Systeemdifferentiatie: Een matrix-vrije impliciete differentierule die het geheugengebruik vermindert van $O(n^2)$ naar $O(n)$, waardoor deep unfolding van full-update conische solvers op grootschalige SDP's mogelijk wordt.
2. Numeriek Stabiele PSD-projectie: Een backward rule gebaseerd op de Dalečii–Krein-stelling die goed gedefinieerd blijft bij herhaalde eigenwaarden, een kritieke vereiste voor training op covariance steering en andere SDP-problemen.
3. Empirische Validatie: Een demonstratie dat deze regels het mogelijk maken om de COSMO-solver uit te rollen om lichtgewicht hyperparameter-policies en warm-starts te leren. De geleerde aanpak wordt geëvalueerd op standalone SDP's/SOCP's en als sub-routine in Sequential Convex Programming (SCP) voor niet-lineaire covariance steering.

Resultaten

De auteurs evalueren de geleerde COSMO-solver tegen de standaard COSMO-solver (met adaptieve heuristieken) en de state-of-the-art interior-point solver Clarabel over verschillende probleemklassen:

• Standalone SDP's en SOCP's: De geleerde policy bereikt significante versnellingen afhankelijk van de probleemklasse:
  • Lovász $\vartheta$ SDP's: Tot 50,4× versnelling in wall-clock tijd.
  • Max-cut SDP's: 2,62× versnelling.
  • Robuuste Kalman Filters: 4,91× versnelling.
  • Lyapunov LMI's: 1,16× versnelling.
• Niet-lineaire Covariance Steering (SCP): Wanneer gebruikt als sub-routine in SCP voor niet-lineaire systemen (double integrator en unicycle dynamica), levert de geleerde aanpak een 30× versnelling vergeleken met vanilla COSMO.
• Geheugenscaling: Experimenten tonen aan dat terwijl baseline methoden het GPU-geheugen (24 GB) uitputten bij $n \approx 20\text{--}50k$ variabelen, de voorgestelde matrix-vrije methode lineair schaalt en zelfs bij $n=50k$ onder de 300 MB blijft.

Betekenis en Beperkingen

Het artikel stelt dat deze bijdragen het mogelijk maken om deep unfolding toe te passen op grootschalige conische optimalisatie, een domein dat voorheen beperkt werd door geheugen- en stabiliteitsrestricties. De geleerde policies bieden substantiële versnelling voor real-time robotica-toepassingen waar vaste computationele budgetten vereist zijn.

De auteurs merken specifieke beperkingen op:

• Schaalbaarheid: Hoewel de lineaire solve matrix-vrij is, vereist de PSD-projectie nog steeds een dichte $O(p^3)$ eigendecompositie voor elk semidefiniete blok van grootte $p$. De winst in schaalbaarheid wordt gerealiseerd in het aantal variabelen/beperkingen, niet in de blokgrootte zelf.
• Nauwkeurigheidsregime: De methode richt zich op lage- tot gemiddelde nauwkeurigheid ($\epsilon \approx 10^{-3}$), wat typisch is voor real-time controle. Het claimt niet beter te presteren dan interior-point solvers (zoals Clarabel) bij zeer strikte toleranties, waar eerste-orde methoden traag convergeren.
• Trainingsoverhead: Een aparte policy wordt getraind per probleemfamilie, wat een voorafgaande kostenpost met zich meebrengt (ongeveer 100 problemen per klasse) die moet worden geamortiseerd over vele oplossingen. Het huidige werk toont geen transfer tussen families of schaling naar instanties die substantieel groter zijn dan die tijdens de training zijn gezien.