Source-linked AI summary
Interior Point Differential Dynamic Programming
Andrei Pavlov, Iman Shames, Chris Manzie
TL;DR
The paper addresses the lack of a general DDP method for nonlinear inequality-constrained optimal control. It develops feasible and infeasible primal-dual interior-point DDP variants, proves local quadratic convergence and perturbed-KKT characterizations, and demonstrates convergence on three control problems.
Problem
DDP lacks an elegant generalization for optimal control problems with nonlinear state and input inequality constraints, while existing approaches can require active-set identification or suffer other drawbacks.
Source: §I · p. 1Method
The paper develops Feasible- and Infeasible-IPDDP algorithms by embedding primal-dual interior-point min-max problems within DDP.
Source: §I · p. 1, §III · p. 2Results
The algorithms have locally quadratic convergence to stationary points that satisfy the perturbed KKT system, and numerical simulations demonstrate convergence on three constrained control examples.
Source: B. Properties of… · p. 4, §V · p. 8Takeaways & Limitations
IPDDP handles nonlinear state and input inequality constraints without active-set identification and can approach locally optimal solutions through perturbed KKT points.
Source: §I · p. 1, B. Properties of… · p. 4
Abstract
from arXiv · showhide
This paper introduces a novel Differential Dynamic Programming (DDP) algorithm for solving discrete-time finite-horizon optimal control problems with inequality constraints. Two variants, namely Feasible- and Infeasible-IPDDP algorithms, are developed using primal-dual interior-point methodology, and their local quadratic convergence properties are characterised. We show that the stationary points of the algorithms are the perturbed KKT points, and thus can be moved arbitrarily close to a locally optimal solution. Being free from the burden of the active-set methods, it can handle nonlinear state and input inequality constraints without a discernible increase in its computational complexity relative to the unconstrained case. The performance of the proposed algorithms is demonstrated using numerical experiments on three different problems: control-limited inverted pendulum, car-parking, and unicycle motion control and obstacle avoidance.
I. INTRODUCTION
The paper addresses DDP’s lack of an elegant treatment for nonlinear inequality constraints and introduces primal-dual interior-point extensions with convergence guarantees. It formulates the finite-horizon constrained control problem and perturbed KKT conditions underlying the method.
I. INTRODUCTION
- DDP lacks an elegant generalization to inequality-constrained problems, while existing penalty, barrier, augmented-Lagrangian, and active-set approaches have important drawbacks.These include ill-conditioning, hand-tuning, slow convergence, saddlepoints, or worst-case combinatorial complexity.Source: §I · p. 1
- The paper introduces primal-dual Interior-Point DDP as an extension that avoids objective modification and separate active-constraint identification while providing provable local quadratic convergence for nonlinear state and control constraints.The paper presents Feasible- and Infeasible-IPDDP variants.Source: §I · p. 1
II. PRELIMINARIES
- The control problem uses twice continuously differentiable dynamics, costs, and inequality constraints over a finite prediction horizon with state and control decision variables.The formulation includes a known initial state, stage and terminal costs, and constraints c(x_t,u_t) ≤ 0.Source: §II · pp. 1–2
- The Lagrangian introduces dual variables for dynamics and slack variables for inequality constraints, and the perturbed KKT system uses a positive perturbation vector μ.With μ = 0, the system gives first-order necessary conditions for a local constrained minimizer.Source: §II · p. 2
- Under regularity conditions, solutions of the perturbed KKT system approach an optimal solution as the perturbation decays.This provides the optimality framework for the interior-point approach.Source: §II · p. 2
III. PRIMAL-DUAL INTERIOR-POINT DIFFERENTIAL DYNAMIC PROGRAMMING
The proposed IPDDP method applies dynamic programming to nested constrained control problems after replacing each constrained minimization with a primal-dual min-max formulation. Its feasible variant repeatedly performs backward and forward passes from strictly feasible estimates.
III. PRIMAL-DUAL INTERIOR-POINT DIFFERENTIAL DYNAMIC PROGRAMMING
- The proposed algorithms can handle time-varying dynamics, constraints, and costs because no time-invariance properties are required.The method is introduced for inequality-constrained finite-horizon optimal control.Source: §III · p. 2
- The method replaces DDP’s nested constrained minimizations with primal-dual min-max counterparts, enabling interior-point treatment within dynamic programming.The resulting formulation preserves the sequence of nested optimization problems central to DDP.Source: §III · p. 2
A. Primal-Dual Feasible-Interior-Point DDP
- Feasible-IPDDP starts from a strictly feasible primal-dual estimate, computes control updates from quadratic local models in a backward pass, and generates a new trajectory in a forward pass.The passes repeat until a convergence criterion is satisfied.Source: A. Primal-Dual Feasible-Interior-Point… · p. 2
1) Backward pass:
The backward pass constructs a local quadratic model of the value function and constrained Q-function, eliminating slack variations through a condensed primal-dual system before recursively propagating coefficients.
1) Backward pass:
- The backward pass constructs a quadratic model of the cost-to-go around the current trajectory to obtain local improvements in the decision variables.The model uses second-order variations of the local Q-function and recursively defines value-function coefficients.Source: 1) Backward pass · pp. 2–3
- The recursion initializes terminal value derivatives from the terminal cost and propagates the remaining value-function coefficients backward across the horizon.The terminal coefficients are determined by p(x_N), while earlier coefficients are defined recursively.Source: 1) Backward pass · pp. 2–3
- Slack variations are eliminated from the parametric system, allowing the resulting coefficients to replace standard DDP coefficients in the recursive backward-pass computations.The condensed system incorporates the perturbation vector μ through r_t = S_t c(x_t,u_t) + μ.Source: 1) Backward pass · p. 3
2) Forward pass:
The feasible IPDDP forward pass preserves strict primal-dual feasibility, and its stationary points are perturbed KKT points that converge locally quadratically.
2) Forward pass:
- A line search with step length γ ∈[0,1] is used to keep the new iterate strictly feasible during the forward pass.Source: 2) Forward pass · p. 3
B. Properties of Feasible-Interior-Point DDP
- Strict primal-dual feasibility requires c(x_t,u_t) ≤0, s_t ≥0, and x_{t+1}=f(x_t,u_t) throughout the horizon.Source: B. Properties of… · p. 3
- Positive-definite and invertible coefficient blocks ensure the backward-pass operators exist and remain continuous under strict primal-dual feasibility.Source: B. Properties of… · p. 3
- Primal-dual feasible solutions of F(w, µ)=0 are perturbed KKT points and can be moved arbitrarily close to a locally optimal solution.Source: B. Properties of… · p. 4
- Once sufficiently close to a solution of F(w, µ)=0, IPDDP iterates converge at a quadratic rate.Source: B. Properties of… · p. 4
C. Primal-Dual Infeasible-Interior-Point DDP
The infeasible extension relaxes the restrictive requirement of a strictly primal-dual feasible initial guess by introducing slack variables and perturbed complementarity.
C. Primal-Dual Infeasible-Interior-Point DDP
- The infeasible extension relaxes the requirement for a strictly primal-dual feasible initial solution guess.Source: C. Primal-Dual… · p. 5
- Slack variables y_t ≥0 convert inequality constraints into equalities, c(x_t,u_t)+y_t=0, while S_t y_t−µ=0 imposes perturbed complementarity.Source: 1) Backward pass · p. 5
1) Backward pass:
The infeasible backward pass eliminates slack-variable increments from the linearized system and solves a reduced parametric system for updated coefficients.
1) Backward pass:
- Eliminating δy from the linearized constraint and complementarity equations produces a reduced system similar to the feasible formulation.Source: 1) Backward pass · p. 5
- Solving the resulting parametric system yields the new backward-pass coefficients.Source: 1) Backward pass · p. 5
2) Forward pass:
The infeasible forward pass updates the trajectory without requiring constraint satisfaction at every iterate, while positivity of the slack variables remains necessary.
2) Forward pass:
- The update functions define a new solution guess and recursively compute the forward trajectory from the fixed initial state.Source: 2) Forward pass · p. 5
- Only positivity of s_t^+ must be ensured; satisfaction of c(x_t,u_t)≤0 is guaranteed only in the convergence limit.Source: 2) Forward pass · p. 5
- An appropriate line-search procedure is still required for practical implementations of the infeasible method.Source: 2) Forward pass · p. 5
D. Properties of Infeasible-Interior-Point DDP
The infeasible variant augments the optimization tuple with slack variables and characterizes dual feasibility through a residual system. Under the stated conditions, its operators are continuous and solutions of the residual system correspond to perturbed KKT points with local convergence guarantees.
D. Properties of Infeasible-Interior-Point DDP
- The infeasible formulation augments w = (x, u, s) with slack variables y and defines dual feasibility using nonnegative slacks and system dynamics.Source: D. Properties of… · p. 5
- For strictly dual-feasible w, the linear operators used by the method are continuous at w.Source: D. Properties of… · p. 5
- Solutions of F(w, µ) = 0 that are dual feasible correspond to perturbed KKT points.Source: D. Properties of… · p. 5
- Theorem 3 establishes a local bound for the update w+ when the current and reference tuples are strictly dual feasible and sufficiently close.Source: D. Properties of… · p. 5
- The proof proceeds by Taylor expansion, residual bounds, and iterative backward propagation across the horizon.Source: D. Properties of… · pp. 5–6
IV. NUMERICAL SIMULATIONS
The simulations compare Interior-Point DDP with Control-Limited DDP and log-barrier DDP using repeated randomized trials and logarithmic optimality error. The section emphasizes iteration counts while noting that wall-clock comparisons are outside scope because per-iteration costs differ.
IV. NUMERICAL SIMULATIONS
- The simulations compare IPDDP implementations with Control-Limited DDP and log-barrier DDP.Source: §IV · p. 6
- Iteration counts are emphasized because CLDDP solves N box-QPs per iteration, whereas IPDDP and log-barrier DDP solve N linear systems; wall-clock comparison is beyond scope.Source: §IV · p. 6
- Logarithmic optimality error E_J is plotted against iteration number for the inverted-pendulum experiment.Source: Figure 1 · p. 6, §IV · p. 6
- Inverted-pendulum control inputs u_t are plotted against the time index t.Source: Figure 2 · p. 6
- Each experiment uses 40 trials with random initial control inputs sampled uniformly from [−0.01, 0.01].Source: §IV · p. 6
A. Inverted pendulum
The inverted-pendulum experiments compare constrained DDP variants and show consistent convergence near 150 iterations for the interior-point and log-barrier methods. The car-parking experiments examine convergence behavior and perturbation-step sensitivity, highlighting the proposed methods’ central-path tracking.
A. Inverted pendulum
- About 150 iterations were required consistently by log-barrier DDP, Feasible-IPDDP, and Infeasible-IPDDP, whereas most CLDDP runs exceeded 200 iterations.The authors attribute CLDDP’s slower convergence to difficulties identifying active and inactive constraints for the bang-bang optimum.Source: A. Inverted pendulum · p. 6
- After roughly 70 iterations, the regularization condition remained satisfied and quadratic convergence began along the inverted-pendulum optimization.The condition is violated early because the relevant matrix is not positive definite; later positive definiteness holds near the central path.Source: A. Inverted pendulum · pp. 6–7, Figure 3 · p. 7, Figure 4 · p. 7
B. Car parking problem
- In the car-parking problem, CLDDP often converged faster, but distinct local optima made its performance less predictable than IPDDP and log-barrier DDP.The interior-point methods follow the central path, producing more predictable behavior.Source: B. Car parking problem · p. 7
- Log-barrier DDP was more sensitive than Feasible-IPDDP to perturbation reduction, taking vanishingly small steps for µ ∈ [0.0006, 0.0010].The comparison evaluates maximum accepted stepsizes across two central-path intervals after reducing the perturbation parameter.Source: B. Car parking problem · p. 7, Figure 6 · p. 7
C. Unicycle motion control
The unicycle experiment evaluates IPDDP against relaxed log-barrier DDP for obstacle-avoiding motion, while the conclusions summarize the algorithms’ convergence behavior and future limitations.
C. Unicycle motion control
- The unicycle task has two distinct locally optimal trajectories and nontrivial feasible-solution initialization around circular obstacles.The trajectories plot r_y against r_x, with obstacle boundaries shown as dotted circles.Source: C. Unicycle motion control · p. 7, Figure 7 · p. 8
- IPDDP outperforms relaxed log-barrier DDP in convergence across the unicycle experiment.The methods decrease perturbation only after sufficiently solving the corresponding perturbed or barrier problem.Source: C. Unicycle motion control · p. 8
V. CONCLUSIONS
- Feasible- and Infeasible-IPDDP converge to locally optimal solutions for nonlinear constrained optimal-control problems, often requiring fewer and less variable iterations than competitors.The feasible variant maintains strictly feasible iterates, whereas the infeasible variant permits an infeasible initial guess and satisfies constraints upon convergence.Source: §V · p. 8
- Establishing global convergence and improving numerical performance through adaptive perturbation or predictor-corrector schemes remain future research directions.The paper also identifies differentiable-manifold generalization as a possible extension.Source: §V · p. 8