math.OCNov 15, 2026

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

Authors: Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu

Organizations: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY · Tippie College of Business, University of Iowa, Iowa City, IA · IMAI, Wuhan University; Department of Applied Mathematics, Hong Kong Polytechnic University, China

Abstract

We consider regularized nonconvex optimization over a closed convex set X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d, which involves a convex nonsmooth regularizer rr in the objective and nn smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an εε-KKT point within O(ε−2)O(ε^{-2}) first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let CFO\mathcal{C}_{\mathrm{FO}} and Cr\mathcal{C}_r denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of rr over X\mathcal{X}, respectively. Then SEPi-Prox requires O~(CFOε−2+(dn+Cr)ε−5/2)\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2}) and O~((CFO+dn2+nCr+n3.373)ε−2)\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2}) total arithmetic operations to produce an εε-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when nn is small and nearly matches the optimal dependence on εε. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

Figures & tables

Explore similar work

CardsList
  1. A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

    Jan 31, 2025Wei Liu, Yangyang XuStochastic OptimizationConstrained Optimization

  2. Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

    Jul 9, 2026Linglingzhi Zhu, Jiajin LiPrimal-Dual OptimizationNonconvex Optimization

  3. Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

    Aug 31, 2026Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabiNonconvex OptimizationConstrained Optimization