The Capra-subdifferential of the ℓ 0 pseudonorm
Adrien Le Franc, Jean‐Philippe Chancelier, Michel De Lara · Optimization · 2022
The ℓ0 pseudonorm counts the nonzero coordinates of a vector. It is often used in optimization problems to enforce the sparsity of the solution. However, this function is nonconvex and noncontinuous, and optimization problems formulated with ℓ0 – be it in the objective function or in the constraints – are hard to solve in general. Recently, a new family of coupling functions – called Capra (constant along primal rays) – has proved to induce relevant generalized Fenchel-Moreau conjugacies to handle the ℓ0 pseudonorm. In particular, under a suitable choice of source norm on Rd – used in the definition of the Capra coupling – the function ℓ0 is Capra-subdifferentiable, hence is Capra-convex. In this article, we give explicit formulations for the Capra-subdifferential of the ℓ0 pseudonorm, when the source norm is a ℓp norm with p∈[1,∞]. We illustrate our results with graphical visualizations of the Capra-subdifferential of ℓ0 for the Euclidean source norm.