提出新型拟牛顿法,高效求解非光滑优化问题。
A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization
- 用自适应二次正则化构造模型,每步可近似求解
- 理论保证全局收敛,复杂度最优且无需梯度 Lipschitz 假设
- 适合非凸、非光滑问题,支持并行与独立求解
我们提出 R2N,一种用于最小化 C¹ 函数 $f$ 与下半连续、近端有界的 $h$ 之和的修正拟牛顿方法。两者均可非凸。每步通过最小化 $f$ 的二次模型、$h$ 的模型及自适应二次正则项来计算步长,步长可由近端梯度法变体求得。相比信赖域方法,无需额外的信赖域指示器。我们还提出变体 R2DH,其模型海森矩阵为对角阵,当 $h$ 可分时可免于子问题求解器。R2DH 可独立使用,也可作为 R2N 的子问题求解器。两种方法均支持非单调版本。在不依赖 $ abla f$ 局部 Lipschitz 连续性条件下,一阶平稳性测度可全局收敛至零,允许模型海森矩阵无界增长。在 $ abla f$ Lipschitz 连续下,最坏情况复杂度为 $O(1 / ε^{2/(1 - p)})$,其中 $0 \< p < 1$ 控制海森矩阵增长,要求其增长不超过 $|\< S_k |^p$,$\u003c S_k$ 为前 $k$ 步成功迭代集。当 $p = 1$ 时,复杂度为 $O(\exp(c ε^{-2}))$,$c > 0$。报告了基于 Julia 的实现,并在基追踪、图像去噪、低秩矩阵补全、非线性 SVM 及非线性逆问题上进行了数值实验。
原文摘要 · Abstract (English)
We develop R2N, a modified quasi-Newton method for minimizing the sum of a $\mathcal{C}^1$ function $f$ and a lower semi-continuous prox-bounded $h$. Both $f$ and $h$ may be nonconvex. At each iteration, our method computes a step by minimizing the sum of a quadratic model of $f$, a model of $h$, and an adaptive quadratic regularization term. A step may be computed by a variant of the proximal-gradient method. An advantage of R2N over trust-region (TR) methods is that proximal operators do not involve an extra TR indicator. We also develop the variant R2DH, in which the model Hessian is diagonal, which allows us to compute a step without relying on a subproblem solver when $h$ is separable. R2DH can be used as standalone solver, but also as subproblem solver inside R2N. We describe non-monotone variants of both R2N and R2DH. Global convergence of a first-order stationarity measure to zero holds without relying on local Lipschitz continuity of $\nabla f$, while allowing model Hessians to grow unbounded, an assumption particularly relevant to quasi-Newton models. Under Lipschitz-continuity of $\nabla f$, we establish a tight worst-case complexity bound of $O(1 / ε^{2/(1 - p)})$ to bring said measure below $ε> 0$, where $0 \leq p < 1$ controls the growth of model Hessians. The latter must not diverge faster than $|\mathcal{S}_k|^p$, where $\mathcal{S}_k$ is the set of successful iterations up to iteration $k$. When $p = 1$, we establish the tight exponential complexity bound $O(\exp(c ε^{-2}))$ where $c > 0$ is a constant. We describe our Julia implementation and report numerical experience on a classic basis-pursuit problem, an image denoising problem, a minimum-rank matrix completion problem, a nonlinear support vector machine and an inverse nonlinear problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。