如何快速判斷目標函數的凸性？

01-03

除了利用凸函數原始定義、Hessian半正定等進行證明以外，有沒有什麼更快捷簡便的方法來判斷目標函數是否為凸呢？

應該很多人用過凸優化自動解析和轉換軟體CVX或YALMIP，沒有人好奇這背後的原理嗎？你輸入一個結構複雜，奇形怪狀的凸優化問題，為什麼這些軟體能夠準確識別凸性，並且轉化成底層solvers(SDPT3,SeDuMi,SCS)的標準形式呢？我來介紹這些背後的原理-----DCP：Disciplined Convex Programming...熟悉這背後的原理，一方面，我們自己可以像程序一樣按照套路快速地判斷一個優化問題是不是凸的，另一方面，對於一個凸優化問題，選擇最為合適的形式輸入到這些軟體中去。需要解釋一下第二點，因為凸性是與表示有關的，以及同一個凸集有多種表示形式，只有某些表示形式更適合底層solver，比如如下凸集的三種表示中，第一種表示形式上不是凸的，第二種表示是旋轉二階錐，第三種表示是半定錐。這個例子揭示了為什麼我們要對同一個問題做不同的變換，用不同的表示形式，那就是：同一個問題的不同表示形式雖然數學上等價，但是演算法上不等價！ $left{(x,y,z):x^2le yz,yge0,zge0 ight}=left{(x,y,z):frac{x^2}{y}le z,yge0,zge0 ight}=left{(x,y,z):egin{bmatrix} z x \ x y end{bmatrix}succeq 0 ight}$

先給一個結論，對於一個一般的非線性規劃，不管是理論上還是實際中，檢驗凸性幾乎都是難以完成的。特別地，判斷一個給定的多變數的四次多項式是否為凸多項式的問題是NP-hard。然而，判斷一個非線性規劃是否是DCP則毫無鴨梨。

DCP由兩部分組成[1][2]：基本的凸函數原子庫（atom library）和凸性演算規則（convexity calculus rules）。先放三張圖介紹最常見的例子吧。這些法則覆蓋了凸優化里最常見的八項運算(加減乘除指數對數最大最小)之間的凸性複合規則，所以已經是萬能法寶，能搞定大多數問題了！

具體來說，凸性演算規則包括10條頂層法則( top-level rules，如下圖)，無乘積法則（product-free rules ），符號法則（sign rules ），複合法則（ composition rules ）。無乘積法則是指避免2個凸函數相乘的表示，符號法則則是指避免兩個凸函數相減的表示，複合法則已經有不少回答介紹了，也可以參見Boyd的書籍。

熟悉這10條法則，並且看幾遍CVX的user guide，常見優化問題的凸性判定問題都可以一網打盡了！

[1] Grant M, Boyd S, Ye Y. Disciplined Convex Programming[J]. Nonconvex Optimization Its Applications, 2007, 84:155--210.

[2] Grant M C, Boyd S P. Graph Implementations for Nonsmooth Convex Programs[J]. Lecture Notes in Control Information Sciences, 2008, 371:95-110.

由於題主是做通信的，所以我從Shannon theory的角度總結一下判斷函數convexity/concavity的幾個基本技巧.

技巧1(perspective function): 若 $x ightarrow f(x)$ 是convex/concave, 則 $(x,t) ightarrow t f(x/t)$ 在 $t>0$ 上是convex/concave的。

例1: entropy $p(x) ightarrow H(X)$ 是concave的.

證明: 因為 $log(x)$ 是concave的， $(1,t) ightarrow t log(frac{1}{t})$ 是concave的. 又因為 $H(X)=int p(x) log frac{1}{p(x)}dx$ , 所以關於 $p(x)$ 是concave的.

技巧2: 複合函數的convexity/concavity, 具體參考Boyd的convex optimization第三章.

例2:固定 $p(y|x)$ , mutual information $p(x) ightarrow I(X;Y)$ 是concave的.

證明: $I(X;Y)=H(Y)-H(Y|X)=H(Y)-int p(x)H(Y|X=x)dx$

技巧3: 定義+引入輔助隨機變數.

例3: 固定 $p(y|x)$ , mutual information $p(x) ightarrow I(X;Y)$ 是concave的.

證明: 首先引入一個隨機變數 $heta$ 服從二項分布，即 $P( heta=1)=lambda, P( heta=0)=1-lambda.$ 記 $p(x| heta=1)=p_1(x), p(x| heta=0)=p_2(x)$ , 那麼 $p(x)=lambda p_1(x)+(1-lambda) p_2(x)$ . 同時 $heta ightarrow X ightarrow Y$ 滿足Markov Chain. 因此 $I(X;Y)=I(X, heta;Y)=I( heta;Y)+I(X;Y| heta)geq I(X;Y| heta)$ . 注意到 $I(X;Y| heta)=lambda I(X;Y| heta=1)+(1-lambda)I(X;Y| heta=0)$ , 證明完成。

技巧4 (降維): $f(x)$ 是convex/concave的充要條件為對於任意的 $xin dom f$ 和 $v$ , $g(t)=f(x+tcdot v)$ 是convex/concave的 (t為一個標量，並且 $x+tcdot v in dom f$ )

例4: $logdet(X)$ 在正定矩陣的集合上是concave的.

證明:

$egin{align} g(t)=logdet(X+tcdot V)\ =logdetig(X^frac{1}{2}(I+t cdot X^{-frac{1}{2}}VX^{-frac{1}{2}}) X^frac{1}{2}ig)\ =logdet(X)+logdet(I+t cdot X^{-frac{1}{2}}VX^{-frac{1}{2}}) end{align}$

對 $X^{-frac{1}{2}}VX^{-frac{1}{2}}$ 做eigen-decomposition: $X^{-frac{1}{2}}VX^{-frac{1}{2}}=USigma U^dagger$ , 則

$logdet(I+t cdot X^{-frac{1}{2}}VX^{-frac{1}{2}})=sum_i log(1+tcdot Sigma_{ii})$

因此 $g(t)$ 是concave的。從而得到 $logdet(X)$ 是concave的. 證明完成.

技巧5(convex conjugate): 這個簡單來說就是給出函數的variational representation. 此技巧一般用來證明不等式或者設計新演算法，不過也可以用來判斷凹凸性.

1. $log(alpha)=inf_{etain R} e^{-eta-1}alpha+eta$ (pointwise infimum of linear functions is concave).

2. $e^{-alpha}=inf_{eta>0} -eta[alpha+log(eta)-1]$ .

3. $logsum_i e^{x_i}=sup_{ysucceq 0, 1^Ty=1} x^Ty-sum_iy_i log y_i$

4. Donsker-Varadhan variational representation: $D(P||Q)=sup_g E_P (g(X))-log E_Q[e^{f(X)}]$ , 其中D是Kullback-Leibler divergence

一般只能按照你的函數的具體情況進行判斷。

參考凸優化的各種教材，比如convex optimization，都會講凸函數的各種判別方法。

如果是問一眼看穿的trick又懶得證明的話，某些問題在特定情形下可以轉換成特定的凸優化問題，比如說看到Frobenius norm minimization，它就很可能是一個SDP問題，當然也是凸優化問題了...（此處插入不和諧的Schur complement...）

吐槽一個：

貌似很多複雜的工程參數優化問題中，尤其是設計很多很複雜的約束時，幾乎是無法判斷的。

往往只能假定問題是凸的，或者假定某優化演算法，尤其是偏啟發式的，乃至包括「啟發式」選擇優化演算法中參數的（比如，呃，梯度法，乃至大部分優化演算法，都包含一些），狹義的和廣義的蒙特卡羅，在足夠多的嘗試後，幾乎一定返回的是全局最優，或至少離全局最優「不那麼遠」。

記住常見函數的凹凸性，記住常見運算對凹凸性的改變。

如果一個函數的上圖為凸集，那麼這個函數是凸函數。

基本就是定義法，作圖法，結構分析法，一階二階充要條件等。

先畫圖看看，畫不出來的話就帶入幾個特殊值看看滿足凸函數性質不。其他快速判別方法我就不知道了