# On the unit hypercube, the tightest convex relaxation of the $\ell_0$ pseudonorm is the $\ell_1$ norm

Nils Foix-Colonier, Sébastien Bourguignon

<figure><img src="image_1.png" /></figure>

## To cite this version:

Nils Foix-Colonier, Sébastien Bourguignon. On the unit hypercube, the tightest convex relaxation of the $\ell_0$ pseudonorm is the $\ell_1$ norm. 2025. hal-05422973

HAL Id: hal-05422973

https://hal.science/hal-05422973v1

Preprint submitted on 18 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the unit hypercube, the tightest convex relaxation of the $\ell_0$ pseudonorm is the $\ell_1$ norm

Nils Foix-Colonier¹ and Sébastien Bourguignon¹

¹Nantes Université, École Centrale Nantes, CNRS, LS2N, UMR 6004, F-44000 Nantes, France

## Abstract

Convex relaxations of cardinality-constrained optimization problems can be used in many applications requiring sparsity. We consider the case of optimization problems where the feasible domain is restricted to the unit hypercube and includes an $\ell_0$-norm cardinality constraint. Finding the tightest convex relaxation amounts to finding the convex hull of this feasible set. It is a well-known result [1] that for $K = 1$, the convex hull of the $\ell_0$ “ball” of radius $K$ on $[0, 1]^P$ is the $\ell_1$ ball of radius $K$ on $[0, 1]^P$. The property holds for any $K \in \mathbb{N}^*$, yet its proof may not be derived in the same fashion, hence this short contribution.

## 1 Notations and definitions

Let $K \in \mathbb{N}^*$, the $\ell_1$-norm ball of radius $K$ is denoted by:

$$ \mathcal{B}_K^{\ell_1} := \{ \boldsymbol{x} \in \mathbb{R}^P \mid \|\boldsymbol{x}\|_1 \le K \}. \quad (1) $$

The $\ell_0$-“norm” ball of radius $K$ is denoted by:

$$ \mathcal{B}_K^{\ell_0} := \{ \boldsymbol{x} \in \mathbb{R}^P \mid \|\boldsymbol{x}\|_0 \le K \}. \quad (2) $$

The convex hull of a set $E$ is denoted $\text{conv}(E)$. Additionally, it should be noted that:

$$ E \subset F \implies \text{conv}(E) \subseteq \text{conv}(F). \quad (3) $$

Finally, if $E$ is a convex set, then $\text{conv}(E) = E$.

## 2 Convex hull of the $\ell_0$ pseudonorm on the unit hypercube

### Proposition

$$ \text{conv}(\mathcal{B}_K^{\ell_0} \cap [0, 1]^P) = \mathcal{B}_K^{\ell_1} \cap [0, 1]^P \quad (4) $$

### Proof

1. Let $\boldsymbol{x} \in \mathcal{B}_K^{\ell_0} \cap [0, 1]^P$. Since $\boldsymbol{x}$ has a maximum of $K$ nonzero coefficients with maximal value set to 1, then $\|\boldsymbol{x}\|_1 \le K$. Consequently, $\boldsymbol{x} \in \mathcal{B}_K^{\ell_1} \cap [0, 1]^P$. In conjunction with (3), and since $\mathcal{B}_K^{\ell_1} \cap [0, 1]^P$ is convex:

$$ \text{conv}(\mathcal{B}_K^{\ell_0} \cap [0, 1]^P) \subseteq \mathcal{B}_K^{\ell_1} \cap [0, 1]^P. \quad (5) $$

2. The set $\mathcal{B}_K^{\ell_1} \cap [0, 1]^P$ may be written as a $\mathcal{H}$-polytope [2], with a finite set of $2P + 1$ linear inequalities:

$$ \mathcal{B}_K^{\ell_1} \cap [0, 1]^P = \left\{ \boldsymbol{x} \in \mathbb{R}^P \mid \forall i \in [1, P], 0 \le x_i \le 1, \sum_{i=1}^P x_i \le K \right\}. \quad (6) $$

The vertices of a polytope are the points where at least $P$ linearly independent inequalities are active [3]. Let $\mathbf{v}$ be a vertex of the considered polytope:
* If it activates the sum-to-K constraint, then at least $P-1$ other inequality constraints are activated, that is, for example, $v_i \in \{0,1\}, i = 1, \dots, P-1$. Then, the remaining coefficient $v_P = K - \sum_{i=1}^{P-1}$ is also an integer, so that $v \in \{0,1\}^P$.

* Otherwise, $P$ binary constraints must be activated, such that $v \in \{0,1\}^P$.

Thus, any vertex $v$ is an element of $\mathcal{V}$ defined by:

$$ \mathcal{V} := \left\{ \mathbf{v} \in \{0,1\}^P \mid \sum_{i=1}^{P} v_i \le K \right\} = \{ \mathbf{v} \in \{0,1\}^P \mid \|\mathbf{v}\|_0 \le K \}. \quad (7) $$

Reciprocally, any element of $\mathcal{V}$ belongs to $\mathcal{B}_K^{\ell_1} \cap [0,1]^P$ and activates at least $P$ linearly independent inequalities in (6), therefore it is a vertex of this polytope.

Clearly, $\mathcal{V} \subset \mathcal{B}_K^{\ell_0} \cap [0,1]^P$, and with (3):

$$ \mathrm{conv}(\mathcal{V}) \subseteq \mathrm{conv}(\mathcal{B}_K^{\ell_0} \cap [0,1]^P). \quad (8) $$

By definition, the convex hull of the set of vertices of a polytope is the polytope itself, consequently: $\mathrm{conv}(\mathcal{V}) = \mathcal{B}_K^{\ell_1} \cap [0,1]^P$. Thus, we showed that:

$$ \mathcal{B}_K^{\ell_1} \cap [0,1]^P \subseteq \mathrm{conv}(\mathcal{B}_K^{\ell_0} \cap [0,1]^P) \quad (9) $$

Therefore, considering (5) and (9), we proved the proposition by mutual inclusion. $\square$

<figure><img src="image_3.png" /><figcaption>Figure 1: Illustration with $P=3$ and $K=2$ that the convex hull of the $\ell_0$-pseudonorm ball with radius $K$ on $[0,1]^P$ is the $\ell_1$-norm ball with radius $K$ on $[0,1]^P$, which is also the polytope whose vertices are the binary vectors in $\{0,1\}^P$ with no more than $K$ nonzero coefficients.</figcaption></figure>

## 3 References

[1] T. Bittar, J.-P. Chancelier, and M. De Lara, “Best Convex Lower Approximations of the $\ell_0$ Pseudonorm on Unit Balls”, arXiv:2105.14983, 2021.

[2] CD Toth, J O'Rourke, JE Goodman, “Handbook of Discrete and Computational Geometry”, CRC Press, 2017.

[3] M. Conforti, G. Cornuéjols, and G. Zambelli, Integer Programming, vol. 271. in Graduate Texts in Mathematics, Springer International Publishing, 2014.