在更弱条件下，新算法以更低复杂度求解非凸约束优化问题。
Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions
- 基于约束函数的局部误差界假设，设计了不精确的Moreau包络拉格朗日方法。
- 达到ε-KKT点的梯度查询复杂度为˜O(ε⁻²ᵈ)，d∈[1,2]。
- 适用范围比现有方法更广，适合研究约束结构与复杂度关系的学者。
本文研究约束系统结构对带凸不等式约束的简单多面体上光滑非凸优化问题的预言机复杂度的影响。特别地，我们证明：在约束函数满足指数d∈[1,2]的局部误差界条件下，一种不精确的Moreau包络拉格朗日方法可达到ε-Karush–Kuhn–Tucker点，其梯度预言机复杂度为˜O(ε⁻²ᵈ)。当d=1时，该结果与文献中已知最优复杂度一致（仅差对数因子）。重要的是，对任意d∈[1,2]的误差界假设均严格弱于实现最优复杂度所需的局部线性无关约束资格条件。本结果阐明了约束误差界与算法复杂度之间的关系，并将复杂度保证扩展至更广泛的非凸约束优化问题。
原文摘要 · Abstract (English)
In this paper, we investigate how structural properties of the constraint system impact the oracle complexity of smooth non-convex optimization problems with convex inequality constraints over a simple polytope. In particular, we show that, under a local error bound condition with exponent $d\in[1,2]$ on constraint functions, an inexact Moreau envelope Lagrangian method can attain an $ε$-Karush--Kuhn--Tucker point with $\tilde O(ε^{-2d})$ gradient oracle complexity. When $d=1$, this result matches the best-known complexity in literature up to logarithmic factors. Importantly, the assumed error bound condition with any $d\in[1,2]$ is strictly weaker than the local linear independence constraint qualification that is required to achieve the best-known complexity. Our results clarify the interplay between error bound conditions of constraints and algorithmic complexity, and extend complexity guarantees to a broader class of constrained non-convex problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。