PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple and Efficient Algorithm for Nonlinear Model Predictive Control

Lorenzo Stella, Andreas Themelis, Pantelis Sopasakis, Panagiotis Patrinos

arXiv:1709.06487v1math.OC

TL;DR

NMPC optimization can be slow when forward-backward methods face ill-conditioned problems. PANOC combines forward-backward steps with an FBE line search and quasi-Newton directions. Under stated assumptions, it achieves superlinear convergence, and the paper reports favorable performance against state-of-the-art NLP solvers in a benchmark example.

Abstract

from arXiv · show

We present PANOC, a new algorithm for solving optimal control problems arising in nonlinear model predictive control (NMPC). A usual approach to this type of problems is sequential quadratic programming (SQP), which requires the solution of a quadratic program at every iteration and, consequently, inner iterative procedures. As a result, when the problem is ill-conditioned or the prediction horizon is large, each outer iteration becomes computationally very expensive. We propose a line-search algorithm that combines forward-backward iterations (FB) and Newton-type steps over the recently introduced forward-backward envelope (FBE), a continuous, real-valued, exact merit function for the original problem. The curvature information of Newton-type methods enables asymptotic superlinear rates under mild assumptions at the limit point, and the proposed algorithm is based on very simple operations: access to first-order information of the cost and dynamics and low-cost direct linear algebra. No inner iterative procedure nor Hessian evaluation is required, making our approach computationally simpler than SQP methods. The low-memory requirements and simple implementation make our method particularly suited for embedded NMPC applications.

I. INTRODUCTION

NMPC addresses nonlinear systems through constrained nonlinear programs, but conventional first-order splitting can converge slowly on ill-conditioned problems. PANOC combines forward-backward steps with an FBE line search and quasi-Newton directions, retaining simple operations without Hessian evaluation.

I. INTRODUCTION

  • Nonlinear MPC solves a general nonlinear program at each sampling step, often representing a discrete-time approximation of a continuous-time optimal control problem.The framework allows nonlinear dynamics and nonsmooth, possibly nonconvex input penalties.Source: §I · p. 1, A. Problems framework and motivation · p. 1
  • Single-shooting formulations eliminate state variables, while multiple-shooting formulations retain them as problem variables.Both formulations are used in optimal control.Source: §I · p. 1

A. Problems framework and motivation

  • Single-shooting reduces the control problem to smooth, possibly nonconvex cost plus a nonsmooth penalty, but forward-backward splitting can converge slowly when conditioning is poor.The passage notes that nonlinear dynamics and long horizons commonly contribute to ill-conditioning.Source: A. Problems framework and motivation · p. 1

B. Contributions and related works

  • PANOC uses an FBE-based line search to solve the fixed-point equations associated with forward-backward splitting, with quasi-Newton directions yielding superlinear convergence under stated conditions.The method builds on the same basic operations as forward-backward splitting.Source: B. Contributions and related works · pp. 1–2
  • The algorithm needs gradients and proximal mappings rather than second-order cost information; limited-memory L-BFGS directions can make it matrix-free for embedded use.Automatic differentiation can compute gradients, while the proximal mapping is often available in closed form.Source: B. Contributions and related works · p. 2

II. PROBLEM FORMULATION

The formulation expresses finite-horizon control as optimization over inputs, with states propagated by the dynamics. Forward-backward splitting applies to the resulting smooth cost plus a simple nonsmooth penalty.

II. PROBLEM FORMULATION

  • The finite-horizon model includes stage costs and input penalties, a terminal cost, an initial-state condition, and nonlinear state-transition dynamics.The dynamics and costs are smooth, while input penalties may be nonsmooth, nonconvex, or encode constraints.Source: §II · p. 2
  • Propagating states from the initial condition makes the cost a function of inputs alone, yielding a smooth objective plus a possibly nonsmooth penalty.This is the single-shooting formulation targeted by the paper.Source: §II · p. 2
  • Forward-backward splitting applies a gradient step to the smooth cost followed by the proximal mapping of the penalty, which is assumed efficiently computable.When the penalty is an indicator of a set, the proximal mapping is projection onto that set.Source: §II · p. 2
  • The gradient of the reduced cost can be computed by backward automatic differentiation, while the standard proximal-gradient approach may be inefficient for ill-conditioned problems.Some alternative methods become complex or inapplicable for general nonsmooth penalties.Source: §II · p. 2
  • The proposed algorithm seeks faster convergence by exploiting curvature while requiring the same computational oracle as forward-backward splitting.The oracle consists of operations such as evaluating gradients and proximal mappings.Source: §II · p. 2

A. Handling state constraints

State constraints can be incorporated through penalties and a smooth reformulation using the Moreau envelope. This preserves the problem form needed for efficient gradient computation.

A. Handling state constraints

  • The problem with state constraints is expressed as the smooth cost plus input penalty and a penalty term composed with the state-constraint mapping.The mappings encode constraints on states and, where applicable, inputs.Source: A. Handling state constraints · p. 2
  • State constraints may be represented by smooth penalties, including a squared-distance penalty, to reduce the risk of infeasible optimal control problems under disturbances or plant-model mismatch.The formulation also accommodates hard state constraints through the specified constraint functions and penalties.Source: A. Handling state constraints · pp. 2–3
  • Replacing the constraint penalty with its Moreau envelope smooths the stage costs when the underlying penalty is proper, closed, and convex.The smoothed composition remains differentiable because the constraint mapping is smooth.Source: A. Handling state constraints · p. 3
  • A backward-AD procedure computes the gradient for the soft-constrained formulation, and the penalty parameter can vary by stage or across separable constraints.The scalar parameter is used for simplicity; the stated adaptation permits vector parameters when penalties are separable.Source: A. Handling state constraints · p. 3

III. FORWARD-BACKWARD NEWTON TYPE ALGORITHM

Forward-backward iterations have convergence guarantees under stated assumptions, but their tail convergence can be slow for ill-conditioned problems. Newton-type acceleration can improve local rates, while complicating proximal steps is a concern for variable-metric alternatives.

III. FORWARD-BACKWARD NEWTON TYPE ALGORITHM

  • For nonconvex smooth costs with Lipschitz gradients and lower-bounded penalties, accumulation points of forward-backward iterations are critical under the stated stepsize condition.If the objective also has the Kurdyka–Łojasiewicz property, bounded iterates converge globally to a unique critical point.Source: §III · p. 3
  • Forward-backward splitting has at best Q-linear tail convergence, often with a factor near one on ill-conditioned problems.Variable metrics can improve convergence, but may make proximal steps prohibitively complex and require inner procedures.Source: §III · p. 3

A. Newton-type methods on generalized equations

The section motivates solving a generalized equation through its fixed-point residual, which behaves regularly near critical points. Newton-type and quasi-Newton methods use curvature information to obtain fast local convergence.

B. Forward-backward envelope

The forward-backward envelope provides an exact continuous penalty for globalizing iterations, while preserving the original problem's minimizers. Under stated differentiability conditions, its local curvature also relates to the original objective's strong local minima.

  • The forward-backward envelope is an exact, continuous, real-valued penalty for the original problem and provides a globalization strategy for iterations that may diverge without one.Without globalization, convergence of these iterations is guaranteed only when the initial point is sufficiently close to a solution.Source: B. Forward-backward envelope · p. 3
  • The envelope is strictly continuous and preserves both the infimum and the set of minimizers of the original objective.Source: B. Forward-backward envelope · p. 4
  • At a selected point ū ∈ Tγ(u), the envelope expression combines ℓ(u), its linearization at ū, g(ū), and a quadratic distance penalty.Source: B. Forward-backward envelope · p. 4
  • When ℓ is twice differentiable at a critical point and proxγg is differentiable at the corresponding forward step, the envelope Hessian factors as Qγ(u⋆)J_Rγ(u⋆).For γ < 1/Lℓ, Qγ is positive definite wherever it exists; a sufficient condition on proxγg involves prox-regularity and twice epi-differentiability.Source: B. Forward-backward envelope · p. 4
  • Under the theorem's differentiability and step-size assumptions, the original objective and its envelope have the same strong local minima; the envelope Hessian is positive definite and the residual Jacobian invertible there.Source: B. Forward-backward envelope · p. 4

C. A superlinearly convergent algorithm based on FBS steps

PANOC combines forward-backward steps with quasi-Newton directions, using the forward-backward envelope for line search. Under stated local assumptions, it achieves superlinear convergence while retaining global subsequential convergence.

C. A superlinearly convergent algorithm based on FBS steps

  • PANOC averages the nominal forward-backward update with a fast candidate direction, using line search to ensure sufficient envelope decrease and allowing fast directions to take over near a solution.Near a solution, iterations reduce to the fast-direction update.Source: C. A superlinearly convergent… · p. 4
  • The residuals converge to zero square-summably, and all cluster points satisfy the necessary condition for local minimality.The iterates and forward-backward points have the same cluster points.Source: C. A superlinearly convergent… · p. 4
  • PANOC can estimate the gradient Lipschitz constant during line search; after finitely many updates, the stepsize parameters remain constant.The stated approach halves γ and σ and doubles L when the test fails.Source: C. A superlinearly convergent… · p. 4
  • With Dennis-Moré directions and strict differentiability at a strong local minimum, PANOC eventually accepts unit steps and converges at a superlinear rate.Eventually each iteration requires exactly one forward-backward step.Source: C. A superlinearly convergent… · p. 5
  • The local assumptions can hold without smoothness of g when it is prox-regular and has a generalized quadratic epigraphical Hessian at the limit point.Partly smooth functions are one class for which the required properties hold, subject to the stated qualification.Source: C. A superlinearly convergent… · p. 5
  • L-BFGS directions retain limited memory by storing a small number of iterate and residual-difference pairs instead of the matrices Hk.The direction is recovered using scalar products.Source: C. A superlinearly convergent… · p. 5

IV. NUMERICAL SIMULATIONS

The simulations use a chain of masses connected by springs, controlled through the velocity of a handle at one end. Its states include the positions of all masses and the handle, together with the velocities of the masses.

IV. NUMERICAL SIMULATIONS

  • The test system is a chain of M masses connected by springs, with one end fixed at the origin and a controllable handle at the other.Each mass has mass m; the springs have constant D and rest length L.Source: §IV · p. 5
  • The control input u(t) is the three-dimensional velocity of the handle, while the state collects mass and handle positions and mass velocities.The state has nx = 3(2M + 1) variables and the input has nu = 3.Source: §IV · pp. 5–6
  • The continuous-time dynamics comprise mass velocities, the handle input, and the accelerations of the masses under the spring system and gravity.Gravity is specified as a = (0, 0, −9.81).Source: §IV · pp. 5–6

A. Simulation scenario

The scenario perturbs a computed equilibrium and seeks to return the chain to its reference equilibrium. The finite-horizon problem is discretized with piecewise-constant controls, and state and input feasibility are represented by indicator functions.

A. Simulation scenario

  • After computing an equilibrium with the handle at a given pend, the chain is perturbed by applying u = (−1, 1, 1) for one second; the objective is to return to the reference equilibrium.Source: A. Simulation scenario · p. 6
  • The horizon is divided into N intervals of length ts with piecewise-constant inputs, and the integrals and dynamics are discretized to form the finite-dimensional problem.The scenario uses T = 4 seconds, ts = 0.1 seconds, N = 40, and one-step fourth-order Runge-Kutta integration.Source: A. Simulation scenario · p. 6
  • State and input constraints are encoded by feasible-set indicator functions, and the state constraints are softened using component-specific parameters.The simulation sets µ1 = µ2 = µ3 = 102 and µ4 = µ5 = µ6 = 10.Source: A. Simulation scenario · p. 6
  • The model uses M = 5 masses and is implemented with CasADi to evaluate the dynamics, cost, Jacobian, and gradient.The specified parameters include m = 0.03 kg, D = 0.1 N/m, and L = 0.033 m.Source: A. Simulation scenario · p. 6

B. Results

In the closed-loop simulation, PANOC outperforms the other tested solvers and accelerates markedly over FBS, especially early in the simulation. Soft state constraints improve solution time without sacrificing closed-loop performance.

B. Results

  • The comparison includes FBS, FMINCON with SQP, and IPOPT in single- and multiple-shooting formulations, plus IPOPT with hard state constraints.FMINCON was not applied to multiple shooting because it performed considerably worse.Source: B. Results · p. 6
  • PANOC outperforms the tested methods and greatly accelerates over FBS, particularly early in the simulation when the system is far from equilibrium.Fig. 1 reports the solver CPU times; its convergence comparison uses the first problem solved to medium/high accuracy.Source: B. Results · p. 6, Figure 1 · p. 6
  • Soft state constraints considerably improve solution time without sacrificing closed-loop performance.Source: B. Results · p. 6
  • For closed-loop runs, PANOC and FBS stop at residual ∥rk∥∞ ≤ 10^-3, while the other solvers use default options.Source: B. Results · p. 6

V. CONCLUSIONS

The conclusions present PANOC as a simple, structure-exploiting solver for nonlinear constrained optimal control, with superlinear convergence under mild assumptions. They report favorable benchmark performance for L-BFGS directions and identify several research directions.

  • L-BFGS directions performed favorably against state-of-the-art NLP solvers in a benchmark example.Source: §V · p. 6
  • PANOC avoids a quadratic program at every iteration and is superlinearly convergent under mild assumptions.Source: §V · p. 6
  • Future work includes semismooth Newton directions intended to exploit problem structure and enable quadratic convergence.Source: §V · p. 6
  • Other proposed directions are augmented-Lagrangian handling of state constraints, sensitivity-based warm starts for real-time iterations, and code generation for embedded applications.Source: §V · pp. 6–7
Loading 1709.06487v1…