← 研踪 PaperTrailarXiv:2611.19887 · v1
First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization
首次提交 2026-11-15 17:06
版本更新 2026-11-15 17:06
雷达观测 2026-11-17 12:06
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-15 17:06 · 最新观测版本
First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization
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.
查看此版本解读 →查看此版本原文 ↗