Relaxation approaches for nonlinear sparse optimization problems

AbstractIn many recent applications, sparse solutions of the optimization problems are favoured over non-sparse solutions with comparable objective values. A standard method to induce the sparsity of the solution is based on the use of the ℓ0 norm in the objective. However, if the underlying optimization problem is nonlinear, the solution of the nonlinear (sparse) ℓ0-optimization problem is difficult. Therefore, it is often approximated using the convex ℓ1-norm although this can lead to suboptimal solutions for the sparsity of the solution. In this paper, we follow another direction. We present exact reformulations (with respect to the ℓ0 norm) and their relaxations leading to standard nonlinear but nonconvex programmes. We discuss and relate the relations between the different reformulations with repect to the original problem. We accompany our theoretical results by some numerical tests using randomly generated datasets.Keywords: Sparse optimizationnonlinear programmingcomplementarity constraintsmixed-integer nonlinear programming Disclosure statementNo potential conflict of interest was reported by the author(s).