arXiv:2410.20153math.OCcs.LG2024-10中稿 · publication in Tra…被引 3

用非标准幂次正则项改进非凸约束优化,提升收敛速度。

The inexact power augmented Lagrangian method for constrained nonconvex optimization

  • 采用1到2次幂的欧氏范数作增广项,突破传统平方形式限制。
  • 在弱凸和霍尔德光滑条件下,实现最优收敛速率,降低原始复杂度。
  • 实验证明低次幂增广项更优,适合求解复杂非凸优化问题。

本文提出一种非精确增广拉格朗日方法,其增广项为介于1到2次幂之间的欧氏范数。该算法适用于包含非线性等式约束的广泛非凸最小化问题。首先,在温和正则性条件下,通过加速一阶算法求解霍尔德光滑子问题,完成全复杂度分析。结果表明:较低幂次的增广项能更快满足约束,但对偶残差下降较慢。分析不依赖迭代序列有界性假设。随后,提出一种用于求解弱凸与霍尔德光滑子问题的非精确邻近点法,并证明组合方案达到更优收敛率;当增广项为经典平方欧氏范数时,收敛率退化至现有最佳水平。使用更低幂次的增广项可进一步降低原始复杂度,代价是增加对偶复杂度。数值实验验证了非标准增广项的实际有效性。

原文摘要 · Abstract (English)

This work introduces an unconventional inexact augmented Lagrangian method where the augmenting term is a Euclidean norm raised to a power between one and two. The proposed algorithm is applicable to a broad class of constrained nonconvex minimization problems that involve nonlinear equality constraints. In a first part of this work, we conduct a full complexity analysis of the method under a mild regularity condition, leveraging an accelerated first-order algorithm for solving the Hölder-smooth subproblems. Interestingly, this worst-case result indicates that using lower powers for the augmenting term leads to faster constraint satisfaction, albeit with a slower decrease of the dual residual. Notably, our analysis does not assume boundedness of the iterates. Thereafter, we present an inexact proximal point method for solving the weakly-convex and Hölder-smooth subproblems, and demonstrate that the combined scheme attains an improved rate that reduces to the best-known convergence rate whenever the augmenting term is a classical squared Euclidean norm. Different augmenting terms, involving a lower power, further improve the primal complexity at the cost of the dual complexity. Finally, numerical experiments validate the practical performance of unconventional augmenting terms.

非凸优化增广拉格朗日霍尔德光滑收敛速率

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。