An Inexact Trust-Region Algorithm for Nonsmooth Nonconvex Regularized Problems

Robert Baraldi
Sandia National Labs

Many inverse problems require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoise applications in data science require minimizing a measure of data misfit plus an L1-regularizer. Similar problems arise in the optimal control of partial differential equations (PDEs) when sparsity of the control is desired. For such applications, it is often impossible to compute exact derivatives or function values due to problem size and complexity. We develop a novel inexact trust-region method to minimize the sum of a smooth nonconvex function and a nonsmooth convex function. The trust-region routine permits and systematically controls the use of inexact objective function and derivative evaluations. When using a quadratic Taylor model for the trust-region subproblem, our algorithm is an inexact, matrix-free proximal Newton-type method that permits indefinite Hessians. Using unconstrained and convex constrained trust-region methods as motivation, we describe various methods for efficiently solving the nonsmooth trust-region subproblem. We also prove global convergence of our method in Hilbert space and demonstrate its efficacy on three examples from data science and PDE-constrained optimization.