标题： EIQP：执行时间认证且不可行性检测的二次规划求解器 显示英文标题

标题： EIQP: Execution-time-certified and Infeasibility-detecting QP Solver

摘要： 求解实时二次规划（QP）是控制工程中的常见任务，例如在模型预测控制和基于控制障碍函数的QP中。 在这样的实时场景中，认证所采用的QP算法能够在预定义的采样时间之前返回一个在预定义最优性水平内的解或检测QP不可行性是一个迫切的需求。 本文考虑凸QP（包括线性规划），并采用其同源形式以实现不可行性检测。 利用这种同源形式，本文提出了一种新的不可行内点法（IPM）算法，其迭代复杂度为最优理论下的$O(\sqrt{n})$。 迭代复杂度被证明为\textit{精确的}（而不是上界），\textit{易于计算}，和\textit{数据独立}，其中值$\left\lceil\frac{\log(\frac{n+1}{\epsilon})}{-\log(1-\frac{0.414213}{\sqrt{n+1}})}\right\rceil$（其中$n$和$\epsilon$分别表示约束的数量和预定义的最优性水平），使其适用于认证在线时变凸QP的执行时间。 所提出的算法易于实现，无需进行线搜索过程（使用完整的牛顿步长），其C语言实现（提供MATLAB、Julia和Python接口）和数值示例可在https://github.com/liangwu2019/EIQP公开获取。 显示英文摘要

摘要： 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}{\epsilon})}{-\log(1-\frac{0.414213}{\sqrt{n+1}})}\right\rceil$ (where $n$ and $\epsilon$ 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.