Interior-Point Method

Unlike active-set methods that travel along the boundary of the feasible region, interior-point methods maintain strict feasibility by keeping all iterates inside the constraint set. They approach the optimal solution by following a central path, a trajectory through the interior that balances optimality with centrality, preventing the algorithm from getting stuck on constraint boundaries prematurely. This characteristic makes them highly efficient for problems with many constraints.

Inequality constraints are handled by incorporating a barrier function into the objective. For a constraint g(x) ≤ 0, a logarithmic barrier -μ * log(-g(x)) is added, where μ > 0 is the barrier parameter. This function becomes infinite as g(x) approaches zero from the feasible side, creating a "wall" that keeps the solution interior. The core algorithm solves a sequence of these unconstrained (or equality-constrained) barrier problems while driving μ to zero, converging to the true constrained optimum.

Modern implementations are primal-dual methods. They solve the Karush-Kuhn-Tucker (KKT) conditions for the barrier problem simultaneously for both primal variables (x) and dual variables (Lagrange multipliers, λ). This approach:

• Provides excellent convergence rates (superlinear/quadratic).
• Offers direct estimates of constraint sensitivity via the dual variables.
• Avoids the ill-conditioning associated with pure barrier methods as μ → 0. The search direction is typically computed via a Newton-type iteration on the perturbed KKT system.

For convex optimization problems, particularly Linear Programs (LPs) and Semidefinite Programs (SDPs), certain interior-point methods have proven polynomial-time worst-case complexity. This means the number of iterations required to find an ε-optimal solution is bounded by a polynomial in the problem dimensions and log(1/ε). While practical performance often differs from the worst-case bound, this theoretical guarantee was a breakthrough that distinguished them from the simplex method.

In Linear MPC, the online optimization is a Quadratic Program (QP) with inequality constraints (e.g., input/state limits). Interior-point methods are highly suited for this because:

• The QP is convex.
• The Hessian matrix is constant and positive definite (or semidefinite).
• The structure allows for efficient factorization and solve routines. Warm-starting from the previous MPC solution drastically reduces the number of iterations, making real-time execution feasible. Solvers like OOQP and OSQP (which uses an ADMM-based method) leverage these principles.

Key distinctions from active-set methods, the other major class of constrained optimizers:

• Iterate Feasibility: Interior-point methods stay strictly feasible; active-set methods may be infeasible intermediately.
• Constraint Handling: Interior-point methods treat all constraints simultaneously via the barrier; active-set methods explicitly guess and update the set of active constraints.
• Problem Scale: Interior-point methods often excel with many dense constraints, while active-set methods can be more efficient for problems with few constraints or highly sparse matrices.
• Warm-Start: Active-set methods benefit more from a good warm-start, as the active set may change little between MPC steps.

In legged robot locomotion and autonomous vehicle path planning, the interior-point method solves the Optimal Control Problem (OCP) at the core of Nonlinear MPC (NMPC). It efficiently handles state constraints (like joint limits) and input constraints (like actuator torque limits) to generate smooth, collision-free trajectories. By approaching the optimum from within the feasible region, it ensures intermediate solutions are always valid, which is critical for real-time control loops where warm-starting from the previous solution is essential for meeting sub-millisecond timing deadlines.

For robots making and breaking contact with the environment (e.g., a humanoid footstep planner), the interior-point method excels at solving large Quadratic Programming (QP) problems. These QPs arise from linearizing complex, non-convex contact dynamics into a Second-Order Cone Program (SOCP)—a convex form. The solver handles the complementarity constraints (e.g., foot force must be zero if not in contact) not as rigid switches but through barrier functions, allowing for smooth, numerically stable solutions essential for real-time optimization (RTO) in dynamic environments.

In heterogeneous fleet orchestration for warehouse robots or drone swarms, a Distributed MPC architecture is often used. Here, each agent solves a local optimization problem with coupling constraints (e.g., collision avoidance). Primal-dual interior-point methods are well-suited for this structure. They can efficiently solve the large, sparse Karush–Kuhn–Tucker (KKT) systems that arise, enabling iterative coordination. This allows scalable computation for dozens of agents where a centralized solver would be intractable, ensuring constraint satisfaction across the entire system.

To ensure the MPC optimization problem remains feasible in the face of unexpected disturbances, soft constraints are implemented using slack variables. The interior-point method naturally incorporates these slack variables into its barrier function. This allows the solver to gently penalize minor constraint violations (e.g., a robot temporarily exceeding a velocity limit to avoid an obstacle) rather than failing entirely. This technique is fundamental to Robust MPC and Stochastic MPC formulations, increasing the resilience of autonomous systems operating in uncertain environments.

For Nonlinear MPC (NMPC) problems, a common approach is Sequential Quadratic Programming (SQP). At each SQP iteration, a convex QP subproblem must be solved. Interior-point QP solvers (like those in OSQP or ECOS) are the industry standard for this step due to their reliability and polynomial-time convergence. Their predictability is crucial for Hardware-in-the-Loop (HIL) testing, where the worst-case execution time of the solver must be bounded to guarantee the stability of the embedded control system.

During sim-to-real transfer learning, robots are trained in high-fidelity physics-based robotic simulations. The interior-point method is often the solver used within the simulation's NMPC controller. Its numerical stability and ability to handle the complex, constrained dynamics of simulated robots (with friction, contacts, and noise) make it ideal for generating the vast datasets of optimal trajectories needed to train Reinforcement Learning or Imitation Learning policies. This bridges the gap between differentiable optimization and learning-based control.

A Quadratic Programming (QP) solver is a numerical optimization algorithm used to solve convex optimization problems where the objective function is quadratic and the constraints are linear. In Linear MPC, the online optimization at each time step is typically a QP. Interior-point methods are one of the primary algorithm families for solving these problems, competing with active-set methods. Their efficiency on large, sparse problems makes them well-suited for MPC applications.

• Core Problem: Minimize a quadratic cost (e.g., tracking error + control effort).
• Key Differentiator: Interior-point methods handle inequality constraints by staying inside the feasible region, unlike active-set methods which travel along its boundary.

Sequential Quadratic Programming (SQP) is a leading iterative algorithm for solving the Nonlinear Programming (NLP) problems that arise in Nonlinear MPC (NMPC). It works by approximating the complex NLP with a series of simpler Quadratic Programming (QP) subproblems at each iteration. Interior-point methods are frequently employed as the core QP solver within each SQP iteration. This combination is powerful: SQP handles the nonlinearities through sequential linearization, while the interior-point QP solver efficiently manages the inequality constraints of the linearized subproblem.

• Primary Use: Solving NMPC problems online.
• Synergy: SQP provides the framework; interior-point methods solve the subproblems.

An Optimal Control Problem (OCP) is the fundamental mathematical formulation solved by MPC. It is defined by:

• A dynamic model (e.g., differential/difference equations) predicting state evolution.
• A cost function to minimize over a horizon (e.g., tracking error).
• Path constraints on states and inputs (e.g., actuator limits, safety bounds).
• Possible terminal constraints for stability.

The interior-point method is a numerical transcription strategy for solving the OCP. It converts the continuous-time OCP into a large, sparse Nonlinear Program (NLP) by discretizing the dynamics and then solves it by navigating the interior of the constraint set.

Constraint handling is a defining feature of MPC, distinguishing it from unconstrained controllers like PID. Interior-point methods provide a specific, powerful mechanism for this:

• Hard vs. Soft Constraints: Interior-point methods natively enforce hard constraints (must not be violated) by using barrier functions that penalize proximity to constraint boundaries. For soft constraints (allowable violation with penalty), slack variables are introduced, which the method also handles efficiently.
• Mechanism: The method modifies the cost function with a logarithmic barrier term for each inequality constraint. As the algorithm iterates, this barrier parameter is reduced, allowing the solution to approach the optimal point on the constraint boundary from the strictly feasible interior.
• Advantage: This approach is particularly effective for problems with many constraints, as it avoids the combinatorial complexity of identifying the active set.

Primal-dual interior-point methods are the most prevalent variant used in practice. They simultaneously solve for both the primal variables (the original decision variables, like states and inputs) and the dual variables (Lagrange multipliers associated with the constraints).

• Duality Gap: The algorithm tracks the complementarity slackness condition, which measures the optimality gap. It drives a parameter (μ) to zero, forcing the solution to satisfy the Karush-Kuhn-Tucker (KKT) conditions for optimality.
• Newton's Method Core: Each iteration typically involves solving a linear system derived from a Newton step applied to the perturbed KKT conditions. For MPC, this system has a special, sparse structure that can be solved very efficiently.
• Benefit: This approach often exhibits superlinear or quadratic convergence near the solution, leading to fast final iterations.

Convex optimization is the mathematical foundation that makes interior-point methods in MPC both reliable and efficient. A problem is convex if its feasible set is a convex set and its objective function is convex. For MPC:

• Linear MPC with quadratic cost yields a Convex Quadratic Program (QP).
• Convexity Guarantee: Ensures that any locally optimal solution found is also globally optimal. This is critical for control performance and stability.
• Interior-Point Efficiency: These methods exploit convexity to guarantee polynomial-time convergence. The self-concordant theory of barrier functions for convex sets is what enables the sophisticated path-following algorithms with strong theoretical guarantees.
• Non-Convex Challenge: In Nonlinear MPC, the problem is often non-convex, losing these guarantees. Interior-point methods can still be applied but may converge to local minima.