Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms

This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinatewise optimality. These conditions are then used to der...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2013-01, Vol.23 (3), p.1480-1509
Main Authors: Beck, Amir, Eldar, Yonina C
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Computer engineering
Convergence
Fourier transforms
Mathematical analysis
Mathematical models
Methods
Nonlinearity
Optimality criteria
Optimization
Projection
Semiconductor research
Signal processing
Sparsity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinatewise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method, while the remaining two algorithms are of a coordinate descent type. The theoretical convergence of these techniques and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples. [PUBLICATION ABSTRACT]
ISSN:1052-6234
1095-7189
DOI:10.1137/120869778