Optimization Online


Greedy approximation in convex optimization

Vladimir Temlyakov(temlyakovv***at***gmail.com)

Abstract: We study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. The problem of approximation of a given element of a Banach space by linear combinations of elements from a given system (dictionary) is well studied in nonlinear approximation theory. At a first glance the settings of approximation and optimization problems are very different. In the approximation problem an element is given and our task is to find a sparse approximation of it. In optimization theory an energy function is given and we should find an approximate sparse solution to the minimization problem. It turns out that the same technique can be used for solving both problems. We show how the technique developed in nonlinear approximation theory, in particular, the greedy approximation technique can be adjusted for finding a sparse solution of an optimization problem.

Keywords: Greedy algorithms, convergence, rate of convergence, convex optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: University of South Carolina, June 2012.

Download: [PDF]

Entry Submitted: 06/02/2012
Entry Accepted: 06/02/2012
Entry Last Modified: 06/02/2012

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