First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization
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 , 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.
Figures & tables
| Method | Eq. ∗ | Ineq. ∗ | Regularity Condition | Oracle Complexity | Arithmetic Complexity |
|---|---|---|---|---|---|
| iALM [ 31 ] | ✓ | Iterate-wise NSC ‡ | |||
| iPPP [ 32 ] | ✓ | ✓ | Global NSC ‡ | ||
| LCPG [ 8 ] | ✓ | Uniform MFCQ | ¶ | ||
| IQRC † [ 36 ] /ICPPC [ 7 ] | ✓ | Uniform Slater/Strong feasibility | |||
| Proximal-gradient † [ 16 ] | ✓ | Sequential LICQ-type CQ ‡ | ¶ | ||
| SPALM [ 58 ] | ✓ | Local conic regularity ‡ | ¶ |
| (12) |
Nonconvex Optimization
Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.
See all 163 papers