系列文章目錄

凸優化理論學習一|最優化及凸集的基本概念

---

一、凸函數

（一）凸集

設$S$為$n$維歐氏空間$R^n$中一個集合，若對$S$中任意兩點，連接他們的線段仍屬于$S$；換言之，對$S$中任意兩點$x^{(1)}$，$x^{(2)}$及每個實數$\lambda \in [0,1]$，都有：
$$\lambda x^{(1)}+(1?\lambda )x^{(2)}\in S$$
則稱$S$為凸集，其中$x^{(1)}$，$x^{(2)}$表示向量，$\lambda x^{(1)}+(1?\lambda )x^{(2)}$稱為$x^{(1)}$，$x^{(2)}$的凸組合。

（二）凸函數的定義及舉例

設$S$為$n$維歐氏空間$R^n$中的非空凸集，$f$是定義在$S$上的實函數，如果對任意的$x,y\in S$及$0\le \theta \le 1$，有：
$$f(\theta x+(1?\theta )y)\le \theta f(x)+(1?\theta )f(y)$$
則稱$f$為$S$上的凸函數。（這里的凸函數與高數里面定義的凸函數則恰恰相反。）

• 如果 -f 是凸的，則 f 是凹的
• 當不需要滿足等號條件時，$f$為嚴格凸函數
  

標量/一維空間內的凸函數：

• 仿射集：在實數域的所有$ax+b,a,b\in R$
• 指數函數：$e^{ax},a\in R$
• 冪函數：$x^{\alpha },\alpha \ge 1$或$\alpha \le 0$
• 冪函數的絕對值：$|x{|}^p,p\ge 1$
• 負熵函數：$xlogx$，定義域$R_{++}$

標量/一維空間內的凹函數：

• 仿射集：在實數域的所有$ax+b,a,b\in R$
• 冪函數：$x^{\alpha },0\le \alpha \le 1$
• 熵函數：$?xlogx$，定義域$R_{++}$

n 維歐幾里得空間的凸函數：

• 仿射函數：$f(x)=a^{T}x+b$
• 任意范式：$||x|{|}_p=(|x_1{|}^p+..{.}_{|}{x}_n{|}^p{)}^{1/p}forp\ge 1$、 ∣ ∣ x ∣ ∣ ∞ = m a x { ∣ x 1 ∣ , . . . , ∣ x 2 ∣ } ||x||_∞=max\{|x_1|,...,|x_2|\} ∣∣x∣∣∞?=max{∣x1?∣,...,∣x2?∣}
• 平方和：$||x|{|}_2^2=x_1^2+...+x_n^2$
• 最大值函數： m a x ( x ) = m a x { x 1 , x 2 , . . . , x n } max(x)=max\{x_1,x_2,...,x_n\} max(x)=max{x1?,x2?,...,xn?}
• softmax函數或log-sum-exp函數：$log(exp{x}_1+...+exp{x}_n)$

矩陣空間上的凸函數：

• 仿射函數：$f(X)=tr(A^{T}X)+b={\sum }_{i=1}^m{\sum }_{j=1}^n{A}_{ij}{X}_{ij}+b$，其中$A\in R^{m\times n},b\in R$
• 譜范數（最大奇異值）是凸的：$f(X)=||X|{|}_2={\sigma }_{max}(X)=({\lambda }_{max}(X^{T}X){)}^{1/2}$
• 對數行列式：$X\in S_{++}^n,f(X)=logdetX$

（三）凸函數的證明

在判斷函數是凸函數還是凹函數的時候，不管是一階還是二階條件，必須滿足函數f的定義域domf必須是凸集這個前提條件

1、將凸函數限制在一條直線上

如果能夠把一個凸函數限制到一條直線上后仍是凸的，就可以判定這個凸函數是凸的：

• 數學表達式理解：函數$f:R^n\to R$是凸函數當且僅當對于任意的$x\in domf$和任意向量$v\in R^n$，函數 g ( t ) = f ( x + t v ) , d o m g = { t ∣ x + t v ∈ d o m f } g(t)=f(x+tv),dom\ g=\{t|x+tv\in dom\ f\} g(t)=f(x+tv),dom?g={t∣x+tv∈dom?f}為凸函數。
• 通俗理解：將n維空間的函數映射到一維平面上，問題就轉換為判斷一維空間中的函數$g(t)$是否為凸函數。

應用示例：

2、判斷函數是否為凸函數的一階條件

假設函數$f$可微，其梯度$\Delta f$在開集定義域中處處存在，則函數f是凸函數的充要條件是定義域為凸集，且對任意$x,y\in domf$，下式成立：
$$f(y)\ge f(x)+\Delta f(x{)}^T(y?x)$$
梯度定義為：
$$\Delta f(x)=(\frac{?f(x)}{?x_1},\frac{?f(x)}{?x_2},...,\frac{?f(x)}{?x_n})$$

3、判斷函數是否為凸函數的二階條件

假設函數$f$二階可微，則對于函數$f$的開集定義域dom內的任意一點，它的Hessian矩陣或者二階導數${\Delta }^{2}f$存在，函數$f$是凸函數的充要條件是其Hessian矩陣為半正定矩陣：
$${\Delta }^{2}f(x{)}_{ij}=\frac{{?}^{2}f(x)}{?x_i?y_j},i,j=1,...,n,{\Delta }^{2}f(x)\ge 0,?x\in domf$$

其梯度$\Delta f$在開集定義域中處處存在，則函數f是凸函數的充要條件是定義域為凸集，且對任意$x,y\in domf$，下式成立：
$$f(y)\ge f(x)+\Delta f(x{)}^T(y?x)$$
梯度定義為：
$$\Delta f(x)=(\frac{?f(x)}{?x_1},\frac{?f(x)}{?x_2},...,\frac{?f(x)}{?x_n})$$

應用示例：

（四）下水平集和表觀

Epigraph和α-sublevel set的聯系是對于任意一個t，都對應一個α-sublevel set。

下水平集α-sublevel set：

• 函數$f:R^n\to R$的α-下水平集定義為：
  C α = { x ∈ d o m f ∣ f ( x ) ≤ α } C_{\alpha}=\{x\in dom\ f|f(x)\leq\alpha\} Cα?={x∈dom?f∣f(x)≤α}
• 對于任何的值，凸函數的下水平集仍然是凸集，但反之不一定正確，即某函數的所有下水平集都是凸集，但是這個函數可能不是凸函數

表觀Epigraph：

• f 是凸的當且僅當其表觀是凸集
• 函數$f:R^n\to R$的圖像定義為：（是$R^{n+1}$空間的一個子集）
  $$\{(x,f(x))|x\in domf\}$$
• 函數$f:R^n\to R$的表觀定義為：
  $$epif=\{(x,t)\in R^{t+1}|x\in domff(x)\le t\}$$
  

（五）詹森不等式

基本不等式：如果$f$是凸的，對于$x,y\in domf，0\le \theta \le 1$，有：
$$f(\theta x+(1?\theta )y)\le \theta f(x)+(1?\theta )f(y)$$

應用示例：

拓展：如果$f$是凸的，并且$z$是$domf$上的一個隨機向量，則有：
$$f(Ez)\le Ef(z)$$
基本不等式在離散分布的特殊情況：
$$prob(z=x)=\theta ,prob(z=y)=1?\theta$$

二、函數的保凸運算

（一）證明一個函數是凸函數

根據凸優化理論學習一|最優化及凸集的基本概念可知：證明集合 C 是凸集的方法：

• 基于定義：如果$x_1,x_2\in C,0\le \theta \le 1$，則有$\theta x_1+(1?\theta )x_2\in C$；
• 使用凸函數；
• 表明 C 是通過保留凸性的操作從簡單凸集（超平面、半空間、范數球……）獲得的，這里保留凸性的操作有：交運算、仿射映射、透視函數、線性分數函數等。

• 基于定義（通常通過將凸函數限制在一條直線上來簡化）
• 基于凸函數的一、二階條件
• 證明函數f是通過保留凸性的操作從簡單的凸函數獲得的，這里保留凸性的操作有：非負加權和、與仿射函數的復合、逐點極大值和上確值、與標量或向量函數的復合、取下確界、透視函數等。

（二）保留凸性的運算

1、非負縮放、總和、積分

非負倍數： 如果$f$是凸函數，且$\alpha \ge 0$，則$\alpha f$是凸函數

和： 如果$f_1,f_2$均為凸函數，則$f_1+f_2$也為凸函數

無窮總和： 如果$f_1,f_2,...$均為凸函數，則${\sum }_{i=1}^{\infty }{f}_i$也為凸函數

積分： 如果$f(x,\alpha )$對于每一個$\alpha \in A$是凸函數，那么${\int }_{\alpha \in A}f(x,\alpha )\mathrm{d}\alpha$也為凸函數

2、與仿射函數的復合

具有仿射函數的（預）組合：如果 $f$ 是凸函數，則 $f(Ax+b)$ 也是凸函數。即自變量先進行仿射變換，再代入函數后仍會保持凸性。

證明：

• 線性不等式的對數障礙函數： f ( x ) = ? ∑ i = 1 m l o g ( b i ? a i T x ) , d o m f = { x ∣ a i T < b , i = 1 , 2 , . . . , m } f(x)=-\sum_{i=1}^m log(b_i-a_i^Tx),dom \ f=\{x|a_i^T<b,i=1,2,...,m\} f(x)=?∑i=1m?log(bi??aiT?x),dom?f={x∣aiT?<b,i=1,2,...,m}
• 仿射函數的任意范數：$f(x)=||Ax+b||$

3、逐點最大值

若$f_1,f_2,...,f_m$是凸函數，則 f ( x ) = m a x { f 1 , f 2 , . . . , f m } f(x)=max\{f_{1},f_{2},...,f_{m}\} f(x)=max{f1?,f2?,...,fm?}是凸函數。

證明：（以兩個函數為例）

• 分段線性函數：$f(x)=\underset{i=1,2,...,m}{\max }(a_i^{T}x+b_i)$是凸函數
• $x\in {\mathbb{R}}^n$的前 $r$個最大分量之和是凸函數：$f(x)=x_{[1]}+x_{[2]}+...+x_{[r]}$（$x_{[i]}$為$x$的從大到小排列的第$i$個分量）

4、逐點取上界

如果對于每個$y\in A$，$f(x,y)$ 是關于$x$的凸函數，則 $g(x)={sup}_{y\in A}f(x,y)$ 是凸函數。

• 集合$C$的支撐函數：$S_C(x)=\underset{y\in C}{\sup }{y}^{T}x$是凸函數
• 集合$C$點到給定點$x$的最遠距離：$f(x)=\underset{y\in C}{\sup }||x?y||$
• 對稱矩陣$X\in S^n$的最大特征值：${\lambda }_{max}(X)=\underset{||y|{|}_2=1}{\sup }{y}^{T}Xy$

5、取下確界

若$f(x,y)$關于$(x,y)$整體是凸函數，$C$是凸集，則$g(x)=\underset{y\in C}{\inf }f(x,y)$是凸函數

點$x$到凸集$S$的距離$dist(x,S)=\underset{y\in S}{\inf }||x?y||$是凸函數

6、與標量函數復合

給定函數$g:{\mathbb{R}}^n\to \mathbb{R}$和$h:\mathbb{R}\to \mathbb{R}$，有$f(x)=h(g(x))$，有以下4條結論成立：

• h為凸， $\tilde{h}$不降， $g$為凸，則 $f$為凸
• h為凸， $\tilde{h}$不增， $g$為凹，則 $f$為凸
• h為凹， $\tilde{h}$不降， $g$為凹，則 $f$為凹
• h為凹， $\tilde{h}$不增， $g$為凸，則 $f$為凹

$\tilde{h}$是$h$ 的 Legendre 變換，對于一個函數$h:\mathbb{R}\to \mathbb{R}$，它的Legendre變換定義為：
h ~ ( t ) = s u p s ∈ R { t s ? h ( s ) } \tilde{h}(t)=sup_{s\in R}\{ts-h(s)\} h~(t)=sups∈R?{ts?h(s)}

推論

• 如果 $g$是凸函數，則$e^{g(x)}$是凸函數
• 如果 $g$是正值凹函數，則$\frac{1}{g(x)}$?是凸函數

7、與向量函數復合

給定函數$g:{\mathbb{R}}^n\to {\mathbb{R}}^k$和$h:{\mathbb{R}}^k\to \mathbb{R}$，有$f(x)=h(g(x))=h(g_1(x),g_2(x),...,g_k(x))$，有以下4條結論成立：

• h為凸， $\tilde{h}$每個分量不降， $g$為凸，則 $f$為凸
• h為凸， $\tilde{h}$每個分量不增， $g$為凹，則 $f$為凸
• h為凹， $\tilde{h}$每個分量不降， $g$為凹，則 $f$為凹
• h為凹， $\tilde{h}$每個分量不增， $g$為凸，則 $f$為凹

推論

• 如果 $g_i$是凸函數，則$log{\sum }_{i=1}^m{e}^{g(x)}$是凸函數
• 如果 $g_i$是正值凹函數，則${\sum }_{i=1}^{m}log{g}_i(x)$?是凹函數

三、構造性凸分析

• 從作為表達式給出的函數 f 開始
• 為表達式構建解析樹
  • 葉子是變量或常量
  • 節點是子表達式的函數
• 使用組合規則將子表達式標記為凸、凹、仿射或無
• 如果根節點標記為凸（凹），則 f 為凸（凹）
  

四、透視與共軛

（一）透視函數

定義$f:{\mathbb{R}}^n\to \mathbb{R}$ 和$g:{\mathbb{R}}^n\times \mathbb{R}\to \mathbb{R}$，且

$$g(x,t)=tf(\frac{x}{t}),domg=\{(x,t)|\frac{x}{t}\in domf,t>0\}$$

若$f$是凸函數，則$g$是凸函數。

• $f(x)=x^{T}x$是凸函數，因此$g(x,t)=\frac{x^{T}x}{t}$是區域$\{(x,t)|t>0\}$上的凸函數
• $f(x)=?logx$是凸函數，因此相對熵函數$g(x,t)=tlogt?tlogx$是${\mathbb{R}}_{++}^2$?上的凸函數
• 若$f$是凸函數，那么$g(x)=(c^{T}x+d)f(\frac{Ax+b}{c^{T}x+d})$是區域 { x ∣ c T x + d > 0 , A x + b c T x + d ∈ d o m f } \{x|c^{T}x+d>0,\frac{Ax+b}{c^{T}x+d}\in domf\} {x∣cTx+d>0,cTx+dAx+b?∈domf}上的凸函數

（二）共軛函數

任一適當函數$f$的共軛函數定義為：
f ? ( y ) = s u p x ∈ d o m f { y T x ? f ( x ) } f^?(y)=sup_{x∈dom\ f} \{y^Tx?f(x)\} f?(y)=supx∈dom?f?{yTx?f(x)}
對任意函數$f$都可以定義為共軛函數，也即不要求$f$是凸的（因為共軛函數是一組仿射函數的上界，因此不論 $f$凹凸性，$f^{?}$必為凸函數）

• 根據凸性充要條件，$f(x)$在$?x\in D?\mathbb{R}$的切線都是對$f(x)$的下界，即 $f(x)\ge f(x_0)+f^{{}^{\prime }}(x_0)(x?x_0)=f^{{}^{\prime }}(x_0)x+f(x_0)?f^{{}^{\prime }}(x_0)x_0$?
• 反過來，如果確定斜率$k$，就可以得到一組平行線 { k x + b : b ∈ R } \{kx+b:b\in \R\} {kx+b:b∈R}，從$?\infty$ 增大$b$，直到直線與$f(x)$相切時有$f(x)\ge kx+b$，也即$?b\ge kx?f(x)$，此不等式在$D$上恒成立，并且能夠取相等，因此$?b=\underset{x\in D}{\sup }(kx?f(x))=f^{?}(y)$

$f^{?}(y)$給出了斜率為$y$且與$f(x)$相切直線截距的相反數，或者說共軛函數$f^{?}(y)$表示了線性函數$y^{T}x$和$f(x)$之間的最大差異。

五、擬凸性

（一）擬凸函數(quasiconvex function) 定義

若$\text{dom}f$為凸集，且對任意的$\alpha$，其下水平集 S α = { x ∈ dom f ∣ f ( x ) ≤ α } S_\alpha = \{x\in\text{dom}f | f(x)\le\alpha\} Sα?={x∈domf∣f(x)≤α}都是凸集，則$f$為擬凸函數。

• 如果$f$是擬凸的，那么$?f$就是擬凹函數
• 如果一個函數既是擬凸函數又是擬凹函數，那么它是擬線性(quasilinear) 的
  

（二）常見的擬凸、擬凹、擬線性函數

擬凸函數：

• $f(x)=\sqrt{|x|}$
• f ( x ) = ∣ ∣ x ? 1 ∣ ∣ 2 ∣ ∣ x ? b ∣ ∣ 2 , d o m f = { x ∣ ∣ ∣ x ? a ∣ ∣ 2 ≤ ∣ ∣ x ? b ∣ ∣ 2 } f(x)=\frac{||x-1||_2}{||x-b||_2},domf=\{x|\ ||x-a||_2\leq||x-b||_2\} f(x)=∣∣x?b∣∣2?∣∣x?1∣∣2??,domf={x∣?∣∣x?a∣∣2?≤∣∣x?b∣∣2?}

擬凹函數：

• $f(x)=x_1{x}_{2}on{R}^2$

擬線性函數：

• c e i l ( x ) = i n f { z ∈ Z ∣ z ≥ x } ceil(x)=inf\{z\in Z|z\geq x\} ceil(x)=inf{z∈Z∣z≥x}
• $logxon{R}_{++}$
• 線性微分函數 f ( x ) = a T x + b c T x + d , d o m f = { c T x + d > 0 } f(x)=\frac{a^Tx+b}{c^Tx+d},domf=\{c^Tx+d>0\} f(x)=cTx+daTx+b?,domf={cTx+d>0}

（三）擬凸函數的性質

• 修正 Jensen 不等式：函數$f$為擬凸的等價于：定義域為凸集，且
  0 ≤ θ ≤ 1 ? f ( θ x + ( 1 ? θ ) y ) ≤ max ? { f ( x ) , f ( y ) } 0\le\theta\le1 \Longrightarrow f(\theta x+(1-\theta)y)\le\max\{f(x),f(y)\} 0≤θ≤1?f(θx+(1?θ)y)≤max{f(x),f(y)}

• 一階條件：具有凸域的可微 f 是擬凸當且僅當：
  $$f(y)\le f(x)?\Delta f(x{)}^T(y?x)\le 0$$
  

• 擬凸函數之和不一定是擬凸函數

參考：
凸函數
（最優化理論與方法）第二章最優化所需基礎知識-第七節：保凸的運算和共軛函數