提出一种每步都保证可行的优化算法，适合有约束的非凸问题。
Anytime-Feasible First-Order Optimization via Safe Sequential QCQP
- 基于安全序列凸二次约束规划构造连续动力系统，确保每步可行
- 离散化后仍保持 $O(1/t)$ 收敛率和可行性，无需调参
- 主动集变体显著降低计算开销，适合大规模问题
本文提出安全序列二次约束二次规划（SS-QCQP）算法，一种用于光滑不等式约束非凸优化的一阶方法，能在每一步迭代中保证可行性。该方法源自一个连续时间动力系统，其向量场通过求解一个凸二次约束二次规划（QCQP）获得，以确保目标函数单调下降并维持可行集的前向不变性。在标准约束资格条件下，连续时间动态系统可达到 $O(1/t)$ 的收敛速率至一阶驻点。随后，我们设计了一种带自适应步长选择的保护欧拉离散化，保持该收敛速率的同时，在离散时间下同时实现下降性和可行性。为提升可扩展性，进一步开发了主动集变体（SS-QCQP-AS），仅对边界附近的约束进行强化，大幅降低计算成本且不牺牲理论保证。在多智能体非线性最优控制问题上的数值实验表明，SS-QCQP 和 SS-QCQP-AS 均能保持可行性，表现出预测的收敛行为，并达到与二阶求解器（如 SQP、IPOPT）相当的解质量。
原文摘要 · Abstract (English)
This paper presents the Safe Sequential Quadratically Constrained Quadratic Programming (SS-QCQP) algorithm, a first-order method for smooth inequality-constrained nonconvex optimization that guarantees feasibility at every iteration. The method is derived from a continuous-time dynamical system whose vector field is obtained by solving a convex QCQP that enforces monotonic descent of the objective and forward invariance of the feasible set. The resulting continuous-time dynamics achieve an $O(1/t)$ convergence rate to first-order stationary points under standard constraint qualification conditions. We then propose a safeguarded Euler discretization with adaptive step-size selection that preserves this convergence rate while maintaining both descent and feasibility in discrete time. To enhance scalability, we develop an active-set variant (SS-QCQP-AS) that selectively enforces constraints near the boundary, substantially reducing computational cost without compromising theoretical guarantees. Numerical experiments on a multi-agent nonlinear optimal control problem demonstrate that SS-QCQP and SS-QCQP-AS maintain feasibility, exhibit the predicted convergence behavior, and deliver solution quality comparable to second-order solvers such as SQP and IPOPT.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。