# EIQP: Execution-time-certified and Infeasibility-detecting QP Solver

arXiv: https://arxiv.org/abs/2502.07738 · HTML: https://mlsanity.com/paper/2502.07738/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Optimal Output Feedback Learning Control for Discrete-Time Linear Quadratic Regulation](https://mlsanity.com/paper/2503.06226/) (2025)

## Abstract (arXiv)

Solving real-time quadratic programming (QP) is a ubiquitous task in control engineering, such as in model predictive control and control barrier function-based QP. In such real-time scenarios, certifying that the employed QP algorithm can either return a solution within a predefined level of optimality or detect QP infeasibility before the predefined sampling time is a pressing requirement. This article considers convex QP (including linear programming) and adopts its homogeneous formulation to achieve infeasibility detection. Exploiting this homogeneous formulation, this article proposes a novel infeasible interior-point method (IPM) algorithm with the best theoretical O(√n) iteration complexity that feasible IPM algorithms enjoy. The iteration complexity is proved to be textitexact (rather than an upper bound), textitsimple to calculate, and textitdata independent, with the value leftlceilfraclog(fracn+1ε)-log(1-frac0.414213√n+1)rightrceil (where n and ε denote the number of constraints and the predefined optimality level, respectively), making it appealing to certify the execution time of online time-varying convex QPs. The proposed algorithm is simple to implement without requiring a line search procedure (uses the full Newton step), and its C-code implementation (offering MATLAB, Julia, and Python interfaces) and numerical examples are publicly available at https://github.com/liangwu2019/EIQP.