Sequential Quadratic Programming (SQP)

At its core, SQP solves a difficult Nonlinear Programming (NLP) problem by iteratively approximating it with simpler, convex Quadratic Programming (QP) subproblems. At each iteration k, it constructs a local quadratic model of the Lagrangian function (which combines the objective and constraints) around the current iterate (x_k, λ_k). This involves calculating:

• The gradient of the Lagrangian.
• An approximation of the Hessian of the Lagrangian (often using BFGS or SR1 quasi-Newton updates). The resulting QP subproblem has a quadratic objective and linearized constraints, which can be solved efficiently with dedicated QP solvers.

When properly implemented with exact second-order derivative information (or high-quality quasi-Newton approximations), SQP exhibits a superlinear convergence rate. This means that near the optimal solution, the error decreases faster than linearly (e.g., ||x_{k+1} - x*|| / ||x_k - x*|| → 0). This property is critical for Real-Time Optimization (RTO) in NMPC, as it allows the algorithm to reach a high-accuracy solution in very few iterations, meeting stringent sampling time requirements. The convergence rate is a key advantage over first-order methods like gradient descent.

A major implementation challenge is ensuring global convergence (convergence from any starting point) while maintaining fast local convergence. Two key mechanisms address this:

• Merit Function: A scalar function (like an l1 or augmented Lagrangian penalty function) that balances reduction in the objective with constraint violation. It determines whether a proposed step should be accepted.
• Trust-Region Methods: As an alternative to line searches, these methods restrict the step size to a region where the quadratic model is trusted, dynamically adjusting the region size based on model accuracy. These mechanisms allow the algorithm to take reliable progress steps far from the optimum while preserving the superlinear rate near the solution.

SQP naturally and efficiently handles both equality and inequality constraints. Each QP subproblem solves for a step that respects linearized versions of the original constraints. A crucial part of the QP solution is identifying the active set—the subset of inequality constraints that are binding (equal to their bound) at the solution of the subproblem. The algorithm's ability to accurately predict and adapt this active set from iteration to iteration is central to its efficiency. This makes SQP particularly well-suited for NMPC problems with tight state and input constraints, such as actuator limits or safety boundaries.

This is perhaps SQP's most powerful feature in the context of Receding Horizon Control. At each control time step t, the NMPC problem is re-solved with a shifted horizon and new initial state measurement. The solution from the previous time step t-1 (shifted appropriately) provides an excellent initial guess (or warm start) for the primal variables (x, u) and dual variables (λ) (Lagrange multipliers) of the new problem. Because the optimal solution typically changes smoothly between time steps, SQP often requires only 1-2 iterations to reconverge from this warm start, making real-time execution feasible for many nonlinear systems.

SQP is derived directly from the Karush-Kuhn-Tucker (KKT) conditions, which are the first-order necessary conditions for optimality in constrained NLP. The QP subproblem solved at each SQP iteration is essentially a Newton or quasi-Newton step applied to the system of nonlinear equations formed by the KKT conditions. This direct root-finding approach on the optimality conditions is why SQP is considered a second-order method and achieves its fast convergence. It simultaneously solves for the optimal primal variables and the corresponding Lagrange multipliers, providing sensitivity information about how constraints affect the optimum.

SQP is the dominant iterative method for solving the Nonlinear Programming (NLP) problem that must be solved online at each control step in Nonlinear MPC (NMPC). It enables NMPC by:

• Linearizing the nonlinear system dynamics and constraints around the current state estimate.
• Approximating the cost function as a quadratic form.
• Solving the resulting Quadratic Programming (QP) subproblem to find a search direction.
• Iterating this process until convergence to a (local) optimum for the control sequence. This allows real-time control of systems with significant nonlinearities, such as chemical reactors or agile autonomous vehicles, where linear approximations fail.

In robotics and aerospace, SQP enables real-time trajectory optimization for dynamic systems. Applications include:

• Autonomous Vehicle Path Planning: Computing smooth, collision-free trajectories that respect vehicle dynamics and actuator limits.
• Robotic Arm Motion Planning: Optimizing joint trajectories for manipulation tasks while minimizing jerk or energy.
• Rocket Landing Guidance: Solving fuel-optimal descent profiles under complex nonlinear dynamics and state constraints. SQP's ability to handle nonlinear equality and inequality constraints directly is crucial here, as it allows the optimizer to respect physical limits (e.g., torque saturation, obstacle boundaries) throughout the planned motion.

SQP is not a standalone discretization method but is frequently used as the solver within broader direct optimal control frameworks. It pairs with:

• Direct Multiple Shooting: The time horizon is split into segments, and SQP solves the large, sparse NLP that results from parameterizing controls and states on each segment and enforcing continuity constraints.
• Direct Collocation: Both states and controls are discretized, and SQP solves the NLP where the system dynamics are enforced via algebraic constraints at collocation points. These combinations are implemented in tools like ACADO Toolkit and CasADi, where SQP (often with Interior-Point methods) provides the numerical engine to solve the discretized problem efficiently.

A key advantage of SQP within MPC is its native and rigorous handling of hard constraints. This is vital for:

• Process Safety: In chemical plant MPC, SQP ensures temperatures and pressures never exceed safe operating limits.
• Actuator Saturation: Prevents commands that would overdrive motors, valves, or thrusters.
• Obstacle Avoidance: Encodes collision constraints as nonlinear inequalities for drones or mobile robots. By solving a constrained optimization problem at each step, SQP-based NMPC actively anticipates future constraint violations and adjusts the control plan proactively, unlike traditional control which reacts after a violation occurs.

The sequential nature of SQP is exploited via warm-starting to meet the strict latency requirements of real-time control (often < 100ms).

• Mechanism: The optimal solution (and the associated QP matrices) from the previous MPC time step is used to initialize the SQP solver for the current step.
• Impact: This dramatically reduces the number of SQP iterations needed for convergence, as the system state and optimal solution typically change only incrementally between sampling instants.
• Result: Enables the use of NMPC with SQP on embedded hardware for fast dynamic systems, such as autonomous quadrotors or automotive active suspension control.

Beyond setpoint tracking, SQP enables Economic MPC (EMPC) and complex multi-objective optimization in industrial settings.

• Economic Objective Minimization: Directly optimizing for profit, energy consumption, or raw material cost using nonlinear cost functions.
• Batch Process Optimization: Optimizing time-varying trajectories for temperature or feed rates in pharmaceutical or specialty chemical production.
• Integration with Real-Time Optimization (RTO): Solving steady-state economic optimization problems that provide targets to a lower-level MPC layer. SQP handles the nonlinear process models and economic gradients involved in these non-quadratic, non-convex problems, bridging dynamic control with plant-wide economic performance.

Nonlinear Programming (NLP) is the mathematical framework for optimizing a scalar objective function subject to constraints, where the function or constraints are nonlinear. This is the fundamental problem class solved by SQP.

• Core Problem: Minimize f(x) subject to g(x) = 0 and h(x) ≤ 0, where f, g, and h are smooth, potentially nonlinear functions.
• Role in NMPC: The online optimization in Nonlinear Model Predictive Control is formulated as an NLP, where f is the cost over the horizon, g represents the system dynamics, and h encodes state/input constraints.
• Challenges: NLPs are non-convex, making them significantly harder to solve than Linear or Quadratic Programs, requiring iterative algorithms like SQP.

Quadratic Programming (QP) is an optimization problem with a quadratic objective function and linear constraints. It is a convex problem with efficient, reliable solvers.

• Standard Form: Minimize (1/2)xᵀHx + cᵀx subject to A_eq x = b_eq and A_ineq x ≤ b_ineq.
• SQP's Core Mechanism: At each iteration, SQP approximates the original NLP by constructing a local QP subproblem. This QP uses:
  • A local quadratic model of the Lagrangian (for the objective H matrix).
  • Linearized versions of the constraints (A matrices).
• Solving the Subproblem: The solution to this QP provides a search direction (e.g., a step toward the optimum). The reliability of QP solvers is key to SQP's robustness.

The Karush-Kuhn-Tucker (KKT) conditions are first-order necessary conditions for a solution to be optimal in a constrained nonlinear optimization problem. They generalize the method of Lagrange multipliers to handle inequality constraints.

• Components: For an optimal point x*, there must exist Lagrange multipliers (λ, μ) such that:
  1. Stationarity: ∇f(x*) + ∇g(x*)ᵀλ + ∇h(x*)ᵀμ = 0
  2. Primal Feasibility: g(x*) = 0, h(x*) ≤ 0
  3. Dual Feasibility: μ ≥ 0
  4. Complementary Slackness: μᵢ hᵢ(x*) = 0 for all i
• SQP's Target: Each QP subproblem in SQP is built to model the KKT conditions of the original NLP. Solving the QP finds a step that drives the system toward satisfying these conditions.

An active-set method is a common approach for solving Quadratic Programming (QP) subproblems within SQP. It iteratively identifies which inequality constraints are 'active' (i.e., exactly equal to their bound) at the solution.

• Mechanism: The method maintains a working set of constraints treated as equalities. It solves an equality-constrained QP, then updates the working set based on the computed step and Lagrange multiplier signs.
• Efficiency: It is highly efficient for QPs where the number of active constraints is small compared to the total number of variables and constraints.
• Warm-Starting: Active-set methods benefit greatly from warm-starting—using the active set from the previous SQP iteration as an initial guess—which dramatically speeds up convergence in real-time MPC applications.

A merit function is a scalar function used to assess the quality of a candidate step in SQP, balancing reduction in the objective with violation of the constraints. A line search procedure then uses this function to ensure global convergence.

• Purpose: The pure Newton step from the QP subproblem may not lead to improvement in the actual NLP. The merit function (e.g., L1 or augmented Lagrangian) quantifies progress.
• Process: After computing a search direction pₖ from the QP, SQP performs a line search: xₖ₊₁ = xₖ + α pₖ. The step size α ∈ (0,1] is chosen to produce a 'sufficient decrease' in the merit function.
• Result: This safeguards the algorithm, ensuring it converges to a local optimum from remote starting points, which is critical for the reliability of Nonlinear MPC.

An Interior-Point Method (IPM) is an alternative to active-set methods for solving the QP subproblems in SQP. Instead of tracking the active set, IPMs approach the solution from the interior of the feasible region by using barrier functions.

• Mechanism: Inequality constraints are incorporated into the objective via a logarithmic barrier term, transforming the QP into a sequence of unconstrained or equality-constrained problems.
• Advantages for SQP:
  • Predictable Runtime: Often more consistent iteration counts than active-set methods, beneficial for real-time MPC.
  • Handles Dense Problems Well: Efficient for problems where the Hessian H is not sparse.
• Usage: Many modern, high-performance QP solvers used in production MPC systems (e.g., FORCES Pro, HPIPM) are based on IPM variants.