一、基础知识(2)-凸集、凸函数

一、凸集

1.1 凸集的相关定义

1. 凸集定义：$x_1,x_2\in C\Rightarrow \theta x_1+(1-\theta )x_2\in C,\forall 0\le \theta \le 1$
   • 形式化定义：集合C中的任意两点所连接的线段都在C内，则C为凸集。
2. 凸包定义：$x={\theta }_1{x}_1+{\theta }_2{x}_2+...+{\theta }_k{x}_k,1={\theta }_1+{\theta }_2+...+{\theta }_k$,点$x_i$称为凸组合。
3. 仿射包： S 为 R n 的 子 集 ， { x ∣ x = θ 1 + θ 2 + . . . + θ k , x k ∈ S , θ 1 + θ 2 + . . . + θ k = 1 } S为R^n的子集，\{x|x=\theta_1+\theta_2+...+\theta_k,x_k\in S,\theta_1+\theta_2+...+\theta_k=1\} S为Rn的子集，{x∣x=θ1​+θ2​+...+θk​,xk​∈S,θ1​+θ2​+...+θk​=1}
   
4. 凸锥：$x={\theta }_1{x}_1+{\theta }_2{x}_2,{\theta }_1>0,{\theta }_2>0$，则$x_1,x_2$称为锥组合，集合$S$中任意点的锥组合都在$S$中，则$S$为凸锥。
   

1.2重要的凸集

1.2.1 超平面、半空间

1. 超平面： { x ∣ a T x = b } \{x|a^Tx=b\} {x∣aTx=b}，是放射集、凸集
2. 半空间： { x ∣ a T x ≤ b } \{x|a^Tx\leq b\} {x∣aTx≤b}，是凸集
   

1.2.2 球、椭球、锥

1. 球： B ( x c , r ) = { x ∣ ∣ ∣ x − x c ∣ ∣ 2 ≤ r } = { x c + r u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } B(x_c,r)=\{x|||x-x_c||_2\leq r\}=\{x_c+ru| ||u||_2 \leq 1\} B(xc​,r)={x∣∣∣x−xc​∣∣2​≤r}={xc​+ru∣∣∣u∣∣2​≤1}
2. 椭球： { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } \{x|(x-x_c)^TP^{-1}(x-x_c)\leq 1\} {x∣(x−xc​)TP−1(x−xc​)≤1}
   • $P\in S_{++}^n$是对称正定
3. 范数球： { x ∣ ∣ ∣ x − x c ∣ ∣ ≤ r } \{x|||x-x_c||\leq r\} {x∣∣∣x−xc​∣∣≤r}
4. 范数锥： { ( x , t ) ∣ ∣ ∣ x ∣ ∣ ≤ t } \{(x,t)|||x||\leq t\} {(x,t)∣∣∣x∣∣≤t}

1.3 保凸运算

1. 任意多个凸集的交为凸集，即若$C_i,i\in L$是凸集，${\bigcap }_{i\in L}{C}_i$
2. $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$，凸集在$f$下的像是凸集，原像也是凸集。

1.4 分离超平面定理

1. 分离超平面：$C、D$是两个不相交的凸集，存在非零向量$a$和常数$b$，使得$a^{T}x\le b,\forall x\in C,且a^{T}x⩾b,\forall x\in D$，则 { x ∣ a T x = b } \{x|a^Tx=b\} {x∣aTx=b}分离了C、D。
2. 支撑超平面：集合$C$的边界点$x_0$，若$a\ne 0$，且$a^{T}x\le a^T{x}_0,\forall x\in C$，则 { x ∣ a T x = a T x 0 } \{x|a^Tx=a^Tx_0\} {x∣aTx=aTx0​}为在C在边界点$x_0$的超平面。
   • 直观意义：超平面与集合C在点$x_0$出相切的半空间。
   • 支撑超平面定理：$C$是凸集，则$C$的任意边界点都有支撑超平面。

二、凸函数

2.1 凸函数定义

1. 凸函数定义：$domf$是凸集,且$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$。
   • 几何意义：任意两点的线段都在函数图像的上方
2. 严格凸函数：$domf$是凸集,且$f(\theta x+(1-\theta )y)<\theta f(x)+(1-\theta )f(y)$。
3. 强凸函数：
   • 存在常数$m>0$，使得$g(x)=f(x)-\frac{m}{2}||x|{|}^2$为凸函数，则$f(x)$为强凸函数。
   • 存在常数$m>0$，使得对任意$x,y\in domf,以及\theta \in (0,1)$，有$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)-\frac{m}{2}\theta (1-\theta )||x-y|{|}^2$

2.2 凸函数判定定理

1. 定理：$f(x)$是凸函数当且仅当对任意的$x\in domf,v\in {\mathbb{R}}^n,g:\mathbb{R}\to \mathbb{R}$，则 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),domg={t∣x+tv∈domf}是凸函数。
2. 一阶条件：$f(y)⩾f(x)+\nabla f(x{)}^T(y-x),\forall x,y\in domf$
3. 梯度单调性：$f为可微函数，则f为凸函数当且仅当domf为凸集且\nabla f$为单调映射，$(\nabla f(x)-\nabla f(y){)}^T(x-y)⩾0,\forall x,y\in domf$
   • 严格凸函数：$(\nabla f(x)-\nabla f(y){)}^T(x-y)>0,\forall x,y\in domf$
   • m-强凸函数：$(\nabla f(x)-\nabla f(y){)}^T(x-y)⩾m||x-y|{|}^2,\forall x,y\in domf$
4. 二阶条件：设 f 为定义在凸集上的二阶连续可微函数，则 f 是凸函数当且仅当${\nabla }^{2}f(x)⪰0,\forall x\in domf$

2.3 保凸的运算

1. 定理：
   1. $f$是凸函数，则$af$是凸函数,$a⩾0$
   2. $f_1,f_2$是凸函数，则$f_1+f_2$是凸函数
   3. $f_1,f_2,...,f_m$是凸函数，则 f ( x ) = m a x { f 1 ( x ) , f 2 ( x ) , . . . , f m ( x ) } f(x)=max\{f_1(x),f_2(x),...,f_m(x)\} f(x)=max{f1​(x),f2​(x),...,fm​(x)}是凸函数。

2.4 凸函数的性质

1. 连续性：凸函数在定义域中内点处是连续的。
   • f ( x ) = { 0 , x < 0 1 , x = 0 f\left( x \right) =
     {0,x<01,x=0" role="presentation">{0,x<01,x=0$$\{\begin{array}{l}0,x<0\\ 1,x=0\end{array}$$
     f(x)={0,x<01,x=0​,虽然其为凸函数，但是在点$x=0$处不连续。
2. 凸下水平集合：$f(x)$是凸函数，则$f(x)$所有的a-下水平集$C_a$为凸集。
3. 二次下界：强凸函数具有二次下界性质
   • 二次下界：$f(x)$是参数为$m$的可微强凸函数，则下述成立$f(y)⩾f(x)+\nabla f(x{)}^T(y-x)+\frac{m}{2}||y-x|{|}^2,\forall x,y\in domf$
   • 设 f 为可微强凸函数，则 f 的所有 α-下水平集有界．