Line-Search Filter Differential Dynamic Programming for Optimal Control with Nonlinear Equality Constraints

Technical Summary: FilterDDP for Optimal Control with Nonlinear Equality Constraints

Problem Formulation
The paper addresses discrete-time optimal control problems (OCPs) involving nonlinear equality constraints. These problems are prevalent in robotics for tasks such as motion planning, inverse dynamics, and contact-implicit trajectory optimization (e.g., legged locomotion, manipulation). The specific OCP formulation minimizes a cumulative cost function subject to initial state conditions, system dynamics, and nonlinear equality constraints $c(x_t, u_t) = 0$. While Differential Dynamic Programming (DDP) is efficient for unconstrained problems, extending it to handle nonlinear equality constraints robustly has been an underexplored area. Existing approaches often rely on augmented Lagrangian (AL) methods or merit functions, which can suffer from limited formal convergence guarantees or numerical instability.

Methodology: FilterDDP
The authors propose FilterDDP, a line-search filter algorithm that integrates the DDP framework with a step filter mechanism, similar to the approach used in the general nonlinear programming solver IPOPT. The algorithm alternates between a backward pass and a forward pass:

1. Backward Pass: The algorithm computes first and perturbed second derivatives of a sub-optimal value function. It applies a perturbed Newton step to the stationarity conditions of the Lagrangian. A key innovation is the introduction of perturbation terms ($\delta_w I$ and $-\delta_c I$) in the KKT matrix to ensure the matrix has a specific inertia (positive, negative, zero eigenvalues), guaranteeing non-singularity and stability.
2. Forward Pass: A trial trajectory is generated using a backtracking line search. The step size $\gamma$ is adjusted based on a filter criterion.
3. Filter Criteria: Unlike traditional merit function approaches, FilterDDP uses a filter based on two quantities:
   • Constraint Violation ($\theta$): The sum of $L_1$ norms of constraint violations.
   • Lagrangian ($L$): The value of the Lagrangian function, rather than the raw cost function.
     A trial point is accepted if it yields a sufficient decrease in either the constraint violation or the Lagrangian, provided it does not fall into a "taboo" region defined by the filter.

Key Design Choices and Theoretical Contributions
The paper identifies and rigorously justifies two critical design choices that enhance numerical performance:

1. Lagrangian vs. Cost in Step Acceptance: The authors replace the cost function with the Lagrangian in the step acceptance criterion. They prove that the sufficient decrease condition on the Lagrangian is analogous to the Armijo condition in unconstrained optimization. This choice is supported by a formal proof showing that the directional derivative of the Lagrangian corresponds to the search direction used in the algorithm.
2. Perturbed Hessians and Dual Variables: In the backward pass, the algorithm uses perturbed Hessians and updates the value function gradient using an estimated dual variable of the dynamics constraints rather than the raw value function gradient.
   • Local Quadratic Convergence: The authors provide a formal proof of local quadratic convergence for FilterDDP within a neighborhood of a solution. This generalizes existing proofs for unconstrained DDP (scalar states/controls) to the constrained, vector-valued setting. The proof relies on showing that the optimal point is a fixed point of the algorithm and that the iterates converge quadratically when sufficiently close to the solution.
3. Primal-Dual Extension: The paper presents an extension to handle inequality constraints using a primal-dual interior point framework. This involves introducing dual variables for inequality constraints and solving a sequence of barrier sub-problems with perturbed complementarity conditions.

Experimental Results
FilterDDP was validated on three challenging contact-implicit trajectory optimization problems arising in robotics:

1. Cart-pole swing-up with Coulomb friction.
2. Acrobot swing-up with hard joint limits.
3. Non-prehensile pushing (manipulation) with obstacle avoidance.

The algorithm was compared against:

• IPOPT: A state-of-the-art general nonlinear programming solver.
• IPOPT (B): An L-BFGS variant of IPOPT.
• ProxDDP: An existing AL-based DDP algorithm.

Findings:

• Robustness: FilterDDP demonstrated significantly higher robustness compared to first-order methods (ProxDDP and IPOPT (B)). Notably, ProxDDP and IPOPT (B) failed to solve the acrobot task entirely, yielding infeasible or degenerate solutions.
• Efficiency: FilterDDP achieved convergence in fewer iterations and significantly lower wall-clock time compared to IPOPT. Across the three tasks, FilterDDP's mean wall-clock time was approximately 10–27% of IPOPT's time and 1–5% of IPOPT (B)'s time.
• Convergence: Empirical results confirmed local quadratic convergence, validating the theoretical analysis.
• Ablation Study: Removing the proposed design choices (using cost instead of Lagrangian, or unperturbed Hessians) resulted in increased iteration counts and higher failure rates, confirming the necessity of these modifications.

Significance and Claims
The paper claims that FilterDDP offers a robust, efficient alternative to existing methods for solving equality-constrained OCPs in robotics. By moving away from augmented Lagrangian approaches and adopting a line-search filter framework with specific theoretical modifications (Lagrangian-based acceptance and perturbed Hessians), the authors achieve stronger convergence properties and better numerical performance. The work bridges the gap between the efficiency of DDP and the robustness required for complex, constrained robotic tasks, providing a solver that is faster than general-purpose solvers like IPOPT while maintaining comparable or superior robustness. The authors note that future work will focus on applying FilterDDP to high-dimensional legged robot locomotion and formally establishing global convergence.