An infeasible-point subgradient method using adaptive approximate projections

Abstract. We propose a new subgradient method for the minimization of nonsmooth convex functions over a convex set. To speed up compu-tations we use adaptive approximate projections only requiring to move within a certain distance of the exact projections (which decreases in the course of the algorithm). In particular, the iterates in our method can be infeasible throughout the whole procedure. Nevertheless, we provide con-ditions which ensure convergence to an optimal feasible point under suit-able assumptions. One convergence result deals with step size sequences that are fixed a priori. Two other results handle dynamic Polyak-type step sizes depending on a lower or upper estimate of the optimal ob-jective function value, respectively. Additionally, we briefly sketch two applications: Optimization with convex chance constraints, and finding the minimum `1-norm solution to an underdetermined linear system, an important problem in Compressed Sensing