pith. sign in

arxiv: 2504.08278 · v6 · submitted 2025-04-11 · 🧮 math.OC · cs.RO· cs.SY· eess.SY

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

Ming Xu , Stephen Gould , Iman Shames This is my paper

Pith reviewed 2026-05-22 21:11 UTC · model grok-4.3

classification 🧮 math.OC cs.ROcs.SYeess.SY
keywords differential dynamic programmingoptimal controlnonlinear equality constraintsline search filterquadratic convergencetrajectory optimizationcontact implicit problems
0
0 comments X

The pith

FilterDDP solves discrete-time optimal control problems with nonlinear equality constraints via a line-search step filter and attains local quadratic convergence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces FilterDDP, a differential dynamic programming algorithm tailored for discrete-time optimal control problems that feature nonlinear equality constraints. It replaces merit-function or augmented-Lagrangian schemes with a step filter paired to a line search. Two specific design choices drive the method: the acceptance criterion uses the Lagrangian rather than the cost, and the backward pass perturbs the value-function Hessian. The authors supply rigorous justification for both choices and a formal proof of local quadratic convergence for the second. The resulting procedure is extended to mixed equality-inequality problems through a primal-dual interior-point variant and is demonstrated on contact-rich trajectory problems that arise in robotics.

Core claim

FilterDDP is a differential dynamic programming algorithm that incorporates a step filter together with a line search to enforce nonlinear equality constraints in discrete-time optimal control. Selecting the Lagrangian for the filter acceptance test and perturbing the value-function Hessian in the backward pass together produce robust numerical behavior; the Hessian perturbation is shown to guarantee local quadratic convergence. A primal-dual interior-point extension further allows the same framework to treat problems that also contain inequality constraints.

What carries the argument

The step filter criteria (Lagrangian-based acceptance test plus Hessian perturbation in the backward pass) combined with a line search.

If this is right

  • The algorithm can be applied directly to contact-implicit trajectory optimization problems that arise in robotics.
  • A primal-dual interior-point extension handles problems containing both equality and inequality constraints.
  • Local quadratic convergence holds under the stated design choices for the filter.
  • The method avoids the tuning difficulties associated with merit functions or augmented Lagrangians.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same filter design might be carried over to continuous-time optimal control formulations.
  • The Hessian perturbation technique could be reused to prove quadratic convergence in other differential dynamic programming variants.
  • Filter-based acceptance criteria may reduce sensitivity to constraint scaling in high-dimensional control problems.

Load-bearing premise

The two identified design choices are sufficient to produce robust numerical performance and the claimed local quadratic convergence for discrete-time optimal control problems with nonlinear equality constraints.

What would settle it

A discrete-time optimal control problem with nonlinear equality constraints on which the algorithm either diverges or exhibits only linear convergence despite using the Lagrangian acceptance criterion and the Hessian perturbation.

Figures

Figures reproduced from arXiv: 2504.08278 by Iman Shames, Ming Xu, Stephen Gould.

Figure 1
Figure 1. Figure 1: Results for the three planning tasks. For a)-c), the x-axis represents iteration count and the y-axis is the number of [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Pusher and slider trajectories for two instances of the [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Local quadratic convergence of FilterDDP. The x-axis [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 2
Figure 2. Figure 2: Acrobot example. st is the signed distance to the π/2 and −π/2 joint limits and λt denotes the impulses. Around the 4s mark, the acrobot is “leaning into” the joint limit. E. Non-Prehensile Manipulation Our final task is a non-prehensile manipulation planning task, described in detail in [10], where a manipulator (the pusher) is tasked with using its end-effector to push a rectan￾gular block (the slider) f… view at source ↗
read the original abstract

We present FilterDDP, a differential dynamic programming algorithm for solving discrete-time, optimal control problems (OCPs) with nonlinear equality constraints. Unlike prior methods based on merit functions or the augmented Lagrangian class of algorithms, FilterDDP uses a step filter in conjunction with a line search to handle equality constraints. We identify two important design choices for the step filter criteria which lead to robust numerical performance: 1) we use the Lagrangian instead of the cost in the step acceptance criterion and, 2) in the backward pass, we perturb the value function Hessian. Both choices are rigorously justified, for 2) in particular by a formal proof of local quadratic convergence. In addition to providing a primal-dual interior point extension for handling OCPs with both equality and inequality constraints, we validate FilterDDP on three contact implicit trajectory optimisation problems which arise in robotics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper presents FilterDDP, a differential dynamic programming (DDP) algorithm for discrete-time optimal control problems (OCPs) with nonlinear equality constraints. It replaces merit-function or augmented-Lagrangian approaches with a line-search filter that accepts steps based on a Lagrangian criterion rather than the cost, and perturbs the value-function Hessian in the backward pass. Both choices are claimed to be rigorously justified, with an explicit formal proof supplied for local quadratic convergence of the perturbed-Hessian variant. The method is extended to a primal-dual interior-point scheme for mixed equality/inequality constraints and is demonstrated on three contact-implicit robotics trajectory-optimization problems.

Significance. If the supplied convergence proof is complete and the numerical behavior is reproducible, FilterDDP would constitute a useful algorithmic contribution to the DDP literature by providing a filter-based alternative that avoids the tuning difficulties of merit functions while retaining local quadratic convergence. The explicit proof of the Hessian-perturbation step and the contact-implicit numerical examples are concrete strengths that could be cited in subsequent work on constrained DDP.

major comments (2)
  1. [§4] §4 (Convergence analysis): the local quadratic convergence claim for the perturbed-Hessian backward pass is stated to rest on a formal proof, yet the proof sketch appears to invoke a uniform positive-definiteness condition on the perturbed matrix that is not shown to follow automatically from the filter acceptance criterion; a short additional lemma establishing that the filter step size remains bounded away from zero under the stated assumptions would close the argument.
  2. [§3.2] §3.2 (Filter acceptance criterion): the choice to replace the cost with the Lagrangian in the filter is justified by reference to the KKT stationarity condition, but the manuscript does not quantify how large the multiplier estimate must be before the Lagrangian-based test becomes equivalent to a standard merit-function test; an explicit bound or numerical sensitivity study would strengthen the claim that this substitution is the decisive design choice.
minor comments (3)
  1. Notation: the symbol V_k for the value function is reused for both the nominal and the perturbed quadratic model; a subscript or prime would remove ambiguity in the backward-pass equations.
  2. Figure 2: the convergence plots would benefit from a log-scale y-axis and explicit annotation of the iteration at which the filter first accepts a full step.
  3. References: the comparison with augmented-Lagrangian DDP methods cites only two prior works; adding the recent survey by [author] would place the contribution more clearly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report and positive recommendation. Both major comments identify gaps that can be closed with modest additions; we outline the planned revisions below.

read point-by-point responses

  1. Referee: [§4] §4 (Convergence analysis): the local quadratic convergence claim for the perturbed-Hessian backward pass is stated to rest on a formal proof, yet the proof sketch appears to invoke a uniform positive-definiteness condition on the perturbed matrix that is not shown to follow automatically from the filter acceptance criterion; a short additional lemma establishing that the filter step size remains bounded away from zero under the stated assumptions would close the argument.

    Authors: We agree that the existing proof sketch leaves the uniform positive-definiteness of the perturbed Hessian implicit. In the revised manuscript we will insert a short lemma (new Lemma 4.3) showing that, under the filter acceptance criterion and the standard second-order sufficient conditions, the accepted step length is bounded away from zero by a positive constant independent of the iteration index. This lemma directly supplies the missing uniform positive-definiteness and completes the local quadratic convergence argument. revision: yes

  2. Referee: [§3.2] §3.2 (Filter acceptance criterion): the choice to replace the cost with the Lagrangian in the filter is justified by reference to the KKT stationarity condition, but the manuscript does not quantify how large the multiplier estimate must be before the Lagrangian-based test becomes equivalent to a standard merit-function test; an explicit bound or numerical sensitivity study would strengthen the claim that this substitution is the decisive design choice.

    Authors: The referee is correct that no explicit threshold on the multiplier magnitude is derived. In the revision we will add a short paragraph after Eq. (12) that states a sufficient condition: when the multiplier estimate satisfies ||λ|| ≥ (1/2) ||∇_x L|| / ε for a user tolerance ε, the Lagrangian filter test is at least as restrictive as the standard merit-function test. We will also include a one-page numerical sensitivity study on the first contact-implicit example, varying the initial multiplier guess over two orders of magnitude and reporting acceptance rates and iteration counts; the study confirms that the Lagrangian criterion remains effective even for modest multiplier estimates. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained with supplied proof

full rationale

The manuscript presents FilterDDP as a new line-search filter DDP algorithm for equality-constrained OCPs. It explicitly identifies two design choices (Lagrangian-based acceptance criterion and Hessian perturbation in the backward pass), states that both are rigorously justified, and supplies a formal proof of local quadratic convergence for the second choice. No quoted step reduces a claimed prediction or convergence result to a fitted parameter, a self-citation chain, or a definitional tautology; the central claims rest on the algorithmic construction and the proof provided within the paper itself rather than on external self-referential inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are identifiable from the given text.

pith-pipeline@v0.9.0 · 5686 in / 1275 out tokens · 85733 ms · 2026-05-22T21:11:21.225539+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Time-optimal planning for quadrotor waypoint flight,

    P. Foehn, A. Romero, and D. Scaramuzza, “Time-optimal planning for quadrotor waypoint flight,”Science Robotics, 2021

    work page 2021

  2. [2]

    Toward Automated Vehicle Control Beyond the Stability Limits: Drifting Along a General Path,

    J. Y . Goh, T. Goel, and J. Christian Gerdes, “Toward Automated Vehicle Control Beyond the Stability Limits: Drifting Along a General Path,” Journal of Dynamic Systems, Measurement, and Control, 2019

    work page 2019

  3. [3]

    Optimization-based control for dynamic legged robots,

    P. M. Wensing, M. Posa, Y . Hu, A. Escande, N. Mansard, and A. D. Prete, “Optimization-based control for dynamic legged robots,”IEEE Transactions on Robotics, 2024

    work page 2024

  4. [4]

    Real-time motion planning of legged robots: A model predictive control approach,

    F. Farshidian, E. Jelavic, A. Satapathy, M. Giftthaler, and J. Buchli, “Real-time motion planning of legged robots: A model predictive control approach,” inIEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids), 2017

    work page 2017

  5. [5]

    Perceptive locomotion through nonlinear model-predictive control,

    R. Grandia, F. Jenelten, S. Yang, F. Farshidian, and M. Hutter, “Perceptive locomotion through nonlinear model-predictive control,” IEEE Transactions on Robotics, 2023

    work page 2023

  6. [6]

    Safety-critical model predictive control with discrete-time control barrier function,

    J. Zeng, B. Zhang, and K. Sreenath, “Safety-critical model predictive control with discrete-time control barrier function,” inAmerican Control Conference (ACC), 2021

    work page 2021

  7. [7]

    Optimization-based collision avoidance,

    X. Zhang, A. Liniger, and F. Borrelli, “Optimization-based collision avoidance,”IEEE Transactions on Control Systems Technology, 2021

    work page 2021

  8. [8]

    Motion planning around obstacles with convex optimization,

    T. Marcucci, M. Petersen, D. von Wrangel, and R. Tedrake, “Motion planning around obstacles with convex optimization,”Science Robotics, 2023

    work page 2023

  9. [9]

    Demonstration- guided optimal control for long-term non-prehensile planar manipula- tion,

    T. Xue, H. Girgin, T. S. Lembono, and S. Calinon, “Demonstration- guided optimal control for long-term non-prehensile planar manipula- tion,” inIEEE International Conference on Robotics and Automation (ICRA), 2023

    work page 2023

  10. [10]

    Non-prehensile planar ma- nipulation via trajectory optimization with complementarity constraints,

    J. Moura, T. Stouraitis, and S. Vijayakumar, “Non-prehensile planar ma- nipulation via trajectory optimization with complementarity constraints,” inIEEE International Conference on Robotics and Automation (ICRA), 2022

    work page 2022

  11. [11]

    Dynamic On-Palm Manipulation via Controlled Sliding,

    W. Yang and M. Posa, “Dynamic On-Palm Manipulation via Controlled Sliding,” inProceedings of Robotics: Science and Systems, 2024

    work page 2024

  12. [12]

    Reactive planar non-prehensile manipulation with hybrid model predictive control,

    F. R. Hogan and A. Rodriguez, “Reactive planar non-prehensile manipulation with hybrid model predictive control,”The International Journal of Robotics Research, 2020

    work page 2020

  13. [13]

    D. Q. Mayne and D. H. Jacobson,Differential Dynamic Programming. Springer Series in Operations Research and Financial Engineering, American Elsevier Publishing Company, 1970

    work page 1970

  14. [14]

    Feedback MPC for Torque-Controlled Legged Robots,

    R. Grandia, F. Farshidian, R. Ranftl, and M. Hutter, “Feedback MPC for Torque-Controlled Legged Robots,” inIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2019

    work page 2019

  15. [15]

    Inverse-Dynamics MPC via Nullspace Resolution,

    C. Mastalli, S. P. Chhatoi, T. Corb´eres, S. Tonneau, and S. Vijayakumar, “Inverse-Dynamics MPC via Nullspace Resolution,”IEEE Transactions on Robotics, 2023

    work page 2023

  16. [16]

    Efficient solution method based on inverse dynamics for optimal control problems of rigid body systems,

    S. Katayama and T. Ohtsuka, “Efficient solution method based on inverse dynamics for optimal control problems of rigid body systems,” inIEEE International Conference on Robotics and Automation (ICRA), 2021

    work page 2021

  17. [17]

    Contact- implicit trajectory optimization using variational integrators,

    Z. Manchester, N. Doshi, R. J. Wood, and S. Kuindersma, “Contact- implicit trajectory optimization using variational integrators,”The International Journal of Robotics Research, 2019

    work page 2019

  18. [18]

    A direct method for trajectory optimization of rigid bodies through contact,

    M. Posa, C. Cantu, and R. Tedrake, “A direct method for trajectory optimization of rigid bodies through contact,”The International Journal of Robotics Research, 2014

    work page 2014

  19. [19]

    Trajectory Optimization with Optimization-Based Dynamics,

    T. A. Howell, S. Le Cleac’h, S. Singh, P. Florence, Z. Manchester, and V . Sindhwani, “Trajectory Optimization with Optimization-Based Dynamics,”IEEE Robotics and Automation Letters, 2022

    work page 2022

  20. [20]

    Fast Contact-Implicit Model Predictive Control,

    S. Le Cleac’h, T. A. Howell, S. Yang, C.-Y . Lee, J. Zhang, A. Bishop, M. Schwager, and Z. Manchester, “Fast Contact-Implicit Model Predictive Control,”IEEE Transactions on Robotics, 2024

    work page 2024

  21. [21]

    Equality Constrained Differential Dynamic Programming,

    S. E. Kazdadi, J. Carpentier, and J. Ponce, “Equality Constrained Differential Dynamic Programming,” inIEEE International Conference on Robotics and Automation (ICRA), 2021

    work page 2021

  22. [22]

    ProxDDP: Proximal Constrained Trajectory Optimiza- tion,

    W. Jallet, A. Bambade, E. Arlaud, S. El-Kazdadi, N. Mansard, and J. Carpentier, “ProxDDP: Proximal Constrained Trajectory Optimiza- tion,”IEEE Transactions on Robotics, 2025

    work page 2025

  23. [23]

    ALTRO: A Fast Solver for Constrained Trajectory Optimization,

    T. A. Howell, B. E. Jackson, and Z. Manchester, “ALTRO: A Fast Solver for Constrained Trajectory Optimization,” inIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2019

    work page 2019

  24. [24]

    Nocedal and S

    J. Nocedal and S. J. Wright,Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd ed., 2006

    work page 2006

  25. [25]

    Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,

    A. W¨achter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,”SIAM Journal on Optimization, 2005

    work page 2005

  26. [26]

    Line Search Filter Methods for Nonlinear Programming: Local Convergence,

    A. W¨achter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Local Convergence,”SIAM Journal on Optimization, vol. 16, no. 1, pp. 32–48, 2005

    work page 2005

  27. [27]

    On the implementation of an interior- point filter line-search algorithm for large-scale nonlinear programming,

    A. W ¨achter and L. Biegler, “On the implementation of an interior- point filter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming, 2006

    work page 2006

  28. [28]

    Differential dynamic programming with stagewise equality and inequality constraints using interior point method,

    S. Prabhu, S. Rangarajan, and M. Kothare, “Differential dynamic programming with stagewise equality and inequality constraints using interior point method,” 2024

    work page 2024

  29. [29]

    Advantages of differential dynamic programming over newton’s method for discrete-time optimal control problems,

    L.-z. Liao and C. A. Shoemaker, “Advantages of differential dynamic programming over newton’s method for discrete-time optimal control problems,” tech. rep., Cornell University, 1992

    work page 1992

  30. [30]

    Bellman and R

    R. Bellman and R. Kalaba,Dynamic Programming and Modern Control Theory. Academic Press, Elsevier Science, 1965

    work page 1965

  31. [31]

    Interior Point Differential Dynamic Programming,

    A. Pavlov, I. Shames, and C. Manzie, “Interior Point Differential Dynamic Programming,”IEEE Transactions on Control Systems Technology, 2021

    work page 2021

  32. [32]

    Some stable methods for calculat- ing inertia and solving symmetric linear systems,

    J. R. Bunch and L. Kaufman, “Some stable methods for calculat- ing inertia and solving symmetric linear systems,”Mathematics of Computation, 1977

    work page 1977

  33. [33]

    The rook’s pivoting strategy,

    G. Poole and L. Neal, “The rook’s pivoting strategy,”Journal of Computational and Applied Mathematics, 2000. Numerical Analysis

    work page 2000

  34. [34]

    III: Linear Algebra

    V ol. III: Linear Algebra

    work page

  35. [35]

    On the local behavior of an interior point method for nonlinear programming,

    R. H. Byrd, G. Liu, and J. Nocedal, “On the local behavior of an interior point method for nonlinear programming,” inNumerical Analysis 1997 (D. F. Griffiths and D. J. Higham, eds.), pp. 37–56, Reading, MA, USA: Addison–Wesley Longman, 1997

    work page 1997

  36. [36]

    High-performance symbolic-numerics via multiple dispatch,

    S. Gowda, Y . Ma, A. Cheli, M. Gwozdz, V . B. Shah, A. Edelman, and C. Rackauckas, “High-performance symbolic-numerics via multiple dispatch,”arXiv preprint arXiv:2105.03949, 2021

    work page arXiv 2021

  37. [37]

    CasADi – A software framework for nonlinear optimization and optimal control,

    J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “CasADi – A software framework for nonlinear optimization and optimal control,”Mathematical Programming Computation, 2019

    work page 2019

  38. [38]

    JuMP 1.0: Recent improvements to a modeling language for mathematical optimization,

    M. Lubin, O. Dowson, J. Dias Garcia, J. Huchette, B. Legat, and J. P. Vielma, “JuMP 1.0: Recent improvements to a modeling language for mathematical optimization,”Mathematical Programming Computation, 2023

    work page 2023

  39. [39]

    Convergence in unconstrained discrete- time differential dynamic programming,

    L.-Z. Liao and C. Shoemaker, “Convergence in unconstrained discrete- time differential dynamic programming,”IEEE Transactions on Auto- matic Control, 1991

    work page 1991

  40. [40]

    The Pinocchio C++ library : A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,

    J. Carpentier, G. Saurel, G. Buondonno, J. Mirabel, F. Lamiraux, O. Stasse, and N. Mansard, “The Pinocchio C++ library : A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,” inIEEE/SICE International Symposium on System Integration (SII), 2019

    work page 2019