Generalized Newton Method with Positive Definite Regularization for Nonsmooth Optimization Problems with Nonisolated Solutions

We propose a coderivative-based generalized regularized Newton method with positive definite regularization term (GRNM-PD) to solve $$C^{1,1}$$ C 1 , 1 optimization problems. In GRNM-PD, a general positive definite symmetric matrix is used to regularize the generalized Hessian, in contrast to the recently proposed GRNM, which uses the identity matrix. Our approach features global convergence and fast local convergence rate even for problems with nonisolated solutions. To this end, we introduce the p-order semismooth $${}^*$$ ∗ property which plays the same role in our analysis as Lipschitz continuity of the Hessian does in the $$C^2$$ C 2 case. Imposing only the metric q-subregularity of the gradient at a solution, we establish global convergence of the proposed algorithm as well as its local convergence rate, which can be superlinear, quadratic, or even higher than quadratic, depending on an algorithmic parameter $$\rho $$ ρ and the regularity parameters p and q. Specifically, choosing $$\rho $$ ρ to be one, we achieve quadratic local convergence rate under metric subregularity and the strong semismooth $${^*}$$ ∗ property. The algorithm is applied to a class of nonsmooth convex composite minimization problems through the machinery of forward–backward envelope. The greater flexibility in the choice of regularization matrices leads to notable improvement in practical performance. Numerical experiments on box-constrained quadratic programming problems demonstrate the efficiency of our algorithm.