Optimization Online


An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections

Dirk A. Lorenz (d.lorenz***at***tu-bs.de)
Marc E. Pfetsch (pfetsch***at***mathematik.tu-darmstadt.de)
Andreas M. Tillmann (tillmann***at***mathematik.tu-darmstadt.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.

Download: [PDF]

Entry Submitted: 04/28/2011
Entry Accepted: 04/28/2011
Entry Last Modified: 03/08/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society