A Globally Convergent Newton Method for Nonsmooth Optimization in the absence of Smooth Surrogates
Abstract
We propose a globally convergent Newton method for convex composite optimization problems with polyhedral regularizers. The method rests on the observation that the proximal gradient step yields not only a new point but also a subgradient, which determines the face on which the linearization of the regularizer is exact. Minimizing a second-order model of the objective over this face produces a Newton direction that involves no generalized second-order information about the regularizer and is a descent direction for the objective itself. The method is therefore globalized by an Armijo line search on the original objective which, unlike forward-backward envelope techniques, requires only evaluations of the smooth component. We establish global convergence and local quadratic convergence to tilt-stable minimizers without any nondegeneracy condition, and show that the unit step is always accepted when the smooth component is quadratic, which yields a line-search-free method. The subproblems require only projections onto faces, which are explicit for the Lasso and nonnegative least squares and computable in linear time for the fused Lasso. Numerical experiments show that the method compares favorably with state-of-the-art solvers.
Related
- Globally Convergent Block Coordinate Descent Algorithms for Semi-Nonnegative Independent Component Analysis
- A globally convergent stochastic semismooth Newton method for strongly convex problems in Hilbert spaces
- Globally Convergent Jacobi-Type Algorithms for Robust Approximate Diagonalization of Higher-Order Cumulant Tensors
- Linear convergence rate analysis of Proximal-Tracking for nonsmooth distributed optimization
- Exact penalty methods with adaptive discretization for nonsmooth semi-infinite optimization
BibTeX
@misc{nghia2026globally,
title = {{A Globally Convergent Newton Method for Nonsmooth Optimization in the absence of Smooth Surrogates}},
author = {Tran T. A. Nghia and Nghia V. Vo and Khoa V. H. Vu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31992},
eprint = {2610.31992},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31992},
note = {CC0},
}
RIS
TY - UNPB
TI - A Globally Convergent Newton Method for Nonsmooth Optimization in the absence of Smooth Surrogates
AU - Tran T. A. Nghia
AU - Nghia V. Vo
AU - Khoa V. H. Vu
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31992
UR - https://arxiv.org/abs/2610.31992
AB - We propose a globally convergent Newton method for convex composite optimization problems with polyhedral regularizers. The method rests on the observation that the proximal gradient step yields not only a new point but also a subgradient, which determines the face on which the linearization of the regularizer is exact. Minimizing a second-order model of the objective over this face produces a Newton direction that involves no generalized second-order information about the regularizer and is a descent direction for the objective itself. The method is therefore globalized by an Armijo line search on the original objective which, unlike forward-backward envelope techniques, requires only evaluations of the smooth component. We establish global convergence and local quadratic convergence to tilt-stable minimizers without any nondegeneracy condition, and show that the unit step is always accepted when the smooth component is quadratic, which yields a line-search-free method. The subproblems require only projections onto faces, which are explicit for the Lasso and nonnegative least squares and computable in linear time for the fused Lasso. Numerical experiments show that the method compares favorably with state-of-the-art solvers.
ER -