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

Code

• github.com/liangwu2019/eiqp
  OfficialIn papernone★ 15

Abstract

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 exact (rather than an upper bound), simple to calculate, and data independent, with the value (n+1)-(1-0.414213n+1) (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.

Tasks

Reproductions