在本篇文章中，我們討論一些保凸運算。討論保凸運算的目的在於以下兩個方面：（1）可以很方便地判斷一些函數是否是凸函數（2）利用一些簡單的凸函數中構造複雜的凸函數。

非負加權求和

如果函數 f 是凸函數，那麼對於任意 alpha ge 0 ， alpha f(x) 也是凸函數。如果 f_1，f_2 都是凸函數，那麼 f_1+f_2 也是凸函數。將二者結合，並推廣至高維可得：如果 f_1，f_2，...，f_n 是凸函數，對於 w_1，w_2，...，w_n ge 0 ，函數 f=sum_{i}w_if_i(x) 也是凸函數。

與仿射函數複合

假設 f: mathbf{R}^{n} ightarrow mathbf{R} ， Ain mathbf{R}^{n imes m} ， b in mathbf{R}^n ，定義函數 g:mathbf{R}^m ightarrow mathbf{R} ，如果函數 f是凸函數，那麼函數：

g(x)=f(Ax+b) {x|Ax + b in dom f }

也是凸函數。

逐點取最大值與上確界

如果 f_1,f_2 都是凸函數，那麼它們的逐點最大值函數 f(x)=max(f_1(x),f_2(x)) 也是凸函數。這一點可以從凸函數的定義很容易地驗證：

egin{align} f( heta x+(1 - heta)y) &= max{f_1( heta x+(1 - heta)y) ,f_2( heta x+(1 - heta)y)}\ &le max{ heta f_1(x) + (1 - heta)f_1(y), heta f_2(x) + (1 - heta)f_2(y)}\ &le heta max{f_1(x),f_2(y)}+(1- heta)max{f_1(x),f_2(y)}\ &= heta f(x) + (1 - heta)f(y) end{align}

上式中第一個不等式使用的是凸函數的定義，第二個不等式使用的是max函數的性質。該性質可以進一步推廣至多個凸函數函數的逐點最大值函數：如果 f_1(x),f_2(x),...,f_n(x) 是凸函數，那麼

f(x)=max{f_1(x),f_2(x),...,f_n(x)}

也是凸函數。

由於逐點最大值函數可以保持凸性，因此很容易地可以將其推廣至逐點上確界函數。如果對 forall y in mathcal{A} ， f(x,y) 關於 x 是凸函數，那麼 f(x,y) 關於 x 的逐點上確界函數：

g(x)=sup_{y in mathcal{A}}f(x,y)

是凸函數。 g(x) 的凸性可以從 Epigraph角度進行驗證：

mathbf{Epi} g=igcap_{y in mathcal{A}}mathbf{Epi} f(cdot, y)

由於 f(x,y) 對於給定的 y 是關於 x 的凸函數，因此 mathbf{Epi} f(cdot, y) 對給定的 y 是凸集，因此函數 g(x) 的Epigraph是一系列凸集的交集，因此 mathbf{Epi} g 也是凸集，故而函數 g(x) 是凸函數。

複合函數保凸的必要條件

複合函數在實際應用中非常常見，如果複合函數的各個子函數滿足一定條件，可以保證複合之後的函數的凸性。這一點在工程應用與科學研究中非常重要，因為工程中面對的優化目標往往比較複雜，而比較複雜的函數往往可以看成是簡單函數的複合函數，對於複雜函數直接判斷其凸性比較困難，而利用本節中介紹的條件，可以從複雜函數的簡單子函數出發，通過檢查這些簡單子函數的凸性、單調性來判斷複合函數是否是凸函數。

首先我們給出複合函數的定義：假設兩個函數： h:mathbf{R}^k ightarrow mathbf{R} 和 g:mathbf{R}^{n} ightarrow mathbf{R}^k ，則函數 h,g 的複合函數定義為：

f=h circ g=h(g(x)) dom f={xin dom g|g(x) in dom h}

下面我們將會根據外層函數 h 是標量函數與矢量函數的兩種情況分別介紹複合函數 f 是凸函數的條件。

h 是標量函數

當 h 是標量函數，即 k=1 時，不是一般性，同時假設 g(x) 也是標量函數，即 n=1 。

接下來我們使用凸函數判定的二階條件來給出函數 f 是凸函數的條件。假設f,h,g 是二階可微函數，根據複合函數求導的鏈鎖法則，我們有：

f^{}(x)=h^{}(g(x))g^{}(x)^2+h^{}(g(x))g(x)

若 f 是凸函數，那麼就必須有：

f^{}(x)geq0

現在假設 g(x) 是凸函數， h(x) 是凸函數同時滿足非遞減性，則此時 f^{}(x)geq0 ，即函數 f 是凸函數。類似於這種方法，我們還可以得到以下結論：

  • 若g(x) 是凸函數， h(x) 是凸函數同時滿足非遞減性，則函數 f 是凸函數；
  • 若g(x) 是凹函數， h(x) 是凸函數同時滿足非遞增性，則函數 f 是凸函數；
  • 若g(x) 是凸函數， h(x) 是凹函數同時滿足非遞增性，則函數 f 是凹函數；
  • 若g(x) 是凹函數， h(x) 是凹函數同時滿足非遞減性，則函數 f 是凹函數；

利用上述複合函數的凸性判定條件，我們可以很容易地確定一些簡單複合函數的凸性：

  • 如果 g(x) 是凸函數，那麼 f(x)=exp{g(x)} 是凸函數，因為 h(x) = e^x 是凸函數且非遞減（條件一）；
  • 如果g(x) 是凹函數且恆為正數，那麼 f(x) = log g(x) 是凹函數，因為 h(x)= log x 是凹函數且非遞減（條件四）；
  • 如果g(x) 是凹函數且恆為正數，那麼 f(x) = frac{1}{g(x)} 是凸函數，因為 h(x)=frac{1}{x} 是凸函數且非遞增（條件二）；
  • 如果g(x) 是凸函數且恆為非負數，同時 pge1 ，那麼 g(x)^{p} 是凸函數。因為 h(x)=x^p 在 pge 1 時是凸函數且非遞減（條件一）；
  • 如果 g(x) 是凸函數，那麼 f(x)=-log (-g(x)) 是凸函數，因為 h(x)=-log (-x) 是凸函數且滿足非遞減性（條件一）

h 是矢量函數

在前一節中我們考慮了 k=1 的情況，現在來考慮更一般的 kge1 的情況。假設複合函數 f 可以表示為如下形式：

f(x)=h(g(x))=h(g_1(x),..,g_k(x))

其中， h:mathbf{R}^k ightarrow mathbf{R} ， g_i(x):mathbf{R}^n ightarrow mathbf{R} 。之所以假設 f(x) 具有這種特殊形式是為了方便分析，更一般的複合形式非常複雜，無法分析出有用的規則，而且很多工程中遇到的實際問題中， f(x) 都滿足這種特殊的結構。

不是一般性，這裡我們依然假定 n=1 ，此時函數 f(x)是一個由實數到實數的映射。假設 f(x) 的二階導數存在，其可以表示為：

f^{}(x)=g^{}(x)^T abla^2h(g(x))g^{}(x)+ abla h(g(x))g^{}(x)

類似於前一節中的討論，也可以得到一些關於判定 f(x) 凹凸性的規則，例如：

  • 如果 g_i(x) 是凸函數（ g^{}(x)ge0 ），且 h(x) 是凸函數（ abla^2h(x)in mathbf{S}_{+}^k）同時 h(x) 的每一個維度都是非遞減的（ abla h(x)succeq0 ），那麼f(x)是凸函數；
  • 如果 g_i(x) 是凹函數（ g^{}(x)le0 ），且 h(x) 是凸函數（ abla^2h(x)in mathbf{S}_{+}^k）同時 h(x) 的每一個維度都是非遞增的（ abla h(x)preceq0 ），那麼f(x)是凸函數；
  • 如果 g_i(x) 是凹函數（ g^{}(x)ge0 ），且 h(x) 是凹函數（- abla^2h(x)in mathbf{S}_{+}^k）同時 h(x) 的每一個維度都是非遞減的（ abla h(x)succeq0 ），那麼f(x)是凹函數；

下面給出一些當 h(x) 是矢量函數時判斷複合函數 f(x) 凹凸性的例子。

  • 函數 h(x)=log(sum_{i=1}^n e^{z_i}) 是log-sum-exp函數，在前一篇文章中已經介紹過，它是一個凸函數，同時關於每一個維度它都是非遞減的，因此當 g_i(x) 是凸函數時， f(x)=log(sum_{i=1}^n e^{g_i(x)}) 是凸函數（條件一）。
  • 函數 h(x)=(sum_{i=1}^{k}z_i^p)^{frac{1}{p}} 當 0< p<1 時是凹函數，同時關於每一分量都是非遞減的，因此如果 g_i(x) 是凹函數且取值飛度，那麼函數 f(x)=(sum_{i=1}^{k}g_i(x)^p)^{frac{1}{p}} 是凹函數（條件三）

逐點取最小值與下確界

之前已經說明了逐點取最大值與上確界是一種保凸運算，與之對應的，逐點取最小值與下確界也是保凸運算。假設函數 f 是凸函數， C 是一個非空凸集，那麼函數：

g(x) = inf_{yin C}f(x,y)

是一個凸函數。這個式子的含義是：對於給定的 x ，在凸集 C 中找一個最優的 y^* 使得 f(x,y^*) 最小。

我們可以使用下一篇中提到的詹森不等式來證明這個結論：

egin{align} g( heta x_1+(1 - heta)x_2) &= inf_{y in C}f( heta x_1+(1- heta)x_2,y)\ &le f( heta x_1+(1- heta)x_2, heta y_1+(1- heta)y_2)\ &le heta f(x_1,y_1) + (1 - heta)f(x_2,y_2)\ &le heta g(x_1) + (1- heta)g(x_2) end{align}

第一個不等式根據是 inf 運算元的性質： f(y^*) le f(y), forall yin C ，第二個不等式是詹森不等式，因為 f(x,y) 是凸函數，第三個不等式根據 g(x) 的定義。由此，我們證明了下確界函數與最小化（Minimization）是保凸運算。

函數透視（Perspective of a Function）

函數 f 的透視（perspective）被定義為函數 g:mathbf{R}^{n+1} ightarrow mathbf{R} :

g(x,t) = t f(frac{x}{t})

其中， t>0 。如果函數 f是凸函數，那麼 g(x,t) 也是凸函數。可以從Epigraph的角度證明該結論的正確性：

對於 t>0 ，

egin{align} (x,t,s) in mathbf{epi} g &Leftrightarrow tf(frac{x}{t}) le s\ &Leftrightarrow f(frac{x}{t}) le frac{s}{t}\ &Leftrightarrow frac{x}{t},frac{s}{t} in mathbf{epi} f end{align}

由此，我們發現 mathbf{epi} f 是 mathbf{epi} g 在透視變換 (u,v,w) ightarrow (frac{u}{v}, frac{w}{v}) 下的像（透視函數定義，詳情參見凸集部分有關透視函數的介紹），因為 f 是凸函數，因此mathbf{epi} f是凸集，因此mathbf{epi} f的原像mathbf{epi} g也是凸集，因此函數 g 是凸函數。

總結

本文介紹了一些對於凸函數的保凸運算，包括線性運算、最大化、最小化、透視函數，討論了凸函數的複合函數的凹凸性判斷法並舉了若干實例輔助解釋。本文涉及到的內容對於後續求解凸優化問題非常重要，也是當我們在面對優化問題時幫助我們判斷問題性質的利器，應當仔細掌握並靈活應用。下一篇文章中將會介紹共軛函數和偽凸函數，其中共軛函數在後續的優化演算法分析中具有重要作用。


推薦閱讀：
相关文章