Constant along primal rays conjugacies and the l0 pseudonorm. (1st February 2022)

• Record Type: Journal Article
• Authors: Chancelier, Jean-Philippe; De Lara, Michel
• Is Part Of: Optimization. Volume 71:Number 2(2022)
• Page Start: 355
• Page End: 386
• Publication Date: 2022-02-01
• Subjects: ℓ0 pseudonorm -- Fenchel–Moreau conjugacy -- Capra conjugacy -- coordinate-k norm; 46N10 -- 49N15 -- 46B99 -- 52A41 -- 90C46; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1822836
• Languages: English
• ISSNs: 0233-1934

Abstract

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.