提出一种连续镜流方法,统一解释并改进非凸约束优化中的两类经典算法。
On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem
- 构建基于障碍函数的黎曼子梯度流,保持轨迹在可行域内部。
- 揭示了原有方法的虚假驻点本质,并给出避免条件。
- 设计新迭代算法,适用于非光滑非凸优化问题。
研究定义在非凸约束上的非光滑非凸优化问题,其可行集为开集闭包与光滑流形的交集。通过在开集上赋予由障碍函数诱导的黎曼度量,得到一个保持严格位于可行集内部的黎曼子梯度流,以微分包含形式表述。该连续动力系统统一了赫斯蒂安障碍法与镜面下降法两类迭代优化方法,表明它们可视为该连续流的离散近似。我们分析了轨迹的长期行为,发现原有方法中存在的虚假驻点(spurious stationary points)可被解释为不对应于原问题真实驻点的稳定平衡点。若满足严格互补性条件,可避免此类虚假点;否则,提出随机扰动策略,确保轨迹(子序列)收敛至近似驻点。基于此,提出两种形式为内点法的迭代黎曼子梯度方法,推广了现有赫斯蒂安障碍法与镜面下降法,适用于非光滑非凸优化问题。
原文摘要 · Abstract (English)
We study a nonsmooth nonconvex optimization problem defined over nonconvex constraints, where the feasible set is given by the intersection of the closure of an open set and a smooth manifold. By endowing the open set with a Riemannian metric induced by a barrier function, we obtain a Riemannian subgradient flow formulated as a differential inclusion, which remains strictly within the interior of the feasible set. This continuous dynamical system unifies two classes of iterative optimization methods, namely the Hessian barrier method and mirror descent scheme, by revealing that these methods can be interpreted as discrete approximations of the continuous flow. We explore the long-term behavior of the trajectories generated by this dynamical system and show that the existing deficient convergence properties of the Hessian barrier and mirror descent scheme can be unifily and more insightfully interpreted through these of the continuous trajectory. For instance, the notorious spurious stationary points \cite{chen2024spurious} observed in Hessian barrier method and mirror descent scheme are interpreted as stable equilibria of the dynamical system that do not correspond to real stationary points of the original optimization problem. We provide two sufficient condition such that these spurious stationary points can be avoided if the strict complementarity conditions holds. In the absence of these regularity condition, we propose a random perturbation strategy that ensures the trajectory converges (subsequentially) to an approximate stationary point. Building on these insights, we introduce two iterative Riemannian subgradient methods, form of interior point methods, that generalizes the existing Hessian barrier method and mirror descent scheme for solving nonsmooth nonconvex optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。