A proximal-linearized NEP method for composite optimization with conic and manifold constraints

Abstract

This paper studies difference-of-convex (DC) composite optimization problems with conic and manifold constraints. By penalizing the conic constraint with a distance-based penalty, we propose an inexact proximal-linearized nonsmooth exact penalty (iPLNEP) algorithm. The proposed method successively finds approximate minimizers of proximal-linearized subproblems over the tangent spaces of the manifold based on computable inexactness criteria, while adaptively updating the proximal and penalty parameters. Under a boundedness assumption on the iterate and penalty parameter sequences, iPLNEP is shown to achieve an $O(\epsilon^{-2})$ worst-case iteration complexity bound for finding an $\epsilon$-stationary point. Using accelerated semi-proximal ADMM to solve the subproblems, we establish an overall oracle complexity bound of $O(\epsilon^{-4})$. Under an additional uniform error-bound condition, using semi-proximal ADMM as the subproblem solver yields an improved overall oracle complexity bound of $O(\epsilon^{-2}\log\epsilon^{-1})$. To the best of our knowledge, this provides the first proximal-linearized NEP framework with provable oracle complexity guarantees for DC composite optimization with conic and manifold constraints. If, in addition, the associated potential function satisfies the KL property, the whole sequence of iterates converges to a stationary point. Extensive numerical experiments on composite optimization problems with orthogonal-manifold, nonnegative cone, and second-order cone constraints demonstrate the effectiveness of the proposed method.