betaFeedback

WorksMathematics

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

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.

Paper details

vlnc:W_d4kfsnka
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…