Optimization Online


Structural Properties of Affine Sparsity Constraints

Hongbo Dong (hongbo.dong***at***wsu.edu)
Miju Ahn (mijuahn***at***usc.edu)
Jong-Shi Pang (jongship***at***usc.edu)

Abstract: We introduce a new constraint system for sparse variable selection in statistical learning. Such a system arises when there are logical conditions on the sparsity of certain unknown model parameters that need to be incorporated into their selection process. Formally, extending a cardinality constraint, an affine sparsity constraint (ASC) is defined by a linear inequality with two sets of variables: one set of continuous variables and the other set represented by their nonzero patterns. This paper aims to study an ASC system consisting of finitely many affine sparsity constraints. We investigate a number of fundamental structural properties of the solution set of such a non-standard system of inequalities, including its closedness and the description of its closure, continuous approximations and their set convergence, and characterizations of its tangent cones for use in optimization. Based on the obtained structural properties of an ASC system, we investigate the convergence of B(ouligand) stationary solutions when the ASC is approximated by surrogates of the step $\ell_0$-function commonly employed in sparsity representation. Our study lays a solid mathematical foundation for solving optimization problems involving these affine sparsity constraints through their continuous approximations.

Keywords: Sparse optimization; Nonconvex optimization; Set convergence; B(ouligand) stationary points

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- Science and Engineering (Statistics )

Citation: Dong, H., Ahn, M. & Pang, JS. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1283-3

Download: [PDF]

Entry Submitted: 04/14/2017
Entry Accepted: 04/14/2017
Entry Last Modified: 05/05/2018

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