How to Globally Solve Non-convex Optimization Problems Involving an Approximate ℓ0 Penalization

Abstract

For dealing with sparse models, a large number of continuous approximations of the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> penalization have been proposed. However, the most accurate ones lead to non-convex opti-mization problems. In this paper, by observing that many such approximations are piecewise rational functions, we show that the original optimization problem can be recast as a multivariate polynomial problem. The latter is then globally solved by using recent optimization methods which consist of building a hierarchy of convex problems. Finally, experimental results illustrate that our method always provides a global optimum of the initial problem for standard ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> approximations. This is in contrast with existing local algorithms whose results depend on the initialization.