Constant along primal rays conjugacies and the l0 pseudonorm. (1st February 2022) - Chancelier, Jean-Philippe; De Lara, Michel
Abstract : The so-called ℓ 0 pseudonorm on R d counts the number of nonzero components of a vector. For exact sparse optimization problems – with the ℓ 0 pseudonorm standing either as criterion or in the constraints – the Fenchel conjugacy fails to provide relevant analysis. In this paper, we display a class of conjugacies that are suitable for the ℓ 0 pseudonorm. For this purpose, we suppose given a (source) norm on R d . With this norm, we define, on the one hand, a sequence of so-called coordinate- k norms and, on the other hand, a coupling between R d and itself, called Capra (constant along primal rays). Then, we provide formulas for the Capra-conjugate and biconjugate, and for the Capra subdifferentials, of functions of the ℓ 0 pseudonorm, in terms of the coordinate- k norms. As an application, we provide a new family of lower bounds for the ℓ 0 pseudonorm, as a fraction between two norms, the denominator being any norm.