答Regan Yuan──關於向量範數的凸性

網友Regan Yuan留言:

老师您好,最近有些问题,还望您不吝赐教,谢谢。请问在凸优化的范畴中,范数 \ell_1 与范数 \ell_2 都是凸的(convex),这是如何证明的呢?我知道这个结论,我想学会证明的方法,了解证明的思路,请您明示。如果 f\ell_1\ell_2 的范数比值,f 是否为convex呢?怎么证明或是判断呢?如果我们将这个关系再度引申,设 f=\ell_x/\ell_y,其中 \ell_x\ell_y 是范数,如果 x=1y=2,就是上述的例子,现在 xy 均是介于 [0,+\infty),如何证明或判断 fx,y 取值于 [0,+\infty) 时的凸性呢?最近正为凸优化的问题大伤脑筋,还望老师帮我。

 
答曰:

我們先回顧凸函數 (convex function) 和 \ell_p-範數 (norm) 的定義。令 K\subset\mathbb{R}^n 為一非空凸集 (見“凸組合、凸包與凸集”),也就是說,給定任意兩點 \mathbf{x},\mathbf{y}\in K0\le\lambda\le 1,點 \lambda\mathbf{x}+(1-\lambda)\mathbf{y} 屬於 K。凸函數是指一實函數 f:K\to\mathbb{R} 滿足下列性質 (見“凸函數”):對於任意 \mathbf{x},\mathbf{y}\in K0\le\lambda\le 1

\displaystyle f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)\le \lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})

 
對於幾何座標向量 \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n,歐氏範數可推廣為 \ell_p-範數,或稱 p-範數,如下:

\displaystyle \Vert\mathbf{x}\Vert_p=\left(\sum_{i=1}^n\vert x_i\vert^p\right)^{1/p}

其中 1\le p<\infty。向量 \ell_p-範數具有下列三個性質 (見“向量範數”):

  1. 非負性:對於 \mathbf{x}\in\mathbb{R}^n\Vert\mathbf{x}\Vert_p\ge 0\Vert\mathbf{x}\Vert_p=0 僅發生於 \mathbf{x}=\mathbf{0}
  2. 正齊次性:對於任一純量 c\mathbf{x}\in\mathbb{R}^n\Vert c\mathbf{x}\Vert_p=\vert c\vert \Vert \mathbf{x}\Vert_p
  3. Minkowski 不等式:若 \mathbf{x},\mathbf{y}\in\mathbb{R}^n,則 \Vert \mathbf{x}+\mathbf{y}\Vert_p\le\Vert\mathbf{x}\Vert_p+\Vert\mathbf{y}\Vert_p

請注意,\ell_p-範數僅定義於 1\le p<\infty。當 0< p<1,Minkowski 不等式不成立,\Vert\mathbf{x}\Vert_p 未滿足向量範數要求的三角不等式,故不能稱為範數 (縱使我們仍可以計算它)。

 
隨著 p 值增大,\Vert\mathbf{x}\Vert_p 以遞減方式改變:若 0< p<q<\infty,則 \Vert\mathbf{x}\Vert_p\ge\Vert\mathbf{x}\Vert_q。證明於下:若 \mathbf{x}=\mathbf{0},命題顯然成立。考慮 \mathbf{x}\neq\mathbf{0},令 y_i=\frac{\vert x_i\vert}{\Vert\mathbf{x}\Vert_q}1\le i\le n。因此,

\displaystyle \Vert\mathbf{y}\Vert_p=\left(\sum_{i=1}^n\frac{\vert x_i\vert^p}{\Vert\mathbf{x}\Vert_q^p}\right)^{1/p}=\left(\frac{1}{\Vert\mathbf{x}\Vert_q^p}\sum_{i=1}^n\vert x_i\vert^p\right)^{1/p}=\frac{\Vert\mathbf{x}\Vert_p}{\Vert\mathbf{x}\Vert_q}

若將 p 取代為 q,則有 \Vert\mathbf{y}\Vert_q=1。寫出

\displaystyle y_i^q=\frac{\vert x_i\vert^q}{\sum_{i=1}^n\vert x_i\vert^q}\le 1

可知 y_i\le 11\le i\le n。因為 0\le p<q<\infty,推論 y_i^p\ge y_i^q1\le i\le n,即有

\displaystyle \Vert\mathbf{y}\Vert_p=\left(\sum_{i=1}^n\vert y_i\vert^p\right)^{1/p}\ge\left(\sum_{i=1}^n\vert y_i\vert^q\right)^{(1/q)(q/p)}=\left(\Vert\mathbf{y}\Vert_q\right)^{q/p}=1

故證明 \Vert\mathbf{x}\Vert_p\ge\Vert\mathbf{x}\Vert_q。下圖顯示不同 \ell_p-範數的單位圓。當 0< p<1,單位圓將朝圓心內縮為凹集。值得注意的是,若 \mathbf{x} 僅有一非零元,則對於任意 p>0q>0\Vert\mathbf{x}\Vert_p=\Vert\mathbf{x}\Vert_q (即圖中三個 \ell_p-範數單位圓的交點)。

p-norm

不同 p-範數的單位圓

 
我將你提出的三個問題稍作改寫,重述於下:

  1. 怎麼證明 \ell_p-範數,1\le p<\infty,是凸函數?
  2. f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_1}{\Vert\mathbf{x}\Vert_2} 是凸函數嗎?
  3. 對於 0<p,q<\inftyf(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_p}{\Vert\mathbf{x}\Vert_q} 是凸函數嗎?

 
問題(1):使用定義即可證明 \ell_p-範數 \Vert\mathbf{x}\Vert_p1\le p<\infty,是一個凸函數。對於 \mathbf{x},\mathbf{y}\in\mathbb{R}^n0\le\lambda\le 1,根據正齊次性和 Minkowski 不等式,立得

\displaystyle\begin{aligned} \Vert \lambda\mathbf{x}+(1-\lambda)\mathbf{y}\Vert_p&\le\Vert\lambda\mathbf{x}\Vert+\Vert(1-\lambda)\mathbf{y}\Vert_p\\ &=\lambda\Vert\mathbf{x}\Vert_p+(1-\lambda)\Vert\mathbf{y}\Vert_p. \end{aligned}

0< p<1\Vert\mathbf{x}\Vert_p 不是一個凸函數,因為 Minkowski 不等式不復成立。

 
問題(2):一般而言,兩個凸函數的比率未必是凸函數。很容易舉例證明 f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_1}{\Vert\mathbf{x}\Vert_2} 是一非凸函數。譬如,\mathbf{x}=(1,0)\mathbf{y}=(0,1),則有 \frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}=(\frac{1}{2},\frac{1}{2})。計算可得

\displaystyle f\left(\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}\right)=\frac{\frac{1}{2}+\frac{1}{2}}{\sqrt{\frac{1}{4}+\frac{1}{4}}}=\sqrt{2}

但是

\displaystyle \frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{y})=\left(\frac{1}{2}\right)\frac{1+0}{\sqrt{1+0}}+\left(\frac{1}{2}\right)\frac{0+1}{\sqrt{0+1}}=1

f(\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y})>\frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{y}),表明 f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_1}{\Vert\mathbf{x}\Vert_2} 是一非凸函數。

 
問題(3):f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_p}{\Vert\mathbf{x}\Vert_q}0<p,q<\infty,不是凸函數。無論 pq 如何選擇,我們都可以找到例子證明 f 是一非凸函數。若 p<q,如前例,只要令 \mathbf{x}\mathbf{y} 為不同的標準單位向量即可。若 p>q,譬如,p=2q=1,即 f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_2}{\Vert\mathbf{x}\Vert_1},我們可以反過來做。設 \mathbf{x}=(1,1)\mathbf{y}=(1,-1),則有 \frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}=(1,0) 為標準單位向量。計算可得

\displaystyle f\left(\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}\right)=\frac{\sqrt{1+0}}{1+0}=1

但是

\displaystyle \frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{y})=\left(\frac{1}{2}\right)\frac{\sqrt{1+1}}{1+1}+\left(\frac{1}{2}\right)\frac{\sqrt{1+1}}{1+1}=\frac{\sqrt{2}}{2}

f(\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y})>\frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{y}),證明 f(\mathbf{x})=\frac{\Vert\mathbf{x}\Vert_2}{\Vert\mathbf{x}\Vert_1} 不是一個凸函數。

This entry was posted in 答讀者問, 線性代數專欄, 二次型 and tagged , . Bookmark the permalink.

3 則回應給 答Regan Yuan──關於向量範數的凸性

  1. Regan Yuan 說:

    谢谢老师的精心讲解,令我受益很多,请问对于相关矩阵R而言如果我用的数据X都是实数矩阵,那么R应该都是实对称正定的吗?有没有特殊的例子?

  2. Regan Yuan 說:

    我是说有没有特殊的情况使得R不是正定,或实数对称的呢?再次谢谢老师的指教

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s