On Integer and MPCC Representability of Affine Sparsity

In addition to sparsity, practitioners of statistics and machine learning often wish to promote additional structures in their variable selection process to incorporate prior knowledge. Borrowing the modeling power of linear systems with binary variables, many of such structures can be faithfully modeled as so-called affine sparsity constraints (ASC). In this note we study conditions under which an ASC system can be represented by sets in integer programs and mathematical programs with complementarity conditions (MPCC). Results of this note facilitate developing nonconvex optimization methods for variable selection with structured sparsity.

Citation

Working paper, Department of Mathematics and Statistics, Washington State University

Article

Download

View On Integer and MPCC Representability of Affine Sparsity