用深度展开加速非线性规划,解决约束不可行时的优化问题。
Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding
- 通过ℓ₁弹性松弛构造始终可行的凸二次规划求解器
- 在10,000变量以上的密集问题上仍能高效求解,性能超越现有方法
- 适用于轨迹优化与安全滤波,显著提升成功率和安全性
我们提出FlexQP,一种基于ℓ₁弹性松弛的始终可行的凸二次规划(QP)求解器。若原约束可行,FlexQP可证明收敛至最优解;若约束不可行,则其找到最小化约束违反且违反约束数量稀疏的解,这在序列二次规划(SQP)子问题中因约束线性化而自然出现。我们在弱强制性假设下证明了FlexQP的收敛性,使其对可行与不可行的QP均具有鲁棒性。随后,我们采用深度展开学习基于LSTM的、维度无关的算法参数反馈策略,得到加速版Deep FlexQP。为保留松弛的精确性保证,我们设计了结合拉格朗日乘子的归一化训练损失,并引入对数尺度损失以获得更紧的PAC-Bayes泛化界,从而构建出具有保证性能的加速SQP求解器。Deep FlexQP在组合优化、分类与回归等基准测试中超越当前最先进学习型QP求解器,可通过微调扩展至超10,000变量与约束的密集问题。部署于SQP中时,该方法比使用OSQP的SQP快4-16倍,显著提高成功率达。在预测安全滤波任务中,相比现有方法减少70%以上安全违规,任务完成率提升43%。
原文摘要 · Abstract (English)
We propose FlexQP, an always-feasible convex quadratic programming (QP) solver based on an $\ell_1$ elastic relaxation of the QP constraints. If the original constraints are feasible, FlexQP provably recovers the optimal solution. If the constraints are infeasible, FlexQP identifies a solution that minimizes the constraint violation while keeping the number of violated constraints sparse. Such infeasibilities arise naturally in sequential quadratic programming (SQP) subproblems due to the linearization of the constraints. We prove the convergence of FlexQP under mild coercivity assumptions, making it robust to both feasible and infeasible QPs. We then apply deep unfolding to learn LSTM-based, dimension-agnostic feedback policies for the algorithm parameters, yielding an accelerated Deep FlexQP. To preserve the exactness guarantees of the relaxation, we propose a normalized training loss that incorporates the Lagrange multipliers. We additionally design a log-scaled loss for PAC-Bayes generalization bounds that yields substantially tighter performance certificates, which we use to construct an accelerated SQP solver with guaranteed QP subproblem performance. Deep FlexQP outperforms state-of-the-art learned QP solvers on a suite of benchmarks including portfolio optimization, classification, and regression problems, and scales to dense QPs with over 10k variables and constraints via fine-tuning. When deployed within SQP, our approach solves nonlinear trajectory optimization problems 4-16x faster than SQP with OSQP while substantially improving success rates. On predictive safety filter problems, Deep FlexQP reduces safety violations by over 70\% and increases task completion by 43\% compared to existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。