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

arXiv:2609.14564 · math.OC · Submitted 2026-09-13 · Read on arXiv

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

Related papers