First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization
Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu
原文摘要
We consider regularized nonconvex optimization over a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$, which involves a convex nonsmooth regularizer $r$ in the objective and $n$ 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})$ 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 $\mathcal{C}_{\mathrm{FO}}$ and $\mathcal{C}_r$ denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of $r$ over $\mathcal{X}$, respectively. Then SEPi-Prox requires $\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2})$ and $\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 $n$ 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.
math.OC · cs.LG