Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints
math.OC
Submitted: 2026-09-13
Updated: 2026-10-26
Comments: 59 pages, 4 figures, 5 tables
License: http://creativecommons.org/licenses/by/4.0/
The gist: This paper focuses on difference-of-convex (DC) composite optimization problems with set-inclusion and manifold constraints.
Terminology
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(ε-2) worst-case outer iteration complexity for finding an ε-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(ε-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(ε-2 (1/ε)) 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.
Sources
- Convergence analysis of linearized $\ell_q$ penalty methods for nonconvex optimization with nonlinear equality constraints
- Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise