线性约束复合非凸非光滑问题的近似最优方法

A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems

摘要 Abstract

本文研究了一类具有线性约束的复合非凸非光滑优化问题的一阶方法(FOMs)。近期,文献\cite{liu2025lowercomplexityboundsfirstorder}建立了求解该问题的($\varepsilon,\varepsilon$)-KKT点的下界复杂度。然而,尚未有算法能够达到这一下界。在本文中,我们提出了一种不精确的近邻梯度方法,其中子问题通过恢复原始对偶过程求解。在未假设有界域的情况下,我们证明所提出的算法找到该问题的($\varepsilon,\varepsilon$)-KKT点的oracle复杂度与下界匹配,误差仅为对数因子。因此,在复杂度方面,我们的算法优于所有现有方法。数值实验表明,与交替方向乘子法及其线性化版本以及增广拉格朗日法相比,我们的算法具有明显优势。

We study first-order methods (FOMs) for solving \emph{composite nonconvex nonsmooth} optimization with linear constraints. Recently, the lower complexity bounds of FOMs on finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem is established in \cite{liu2025lowercomplexityboundsfirstorder}. However, optimization algorithms that achieve this lower bound had not been developed. In this paper, we propose an inexact proximal gradient method, where subproblems are solved using a recovering primal-dual procedure. Without making the bounded domain assumption, we establish that the oracle complexity of the proposed method, for finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem, matches the lower bounds up to a logarithmic factor. Consequently, in terms of the complexity, our algorithm outperforms all existing methods. We demonstrate the advantages of our proposed algorithm over the (linearized) alternating direction method of multipliers and the (proximal) augmented Lagrangian method in the numerical experiments.

线性约束复合非凸非光滑问题的近似最优方法 - arXiv