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