Publications

Nonsmooth Newton methods with effective subspaces for polyhedral regularization

Tran T. A. Nghia, Nghia V. Vo, and Khoa V. H. Vu

Mathematics of Operations Research, to appear (accepted September 2026)

Abstract

We develop nonsmooth Newton methods for convex composite problems \(\min_x f(x) + g(x)\), where \(f\) is smooth and \(g\) is a polyhedral regularizer such as the \(\ell_1\) norm, the \(\ell_\infty\) norm, the sorted \(\ell_1\) (OSCAR/SLOPE) norm, or the one-dimensional total variation. The Newton step is computed on an effective subspace built from first-order information about the regularizer, so no generalized Hessian of \(g\) is needed. When the minimizer is tilt-stable, the methods converge quadratically, without requiring strict complementarity. Experiments on Lasso, generalized Lasso, OSCAR-regularized least squares, and an image super-resolution task show faster convergence than first-order methods and several recent nonsmooth Newton methods.

Cite

Tran T. A. Nghia, Nghia V. Vo, and Khoa V. H. Vu. Nonsmooth Newton methods with effective subspaces for polyhedral regularization. Mathematics of Operations Research, to appear. arXiv:2511.16514.

@article{NghiaVoVu2026Newton,
  title   = {Nonsmooth {N}ewton methods with effective subspaces for polyhedral regularization},
  author  = {Nghia, Tran T. A. and Vo, Nghia V. and Vu, Khoa V. H.},
  journal = {Mathematics of Operations Research},
  note    = {To appear. arXiv:2511.16514},
  year    = {2026}
}