WorksMathematics
First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization
Abstract
We consider regularized nonconvex optimization over a closed convex set , which involves a convex nonsmooth regularizer in the objective and 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 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 and denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of over , respectively. Then SEPi-Prox requires and total arithmetic operations to produce an -KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when 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.