破解非凸约束优化难题,首次实现全局最优解的可证明求解。
Global Solutions to Non-Convex Functional Constrained Problems with Hidden Convexity
- 通过改进的近似投影点法,在非光滑情况下实现$ ilde{ ext{O}}(\varepsilon^{-3})$复杂度。
- 对光滑问题提出新型捆绑层级方法,复杂度降至$ ilde{ ext{O}}(\varepsilon^{-1})$。
- 无需约束资格条件,适用于隐藏凸性等式约束,适合控制与强化学习场景。
约束非凸优化本质上极具挑战性,因全局解通常不可行且约束资格条件可能不成立。然而在许多应用中,如控制和强化学习中的安全策略优化,此类问题具有隐藏凸性,即可通过非线性可逆变换重写为凸规划。通常这类变换隐含或未知,导致难以建立与凸规划的直接联系。另一方面,原始变量的(次)梯度往往可得或易估计,这促使算法直接在原(非凸)问题空间中运行,使用标准(次)梯度预言机。本文首次开发出可证明求解此类非凸问题至全局最小值的算法。首先,采用改进的不精确投影点法,在非光滑情形下建立$ ilde{ ext{O}}(\varepsilon^{-3})$的全局最后迭代收敛保证。对于光滑问题,提出一种基于线性约束二次子问题的新式捆绑层级方法,将预言机复杂度提升至$ ilde{ ext{O}}(\varepsilon^{-1})$。令人惊讶的是,尽管存在非凸性,本方法无需任何约束资格条件,可处理隐藏凸等式约束,并达到与求解无约束隐藏凸优化相同的复杂度。
原文摘要 · Abstract (English)
Constrained non-convex optimization is fundamentally challenging, as global solutions are generally intractable and constraint qualifications may not hold. However, in many applications, including safe policy optimization in control and reinforcement learning, such problems possess hidden convexity, meaning they can be reformulated as convex programs via a nonlinear invertible transformation. Typically such transformations are implicit or unknown, making the direct link with the convex program impossible. On the other hand, (sub-)gradients with respect to the original variables are often accessible or can be easily estimated, which motivates algorithms that operate directly in the original (non-convex) problem space using standard (sub-)gradient oracles. In this work, we develop the first algorithms to provably solve such non-convex problems to global minima. First, using a modified inexact proximal point method, we establish global last-iterate convergence guarantees with $\widetilde{\mathcal{O}}(\varepsilon^{-3})$ oracle complexity in non-smooth setting. For smooth problems, we propose a new bundle-level type method based on linearly constrained quadratic subproblems, improving the oracle complexity to $\widetilde{\mathcal{O}}(\varepsilon^{-1})$. Surprisingly, despite non-convexity, our methodology does not require any constraint qualifications, can handle hidden convex equality constraints, and achieves complexities matching those for solving unconstrained hidden convex optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。