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(ε−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(ε−2log(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.
Related
- A Bregman proximal linearized ADMM for fractional programming with nonlinear coupling constraints
- Controlled Block Proximal Linearized Method for Nonconvex and Nonsmooth Optimization
- Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization
- Relative-Error Composite Federated Optimization with One Server-Side Proximal Step per Round
- Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
BibTeX
@misc{he2026proximallinearized,
title = {{Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints}},
author = {Hao He and Ruyu Liu and Shaohua Pan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.14564},
eprint = {2609.14564},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14564},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints
AU - Hao He
AU - Ruyu Liu
AU - Shaohua Pan
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2609.14564
UR - https://arxiv.org/abs/2609.14564
AB - 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(ε^−2log(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.
ER -