2025-11-23T02:40:16.760420

Dual-Regularized Riccati Recursions for Interior-Point Optimal Control

Sousa-Pinto, Orban
We derive closed-form extensions of Riccati's recursions (both sequential and parallel) for solving dual-regularized LQR problems. We show how these methods can be used to solve general constrained, non-convex, discrete-time optimal control problems via a regularized interior point method, while guaranteeing that each step is a descent direction of an Augmented Barrier-Lagrangian merit function. We provide MIT-licensed implementations of our methods in C++ and JAX.
academic

Dual-Regularisierte Riccati-Rekursionen für Interior-Point-Optimalsteuerung

Grundlegende Informationen

  • Paper-ID: 2509.16370
  • Titel: Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
  • Autoren: João Sousa-Pinto, Dominique Orban
  • Klassifizierung: math.OC cs.MS cs.RO cs.SY eess.SY
  • Veröffentlichungsdatum: 15. Oktober 2025 (arXiv v2)
  • Paper-Link: https://arxiv.org/abs/2509.16370

Zusammenfassung

In diesem Artikel werden geschlossene Erweiterungen der Riccati-Rekursion zur Lösung dual-regularisierter LQR-Probleme hergeleitet (einschließlich sequenzieller und paralleler Versionen). Die Autoren zeigen, wie diese Methoden durch regularisierte Interior-Point-Verfahren zur Lösung allgemeiner, eingeschränkter, nicht-konvexer, zeitdiskreter Optimalsteuerungsprobleme verwendet werden können, während gleichzeitig garantiert wird, dass jeder Schritt eine Abstiegsrichtung der erweiterten Barriere-Lagrange-Funktion darstellt. Das Papier bietet MIT-lizenzierte Implementierungen in C++ und JAX.

Forschungshintergrund und Motivation

Kernproblem

Das Kernproblem dieser Forschung besteht darin, wie man effizient nicht-konvexe zeitdiskrete Optimalsteuerungsprobleme mit Gleichheits- und Ungleichheitsnebenbedingungen löst. Traditionelle Methoden haben bei der Behandlung solcher Probleme folgende Herausforderungen:

  1. Rechnerische Effizienzprobleme: Standardmäßige Interior-Point-Verfahren erfordern bei Optimalsteuerungsproblemen die Lösung großer linearer Systeme mit hoher Rechenkomplexität
  2. Numerische Stabilität: Wenn der Regularisierungsparameter gegen Null geht, können traditionelle Methoden numerische Instabilität aufweisen
  3. Parallelisierungsschwierigkeiten: Bestehende Methoden können Parallelrechenressourcen nicht vollständig nutzen

Bedeutung des Problems

Optimalsteuerungsprobleme haben breite Anwendungen in der Robotik, Luft- und Raumfahrt, autonomem Fahren und anderen Bereichen. Die effiziente Lösung solcher Probleme ist für Echtzeit-Steuersysteme entscheidend, besonders in Szenarien, die komplexe Nebenbedingungen erfordern.

Einschränkungen bestehender Methoden

  1. DDP-Algorithmus: Obwohl die in der Praxis am häufigsten verwendete Methode, kann diese Single-Shooting-Methode Zustandstrajektorien nicht unabhängig warm starten
  2. Standard-LQR-Methoden: Nur für uneingeschränkte oder einfach eingeschränkte lineare Systeme geeignet
  3. Bestehende Interior-Point-Verfahren: Wie IPOPT und andere universelle Löser können die Struktureigenschaften von Optimalsteuerungsproblemen nicht vollständig ausnutzen

Kernbeiträge

  1. Theoretischer Beitrag: Herleitung geschlossener Riccati-Rekursionserweiterungen zur Lösung dual-regularisierter LQR-Probleme, einschließlich sequenzieller und paralleler Versionen
  2. Algorithmische Innovation: Vorschlag eines regularisierten Interior-Point-Verfahrens, das Abstiegsrichtungen garantiert, unter Verwendung der erweiterten Barriere-Lagrange-Funktion als Merit-Funktion
  3. Numerische Stabilität: Entwurf eines Algorithmus, der numerisch stabil ist, wenn der Regularisierungsparameter δ→0 geht und den Standard-LQR-Algorithmus wiederherstellen kann
  4. Parallelisierter Algorithmus: Implementierung eines Lösungsalgorithmus mit O(log N) paralleler Zeitkomplexität basierend auf assoziativen Scans
  5. Software-Beitrag: Bereitstellung von Open-Source-Implementierungen in C++ und JAX mit Unterstützung für effiziente dünnbesetzte lineare Algebra

Methodische Details

Aufgabendefinition

Betrachten Sie das zeitdiskrete Optimalsteuerungsproblem:

min⁡x0,u0,…,xN∑i=0N−1fi(xi,ui)+fN(xN)\min_{x_0,u_0,\ldots,x_N} \sum_{i=0}^{N-1} f_i(x_i, u_i) + f_N(x_N)

Nebenbedingungen:

  • Anfangszustand: x0=s0x_0 = s_0
  • Dynamische Nebenbedingungen: xi+1=di(xi,ui),∀i∈{0,…,N−1}x_{i+1} = d_i(x_i, u_i), \forall i \in \{0,\ldots,N-1\}
  • Gleichheitsnebenbedingungen: ci(xi,ui)=0,∀i∈{0,…,N−1}c_i(x_i, u_i) = 0, \forall i \in \{0,\ldots,N-1\}
  • Ungleichheitsnebenbedingungen: gi(xi,ui)≤0,∀i∈{0,…,N−1}g_i(x_i, u_i) \leq 0, \forall i \in \{0,\ldots,N-1\}
  • Endbedingungen: cN(xN)=0,gN(xN)≤0c_N(x_N) = 0, g_N(x_N) \leq 0

Regularisiertes Interior-Point-Verfahren-Rahmenwerk

Erweiterte Barriere-Lagrange-Funktion

Definition der Barriere-Lagrange-Funktion: L(x,s,y,z;μ)=f(x)−μ∑ilog⁡(si)+yTc(x)+zT(g(x)+s)L(x,s,y,z;\mu) = f(x) - \mu\sum_i \log(s_i) + y^T c(x) + z^T(g(x) + s)

Erweiterte Version: A(x,s,y,z;μ,η)=L(x,s,y,z;μ)+η2(∥c(x)∥2+∥g(x)+s∥2)A(x,s,y,z;\mu,\eta) = L(x,s,y,z;\mu) + \frac{\eta}{2}(\|c(x)\|^2 + \|g(x)+s\|^2)

Lösung linearer Systeme

Jede Iteration erfordert die Lösung des linearen Systems: [P0CTGT0S−1Z0IC0−1ηI0GI0−1ηI][ΔxΔsΔyΔz]=−∇L(x,s,y,z;μ)\begin{bmatrix} P & 0 & C^T & G^T \\ 0 & S^{-1}Z & 0 & I \\ C & 0 & -\frac{1}{\eta}I & 0 \\ G & I & 0 & -\frac{1}{\eta}I \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta y \\ \Delta z \end{bmatrix} = -\nabla L(x,s,y,z;\mu)

Dual-regularisiertes LQR-Problem

Durch Variableneliminierung wird das lineare System des Interior-Point-Verfahrens in ein dual-regularisiertes LQR-Problem transformiert: [PCTC−δI][xy]=−[sc]\begin{bmatrix} P & C^T \\ C & -\delta I \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = -\begin{bmatrix} s \\ c \end{bmatrix}

wobei δ>0\delta > 0 der Regularisierungsparameter ist, die Matrix PP eine Blockdiagonalstruktur aufweist und CC die Jacobi-Matrizen der dynamischen Nebenbedingungen enthält.

Sequenzieller Algorithmus

Rückwärts-Rekursion

Definition von Schlüsselvariablen:

  • Vi=1δ(Fi−I)V_i = \frac{1}{\delta}(F_i - I): Wertfunktions-Approximation
  • vi=1δ(fi+ci)v_i = \frac{1}{\delta}(f_i + c_i): Offset-Vektor

Rekursionsformeln:

G_i = B_i^T W_{i+1} B_i + R_i
H_i = B_i^T W_{i+1} A_i + M_i^T
h_i = r_i + B_i^T g_{i+1}
K_i = -G_i^{-1} H_i
k_i = -G_i^{-1} h_i
V_i = A_i^T W_{i+1} A_i + Q_i + H_i^T K_i
v_i = q_i + A_i^T g_{i+1} + H_i^T k_i
W_i = (I + \delta V_i)^{-1} V_i
g_i = v_i + W_i(c_i - \delta v_i)

Vorwärts-Rekursion

Wiederherstellung der optimalen Trajektorie durch das Steuergesetz ui=Kixi+kiu_i = K_i x_i + k_i und die Zustandsübergangsgleichung.

Paralleler Algorithmus

Parallelisierung durch assoziative Scans

Implementierung von O(log N) paralleler Zeitkomplexität unter Verwendung von assoziativen Scans:

  1. Intervall-Wertfunktionen: Definition von Vi→j(xi,xj)V_{i \to j}(x_i, x_j), die die Wertfunktion von Phase i bis j darstellt
  2. Kombinationsregeln: Etablierung von Kombinationsoperationen für Intervall-Wertfunktionen, die Assoziativität erfüllen
  3. Parallele Berechnung: Parallele Berechnung aller Vi→N+1V_{i \to N+1} durch rückwärts-assoziative Scans

Affine Funktionszusammensetzung

Transformation der Vorwärts-Rekursion in eine Zusammensetzung affiner Funktionen: xi+1=Mixi+mix_{i+1} = M_i x_i + m_i

Verwendung von assoziativen Scans zur parallelen Zusammensetzung aller affinen Transformationen, um O(log N) parallele Vorwärts-Propagation zu erreichen.

Technische Innovationen

  1. Numerische Stabilitätsgestaltung: Vermeidung numerischer Probleme bei δ→0\delta \to 0 durch Reparametrisierung
  2. Garantie der Abstiegsrichtung: Theoretischer Beweis, dass die Suchrichtung eine Abstiegsrichtung der erweiterten Barriere-Lagrange-Funktion ist
  3. Strukturierte Lösung: Vollständige Ausnutzung der zeitlichen Struktur von Optimalsteuerungsproblemen, Vermeidung der Lösung großer dichter linearer Systeme
  4. Parallelisierungsgestaltung: Effiziente Parallelisierung basierend auf assoziativen Scans aus der funktionalen Programmierung

Experimentelle Einrichtung

Implementierungsdetails

Das Papier bietet zwei Implementierungssätze:

  1. C++-Implementierung:
    • Basierend auf dem SIP-Rahmenwerk (Simple Interior Point)
    • Unterstützung für QDLDL-Dünnbesetzter-Löser-Integration
    • Vermeidung dynamischer Speicherzuweisung zur Laufzeit
    • Unterstützung für benutzerdefinierte KKT-Systemlöser
  2. JAX-Implementierung:
    • Unterstützung für automatische Differentiation
    • GPU/TPU-Beschleunigung
    • Vollständige Unit-Test-Suite

Verifikationsmethoden

  • Verifikation der Algorithmen-Korrektheit auf zufällig generierten Beispielen, die erforderliche positive Definitheit erfüllen
  • Konsistenzverifikation mit Standard-LQR-Algorithmus bei δ=0\delta = 0
  • Numerische Stabilitätstests

Experimentelle Ergebnisse

Korrektheit-Verifikation

Das Papier verifiziert die Algorithmen-Korrektheit auf folgende Weise:

  1. Theoretische Verifikation: Bei δ=0\delta = 0 degeneriert der Algorithmus zum Standard-LQR-Algorithmus
  2. Numerische Verifikation: Verifikation der Lösungskorrektheit auf zufällig generierten Testfällen
  3. Unit-Tests: Die JAX-Implementierung enthält eine vollständige Unit-Test-Suite

Garantie der Abstiegsrichtung

Theorem 1.2 beweist, dass wenn Δx≠0\Delta x \neq 0 oder Δs≠0\Delta s \neq 0, die Richtungsableitung erfüllt: D(A(⋅,⋅,y,z;μ,η);(Δx,Δs))(x,s)<0D(A(\cdot,\cdot,y,z;\mu,\eta);(\Delta x,\Delta s))(x,s) < 0

Dies garantiert die globale Konvergenz des Algorithmus.

Komplexitätsanalyse

  • Sequenzieller Algorithmus: O(N) Zeitkomplexität
  • Paralleler Algorithmus: O(log N) parallele Zeitkomplexität
  • Raumkomplexität: O(N), linear mit der Problemgröße

Verwandte Arbeiten

Hauptforschungsrichtungen

  1. Klassische LQR-Methoden: Kalman (1960) leitete erstmals die Riccati-Rekursion her
  2. Interior-Point-Verfahren-Anwendungen: Rao et al. (1998) wendeten erstmals Interior-Point-Verfahren auf modellprädiktive Steuerung an
  3. Paralleles LQR: Särkkä und García-Fernández (2021) schlugen den ersten O(log N) parallelen LQR-Algorithmus vor
  4. Strukturierte Löser: Neuere Arbeiten wie FATROP erkunden strukturierte Nebenbedingungsbehandlung

Relative Vorteile dieses Papiers

  1. Theoretische Vollständigkeit: Vollständige theoretische Analyse und Konvergenzgarantien
  2. Numerische Stabilität: Lösung numerischer Probleme, wenn der Regularisierungsparameter gegen Null geht
  3. Praktikalität: Vollständige Open-Source-Implementierung
  4. Allgemeinheit: Kann allgemeine nicht-konvexe eingeschränkte Optimalsteuerungsprobleme behandeln

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Erfolgreiche Herleitung geschlossener Riccati-Rekursionserweiterungen für dual-regularisierte LQR-Probleme
  2. Etablierung der Verbindung zu regularisierten Interior-Point-Verfahren mit Konvergenzgarantien
  3. Implementierung eines effizienten Algorithmus mit O(log N) paralleler Zeitkomplexität
  4. Bereitstellung einer numerisch stabilen und praktischen Open-Source-Implementierung

Einschränkungen

  1. Nebenbedingungstyp-Einschränkungen: Die Methode ist hauptsächlich auf Probleme anwendbar, die in LQR-Form transformiert werden können
  2. Positive-Definitheit-Anforderungen: Der Algorithmus erfordert Annahmen zur positiven Definitheit der Hessian-Matrix
  3. Praktische Leistung: Das Papier fehlt ein Leistungsvergleich bei großen praktischen Problemen

Zukünftige Richtungen

  1. Erweiterung auf allgemeinere Nebenbedingungen: Behandlung von Pfadnebenbedingungen und komplexeren Endbedingungen
  2. Adaptive Regularisierung: Entwicklung von Strategien zur adaptiven Auswahl von Regularisierungsparametern
  3. Praktische Anwendungsverifikation: Verifikation der Methoden-Effektivität in praktischen Anwendungen wie Robotersteuerung

Tiefgreifende Bewertung

Stärken

  1. Signifikanter theoretischer Beitrag: Erstmalige Kombination von dual-regularisierten Techniken mit Riccati-Rekursion mit vollständiger theoretischer Analyse
  2. Elegantes Algorithmen-Design: Geschickte Ausnutzung der zeitlichen Struktur von Optimalsteuerungsproblemen
  3. Sorgfältige numerische Überlegungen: Besondere Aufmerksamkeit auf Numerische-Stabilitätsprobleme
  4. Hochwertige Implementierung: Hochwertige Open-Source-Implementierungen in zwei Programmiersprachen
  5. Parallelisierungs-Innovation: Die auf assoziativen Scans basierende Parallelisierungsmethode hat theoretischen und praktischen Wert

Mängel

  1. Begrenzte experimentelle Verifikation: Hauptsächlich theoretische Verifikation und einfache numerische Tests, fehlende Vergleiche bei großen praktischen Problemen
  2. Unzureichende Leistungsanalyse: Keine detaillierten Analysen von Rechenzeit und Speichernutzung
  3. Unzureichende Diskussion des Anwendungsbereichs: Mangelnde tiefgreifende Diskussion, für welche Arten von Optimalsteuerungsproblemen die Methode am besten geeignet ist
  4. Fehlende Parameterwahlrichtlinien: Begrenzte Diskussion von Strategien zur Auswahl des Regularisierungsparameters

Einfluss

  1. Akademischer Wert: Bietet neue theoretische Werkzeuge für numerische Methoden der Optimalsteuerung
  2. Praktischer Wert: Open-Source-Implementierung fördert die Verbreitung und Anwendung der Methode
  3. Reproduzierbarkeit: Detaillierte Algorithmusbeschreibung und Open-Source-Code garantieren Reproduzierbarkeit
  4. Inspirationswert: Die Dual-Regularisierungs-Idee kann andere Optimierungsprobleme inspirieren

Anwendungsszenarien

  1. Echtzeit-Steuersysteme: Modellprädiktive Steuerungsanwendungen, die schnelle Lösungen erfordern
  2. Großskalige Optimierung: Optimalsteuerungsprobleme mit langen Zeithorizonten
  3. Parallelrechenumgebungen: Anwendungsszenarien, die Multi-Core- oder GPU-Ressourcen vollständig nutzen können
  4. Eingeschränkte Optimierung: Steuerungsprobleme, die komplexe Gleichheits- und Ungleichheitsnebenbedingungen erfordern

Referenzen

Das Papier zitiert wichtige Literatur in diesem Bereich, einschließlich:

  • Kalman (1960): Grundlagen der Optimalsteuerungstheorie
  • Blelloch (1989): Parallelisierungstheorie für assoziative Scans
  • Särkkä & García-Fernández (2021): Parallele LQR-Algorithmen
  • Wächter & Biegler (2006): IPOPT Interior-Point-Löser

Gesamtbewertung: Dies ist ein ausgezeichnetes Papier mit herausragendem theoretischem Beitrag und deutlichen technischen Innovationen. Die Autoren haben erfolgreich dual-regularisierte Techniken in die Riccati-Rekursion eingeführt, nicht nur numerische Stabilität bewahrt, sondern auch effiziente Parallelisierung erreicht. Obwohl es noch Raum für Verbesserungen bei der praktischen Anwendungsverifikation gibt, machen sein theoretischer Wert und sein Open-Source-Beitrag es zu einem wichtigen Fortschritt im Bereich der numerischen Methoden für Optimalsteuerung.