A Globalized Semismooth Newton Method for Prox-regular Optimization Problems

Yuqia Wu , Pengcheng Wu, Yaohua Hu, Shaohua Pan , Xiaoqi Yang · 2025

Read A Globalized Semismooth Newton Method for Prox-regular Optimization Problems by Yuqia Wu , Pengcheng Wu, Yaohua Hu, Shaohua Pan , Xiaoqi Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05765.txt.

Introduction

A faster way to solve a stubborn class of optimization problems is proposed in a 2025 paper by Yuqia Wu and four co-authors. The problems mix a smooth twice-differentiable part with a prox-regular part, a function that is rough yet well behaved near a point. Such problems are both nonconvex and nonsmooth, so standard solvers can stall.

The team first shows when the proximal mapping, a key building block, stays single-valued and steady under small changes. They then blend proximal gradient steps with semismooth Newton steps into one globalized method. The full sequence settles at a stationary point, and under extra conditions it speeds up to a superlinear rate near the end. Tests on sparse-norm problems show it matching strong second-order rivals.

Catalog record

CREATORYuqia Wu , Pengcheng Wu, Yaohua Hu, Shaohua Pan , Xiaoqi Yang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05765

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Globalized Semismooth Newton Method for Prox-regular Optimization Problems Yuqia Wu , Pengcheng Wu, Yaohua Hu, Shaohua Pan , Xiaoqi Yang Abstract We are concerned with a class of nonconvex and nonsmooth composite optimization problems, comprising a twice differentiable function and a prox-regular function. We establish a sufficient condition for the proximal mapping of a prox-regular function to be single-valued and locally Lipschitz continuous. By virtue of this property, we propose a hybrid of proximal gradient and semismooth Newton methods for solving these composite optimization problems, which is a globalized semismooth Newton method. The whole sequence is shown to converge to an L L -stationary point under a Kurdyka-Łojasiewicz exponent assumption. Under an additional error bound condition and some other mild conditions, we prove that the sequence converges to a nonisolated L L -stationary point at a superlinear convergence rate. Numerical comparison with several existing second order methods reveal that our approach performs comparably well in solving both the ℓ q ​ ( 0 < q < 1 ) \ell_{q}(0<q<1) quasi-norm regularized problems and the fused zero-norm regularization problems. 1 Introduction We are interested in the following nonsmooth and nonconvex composite optimization problem \min_{x\in\mathbb{R}^{n}}F(x):=f(x)+g(x). (1) We assume that F satisfies the following assumptions. Assumption 1 (i) f\!:\mathbb{R}^{n}\to\overline{\mathbb{R}}\!:=\mathbb{R}\cup\{\infty\} is twice differentiable on an open set \mathcal{O}\supset{\rm dom}g , and \nabla\!f and \nabla^{2}\!f are Lipschitz continuous on \mathcal{O} , where the former has a Lipschitz constant L . (ii) g\!:\mathbb{R}^{n}\to\overline{\mathbb{R}} is proper and lsc, and g has a computable proximal mapping. (iii) F is lower bounded, i.e., \underline{F}:=\inf_{x\in\mathbb{R}^{n}}F(x)>-\infty . Problem ( 1 ) frequently arises from sparse optimization, which has a wide range of applications in signal processing, statistics, machine learning, and so on. The function g in Assumption 1 (ii) includes the \ell_{q} quasi-norm \|x\|_{q}^{q} with q=\frac{1}{2},\frac{2}{3},1 , the zero norm, SCAD, MCP (see [ 47 , 10 , 15 , 50 ] ), and the fused zero-norms [ 45 ] . 1.1 Related works Recent years have witnessed active research interests in Newton-type methods for the general nonsmooth and nonconvex composite problem ( 1 ). The proximal Newton-type method has been shown to be effective for tackling problem ( 1 ) with a convex or weakly convex g (see, e.g., [ 7 , 25 , 49 , 31 , 22 , 28 ] ). The semismooth Newton method has been a favored second-order method for solving problem ( 1 ) or its special case, as evidenced in [ 30 , 46 , 41 , 51 , 20 , 19 , 33 ] . Specifically, Ouyang and Milzarek [ 33 ] considered problem ( 1 ) with convex g , and proposed a trust region-type normal map-based semismooth Newton method, which achieves convergence of the sequence under the KL property of a merit function, and a superlinear convergence rate under mild conditions. In addition, the second-order algorithms designed by the forward-backward envelope (FBE) of F also have become popular ones; see [ 40 , 42 , 41 , 1 , 24 , 23 ] . When the proximal mapping of g is accessible, a natural residual mapping of ( 1 ) is the one from the fixed point form of the proximal gradient (PG) method, that is, \mathcal{R}_{\gamma}(x)\!:=\gamma^{-1}\left(x-\mathcal{T}_{\gamma}(x)\right)\ \ {\rm with}\ \ \mathcal{T}_{\gamma}(x):=\mathcal{P}_{\gamma}g(x-\gamma\nabla\!f(x))\quad{\rm for}\ x\in\mathbb{R}^{n}, (2) where \mathcal{P}_{\gamma}g is the proximal mapping of g associated with parameter \gamma>0 ; see ( 4 ) for its definition. To apply the semismooth Newton method to solve the generalized equation 0\in\mathcal{R}_{\gamma}(x) , the key is the existence of the Clarke Jacobian of \mathcal{R}_{\gamma} at the iterate, at which \mathcal{R}_{\gamma} should be single-valued and locally Lipschitz continuous [ 37 ] . When g is convex, \mathcal{P}_{\gamma}g is single-valued and nonexpansive everywhere [ 39 , Proposition 12.19] . By leveraging this property, for problem ( 1 ) with convex f and g , Themelis et al. [ 41 ] proposed a globally convergent semismooth Newton method to seek a root of the system \mathcal{R}_{\gamma}(x)=0 , which achieves superlinear convergence by requiring that F has a locally quadratic growth property at the limit point at which \mathcal{R}_{\gamma} is strict differentiable, and restricting the length of the Newton directions. However, this method cannot be directly extended to solve ( 1 ) with nonconvex g since now the single-valuedness and local Lipschitz continuity of \mathcal{R}_{\gamma} cannot be guaranteed. Even if g is prox-regular at x for some v\in\partial g(x) , according to [ 39 , Proposition 13.37] , there only exist a neighborhood \mathcal{V}(x) of x and a constant \gamma_{0}>0 such that \mathcal{P}_{\gamma}g is single-valued and locally Lipschitz continuous at z+\gamma v for all z\in\mathcal{V}(x) and \gamma\in(0,\gamma_{0}) . This guarantees the single-valuedness and local Lipschitz continuity of \mathcal{P}_{\gamma}g in ( 2 ) at x+\gamma v instead of x-\gamma\nabla f(x) , which prevents semismooth Newton method from solving the nonsmooth system 0\in\mathcal{R}_{\gamma}(x) . To overcome this difficulty, Hu et al. [ 19 ] investigated problem ( 1 ) with a so-called strongly prox-regular g to ensure the single-valuedness and local Lipschitz continuity of \mathcal{R}_{\gamma} on {\rm dom}\,g . They proposed a globally convergent semismooth Newton method with a superlinear convergence rate under the BD-regularity of the limit point. It is worth mentioning that, a similar variant of the prox-regularity, called r -prox-regular, was also used in [ 6 ] to prove the stability of the manifold identification. For convex composite problems, Khanh et al. [ 24 ] proposed a coderivative-based Newton method, and obtained the superlinear convergence under the semismooth ∗ property and the twice epi-differentiability of \partial g at the limit. This method was extended to handle structured nonconvex optimization in [ 23 ] , which seeks a critical point of ( 1 ) by solving the system 0\in\mathcal{R}_{\gamma}(x) . Since the Newton direction is obtained by coderivative of \mathcal{R}_{\gamma} , its single-valuedness and local Lipschitz continuity is unnecessary. They established a superlinear convergence for a prox-regular g by assuming that the limit point is a tilt-stable local minimum and \partial g has the {\rm semismooth}^{*} property. It was pointed out in [ 17 , Eq. (2.2)] that if \mathcal{R}_{\gamma} is single-valued at x , then {\rm conv}D^{*}\mathcal{R}_{\gamma}(x)(v)=\{A^{\top}v\ |\ A\in\partial_{C}\mathcal{R}_{\gamma}(x)\}, where D^{*}\mathcal{R}_{\gamma}(x)(v) denotes the coderivative of \mathcal{R}_{\gamma} at x for v . From this point of view, the solvability of the generalized Newton systems at (x,v)\in{\rm gph}\mathcal{R}_{\gamma} is somehow restricted. In fact, one of the sufficient conditions is the strong metric subregularity of \mathcal{R}_{\gamma} at (x,v) for some v\in\mathcal{R}_{\gamma}(x) ; see [ 23 , Lemma 3.1] . Recently, Gfrerer [ 16 ] introduced from another perspective a globalized {\rm semismooth}^{*} Newton method that does not require the single-valuedness of \mathcal{R}_{\gamma} . This method achieves the superlinear convergence under the assumptions of SCD regularity and SCD {\rm semismooth}^{*} property of \partial F at the origin. These two assumptions are respectively weaker than metric regularity and {\rm semismooth}^{*} property, but similar to other generalized Newton methods, the well-definedness of the generalized Newton system still requires strong conditions. We are interested in designing a globalized semismooth Newton method for ( 1 ) by solving the system 0\in\mathcal{R}_{\gamma}(x) that owns global and superlinear convergence simultaneously, by exploring the sufficient conditions of the existence of Clarke Jacobian of \mathcal{R}_{\gamma} . It is worth emphasizing

Read the complete text