arXiv:2608.12665math.OCcs.LG2026-08

提出一种新算法,可在接近最优解时实现快速收敛,适合大规模约束优化。

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

  • 基于Fletcher的增广拉格朗日函数,通过小步长和大惩罚参数实现局部线性收敛。
  • 在接近强二阶驻点时,收敛速度比传统方法快,且对大样本问题更高效。
  • 特别适合处理由大量样本平均定义的目标与约束问题,降低样本复杂度。

针对非凸等式约束优化问题,近期提出的梯度-特征步算法(Gradient-Eigenstep Algorithm)是一种高效的迭代方法,通过最小化Fletcher的增广拉格朗日函数,从任意初始点出发逼近二阶近似驻点。本文拓展了该算法的分析,作出两方面贡献:首先,若算法初始化足够接近强二阶驻点,并采用足够小的步长和足够大的惩罚参数,则可获得局部线性收敛率;此时算法退化为对Fletcher增广拉格朗日函数进行梯度下降。其次,作为第一项结果的直接应用,该算法可作为大规模样本平均型等式约束优化中渐进采样策略的高效子问题求解器,相比直接求解全样本问题,显著提升了最坏情况下的样本复杂度。

原文摘要 · Abstract (English)

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

优化算法非凸优化约束优化收敛分析

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