Complementarity Formulations of ℓ0-norm Optimization Problems (pdf)

Mingbin Feng*, John E. Mitchell, Jong-Shi Pang, Xin Shen§, and Andreas Wächter

Pacific Journal of Optimization, Volume 14, Number 2, 273-305, 2018.

* Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA. This author is supported by National Science Foundation grant DMS-1216920. E-Mail: mingbinfeng2011@...
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. This author was supported by the National Science Foundation under Grant Number CMMI-1334327 and by the Air Force Office of Scientific Research under Grant Number FA9550-11-1-0260. E-Mail: mitchj@...
Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA. This author was supported by the National Science Foundation under Grant Number CMMI-1333902 and by the Air Force Office of Scientific Research under Grant Number FA9550-11-1-0151. E-Mail: jongship@...
§Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. This author was supported by the National Science Foundation under Grant Number CMMI-1334327 and by the Air Force Office of Scientific Research under Grant Number FA9550-11-1-0260. E-Mail: shenx5@...
Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA. This author was supported by National Science Foundation grant DMS-1216920 and grant CMMI-1334639. Email: andreas.waechter@...

Abstract

In a number of application areas, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its 0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the 1-norm. In contrast, we consider exact formulations as mathematical programs with complementarity constraints and their reformulations as smooth nonlinear programs. We discuss properties of the various formulations and their connections to the original 0-minimization problem in terms of stationarity conditions, as well as local and global optimality. We prove that any limit point of a sequence of local minimizers to a relaxation of the formulation satisfies certain desirable properties. Numerical experiments using randomly generated problems show that standard nonlinear programming solvers, applied to the smooth but nonconvex equivalent reformulations, are often able to find sparser solutions than those obtained by the convex 1-approximation.
Keywords: 0-norm minimization, complementarity constraints, nonlinear programming


Download the paper (pdf) | Optimization Online listing | Return to my list of papers | John E. Mitchell