Lecture 2 凸集

Note: The lecture from cxt.

引入：凸优化问题

1. 可行域凸集；
2. 局部最优即是全局最优;
3. 最优点处的负梯度方向与凸可行集上任意方向的夹角大于90°，非凸集未必成立；

$-\mathrm{\nabla }f(x^{\ast }{)}^T(x-x^{\ast })\le 0,\mathrm{\forall }x\in S-\backslash nabla\; f(x^*)^T(x-x^*)\backslash leq0,\; \backslash forall\; x\backslash in\; S$

上式也是最优点成立的等价条件；

基本定义

1. 凸集：集合中两点的连线仍在集合内；

对$\mathrm{\forall }x,y\in C,\mathrm{\forall }\lambda \in [0,1]\backslash forall\; x,y\backslash in\; C,\backslash \; \backslash forall\; \backslash lambda\backslash in[0,1]$有：$\lambda x+(1-\lambda )y\in C\backslash lambda\; x+(1-\backslash lambda)y\backslash in\; C$

2. 凸组合：系数非负，且和为1；

3. 凸包：对任意集合里的点，凸组合构成的集合，是一个凸集，可以理解成将非凸集给填充成一个凸集；

   • 对非凸的结构凸化：对整数可行集凸包化成一个多边形，利用线性规划解决；
   • 如何构造凸包？

4. 常见凸集

   • 超平面$\{x\mathrm{\mid }{a}^{T}x=b,a\mathrm{\ne }0\}\backslash \{x|a^Tx=b,a\backslash neq\; 0\backslash \}$
   • 半空间$\{x\mathrm{\mid }{a}^{T}x\ge b,a\mathrm{\ne }0\}\backslash \{x|a^Tx\backslash geq\; b,a\backslash neq\; 0\backslash \}$
   • 多面体：多个线性不等式构成的集合区域；
   • 欧几里得球：同boyd讲义，$\mathrm{\mid }\mathrm{\mid }u\mathrm{\mid }{\mathrm{\mid }}_2||u||\_2$表示球心为0，半径为1的单位球，球心平移的操作得到$\{x_c+ru\mathrm{\mid }\mathrm{\mid }\mathrm{\mid }u\mathrm{\mid }{\mathrm{\mid }}_2\le 1\}\backslash \{x\_c+ru|\backslash \; ||u||\_2\backslash leq1\backslash \}$；
   • 椭球：正定矩阵的特征值开方即是椭球的半轴长；
   • 二阶锥：
     • 锥：$x\in C,\lambda \ge 0,\lambda x\in Cx\backslash in\; C,\; \backslash lambda\backslash geq\; 0,\; \backslash lambda\; x\backslash in\; C$
     • 二阶锥定义：$\{(x,t)\mathrm{\mid }\mathrm{\mid }\mathrm{\mid }x\mathrm{\mid }{\mathrm{\mid }}_2\le t\}\backslash \{(x,t)|\backslash \; ||x||\_2\backslash leq\; t\backslash \}$，思考二维$xx$构成的几何结构$\sqrt{x_1^2+x_2^2\le t}\backslash sqrt\{x\_1^2+x\_2^2\backslash leq\; t\}$；
   • 半正定锥$S_{+}^{n}S\_\{+\}^n$：$X\ge 0⟺z^{T}Xz\ge 0,\mathrm{\forall }zX\backslash geq\; 0\backslash iff\; z^TXz\backslash geq\; 0,\; \backslash forall\; z$
   • 练习：线性规划的最优解组成的集合是凸集；

5. 保凸运算

   • 两个凸集的交
   • 两个凸集元素的加减构成的集合
   • 一个线性的绝对值不等式可以看成两个半空间的交
   • 放射变换：有偏差的线性变换$f(x)=Ax+bf(x)=Ax+b$
     • 凸集上的放射变换得到集合是凸集
     • 凸集上的逆放射变换得到的集合（原像）是凸集
     • 放缩：想象二维的放缩，如锥束一样；
     • 平移：凸集的移动，不改变凸性；
     • 投影：有种降维操作的感觉，想象三维空间的球凸集，投影到二维平面的圆；

凸集基本性质

1. 投影定理：在非空闭凸集上存在唯一的一点到该集合外的任一点距离最小；
   • 存在且唯一
     • 连续函数在有界区域上求最值，存在
   • 投影点的充要条件：$(x-x^{\ast }{)}^T(y-x^{\ast })\le 0,\mathrm{\forall }x\in C(x-x^*)^T(y-x^*)\backslash leq\; 0,\; \backslash forall\; x\backslash in\; C$
     • 等价问题 $min\mathrm{\mid }\mathrm{\mid }y-x\mathrm{\mid }{\mathrm{\mid }}_2^{2}s\mathrm{.}tx\in Cmin\; ||y-x||\_2^2\backslash \; s.t\backslash \; x\backslash in\; C$
2. 点与凸集的分离
   • 一个超平面${\alpha }^{T}x=b\backslash alpha^Tx=b$可以将两个凸集$C_1,C_{2}C\_1,C\_2$分开，在两个半空间里
   • 证明分析常用：凸集分离等价于${\alpha }^{T}z\le {\alpha }^{T}x,x\in C_1,z\in C_2\backslash alpha^T\; z\backslash leq\backslash alpha^Tx,\backslash \; x\backslash in\; C\_1,\backslash \; z\backslash in\; C\_2$
   • 两个不相交的非空凸集，一定可以分离，但如果不是凸集，未必线性可分；
3. 支撑超平面

   • 对于非空凸集$CC$，边界点$\tilde{x}\backslash tilde\; x$，则存在非零向量$\alpha \backslash alpha$，使得${\alpha }^{T}x\le \alpha \tilde{x}\backslash alpha^Tx\backslash leq\backslash alpha\; \backslash tilde\; x$，称此时构成的超平面为支撑超平面；

   • 理解：对于非空凸集，可以在边界点处，找到一个经过该点的超平面，使得非空凸集在超平面的某个半空间里，注意非凸集合不可以；

   • 证明参考boyd讲义；