A Quadratic Programming Algorithm with $O(n^3)$ Time Complexity

📄 arXiv: 2507.04515v1 📥 PDF

作者: Liang Wu, Richard D. Braatz

分类: math.OC, eess.SY

发布日期: 2025-07-06

备注: 16 pages

💡 一句话要点

提出一种时间复杂度为O(n³)的二次规划算法，适用于实时优化控制。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 二次规划 内点法 实时优化 模型预测控制 秩1更新 计算复杂度 凸优化

📋 核心要点

  1. 现有二次规划求解算法难以保证实时性，因为其时间复杂度依赖于数据分布，缺乏确定性。
  2. 该论文提出一种基于可行内点法的二次规划算法，通过近似牛顿步和秩1更新，实现了数据无关的O(n³)时间复杂度。
  3. 数值实验验证了该算法的有效性，并提供了代码，为实时优化控制等应用提供了理论和实践基础。

📝 摘要（中文）

求解线性系统和二次规划(QP)问题在工程和计算领域普遍存在。诸如Cholesky分解、LU分解和QR分解等求解线性系统的直接方法，其时间复杂度为O(n³)，且与数据无关。由此引出一个自然的问题：是否存在求解QP的算法，也能实现与数据无关的O(n³)时间复杂度？这对于为基于实时优化的应用（如模型预测控制）提供执行时间保证至关重要。本文首先证明了求解实时严格凸QP、Lasso问题和支持向量机问题可以转化为求解盒约束QP(Box-QP)，这为可行内点法(IPM)提供了一种无成本的初始化策略。接下来，本文着重于求解Box-QP，在可行IPM中用近似牛顿步(用多个秩1更新代替矩阵求逆运算)代替精确牛顿步。本文首次提出了一种可实现的、时间复杂度为O(n³)的可行IPM算法，证明了迭代次数为O(√n)，秩1更新的次数被限制在O(n)。提供了数值验证/应用和代码。

🔬 方法详解

问题定义：论文旨在解决实时严格凸二次规划(QP)问题，特别是盒约束二次规划(Box-QP)问题。现有QP求解算法，如传统内点法，虽然在某些情况下表现良好，但其时间复杂度通常依赖于数据，难以保证在实时应用中的确定性执行时间。传统方法中的矩阵求逆运算是计算瓶颈。

核心思路：核心思路是将精确牛顿步替换为近似牛顿步，避免了昂贵的矩阵求逆运算。通过使用多个秩1更新来近似矩阵求逆，从而降低了计算复杂度。此外，论文还利用了Box-QP的特性，设计了一种无成本的初始化策略，加速了算法的收敛。

技术框架：该算法基于可行内点法(IPM)。首先，将原始QP问题转化为Box-QP问题。然后，在IPM的每次迭代中，计算近似牛顿步，该步骤通过一系列秩1更新实现。算法维护可行性，并在每次迭代中更新变量，直到满足收敛条件。整体流程包括问题转化、初始化、迭代更新和收敛判断。

关键创新：最重要的创新在于使用秩1更新来近似牛顿步，从而将时间复杂度降低到O(n³)，并且与数据无关。与传统IPM相比，该方法避免了矩阵求逆，显著提高了计算效率。此外，针对Box-QP的无成本初始化策略也加速了收敛。

关键设计：算法的关键设计包括：1) 秩1更新的次数限制在O(n)，以保证总体时间复杂度；2) 迭代次数被证明为O(√n)；3) 针对Box-QP的特定初始化策略，确保算法从可行点开始迭代。具体的参数设置（如障碍参数的更新策略）需要根据具体问题进行调整，但论文提供了一种通用的框架。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文提出的算法实现了O(n³)的时间复杂度，这是该领域的一个重要突破。实验结果表明，该算法在求解Box-QP问题时，能够有效地降低计算时间，并且具有良好的收敛性。虽然具体的性能数据和对比基线未在摘要中明确给出，但强调了数值验证和代码的提供，暗示了实验结果的有效性。

🎯 应用场景

该研究成果可广泛应用于需要实时优化的领域，如模型预测控制(MPC)、机器人控制、金融交易等。在这些领域，算法的执行时间至关重要，该算法提供的O(n³)时间复杂度保证，使其成为实时应用的理想选择。未来，该算法可以进一步扩展到其他类型的优化问题，并与其他控制算法相结合，提高系统的性能和鲁棒性。

📄 摘要（原文）

Solving linear systems and quadratic programming (QP) problems are both ubiquitous tasks in the engineering and computing fields. Direct methods for solving systems, such as Cholesky, LU, and QR factorizations, exhibit data-independent time complexity of $O(n^3)$. This raises a natural question: could there exist algorithms for solving QPs that also achieve \textit{data-independent} time complexity of $O(n^3)$? This raises a natural question: could there exist algorithms for solving QPs that also achieve data-independent time complexity of $O(n^3)$? This is critical for offering an execution time certificate for real-time optimization-based applications such as model predictive control. This article first demonstrates that solving real-time strictly convex QPs, Lasso problems, and support vector machine problems can be turned into solving box-constrained QPs (Box-QPs), which support a cost-free initialization strategy for feasible interior-point methods (IPMs). Next, focusing on solving Box-QPs, this article replaces the exact Newton step with an approximated Newton step (substituting the matrix-inversion operation with multiple rank-1 updates) within feasible IPMs. For the first time, this article proposes an implementable feasible IPM algorithm with $O(n^3)$ time complexity, by proving the number of iterations is exact $O(\sqrt{n})$ and the number of rank-1 updates is bounded by $O(n)$. Numerical validations/applications and codes are provided.