Customized Interior-Point Methods Solver for Embedded Real-Time Convex Optimization

This paper presents a customized, dependency-free C-based second-order cone programming solver for embedded real-time guidance and control applications that utilizes a predictor-corrector primal-dual interior-point method with homogeneous embedding to efficiently handle quadratic objectives without sparsity loss, supported by an automated code generation tool that outperforms existing solvers on typical problem scales.

The Gist

Imagine you are the pilot of a spaceship or a drone, and you need to make split-second decisions to stay safe and reach your destination. You have to calculate the perfect path, avoid obstacles, and manage your fuel, all while your computer has very limited brainpower and memory. This is the world of embedded real-time optimization.

For decades, solving these complex math puzzles on small, weak computers has been like trying to run a marathon while carrying a heavy backpack. The tools available were either too slow, too memory-hungry, or they would crash if the problem was slightly "broken" (infeasible).

This paper introduces a new, custom-built tool designed specifically to solve these problems efficiently on small computers. Here is a simple breakdown of what they did:

1. The Problem: The "One-Size-Fits-All" Backpack

Think of existing math solvers (like ECOS or MOSEK) as universal backpacks. They are designed to carry any kind of math problem.

• The Issue: If you are a drone, you don't need a backpack that can carry a piano and a feather. You just need a backpack for feathers. But because the universal backpack is built for everything, it's heavy, slow, and takes up too much space.
• The Quadratic Cost: Many real-world problems (like landing a rocket) involve "curved" math (quadratic costs). Old universal backpacks couldn't handle these curves directly. They had to force the curve into a straight line first, which was like trying to fit a round peg into a square hole. This made the problem bigger, slower, and more likely to break.

2. The Solution: A Custom-Tailored Suit

The authors built a custom-tailored suit (a customized solver) instead of a universal backpack.

• How it works: Before the drone even takes off, the engineers analyze the specific type of math problem the drone will face. They then write a computer program (in the C language) that is only for that specific problem.
• The Benefit: Because the program knows exactly what the problem looks like, it doesn't need to carry extra tools. It fits perfectly in the drone's tiny memory (RAM) and runs incredibly fast. It's like having a key cut specifically for your lock, rather than trying to pick the lock with a master key set.

3. The "Magic Trick": Seeing the Impossible

One of the biggest headaches in guidance systems is when a mission is impossible (e.g., "Land on Mars in 5 seconds" when physics says it needs 10).

• Old Solvers: If you asked an old solver to solve an impossible mission, it might spin its wheels forever, trying to find an answer that doesn't exist, until the drone crashes.
• The New Solver: This new tool uses a technique called Homogeneous Embedding. Imagine a detective who, instead of just looking for the suspect, also checks if the crime scene is even real. If the mission is impossible, the solver instantly raises a red flag saying, "This is impossible!" and stops. It does this without getting stuck or wasting time.

4. The "Factory": The Code Generator

Writing a custom suit for every single drone is hard work. So, the authors built a factory machine (a code generation tool).

• How it works: You feed the factory the "blueprints" of your problem (the math equations). The factory automatically builds the custom solver code for you.
• The Output: It spits out a tiny, super-fast C program that needs no extra libraries (it's self-contained). It also gives you a "user manual" (parsing information) so you know exactly how to feed data into it.

5. The Results: Faster and Smarter

The team tested their new tool against the "universal backpacks" (ECOS, MOSEK, SCS) on two real-world scenarios:

1. Mars Landing: Calculating the path to land a rocket.
2. Quadcopter Control: Keeping a drone steady in the wind.

The Outcome:

• Speed: The custom solver was significantly faster, especially on the small-to-medium problems typical of drones and rockets.
• Reliability: It correctly identified impossible missions instantly, whereas others struggled.
• Efficiency: It ran perfectly on a small, embedded computer (like the ones inside a drone), using very little memory and no dynamic memory allocation (no "malloc" which can cause crashes in embedded systems).

The Bottom Line

This paper is about moving away from "one-size-fits-all" math tools and toward specialized, custom-built tools for critical, real-time missions. By tailoring the math solver to the specific job and giving it the ability to instantly spot impossible tasks, the authors have made it much safer and faster to run complex optimization on small, embedded computers like those found in rockets, drones, and self-driving cars.

Technical Summary

Here is a detailed technical summary of the paper "Customized Interior-Point Methods Solver for Embedded Real-Time Convex Optimization."

1. Problem Statement

Modern Guidance and Control (G&C) applications, such as Model Predictive Control (MPC) and onboard trajectory optimization, rely heavily on solving constrained convex optimization problems in real-time. These problems are often formulated as Second-Order Cone Programs (SOCPs) with quadratic cost functions (e.g., minimizing fuel consumption or tracking error).

However, deploying these solvers on embedded systems (e.g., spacecraft or drones) faces significant challenges:

• Resource Constraints: Limited computational power and memory (RAM) prevent the use of heavy, general-purpose solvers.
• Real-Time Requirements: Strict execution time limits require highly efficient algorithms.
• Infeasibility Detection: G&C problems often become infeasible due to changing dynamics or constraints (e.g., insufficient fuel or time). Standard solvers may fail to converge or provide a certificate of infeasibility, leading to system failure.
• Quadratic Objectives: Many existing efficient solvers (like CVXGEN or standard homogeneous self-dual embeddings) are limited to linear objectives. Handling quadratic objectives often requires reformulation (introducing slack variables and extra cones), which increases problem size, destroys sparsity, and degrades performance.

2. Methodology

The authors propose a customized, second-order cone programming (SOCP) solver based on a Primal-Dual Interior-Point Method (PDIPM). The core technical innovations include:

A. Algorithmic Core: Homogeneous Embedding for Quadratic Costs

• Direct Handling of Quadratic Costs: Unlike conventional homogeneous self-dual embeddings that require reformulating quadratic objectives into linear ones (adding variables and constraints), this solver adopts a Homogeneous Embedding for Monotone Complementarity Problems (HMCP). This allows the solver to handle quadratic cost functions ($x^T Q x$) directly without reformulation, preserving the original problem's sparsity and size.
• Infeasibility Detection: The HMCP framework ensures that the algorithm converges to a solution regardless of the original problem's feasibility.
  • If $\tau^* > 0$, the solution is optimal.
  • If $\kappa^* > 0$, the problem is infeasible (providing a certificate of primal or dual infeasibility).
• Nesterov-Todd (NT) Scaling: The solver utilizes NT-scaling to maintain numerical stability and efficiency when dealing with symmetric cones (Non-negative and Second-Order Cones).
• Predictor-Corrector Strategy: A Mehrotra-type predictor-corrector approach is used to determine search directions, balancing the reduction of the duality gap with maintaining proximity to the central path.

B. Solver Customization and Code Generation

To optimize for embedded hardware, the solver is not a generic library but a custom-generated C code:

• Offline Analysis: A code generation tool (implemented in MATLAB) analyzes the sparsity pattern of the specific problem family (fixed structure, varying data).
• Static Allocation: All memory is statically allocated. This eliminates dynamic memory allocation (malloc), preventing memory fragmentation and leaks, which is critical for safety-critical embedded systems.
• Sparsity Exploitation: The tool performs Approximate Minimum Degree (AMD) ordering and symbolic factorization offline. The resulting permutation and sparsity patterns are hardcoded into the solver.
• Loop-Based Linear Algebra: Instead of hard-coding matrix operations for specific sizes (which leads to code bloat), the solver uses loop-based structures for linear algebra routines. This keeps the code size nearly constant regardless of problem dimension while exploiting sparsity.
• Dependencies: The generated code relies only on the standard C library (math.h), making it highly portable.

3. Key Contributions

1. Algorithmic Formulation: Development of a PDIPM capable of solving SOCPs with quadratic objectives directly, avoiding the performance penalties associated with problem reformulation.
2. Robust Infeasibility Detection: Integration of homogeneous embedding to guarantee convergence and provide certificates of infeasibility within a finite number of iterations, crucial for G&C safety.
3. Customization Framework: A dedicated code generation tool that automates the creation of C solvers. It supports:
   • Complete static memory allocation.
   • Exploitation of sparsity patterns via pre-computed permutations.
   • Parsing information generation to facilitate easy data updates for varying problem instances.
4. Embedded Optimization: Implementation of the solver in C with no external dependencies, specifically tailored for resource-constrained environments.

4. Results

The authors conducted extensive benchmarking and numerical experiments:

A. Benchmark Tests (Desktop Environment)

• Datasets: Maros-Mészáros QP set, Portfolio Optimization, and LASSO problems.
• Comparators: ECOS (Open-source IPM), MOSEK (Commercial IPM), and SCS (ADMM-based).
• Findings:
  • The developed solver outperformed ECOS and MOSEK in both speed and success rate, particularly for problems with quadratic costs. ECOS and MOSEK suffered from numerical failures or reformulation overhead.
  • For small-to-medium scale problems (typical of G&C), the custom solver was significantly faster than SCS (ADMM), which suffers from slow tail convergence.
  • For very large-scale problems, SCS showed better performance due to lower per-iteration costs, but the custom solver still outperformed other IPM-based solvers.

B. Embedded System Experiments

• Hardware: AMD Zynq-7000 SoC (ARM Cortex-A9, 650MHz, 512MB RAM).
• Applications:
  1. Mars Landing Trajectory Optimization: A convexified SOCP problem.
     • The solver achieved convergence in 7–8 iterations even for infeasible cases, successfully detecting infeasibility.
     • It demonstrated faster solve times than ECOS and SCS, especially as the number of nodes increased.
  2. Quadcopter MPC: A QP problem for real-time control.
     • The solver produced solutions with residuals consistent with the tolerance ($10^{-6}$) and matched the accuracy of ECOS.
     • It achieved the fastest computation times, validating its suitability for real-time feedback loops.

5. Significance

This paper addresses a critical gap in the deployment of advanced optimization algorithms in aerospace and robotics. By combining a robust mathematical formulation (handling quadratic costs and infeasibility) with system-level engineering (static allocation, code generation, and C implementation), the authors provide a practical solution for onboard real-time optimization.

The work demonstrates that customized solvers can significantly outperform general-purpose libraries in embedded environments, enabling more complex and reliable G&C strategies (like MPC and trajectory planning) on hardware with severe resource limitations. The ability to detect infeasibility quickly is particularly valuable for establishing contingency strategies in autonomous systems.