用隐式方法解决二次规划，提升求解精度与效率。
Implicit Primal-Dual Interior-Point Methods for Quadratic Programming
- 通过辅助变量和收缩映射隐式满足互补性条件。
- 新方法使KKT系统谱有界，解决病态问题。
- 适合大规模高精度二次规划求解，支持低精度计算。
本文提出一种新的二次规划求解方法，基于原对偶内点法。不同于传统方法在KKT条件中显式处理互补性，本方法通过引入辅助变量，并利用收缩映射将其与对偶变量和松弛变量关联，隐式保证互补性成立。特别地，证明软激活函数（softplus）相比常用的指数映射具有更优的数值性质。由此得到的KKT系统具有谱有界性，从而消除原对偶方法最严重的局限——接近解时的病态问题。这一特性使得线性系统的求解更加高效：既可避免每轮迭代都进行分解，支持无需分解的间接求解器；也可在低精度算术下实现高精度求解。该新视角为内点法在大规模高精度问题中的应用开辟了新可能。
原文摘要 · Abstract (English)
This paper introduces a new method for solving quadratic programs using primal-dual interior-point methods. Instead of handling complementarity as an explicit equation in the Karush-Kuhn-Tucker (KKT) conditions, we ensure that complementarity is implicitly satisfied by construction. This is achieved by introducing an auxiliary variable and relating it to the duals and slacks via a retraction map. Specifically, we prove that the softplus function has favorable numerical properties compared to the commonly used exponential map. The resulting KKT system is guaranteed to be spectrally bounded, thereby eliminating the most pressing limitation of primal-dual methods: ill-conditioning near the solution. These attributes facilitate the solution of the underlying linear system, either by removing the need to compute factorizations at every iteration, enabling factorization-free approaches like indirect solvers, or allowing the solver to achieve high accuracy in low-precision arithmetic. Consequently, this novel perspective opens new opportunities for interior-point methods, especially for solving large-scale problems to high precision.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。