Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM] seminar - A Descent-Oriented Subgradient Method for Nonsmooth Optimization

In nonsmooth optimization, the absence of gradient continuity presents a fundamental challenge to the design of convergent descent methods based merely on first-order information. Classical methods, such as bundle techniques and gradient sampling, attempt to overcome this by aggregating subgradients from a local neighborhood. However, these approaches are often computationally burdensome or lack deterministic guarantees. In this talk, I will present a unifying principle behind these methods and introduce a general framework for provably convergent descent algorithms under a solely first-order oracle. Central to this framework is a simple yet powerful technique called subgradient regularization, which generates stable descent directions for a class of marginal functions using information at only a single point, effectively eliminating the need for neighborhood sampling. Notably, when applied to the composition of a convex function with a smooth map, our approach recovers the classical prox-linear method and offers a new dual perspective. I will conclude with numerical experiments showcasing the method’s effectiveness on challenging nonsmooth problems, such as the minimization of Nesterov’s Chebyshev-Rosenbrock function.