EIQP: Execution-time-certified and Infeasibility-detecting QP Solver
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916613475794944 |
|---|---|
| author | Wu, Liang Xiao, Wei Braatz, Richard D. |
| author_facet | Wu, Liang Xiao, Wei Braatz, Richard D. |
| contents | 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(\sqrt{n})$ iteration complexity that feasible IPM algorithms enjoy. The iteration complexity is proved to be \textit{exact} (rather than an upper bound), \textit{simple to calculate}, and \textit{data independent}, with the value $\left\lceil\frac{\log(\frac{n+1}ε)}{-\log(1-\frac{0.414213}{\sqrt{n+1}})}\right\rceil$ (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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07738 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | EIQP: Execution-time-certified and Infeasibility-detecting QP Solver Wu, Liang Xiao, Wei Braatz, Richard D. Systems and Control Optimization and Control 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(\sqrt{n})$ iteration complexity that feasible IPM algorithms enjoy. The iteration complexity is proved to be \textit{exact} (rather than an upper bound), \textit{simple to calculate}, and \textit{data independent}, with the value $\left\lceil\frac{\log(\frac{n+1}ε)}{-\log(1-\frac{0.414213}{\sqrt{n+1}})}\right\rceil$ (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. |
| title | EIQP: Execution-time-certified and Infeasibility-detecting QP Solver |
| topic | Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2502.07738 |