Abstract

The so-called ℓ0\ell_0 pseudonorm on Rd\mathbb{R}^d counts the number of nonzero components of a vector. It is well-known that the ℓ0\ell_0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, ECapra, that has the property of being constant along primal rays like the ℓ0\ell_0 pseudonorm. The coupling ECapra belongs to the class of one-sided linear couplings, that we introduce; we show that they induce conjugacies that share nice properties with the classic Fenchel conjugacy. For the ECapra conjugacy, induced by the coupling ECapra, we relate the ECapra conjugate and biconjugate of the ℓ0\ell_0 pseudonorm, the characteristic functions of its level sets and the sequence of so-called top-k norms. In particular, we prove that the ℓ0\ell_0 pseudonorm is equal to its biconjugate: hence, the ℓ0\ell_0 pseudonorm is ECapra-convex in the sense of generalized convexity. As a corollary, we show that there exists a proper convex lower semicontinuous function on Rd\mathbb{R}^d such that this function and the ℓ0\ell_0 pseudonorm coincide on the Euclidian unit sphere. This hidden convexity property is somewhat surprising as the ℓ0\ell_0 pseudonorm is a highly nonconvex function of combinatorial nature. We provide different expressions for this proper convex lower semicontinuous function, and we give explicit formulas in the two-dimensional case.

Author information

Contact details are reproduced from the original publication and may be historical.

Jean-Philippe Chancelier

CERMICS, École des Ponts, Marne-la-Vallée, France

Keywords

  • l-0-pseudonorm
  • coupling
  • Fenchel-Moreau conjugacy
  • top-k norms
  • k-support norms
  • hidden convexity

Mathematics Subject Classification

46N10, 49N15, 46B99, 52A41, 90C46

References

  1. A. Argyriou, R. Foygel, N. Srebro: Sparse prediction with the k-support norm, in: Proceedings of the 25th International Conference on Neural Information Processing Systems, Volume 1, NIPS’12, Curran Associates, Red Hook (2012) 1457–1465.Google Scholar
  2. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., CMS Books in Mathematics, Springer, Berlin (2017).https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  3. A. Ben-Tal, M. Teboulle: Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program. 72 (1996) 51–63.https://doi.org/10.1007/BF02592331Google Scholar
  4. J.-P. Chancelier, M. De Lara: Constant along primal rays conjugacies and the l0 pseudonorm, Optimization, preprint hal-02459673, arXiv: 2001.11828 (2020).https://doi.org/10.1080/02331934.2020.1822836Google Scholar
  5. J.-P. Chancelier, M. De Lara: Variational formulations for the l0 pseudonorm and applications to sparse optimization, preprint hal-02459688, arXiv: 2002.01314 (2020).Google Scholar
  6. J.-B. Hiriart-Urruty: Optimisation et Analyse Convexe, Presses Universitaires de France, Paris (1998).Google Scholar
  7. J.-B. Hiriart-Urruty, H. Le: A variational approach of the rank function, TOP 21(2) (2013) 207–240.https://doi.org/10.1007/s11750-013-0283-yGoogle Scholar
  8. J.-B. Hiriart-Ururty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  9. J. E. Martínez-Legaz: Generalized convex duality and its economic applications, in: Handbook of Generalized Convexity and Generalized Monotonicity, N. Hadjisavvas, S. Komlósi, S. S.Schaible (eds.), Nonconvex Optimization and its Applications Vol. 76, Springer, Berlin (2005) 237–292.https://doi.org/10.1007/0-387-23393-8_6Google Scholar
  10. J. J. Moreau: Inf-convolution, sous-additivité, convexité des fonctions numériques, J. Math. Pures Appl. (9) 49 (1970) 109–154.Google Scholar
  11. R. T. Rockafellar: Conjugate Duality and Optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia (1974).Google Scholar
  12. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  13. T. R. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  14. A. Rubinov: Abstract Convexity and Global Optimization, Nonconvex Optimization and its Applications 44, Kluwer Academic Publishers, Dordrecht (2000).https://doi.org/10.1007/978-1-4757-3200-9Google Scholar
  15. I. Singer: Abstract Convex Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, New York (1997).Google Scholar
  16. K. Tono, A. Takeda, J.-y. Gotoh: Efficient DC algorithm for constrained sparse optimization, arXiv: 1701.08498 (2017).Google Scholar
  17. H. S. Witsenhausen: On policy independence of conditional expectations, Information and Control 28(1) (1975) 65–75.https://doi.org/10.1016/S0019-9958(75)90240-5Google Scholar
  18. C. Zalinescu: Convex Analysis in General Vector Spaces, World Scientific, Singapore (2002).https://doi.org/10.1142/5021Google Scholar

Suggested citation

J.-P. Chancelier, M. De Lara. “Hidden Convexity in the l_0 Pseudonorm.” Journal of Convex Analysis 28 (2021), No. 1, 203–236. https://doi.org/10.68381/jca28015

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2021. Rights now held by Banach Press.