好幾天沒有寫東西了，今天趕緊起來補救一下，假裝自己還在認真學習凸優化哈哈哈～話不多說，我們步入今天的正題——共軛函數與偽凸函數。共軛函數在後面的介紹對偶性以及牛頓法時會涉及到，偽凸函數則在後面的內容中用得較少，主要是為了介紹一種類似於凸函數的非凸函數，由於偽凸函數與凸函數高度相似，因此求解偽凸優化問題的方法亦類似於求解凸優化問題的方法。

共軛函數

共軛函數定義與示例

假設 f:mathbf{R}^n ightarrow mathbf{R}，函數 f^*:mathbf{R} ightarrow mathbf{R} ,如果函數 f 與函數 f^* 之間滿足如下關係：

f^{*}(y)=sup_{xin dom f}{y^Tx-f(x)}

則稱 f^* 為函數 f 的共軛函數。共軛函數 f^* 的定義域是使得上式中 sup 結果小於 infty的部分。從共軛函數的定義來看，共軛函數的幾何意義是對於給定的 y ，共軛函數值 f^*(y) 等於線性函數 y^Tx 與原函數 f(x) 差的最大值。共軛函數的幾何意義可以使用下圖表示：

我們可以很容易地發現， f^*(y) 是凸函數。因為對於確定的 x ， f(x) 是定值，而 y^Tx 是關於 y 的線性函數，而 sup 運算在之前的介紹中已經介紹了，是保凸的運算，因此f^*(y) 是凸函數。這一點與 f(x) 是否是凸函數無關。下面我們推導一些常見函數的共軛函數表達式。

共軛函數示例

  1. 一些定義在 mathbf{R} 上的函數的共軛函數
  • 仿射函數： f(x)=ax+b 的共軛函數為：

f^*(y)=sup yx-ax-b

從共軛函數的幾何意義，很容易地可以驗證，如果 y eq a ，那麼 f^*(y) = infty ，當 y = a 時， f^*(y) = -b ;

  • 負對數：函數 f(x)=-log x 的共軛函數為：

f^*(y) = sup_{x>0} yx - logx

對於固定的 y ,令 yx - logx 對 x 的導數為0，可以求得 y^* = frac{1}{x} ，將 y^* 帶入上式，可得 f^*(y) = -log(-y) - 1

  • 指數函數：函數 f(x)=e^x 的共軛函數為：

f^*(y) = sup yx - e^x

對於固定的 y ,令 yx - e^x 對 x 的導數為0，可以求得 y^* = log x ,將 y^* 帶入上式，可得 f^*(y) = ylog y-y

  • 負熵：函數 f(x)=xlogx 當共軛函數為：

f^*(y) = yx - xlogx

對於固定的 y ,令 yx - xlogx 對 x 的導數為0，可以求得 y^* = 1 + logx ,將 y^* 帶入上式，可得 f^*(y) = e^{y-1}

  • 分數函數：函數 f(x) = frac{1}{x} 的共軛函數為：

f^*(y) = sup yx - frac{1}{x}

對於固定的 y ,令 yx - xlogx 對 x 的導數為0，可以求得 y^* = -frac{1}{x^2} ，將 y^* 帶入上式，可得 f^*(y) = -2(-y)^{-frac{1}{2}}

2. 一些定義在 mathbf{R}^n 上的函數的共軛函數

  • 二次函數（Quadratic Function）：函數 f(x)=frac{1}{2}x^TQx , Qin mathbf{S}_{+}^n 的共軛函數為： f^*(y) = sup y^Tx-frac{1}{2}x^TQx

對於固定的 y ,令 y^Tx-frac{1}{2}x^TQx 對 x 的梯度為0，可得 x^* = Q^{-1}y ，將 x^* 帶入上式，可得： f^*(y)=y^TQ^{-1}y-frac{1}{2}y^TQ^{-1}QQ^{-1}y=frac{1}{2}y^TQ^{-1}y

  • Log-sum-exp函數：函數 f(x) = log(sum_{i=1}^{n}e^{x_i}) 的共軛函數為：

f^*(y) = sup y^Tx-log(sum_{i=1}^{n}e^{x_i})

上式當 y^*_i=frac{e^{x_i}}{sum_{i=1}^{n}e^{x_i}} 時取最大值，因此 x^*_i = logy_i + log (sum_{i=1}^{n}e^{x_i}) 帶入上式可得：

f^*(y) = sum_{i=1}^{n}y_ilogy_i + sum_{i=1}^{n}y_ilog(sum_{i=1}^{n}e^{x_i})-log(sum_{i=1}^{n}e^{x_i})=sum_{i=1}^{n}y_ilogy_i +log(sum_{i=1}^{n}e^{x_i})(log(sum_{i=1}^{n}y_i-1)

於是我們得到，當 sum_{i=1}^{n}y_i=1,y_ige0 (0log0equiv0) 時，Log-sum-exp函數的共軛函數時負熵函數 f^*(y) = sum_{i=1}^{n}y_ilogy_i

  • 範數（Norm）:函數 f(x)=||x||_p 的共軛函數為：

f^*(y)=egin{cases} 0, ||y||_*le1\ infty, otherwise end{cases}

其中， ||y||_* 表示函數 ||cdot||_p 的對偶範數。

共軛函數的性質

  • Fenchel不等式:由共軛函數的定義，我們可以馬上得到：

f(x)+f^*(y)ge y^Tx

  • 共軛的反身性：如果函數 f(x) 是凸函數，那麼 f^{**}(x)=f(x) ，即凸函數共軛的共軛還是其本身
  • 線性變換複合函數的共軛：對於 a>0 ，函數 g(x)=af(x)+b 的共軛函數為 g^*(y) = af^*(y/a)-b ，對於矢量函數的情況，對於可逆矩陣 A 以及向量 b ，函數 g(x)=f(Ax+b) 的共軛函數為： g^*(y)=f(A^{-T}y)-b^TA^{-T}y

偽凸函數（Quasiconvex Functions）

定義與示例

函數 f:mathbf{R}^n ightarrow mathbf{R} 被稱為偽凸函數當且僅當它的定義域以及所有的子水平集：

S_{alpha}={x|f(x)le alpha}

都是凸集。一個函數是偽凹函數當且僅當它的反函數是偽凸函數，一個函數如果即是偽凸函數又是偽凹函數，那麼稱這個函數為偽線性的。凸函數的定義域與所有子水平集都是凸集，滿足偽凸函數的定義，因此所有凸函數都是偽凸的，但是反之則不然。考慮一個定義在 mathbf{R} 上的偽凸函數，其函數圖像如下：

從上圖中可以發現，該函數具有不止一個的全局最小值，但這些全局最小值都是相同的。因此，我們可以發現偽凸函數並不都是凸函數，或者說偽凸函數是凸函數的拓展。

下面我們展示一些定義在 mathbf{R} 上的偽凸函數例子。

  • 對數函數： log x 是偽凸函數，同時也是偽凹函數（因此是偽線性函數）；

向上取整函數： ceil(x) = inf{zin mathbf{Z}|zge x} 是偽凸函數，同時也是偽凹函數（因此是偽線性的）

上面兩個例子說明了偽凸函數可能是凹函數，也可能是不連續函數。

下面我們來看幾個定義在 mathbf{R}^n 上的偽函數的例子。

  • 向量長度：定義向量的長度等於向量中非零元素的最大下標：

f(x)=max{i|x_i eq0}

該函數是偽凸的，因為它的所有子水平集：

f(x)le alpha Leftrightarrow x_i=0 , i=lfloor alpha floor + 1,...,n

是 mathbf{R}^n 空間的子空間，是凸集。

  • 線性分數函數（linear fractional function）:函數

f(x) = frac{a^Tx+b}{c^Tx+d} dom f = {x| c^Tx+d > 0}

是偽凸函數，也是偽凹函數，因此是偽線性函數。首先，其定義域 dom f = {x| c^Tx+d > 0} 是一個半空間，因此是一個凸集。其次，它的任意子水平集：

egin{align} S_{alpha} &= {x| c^Tx+d > 0, (a^Tx+b)/(c^Tx + d) le alpha}\ &={x|c^Tx+d>0, a^Tx+b le alpha(c^Tx + d)} end{align}

是一個凸集。類似的還可以證明它的任意超水平集（superlevel set）也是凸集，因此該函數既是偽凸的，又是偽凹的，因此是偽線性的。

  • 距離比函數：假設 a,bin mathbf{R}^n ，那麼函數：

f(x) = frac{||x-a||_2}{||x-b||_2}

當 x 滿足 ||x-a||_2 le ||x-b||_2 時是偽凸函數。考慮該函數的 alpha 子水平集，因為 ||x-a||_2 le ||x-b||_2 成立，因此必然有 alpha le 1 ，因此alpha 子水平集等價於找到不等式：

||x-a||_2 le alpha||x-b||_2

的解。將不等式兩邊同時平方，可得：

(1 - alpha)^2 x^Tx -2(a - a^2b)^Tx+a^T a-a^2b^Tble0

上式當 alpha le 1 時表示了一個歐氏空間中的一個球，因此是凸集。因此證明了距離比函數是偽凸函數。

基本性質

從偽凸函數的定義，我們可以發現偽凸函數與凸函數之間有很多相似性，許多凸函數的性質都可以類比到偽凸函數中。

  • 廣義詹森不等式：如果函數 f(x) 是偽凸函數，那麼有下式成立：

f( heta x + (1 - heta)y) le min{f(x), f(y)}

類比凸函數對應的詹森不等式，可以發現二者在不等式右邊有所區別。該不等式可以使用下圖作一個形象的闡釋。

  • mathbf{R} 上的偽凸函數：定義在mathbf{R} 上的偽凸函數必須至少滿足一下三個性質之一：
  1. 非遞減；
  2. 非遞減；
  3. 存在一個點 c ，當 x<c 時函數非遞增，當 x > c 時函數非遞減，即 c 是全局最小值對應的點

下圖形象地說明了該性質：

可微的偽凸函數

一階條件

如果函數 f(x) 是偽凸函數，那麼有下式成立：

f(y) - f(x) Rightarrow abla f(x)^T(y - x) le 0

回顧凸函數的一階條件：

f(x) + abla f(x)^T(y - x) le f(y)

可以發現，偽凸函數的一階條件可以直接從凸函數的一階條件得到：

abla f(x)^T (y -x) le f(y) - f(x) le 0 (f(y) le f(x))

值得注意的是，與凸函數不同，對於凸函數而言， abla f(x)=0 的位置就是global minimizer，但是對於偽凸函數而言 abla f(x) =0 的位置不一定是global minimizer。這一點可以從偽凸函數的示例圖中看出。

二階條件

與凸函數的二階條件類似，偽凸函數成立的二階條件是：

y^T abla f(x) =0 Rightarrow y^T abla^2f(x) y ge 0

對於標量函數，

f(x)=0 Rightarrow f(x)ge0

即所有具有零梯度的位置都必然具有非零的曲率。

總結

本文簡要介紹了共軛函數與偽凸函數，側重二者的基本定義。共軛函數在之後的文章會多次提到，在凸優化中具有重要作用。偽凸函數可以看作是廣義的凸函數，偽凸優化問題是一類比凸優化更難的問題，因為偽凸函數在零梯度的位置不一定是全局最優，這加大了求解偽凸優化的難度。在下一章凸優化問題中將會給出求解偽凸優化問題的最基本演算法——二分查找法。偽凸優化在Convex Optimization這本書中涉及不多，對於初學者而言只要大致了解即可，在紮實學完凸優化相關內容後，遇到偽凸優化問題也可以很快學會求解思路。下一章將會介紹凸函數這一章的最後一個部分——對數凸函數與對數凹函數。

推薦閱讀：

相关文章