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

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

Problem Statement
The paper addresses the challenge of solving discrete-time, finite-horizon optimal control problems (OCPs) subject to nonlinear equality constraints on states and controls, as well as system dynamics. While the Differential Dynamic Programming (DDP) algorithm, originally proposed by Mayne and Jacobson, is a well-established method for unconstrained OCPs with known local quadratic convergence, its application to constrained problems lacks a formal global convergence guarantee in many existing extensions. Previous constrained DDP variants, such as those based on sequential quadratic programming or primal-dual formulations, often provide local convergence results but omit global analysis. The specific gap this work targets is the lack of a rigorous global convergence proof for the FilterDDP algorithm, a line-search filter method proposed by Xu et al. that adapts the general nonlinear programming (NLP) filter approach of Wächter and Biegler to the DDP framework.

Methodology
The authors propose a formal analysis of the FilterDDP algorithm, which integrates a line-search filter procedure with the DDP structure. The core methodology involves replacing the damped Newton step typically used in general NLP filter methods with a DDP-specific trial point generation process consisting of two phases:

1. Backward Recursion: A recursive update of value function approximations and Lagrange multipliers. This phase computes perturbed Hessians and solves a linear system to determine update directions ($\zeta, \beta, \psi, \omega$) for controls, multipliers, and states.
2. Forward Simulation: A simulation phase that generates a new trajectory based on the computed updates and a step size $\alpha$. Crucially, this phase ensures that the dynamic constraints ($x_{t+1} = f(x_t, u_t)$) are satisfied at every iteration, a property inherent to DDP.

The algorithm utilizes a filter mechanism to accept trial points, balancing the reduction of the Lagrangian (as the objective measure) and the constraint violation measure. The step acceptance criteria include sufficient reduction conditions for either the Lagrangian or constraint violation, an Armijo-type condition for "L-type" iterations, and a feasibility restoration phase invoked when step sizes become too small or constraint Jacobians become rank-deficient.

Key Contributions
The primary contribution of this work is the establishment of the global convergence of the FilterDDP algorithm. The authors achieve this by demonstrating that the specific backward-forward procedure of DDP satisfies the same analytical properties required for the global convergence of line-search filter methods in general NLP, as established by Wächter and Biegler.

Key technical steps in this contribution include:

• Equivalence of Steps: Proving that the DDP backward recursion and forward simulation, when viewed through the lens of global convergence analysis, behave identically to a damped Newton step applied to the Karush-Kuhn-Tucker (KKT) conditions of the OCP.
• Lemma Derivation: Establishing a series of lemmas (equivalent to Lemmas 1–3 in Wächter and Biegler's work) that bound the update rules, establish descent properties for non-optimal feasible points, and show that the update rule linearizes the filter criteria (Lagrangian and constraint violation) locally.
• Interior Point Extension: Extending the global convergence analysis to handle inequality constraints (specifically $u_t \geq 0$) via a barrier interior point method. This involves adapting the Hessian approximations and proving that iterates remain bounded away from the boundaries of the feasible region, ensuring the barrier objective and its derivatives remain well-defined.

Results
Under a set of standard regularity and smoothness assumptions (denoted as Assumptions G for equality constraints and Assumptions B for the barrier extension), the paper proves the following convergence properties:

1. Feasibility: The limit points of the sequence of iterates generated by FilterDDP are feasible; specifically, the constraint violation measure $\theta(w_k)$ converges to zero as $k \to \infty$.
2. Optimality: If the sequence of iterates is bounded, there exists at least one limit point that satisfies the first-order optimality conditions (KKT conditions) for the constrained OCP. This is demonstrated by showing that the criticality measure $\chi(w_k)$, defined by the norm of the projected gradient components, has a limit inferior of zero.
3. Barrier Convergence: For the interior point extension, the iterates are proven to remain uniformly bounded away from the inequality constraints' boundaries, ensuring the validity of the barrier formulation throughout the optimization process.

Significance and Claims
The paper claims significance by formally bridging the gap between the practical success of FilterDDP and rigorous theoretical guarantees. The authors state that while the local quadratic convergence of FilterDDP was previously established (ignoring step acceptance criteria), the global convergence analysis was missing. By adapting the analysis of Wächter and Biegler, the paper demonstrates that the DDP structure does not hinder the global convergence properties of the filter method; rather, the backward-forward recursion effectively serves the same role as the Newton step in the general NLP context.

The authors modestly note that this analysis relies on the assumption that the feasibility restoration phase terminates successfully and that the algorithm does not stop prematurely at a non-KKT point. Furthermore, the paper identifies that establishing fast local convergence for FilterDDP (without ignoring step acceptance criteria) remains an open problem, suggesting that a second-order correction step, similar to that used in general NLP, may be necessary for future work. The paper does not propose new applications or experimental benchmarks, focusing strictly on the theoretical convergence properties of the algorithm.