An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections
Dirk A. Lorenz (d.lorenztu-bs.de)
Abstract: 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.
Keywords: Convex Optimization, Projected Subgradient Method, Constrained Optimization, Nonsmooth Optimization, Adaptive Approximate Projections, Basis Pursuit
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )
Category 3: Global Optimization (Theory )
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.
Entry Submitted: 04/28/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|