1.${\ell }_1$-范数的定义

给定一个向量$x=(x_1,x_2,\dots ,x_n)\in {\mathbb{R}}^n$，它的${\ell }_1$-范数定义为：

$$\Vert x{\Vert }_1=\sum _{i=1}^n|x_i|。$$
即${\ell }_1$-范数是向量的所有分量的绝对值之和。

示例
例如，给定向量$x=(3,-4,1)$，其${\ell }_1$-范数为：

$$\Vert x{\Vert }_1=|3|+|-4|+|1|=3+4+1=8。$$

2. 对偶范数的定义

在向量空间中，范数的对偶范数定义如下：

给定一个范数$\Vert \cdot \Vert$，其对偶范数$\Vert \cdot {\Vert }_{\ast }$定义为：

∥ y ∥ ∗ = sup ⁡ { y ⊤ x : ∥ x ∥ ≤ 1 } ， \|y\|_* = \sup \{ y^{\top} x : \|x\| \leq 1 \}， ∥y∥∗​=sup{y⊤x:∥x∥≤1}，

即对偶范数是所有满足$\Vert x\Vert \le 1$的$x$向量上内积$y^{\top }x$的最大值。

3.${\ell }_{\infty }$-范数的定义

对于${\ell }_1$-范数，按照上述对偶范数的定义，其对偶范数是${\ell }_{\infty }$-范数。

给定一个向量$x=(x_1,x_2,\dots ,x_n)\in {\mathbb{R}}^n$，它的${\ell }_{\infty }$-范数定义为：

$$\Vert x{\Vert }_{\infty }=\underset{i}{\max }|x_i|。$$

即${\ell }_{\infty }$-范数是向量中绝对值最大的分量。

示例

例如，给定向量$x=(3,-4,1)$，其${\ell }_{\infty }$-范数为：

$$\Vert x{\Vert }_{\infty }=\max (|3|,|-4|,|1|)=4。$$

4.${\ell }_1$-范数和${\ell }_{\infty }$-范数的对偶关系

对于任何向量空间中的范数$\Vert \cdot \Vert$，其对偶范数$\Vert \cdot {\Vert }_{\ast }$满足：

∥ x ∥ 1 = sup ⁡ { y ⊤ x : ∥ y ∥ ∞ ≤ 1 } ， \|x\|_1 = \sup \{ y^{\top} x : \|y\|_{\infty} \leq 1 \}， ∥x∥1​=sup{y⊤x:∥y∥∞​≤1}，

∥ x ∥ ∞ = sup ⁡ { y ⊤ x : ∥ y ∥ 1 ≤ 1 } 。 \|x\|_{\infty} = \sup \{ y^{\top} x : \|y\|_1 \leq 1 \}。 ∥x∥∞​=sup{y⊤x:∥y∥1​≤1}。

因此，${\ell }_1$-范数的对偶范数是${\ell }_{\infty }$-范数，而${\ell }_{\infty }$-范数的对偶范数是${\ell }_1$-范数。

5. 凸函数的定义

一个函数$f:{\mathbb{R}}^n\to \mathbb{R}$是凸的，当且仅当对于任意$x,y\in {\mathbb{R}}^n$和$\lambda \in [0,1]$，有：

$$f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)。$$

我们需要验证，对于$f(x)=\Vert x{\Vert }_{\infty }$而言，上述不等式是成立的。

6.证明无穷范数是凸函数

设$f(x)=\Vert x{\Vert }_{\infty }={\max }_{i=1,\dots ,n}|x_i|$。我们要证明，对于任意的$x,y\in {\mathbb{R}}^n$和$\lambda \in [0,1]$，有

$$\Vert \lambda x+(1-\lambda )y{\Vert }_{\infty }\le \lambda \Vert x{\Vert }_{\infty }+(1-\lambda )\Vert y{\Vert }_{\infty }。$$

第一步：展开左边的表达式

根据${\ell }_{\infty }$-范数的定义，

$$\Vert \lambda x+(1-\lambda )y{\Vert }_{\infty }=\underset{i=1,\dots ,n}{\max }|\lambda x_i+(1-\lambda )y_i|。$$

第二步：应用三角不等式

利用三角不等式证明无穷范数是凸函数，对于任意$i$，我们有

$$|\lambda x_i+(1-\lambda )y_i|\le |\lambda x_i|+|(1-\lambda )y_i|。$$

再进一步拆分，可以得到

$$|\lambda x_i|+|(1-\lambda )y_i|=\lambda |x_i|+(1-\lambda )|y_i|。$$

因此，对于每个$i$都有

$$|\lambda x_i+(1-\lambda )y_i|\le \lambda |x_i|+(1-\lambda )|y_i|。$$

第三步：取最大值

我们需要将上面的不等式应用到所有分量，并取最大值：

$$\underset{i=1,\dots ,n}{\max }|\lambda x_i+(1-\lambda )y_i|\le \underset{i=1,\dots ,n}{\max }\left(\lambda |x_i|+(1-\lambda )|y_i|\right)。$$

利用最大值的性质，可以分开最大操作：

$$\underset{i=1,\dots ,n}{\max }\left(\lambda |x_i|+(1-\lambda )|y_i|\right)\le \lambda \underset{i=1,\dots ,n}{\max }|x_i|+(1-\lambda )\underset{i=1,\dots ,n}{\max }|y_i|。$$

即

$$\Vert \lambda x+(1-\lambda )y{\Vert }_{\infty }\le \lambda \Vert x{\Vert }_{\infty }+(1-\lambda )\Vert y{\Vert }_{\infty }。$$

结论

我们已经证明，对于任意$x,y\in {\mathbb{R}}^n$和$\lambda \in [0,1]$，有

$$\Vert \lambda x+(1-\lambda )y{\Vert }_{\infty }\le \lambda \Vert x{\Vert }_{\infty }+(1-\lambda )\Vert y{\Vert }_{\infty }。$$

因此，${\ell }_{\infty }$-范数$\Vert x{\Vert }_{\infty }$是一个凸函数。

7.证明${\ell }_1$-范数是凸函数

我们使用三角不等式来证明${\ell }_1$-范数是凸的。

对于任意$x,y\in {\mathbb{R}}^n$和$\lambda \in [0,1]$，我们有

$$\Vert \lambda x+(1-\lambda )y{\Vert }_1=\sum _{i=1}^n|\lambda x_i+(1-\lambda )y_i|。$$
根据三角不等式，

$$|\lambda x_i+(1-\lambda )y_i|\le \lambda |x_i|+(1-\lambda )|y_i|。$$
因此，

$$\Vert \lambda x+(1-\lambda )y{\Vert }_1=\sum _{i=1}^n|\lambda x_i+(1-\lambda )y_i|\le \sum _{i=1}^n\left(\lambda |x_i|+(1-\lambda )|y_i|\right)。$$
将右侧的求和符号展开，我们得到：

$$\Vert \lambda x+(1-\lambda )y{\Vert }_1\le \lambda \sum _{i=1}^n|x_i|+(1-\lambda )\sum _{i=1}^n|y_i|=\lambda \Vert x{\Vert }_1+(1-\lambda )\Vert y{\Vert }_1。$$
这表明$\Vert x{\Vert }_1$满足凸函数的定义，因此${\ell }_1$-范数是一个凸函数。