Optimization Convex set

1. 凸集

   线性与非线性并不是区分问题难度的根本：凸与非凸调试

   本章的内容相对枯燥，主要是基本定义，为后续的凸函数打下基础

   基本集合定义

   • 仿射集

     若通过集合$C\subseteq R^n$ 中的任意两个同点的直线仍在集合$C$中，则称集合$C$是仿射的

     $\forall x_1,x_2\in C,\theta \in R\ \\s.t. \quad\theta x_1+(1-\theta x_2)\in C$

     可对应定义多个点的情况

     比如线性方程组$Ax=b$的解集$X$就是仿射集，

     反之，任何的仿射集都可以表示成为某个线性方程组的解集

     仿射包

     集合$C\subseteq R^n$中的点的所有仿射组合组合成的集合成为$C$的仿射包

     记作$aff \ C$

     $aff\ C=\{\theta_1 x_1 +...+\theta_k x_k | x_1,..x_k\in C ,\ \theta_1 +...+\theta_k =1 \}$

   • 凸集

     连接集合$C$中的任意两点的线段都在$C$内，则称$C$为凸集

     $\forall x_1,x_2\in C,\theta \in [0,1]\ \\s.t.\quad \theta x_1+(1-\theta x_2)\in C$

     显然：仿射集都是凸集

   • 锥

     凸锥的定义如下

     $\forall x_1,...,x_k\in C,\theta_i \ge0\ \\s.t.\quad \theta_1 x_1+...+\theta_k x_k\in C$

   • 超平面与半空间

     超平面的表示如下所示，也可看做法线方向为$a$的超平面，常数决定与与原点的偏移

     $\{x|a^Tx =b\}$

     而一个超平面则将$R^n$划分为两个闭的半空间，表示如下

     $\{x|a^Tx \le b\}$

     易证半空间是凸的，（按照定义即可），但却不仿射

   • 多面体

     多面体可被有限个线性等式与不等式定义

     $P = \{a^T_j\le b_j,j=1...m,c_j^T x = d_j .1...p \}$

     即多面体是由有限个半空间与超平面的交际。显然多面体是凸集

     单纯形

     $R^n$空间的$k$维单纯型

   • 特殊矩阵集合与半正定锥

     对称矩阵集合

     $S^n = \{X\in R^{n\times n}| X^T = X \}$

     半正定矩阵的集合

     $S^n_+ = \{X\in S^n| X\ge 0 \}$

     正定矩阵的集合

     $S^n_{++} = \{X\in S^n| X> 0 \}$

     显然有$S^n,S^n_+$是凸锥，而$S^n_{++}$不是凸锥：不包含特殊超平面

     半正定椎：$S^n_+$

   保凸运算

   首先凸集的数乘、加以及任意的交所得到的集合都是凸集

   • 交集

     易证交集运算是保凸的

   • 仿射变换（缩放、平移、投影）

     设$f$$:R^n\to R^m$ 是仿射变换， 即$f(x) = Ax+b,A\in R^{m\times n},b\in R^m$

     则有：

     • 凸集在$f$下的像是凸集：$S\subseteq R^n$ 是凸集 $\Rightarrow f(S) =\{f(x)|x\in S \}$) 是凸集
     • 凸集在$f$的原像是凸集:$C\subseteq R^n$ 是凸集 $\Rightarrow f^{-1}(C) =\{f(x)|x\in C \}$) 是凸集

   • 线性分式与透视函数的保凸性

     透视变换保凸性定理：集合$\{(x,t)|x\in R^n,t>0 \}$是凸的，则透视变换得到的集合$\{\frac xt|x\in R^n,t>0 \}$也是凸集

     分式线性变换的保凸性定理：集合$\{x|x\in R^n\}$是凸集，则下面的集合也是凸集

     $f(x) = \{ \frac{Ax+b}{c^Tx+d} |x\in R^n,A\in R^{m\times n},c\in R^n,d\in R.b\in R^m,c^Tx+d >0\}$

   分离超平面定理

   下面阐述一些凸集的应用：使用超平面或者仿射函数将两个不相交的凸集分离开，其结果便是超平面分离定理。基本解释如下：

   有$C,D$两个不相交的凸集，则必然存在$a\not = 0,b \quad s.t. \forall x\in C$有$a^Tx\le b,\forall x\in D,a^Tx\ge b$或者说仿射函数$a^Tx-b$在$C$中非正，在$D$中非负。则可称该超平面为$C.D$的分离超平面

   其逆定理：存在右侧条件，则两凸集不相交同样适用较广

   然而涉及到非凸集的划分问题则存在挑战，如下图所示

   

   涉及非凸集无法被超平面划分的示例

   支撑超平面定理

   若$C$是凸集，则$C$的任意边界处都存在支撑超平面

   PS 对偶锥等此处不做介绍了

   课后习题

   证明矩阵的2范数等于其最大奇异值

   个人证明如下：

   设矩阵$A\in R^{m\times n},$ 且矩阵A的二范数的定义如下

   $||A||_2 = \max_{x\in R^n,||x||_2 = 1}||Ax||_2 = \max_{x\in R^n,||x||_2 = 1}\sqrt{(Ax)^TAx}$

   对于半正定矩阵$(A^TA)$，其对应特征向量组合可以构成R^n的一组标准正交基，则必有$x = \sum_{i=1}^n a_i\alpha_i$ ，其中a_i为和常量，$\alpha_i$为矩阵($A^TA)$的一个特征向量，并假设对应的特征值为$\lambda_i$

   则有

   $A^TAx = A^TA \sum_{i=1}^n a_i\alpha_i =\sum_{i=1}^n a_iA^TA\alpha_i = \sum_{i=1}^n a_iA^TA\alpha_i = \sum_{i=1}^n \lambda_ia_i\alpha_i$

   于是

   $\sqrt{(Ax)^TAx} = \sqrt{\sum_{i=1}^n\lambda_ia_i^2}\le \sqrt{\lambda_{max}}$

   而矩阵二范数的数值为$\sqrt{(Ax)^TAx}$的最大值，正是其最大奇异值

   其余也可查看Github项目

   参考资料

   1. 最优化：建模、算法与理论 刘浩洋,户将,李勇锋,文再文著
   2. 凸优化 Stephen Boyd 著
   3. BUAA数学系崔老师的课堂课件