Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints

Abstract

This paper focuses on difference-of-convex (DC) composite optimization problems with set-inclusion and manifold constraints. We develop an inexact proximal-linearized nonsmooth exact penalty (NEP) method that penalizes the conic constraint while retaining the manifold constraint explicitly. At each outer iteration, the method approximately solves a strongly convex proximal-linearized subproblem over the current tangent space, using computable inexactness criteria, adaptive parameters, and a retraction-based acceptance mechanism. Under boundedness of the iterates and penalty parameters, we establish an $O({\epsilon }^{-2})$ worst-case outer iteration complexity for finding an $\epsilon$-approximate KKT point of the original problem. We further develop a complexity-transfer framework relating uniform primal objective-gap and KKT-residual decay, or dual objective-gap decay, to total inner-iteration complexity bounds. This yields an $O({\epsilon }^{-4})$ overall oracle complexity with either accelerated semi-proximal ADMM or FISTA applied to the dual subproblem as the inner solver. Using semi-proximal ADMM as the inner solver improves the bound to $O({\epsilon }^{-2}\log (1/\epsilon ))$ under an additional uniform error-bound condition. We further establish convergence of the entire iterate sequence to a KKT point under the same boundedness assumption and the Kurdyka-Lojasiewicz property of the associated potential function. Numerical experiments demonstrate the competitive performance of the proposed method on row-sparse PCA, clustering, robust SVMs, and nonconvex SOCPs.

arXiv comment59 pages, 4 figures, 5 tables