We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a certain distance of the exact projections (which decrease in the course of the algorithm). In particular, and in contrast to the usual projected subgradient schemes, the iterates in our method can be infeasible throughout the whole procedure and still we are able to provide conditions which ensure convergence to an optimal feasible point under suitable assumptions. Additionally, we briefly sketch two applications: finding the minimum l1-norm solution to an underdetermined linear system, an important problem in Compressed Sensing, and optimization with convex chance constraints.
Citation
Preprint; submitted for publication. Institute for Analysis and Algebra, Technische Universität Braunschweig, Germany; Research Group Optimization, Technische Universität Darmstadt, Germany. April 2011/April 2012/November 2012.