Relaxation approaches for nonlinear sparse optimization problems

Optimization, vol. 73, pp. 3237–3258

Abstract

In 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.

Authors 1

1. Sonja Steffensen corresponding Aachen Institut für Geometrie und Praktische Mathematik

   RWTH Aachen University

   Affiliation as printed

   Institut für Geometrie und Praktische Mathematik, RWTH Aachen University Aachen, Germany