Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

Technische Samenvatting: Mondiale Convergentie van een Line-Search Filter Differential Dynamic Programming Methode

Probleemstelling
Het artikel behandelt de uitdaging van het oplossen van discrete-time, eindige-horizon optimale controleproblemen (OCP's) onderworpen aan nietlineaire gelijkheidsbeperkingen op toestanden en besturingen, evenals systeemdynamica. Hoewel het Differential Dynamic Programming (DDP) algoritme, oorspronkelijk voorgesteld door Mayne en Jacobson, een goed gevestigde methode is voor ongestrede OCP's met bekende lokale kwadratische convergentie, ontbreekt het de toepassing op beperkte problemen vaak aan een formele garantie voor mondiale convergentie in veel bestaande uitbreidingen. Eerdere beperkte DDP-varianten, zoals die gebaseerd op sequential quadratic programming of primal-dual formuleringen, bieden vaak lokale convergentieresultaten maar laten globale analyse achterwege. Het specifieke gat dat dit werk beoogt te dichten, is het gebrek aan een rigoureus bewijs voor de mondiale convergentie van het FilterDDP-algoritme, een line-search filtermethode voorgesteld door Xu et al. die de algemene nietlineaire programmerings (NLP) filtermethode van Wächter en Biegler aanpast aan het DDP-raamwerk.

Methodologie
De auteurs stellen een formele analyse voor van het FilterDDP-algoritme, dat een line-search filterprocedure integreert met de DDP-structuur. De kernmethodologie houdt in dat de typisch gebruikte gedempte Newton-stap in algemene NLP filtermethoden wordt vervangen door een DDP-specifiek generatieproces voor proefpunten, bestaande uit twee fasen:

1. Backward Recursion (Achterwaartse Recursie): Een recursieve update van de benaderingen van de waarde-functie en Lagrange-multiplicatoren. Deze fase berekent geperturbeerde Hessianen en lost een lineair systeem op om update-richtingen ($\zeta, \beta, \psi, \omega$) te bepalen voor besturingen, multiplicatoren en toestanden.
2. Forward Simulation (Voorwaartse Simulatie): Een simulatiefase die een nieuw traject genereert op basis van de berekende updates en een stapgrootte $\alpha$. Cruciaal is dat deze fase ervoor zorgt dat de dynamische beperkingen ($x_{t+1} = f(x_t, u_t)$) bij elke iteratie worden voldaan, een eigenschap die inherent is aan DDP.

Het algoritme maakt gebruik van een filtermechanisme om proefpunten te accepteren, waarbij een balans wordt gevonden tussen de reductie van de Lagrangian (als de objectieve maat) en de maat voor schending van de beperkingen. De criteria voor stapacceptatie omvatten voldoende reductievoorwaarden voor ofwel de Lagrangian of de schending van de beperkingen, een Armijo-type conditie voor "L-type" iteraties, en een feasibility restoration fase (herstel van haalbaarheid) die wordt aangeroepen wanneer de stapgroottes te klein worden of de Jacobiaan van de beperkingen een lage rang krijgt.

Belangrijkste Bijdragen
De primaire bijdrage van dit werk is het vaststellen van de mondiale convergentie van het FilterDDP-algoritme. De auteurs bereiken dit door aan te tonen dat de specifieke backward-forward procedure van DDP dezelfde analytische eigenschappen bezit die vereist zijn voor de mondiale convergentie van line-search filtermethoden in algemene NLP, zoals vastgesteld door Wächter en Biegler.

Belangrijke technische stappen in deze bijdrage zijn onder meer:

• Equivalence of Steps (Gelijkwaardigheid van Stappen): Het bewijzen dat de DDP backward recursie en forward simulatie, wanneer ze worden bekeken door de lens van mondiale convergentieanalyse, zich identiek gedragen als een gedempte Newton-stap toegepast op de Karush-Kuhn-Tucker (KKT) condities van de OCP.
• Lemma Derivatie: Het vaststellen van een reeks lemma's (equivalent aan Lemma's 1–3 in het werk van Wächter en Biegler) die de update-regels begrenzen, descent-eigenschappen voor niet-optimale haalbare punten vaststellen, en aantonen dat de update-regel de filtercriteria (Lagrangian en schending van beperkingen) lokaal lineariseert.
• Interior Point Extension (Interior Point Uitbreiding): Het uitbreiden van de mondiale convergentieanalyse om ongelijkheidsbeperkingen (specifiek $u_t \geq 0$) te behandelen via een barrier interior point methode. Dit omvat het aanpassen van de Hessiane-benaderingen en het bewijzen dat de iteraties begrensd blijven van de grenzen van het haalbare gebied, waardoor de barrière-objectieve functie en de afgeleiden ervan goed gedefinieerd blijven.

Resultaten
Onder een set van standaard regulariteits- en gladheidveronderstellingen (aangeduid als Assumptions G voor gelijkheidsbeperkingen en Assumptions B voor de barrière-uitbreiding), bewijst het artikel de volgende convergentie-eigenschappen:

1. Feasibility (Haalbaarheid): De limietpunten van de sequentie van iteraties gegenereerd door FilterDDP zijn haalbaar; specifiek convergeert de maat voor schending van de beperkingen $\theta(w_k)$ naar nul als $k \to \infty$.
2. Optimality (Optimaliteit): Als de sequentie van iteraties begrensd is, bestaat er ten minste één limietpunt dat voldoet aan de eerste-orde optimaliteitsvoorwaarden (KKT-condities) voor de beperkte OCP. Dit wordt aangetoond door te laten zien dat de way-kritikaliteitsmaat $\chi(w_k)$, gedefinieerd door de norm van de geprojecteerde gradiëntcomponenten, een limietinferieur van nul heeft.
3. Barrier Convergence (Barrière Convergentie): Voor de interior point uitbreiding wordt bewezen dat de iteraties uniform begrensd blijven van de grenzen van de ongelijkheidsbeperkingen, wat de geldigheid van de barrière-formulering gedurende het optimalisatieproces waarborgt.

Betekenis en Claims
Het artikel claimt significantie door formeel de kloof te overbruggen tussen het praktische succes van FilterDDP en rigoureuze theoretische garanties. De auteurs stellen dat hoewel de lokale kwadratische convergentie van FilterDDP eerder is vastgesteld (door de stapacceptatiecriteria te negeren), de mondiale convergentieanalyse ontbrak. Door de analyse van Wächter en Biegler aan te passen, toont het artikel aan dat de DDP-structuur de mondiale convergentie-eigenschappen van de filtermethode niet belemmert; de backward-forward recursie dient effectief dezelfde rol als de Newton-stap in de algemene NLP-context.

De auteurs merken bescheiden op dat deze analyse steunt op de aanname dat de feasibility restoration fase succesvol wordt afgerond en dat het algoritme niet voortijdig stopt bij een niet-KKT punt. Verder identificeren zij dat het vaststellen van snelle lokale convergentie voor FilterDDP (zonder de stapacceptatiecriteria te negeren) een openstaand probleem blijft, wat suggereert dat een tweede-orde correctiestap, vergelijkbaar met die gebruikt in algemene NLP, mogelijk nodig zal zijn voor toekomstig werk. Het artikel stelt geen nieuwe toepassingen of experimentele benchmarks voor, maar richt zich strikt op de theoretische convergentie-eigenschappen van het algoritme.