Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization
Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization
复制标题
DOI：
10.1007/s10107-023-01980-2
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
P. D. Khanh;B. Mordukhovich;Vo Thanh Phat;D. Tran
中科院分区：
文献类型：
--
作者：
P. D. Khanh;B. Mordukhovich;Vo Thanh Phat;D. Tran
本文提出并证明了用变分分析和广义微分方法求解无约束和有约束非光滑优化问题的两种全局收敛的牛顿型方法。这两种方法都是基于协导数的，并使用与目标函数相关的广义Hessians（子梯度映射的协导数），这些目标函数要么是类的，要么以凸复合优化的形式表示，其中一项可能是扩展实值的。本文提出的全局收敛算法分为两类。前者是对阻尼牛顿法的扩展，由于其适定性和高效性能，要求广义Hessians为正定；后者是广义Hessians仅为正半定时，正则牛顿型算法定义良好。这两种方法的收敛速率都至少是线性的，但在子梯度映射的半光滑性下，收敛速率变成了超线性的。利用前后向包络机制，研究了目标函数光滑部分具有强凸性假设和不具有强凸性假设的凸复合优化问题。对Lasso问题和盒约束二次规划进行了数值实验，并将新算法与其他一些在非光滑优化中得到高度认可的一阶和二阶方法进行了性能比较。
This paper proposes and justifies two globally convergent Newton-type methods to solve unconstrained and constrained problems of nonsmooth optimization by using tools of variational analysis and generalized differentiation. Both methods are coderivative-based and employ generalized Hessians (coderivatives of subgradient mappings) associated with objective functions, which are either of class, or are represented in the form of convex composite optimization, where one of the terms may be extended-real-valued. The proposed globally convergent algorithms are of two types. The first one extends the damped Newton method and requires positive-definiteness of the generalized Hessians for its well-posedness and efficient performance, while the other algorithm is of the regularized Newton-type being well-defined when the generalized Hessians are merely positive-semidefinite. The obtained convergence rates for both methods are at least linear, but become superlinear under the semismoothproperty of subgradient mappings. Problems of convex composite optimization are investigated with and without the strong convexity assumption on smooth parts of objective functions by implementing the machinery of forward–backward envelopes. Numerical experiments are conducted for Lasso problems and for box constrained quadratic programs with providing performance comparisons of the new algorithms and some other first-order and second-order methods that are highly recognized in nonsmooth optimization.