Nonsmooth, nonconvex inverse problems arise in a wide range of fields, from PDE-constrained optimization to machine-learning applications. These objectives often have composite structure: an objective that minimizes data misfit and a regularizer that controls model complexity. These regularizers are often nonsmooth or discontinuous, while expensive cost functions must be evaluated inexactly for numerical efficiency. We develop and analyze efficient relaxation algorithms that take advantage of this composite structure and illustrate their performance on seismic interpolation and denoising problems. This work is then extended to the trust-region setting for nonlinear objectives. We conclude by proposing new directions that enable large-scale implementation of these algorithms, such as leveraging inexact evaluations of gradients and operators as well as mixed-precision arithmetic in next-generation hardware.
