跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 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.

查看此版本解读 →查看此版本原文 ↗