Projected Subgradient Methods for a Class of Nonsmooth and Nonconvex Optimization Problems

Abstract

We investigate the optimization problem of minimizing a nonsmooth function that satisfies a nonsmooth version of the descent lemma over a nonempty and closed but not necessarily convex set. The objective function belongs to the class of upper-$\mathcal{C}^2$ functions, whereas the constraints may promote a sparse or low-rank structure. We propose a projected subgradient method with two different globalization strategies: (a) a nonmonotone linesearch and, under additional assumptions, (b) an auto-conditioned method, where the stepsize is given by a formula depending on data from past iterations. We show that both methods converge to solutions that satisfy a stronger stationarity concept than one would expect from the subdifferential sum-rule, which is particularly important since the optimization problems of interest are inherently nonconvex. Finally, we present promising numerical results when applying the algorithm to an MPEC-style problem as well as the matrix optimization problems MAXCUT and Robust PCA.