Spectral Methods and VU-theory for nonsmooth convex optimization

Achieving superlinear convergence in nonsmooth optimization remained an open problem for long after its appearance in the smooth framework. However, in the year 2000, VU theory was launched [The U-Lagrangian of a convex function (2000)] in a paper which included a conceptual superlinearly convergent algorithm for minimizing certain nonsmooth functions. This theory consists of taking advantage of functions whose nonsmoothness comes in a "structured" manner; it is able to decompose the space into two orthogonal subspaces: the V-space, which encompasses all of the function's nonsmoothness and the U-space, in which we are able to get a second order expansion of the function under mild assumptions and a Newton or quasi-Newton step is possible. Since then, there were significant advances in the theory, leading to the development of practical algorithms, the most recent of which deals with composite problems [Proximal gradient VU method with superlinear convergence for nonsmooth convex optimization (2025)]. We propose a new approach to exploit composite and additive structures that combines elements of the spectral gradient [The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem (1997)] and VU algorithms. We investigate the behavior of our proposal in a few examples, and compare its performance with that of different approaches, original VU, spectral proximal point, and proximal gradient algorithms.