凸函數

一.基本性質和例子

1.定義

定義一：函數f: $f : \mathbf{R}^{n} \rightarrow \mathbf{R}$ 是凸的，如果 $\operatorname{dom} f$ 是凸集，且對于任意的 $x,y \in domf$ 和任意的0 $\leqslant \theta \leqslant 1$ ，有 $f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)$ 。
定義二：函數f是凸函數，當且僅當與其定義域相交的任意函數都是凸函數?；蛘哒f，函數f是凸函數，當且僅當對于任意的 $x \in \operatorname{dom} f$ 和任意向量 $v$ ,函數 $g(t)=f(x+t v)$ 是凸函數（其定義域為 $\{t | x+t v \in \operatorname{dom} f\}$ ）
幾何意義：上述不等式意味著 $和(x, f(x)) 和(y, f(y))$ 的線段，即從x到y的弦在圖像上方。
嚴格凸：當 $x \neq y$ 且 $0<\theta<1$ 時，有 $f(\theta x+(1-\theta) y) < \theta f(x)+(1-\theta) f(y)$ 總成立。
函數f是凸函數，當-f是凹函數；f是凹函數，當-f是凸函數。

2.拓展值延伸

定義：

image.png
擴展值延伸的意義：將在函數 $f$ 定義域外的值定義為無窮大，將函數延伸至全空間 $R^n$ 上，這種延伸可以簡化符號表示，且延伸后凸性不變。對于延伸函數 $\tilde{f}$ ，可以描述為：

對任意的 $x,y \in R^n$ 及 $0<\theta<1$ 有 $\tilde{f}(\theta x+(1-\theta) y) \leqslant \theta \tilde{f}(x)+(1-\theta) \tilde{f}(y)$ 。（當 $\theta=0、1$ 時，總成立）
- 當 $x,y \in \operatorname{dom} f$ 時， $\theta x+(1-\theta) y \in dom f$ ,因為 $f$ 為凸函數，上述不等式成立。
- 如果 $x,y$ 任一個在 $domf$ 外，不等式右面為正無窮，左面 $\theta x+(1-\theta) y$ 在
例子：
- 凸集的示性函數，設 $C \subseteq \mathbf{R}^{n}$ 是一個凸集，考慮凸函數 $I_{C}$ ，其定義域為C,對于所有 $x \in C$ ,有 $I_{C}(x)=0$ ，換言之，此函數在集合C上一直為零。其擴展延伸可以描述如下 $\tilde{I}_{C}(x)=\left\{\begin{array}{ll}{0} & {x \in C} \\ {\infty} & {x \not \in C}\end{array}\right.$ 。凸函數 $\tilde{I}_{C}$ 被稱為集合C的示性函數。利用示性函數我們更加靈活的定義符號描述：例如求 $f(x)$ 在C上的極小值，可以描述為求極小化 $f+\tilde{I}_{C}$
- 延伸函數一定要擴展到無窮，不然無法保持凸性。

3.一階條件

一階條件：假設f可微（即其梯度 $\nabla f$ 在開集 $domf$ 內處處存在），則函數 $f$ 是凸函數的充分必要條件是 $domf$ 是凸集且對于任意的 $x, y \in \operatorname{dom} f$ ，下式成立 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
幾何意義：
- 快照57.png
- $\nabla f(x)^{T}(y-x)$ 是仿射函數y即為函數 $f$ 在點 $x$ 附近的Taylor近似，在這里Taylor近似其實是原函數的一個全局下估計
- 極值點：如果 $\nabla f(x)=0$ ，那么對于所有的 $y \in \operatorname{dom} f$ ，存在 $f(y) \geqslant f(x)$ ，所以x是全局最小點
- 嚴格凸：函數f嚴格凸的充分必要條件是
證明：一階條件是指在任意維凸集中均成立
- 我們首先在證明在一維的情況下成立:即可微函數 $f : \mathbf{R} \rightarrow \mathbf{R}$ 是凸函數的充分必要條件是 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
  - 必要性：
    
    首先假設f是凸函數，由凸函數的定義我們可以得到 $domf$ 是一個凸集
    
    假設 $x, y \in \operatorname{dom} f$ ，則對于任意的 $0<t \leqslant 1$ ，有 $x+t(y-x) \in \operatorname{dom} f$ ，
    
    由凸函數的定義一可得 $f(x+t(y-x)) \leqslant(1-t) f(x)+t f(y)$
    
    上式兩端同除以t得 $f(y) \geqslant f(x)+\frac{f(x+t(y-x))-f(x)}{t}$
    
    因為f是可微函數，所以令 $t \rightarrow 0$ ，可得到 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
    
    (當t=0時顯然成立。)
  - 充分性
    
    假設 $dom f$ 內的任意x,y在定義域中，滿足 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
    
    假設 $x \neq y, 0 \leqslant \theta \leqslant 1$ ， $z=\theta x+(1-\theta) y$ 由上述不等式可得：
    
    $f(x) \geqslant f(z)+f^{\prime}(z)(x-z), \quad f(y) \geqslant f(z)+f^{\prime}(z)(y-z)$
    
    將第一個不等式同乘 $\theta$ ,第二個不等式同乘 $1-\theta$ ，并將二者相加可得：
    
    $\theta f(x)+(1-\theta) f(y) \geqslant f(z)$
    
    得證
- 下邊利用定義二由一維推理一般情況：
  
  對于高維空間的函數f: $\mathbf{R}^{n} \rightarrow \mathbf{R}$ ,假設 $x, y \in \mathbf{R}^{n}$ ，構造一個一維的函數 $g(t)=f(t y+(1-t) x)$ ，
  
  此函數的導數為 $g^{\prime}(t)=\nabla f(t y+(1-t ) x )^{T}(y-x)$ 。
  - 首先假設f是凸函數，證明 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
    
    因為f是凸函數，由定義二可得g是凸函數。
    
    由g是一個一維空間的凸函數，由第一步證明可得對于任意的， $x,y \in dom g$ 可得:
    
    $g(y) \geqslant g(x)+\nabla g(x)^{T}(y-x)$ ,
    
    取 $y=1,x=0$ ,帶入 $g^{\prime}(t)=\nabla f(t y+(1-t ) x )^{T}(y-x)$ ，化簡
    
    $g(1)\geqslant g(0)+\nabla g(0)$
    
    $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
    
    得證
  - 其次，假設若對于任意的 $x,y \in dom f$ ,有 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 則f是一個凸函數
    
    因為 $domf$ 是一個凸集，
    
    所以對于任意的 $x,y \in domf$ ,有 $t y+(1-t) x \in \operatorname{dom} f$ ， $\tilde{t} y+(1-\tilde{t}) x \in \operatorname{dom} f$
    
    所以有 $f(t y+(1-t) x) \geqslant f(\tilde{t} y+(1-\tilde{t}) x)+\nabla f(\tilde{t} y+(1-\tilde{t}) x)^{T}(y-x)(t-\tilde{t})$
    
    化簡得 $g(t) \geqslant g(\tilde{t})+g^{\prime}(\tilde{t})(t-\tilde{t})$ 。

4.二階條件

定義：若函數 $f : \mathbf{R} \rightarrow \mathbf{R^n}$ 二階可微，則f為凸函數的充分必要條件是：
1. $domf$ 為凸集
2. $\nabla^{2} f(x) \succeq 0$ ，對于任意的 $x \in domf$
幾何意義，二階導數大于零，曲率為正，一階導數為增函數。為了更好理解，可以局限在一維情況下，參照一下數學分析。
證明：

書上說讓自己證明哦！

顯然可得。
嚴格凸：對于任意的 $x \in domf$ ,若 $\nabla^{2} f(x)>0$ ，則函數f是嚴格凸函數。

? 若函數f是嚴格凸函數，那么對于任意的 $x \in domf$ ， $\nabla^{2} f(x)>0$ 未必成立。

? 也就是說 $\nabla^{2} f(x)>0$ 大于零是嚴格凸的充分不必要條件。
- 例如：函數 $f : \mathbf{R} \rightarrow \mathbf{R}$ ， $f=x^4$ 二階可導， $f''(x)=12x^2 \geqslant0$ ,然而從圖像可知此函數還是一個嚴格凸函數。
例題:特殊情況：二次函數嚴格凸的充分必要條件是 $\nabla^{2} f(x)>0$

快照58.png

注：關于Hessian矩陣：聯想一下二次型就可以理解了，特征值，特征向量。

5.例子

快照69.png

補充：

范數定義：的范數滿足
1. $P(ax)=|a|P(x)$
2. $P(x+y)\leqslant P(x)+P(y)$
3. 若 $P(x)=0$ ，則 $x=0$
零范數： $非零元素的數目||x||_0=非零元素的數目$ ，不是一個凸函數。它也不滿足范數定義。

二.保凸運算

1.非負加權和

非負加權和：凸函數集合本身是一個凸錐：凸函數的非負加權和任然是凸函數。若為凸 $f_1,f_2...f_m$ 為凸，則 $f(x)=\sum_{i=1}^{m} w_if_{i}（x）$ 為凸函數。其中 $w_i >=0$

證明：首先 $domf$ 為所有 $f_i$ 定義域的交集，所以定義域為凸集。其次，顯然。
非負加權和拓展: 若 $f(x,y)$ 對任意固定的 $y \in A,f(x,y)$ 均為關于 $x$ 凸函數，設 $w(y)>=0$ ,那么

$g(x)=\int_{y \in A} w(y) f(x, y) d y$ 為關于x的凸函數。

2.復合仿射映射

定義:假設函數 $f : \mathbf{R}^{n} \rightarrow \mathbf{R}, A \in \mathbf{R}^{n \times m}$ ，以及 $b \in \mathbf{R}^{n}$ ，定義 $g : \mathbf{R}^{m} \rightarrow \mathbf{R}$ 為 $g(x)=f(A x+b)$ ，其中 $\operatorname{dom} g=\{x | A x+b \in \operatorname{dom} f\}$ 。若函數f是凸函數，那么g是凸函數；如果函數f是凹函數，那么函數g是凹函數。
- 證明：
  
  1.證明 $\operatorname{dom} g=\{x | A x+b \in \operatorname{dom} f\}$ 是一個凸集
  
  對于任意的 $x,y \in domg,0 \leqslant \theta \leqslant 1$ , $A(\theta x+(1-\theta )y)+b=\theta (Ax+b)+(1- \theta)(Ay+b)$ ,
  
  已知 $domf$ 是一個凸集且 $A x+b \in \operatorname{dom} f,A y+b \in \operatorname{dom} f$
  
  由凸集的定義可得 $\theta (Ax+b)+(1- \theta)(Ay+b) \in domf$
  
  所以 $\theta x+(1-\theta )y \in domg$
  
  2.證明： $g(x)=f(A x+b)$ 是凸函數。
  
  因為 $f(x)$ 是凸函數，那么可得 $f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)$
  
  $g(\theta x+(1-\theta) y) =f(A(\theta x+(1-\theta)) y+b)=f(\theta (Ax+b)+(1-\theta)(Ay+b))$
  
  $\leqslant \theta f(Ax+b)+\theta f(Ay+b)=\theta g(x)+ (1-\theta) g(y)$
  
  得證，所以復合仿射映射是一個凸函數。

3.逐點最大和逐點上確界

逐點最大和
- 定義：如果函數 $f_1$ 和 $f_2$ 均為凸函數，則二者的逐點最大函數 $f$ , $f(x)=\max \left\{f_{1}(x), f_{2}(x)\right\}$ ,定義域是 $\operatorname{dom} f=\operatorname{dom} f_{1} \cap \operatorname{dom} f_{2}$ ，仍然是個凸函數。
- 證明：任取0 $\leqslant \theta \leqslant 1$ 以及 $x, y \in \operatorname{dom} f$ ，有
  
  $\begin{aligned} f(\theta x+(1-\theta) y) &=\max \left\{f_{1}(\theta x+(1-\theta) y), f_{2}(\theta x+(1-\theta) y)\right\} \\ & \leqslant \max \left\{\theta f_{1}(x)+(1-\theta) f_{1}(y), \theta f_{2}(x)+(1-\theta) f_{2}(y)\right\} \\ & \leqslant \max \left\{\theta f_{1}(x)+\theta f_{2}(x)\right\}+ \max \left\{(1-\theta) f_{1}(y), (1-\theta)f_{2}(y)\right\} \\ & \leqslant \theta \max \left\{f_{1}(x), f_{2}(x)\right\}+(1-\theta) \max \left\{f_{1}(y), f_{2}(y)\right\} \\ &=\theta f(x)+(1-\theta) f(y) \end{aligned}$
- 例題： $f(x)=max\{x^2,x\}$
- 推廣：如果函數 $f_{1}, \cdots, f_{m}$ 是凸函數，那么他們的逐點最大和 $f(x)=\max \left\{f_{1}(x), \cdots, f_{m}(x)\right\}$ 也是凸函數。
最大的r個分量之和：
- 定義：對任意 $x \in \mathbf{R}^{n}$ ，用 $x_i$ 表示 $x$ 中第i大的分量，即將 $x$ 中分量按照非降序排列得到下式： $x_{[1]} \geqslant x_{[2]} \geqslant \cdots \geqslant x_{[n]}$ ，對x中前r個大的分量進行求和得到 $f(x)=\sum_{i=1}^{r} x_{[i]}$ 是一個凸函數。
  
  此函數可以描述為 $f(x)=\sum_{i=1}^{r} x_{[i]}=\max \left\{x_{i_{1}}+\cdots+x_{i_{r}} | 1 \leqslant i_{1}<i_{2}<\cdots<i_{r} \leqslant n\right\}$
- 理解：即從 $x$ 中隨機選擇r個元素求和可能組合中的最大值，這種取法共有 $n ! /(r !(n-r) !)$ 可能。將每一種可能看做一個函數，那個最大的r個分量之和相當于對這 $n ! /(r !(n-r) !)$ 逐點求和。而隨機取值求和函數又是關于 $x$ 的仿射映射，一定是一個凸函數，所以最大的r個分量之和也是凸函數。
- 推廣： $w_{1} \geqslant w_{2} \geqslant \cdots \geqslant w_{r} \geqslant 0$ ， $\sum_{i=1}^{r} w_{i} x_{[i]}$ 也是一個凸函數
- 推廣：無限個凸函數的逐點上確界：如果對任意的 $y \in \mathcal{A}$ ，函數 $f(x, y)$ 關于 $x$ 是凸的，則函數 $g(x)=\sup _{y \in \mathcal{A}} f(x, y)$ 也是凸的，定義域為 $\operatorname{dom} g=\left\{x |(x, y) \in \operatorname{dom} f \forall y \in \mathcal{A}, \sup _{y \in \mathcal{A}} f(x, y)<\infty\right\}$
實對稱陣的最大特征值：

$f(X)=\lambda_{max}(X),domf=S^m$ , $y$ 是特征向量，

$Xy=\lambda y$

$y^TXy=y^T\lambda y$

$\lambda=y^TXy/||y||_2$

當 $時，||y||_2=1時，\lambda_{max}(x)=sup\{y^TXy| ||y||_2=1\}$

由上述定理可知若對于每一個y, $是一個凸函數y^TXy是一個凸函數$ ，那么 $\lambda_{max}(x)=sup\{y^TXy| ||y||_2=1\}$ 是一個凸函數。