凸优化数学基础笔记（六）：凸集、凸函数与凸规划

凸优化数学基础笔记（六）：凸集、凸函数与凸规划

现有最优化方法对一般函数只能找到局部最优解，判断有无极值点以及它是否为全局最优解要用到函数凸性概念。一般在现实优化问题上，我们一般把优化问题变成凸优化问题，因为凸优化，凸优化（Convex OPtimization）是数学优化中的一个重要分支，研究的是在凸集上极小值的问题。下面首先介绍凸集。从直观上看，凸集是这样一些点的集合，它的内部没有“洞”（hole），边界不向内凹。凸集的基本特征，是其上任取两点所联成线段上的点依然属于这个集合。在数学上就是采用这种描述方法给凸集下定义的。首先给出凸组合的概念，在给出凸集和凸函数的定义，并简单讨论凸函数判定方法。
1.凸 集（Convex Set）

​        Definition 6.1（凸组合定义） 设\(\mathbf{X}_1,\mathbf{X}_2,\cdots,\mathbf{X}_l\) 是\(\mathbf{R}^n\) 中的\(l\)个已知点。若对于某个点\(\mathbf{X}\in\mathbf{R}^n\) 存在常数\(\alpha_1,\alpha_2,\cdots,\alpha_{l}\geq0\)，且\(\sum_{i=1}^{l}\alpha_i=1\) 使得\(\mathbf{X}=\sum_{i=1}^l\alpha_i\mathbf{X}_i\)，则称\(\mathbf{X}\) 是\(\mathbf{X}_1,\mathbf{X}_2,\cdots,\mathbf{X}_l\) 的凸组合。若 \(\alpha_1,\alpha_2,\cdots,\alpha_l>0\) 且\(\sum_{i=1}^l\alpha_i=1\)，则称\(\mathbf{X}\)是\(\mathbf{X_1},\mathbf{X}_2,\cdots,\mathbf{X}_l\) 的严格凸组合。
​        考虑两点\(\mathbf{X}_1\)和\(\mathbf{X}_2\)的凸组合\(\mathbf{X}=\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2\) ，其中\(\alpha_1,\alpha_2\geq{0}\) 且\(\alpha_1+\alpha_2=1\)。把 \(\alpha_2=1-\alpha_1\) 代入\(\mathbf{X}\) 的凸组合中得到\(\mathbf{X}=\mathbf{X}_2+\alpha_1(\mathbf{X}_1-\mathbf{X}_2)\) ，其中\(\alpha\in[0,1]\)。由解析几何知识可知，当 \(\alpha_1\)从0变到1时，点\(\mathbf{X}\) 由点\(\mathbf{X}_2\) 出发沿\(\mathbf{X}_1-\mathbf{X}_2\) 的方向移动到\(\mathbf{X}_1\) 。由此可知，\(\mathbf{X}_1\)和\(\mathbf{X}_2\) 所有严格凸组合的集合是不含\(\mathbf{X}_1\)和\(\mathbf{X}_2\) 两端点的线段。
​        Definition 6.2 （凸集的定义） 设集合\(\mathbf{C}\subseteq{\mathbf{R}^n}\)。如果对于任意两点\(\mathbf{X}_1,\mathbf{X}_2\in{\mathbf{C}}\) ，它们的任意两点\(\mathbf{X}_1,\mathbf{X}_2\in{\mathbf{C}}\) ，它们的任意凸组合仍然属于\(\mathbf{C}\) ，则称集合\(\mathbf{C}\) 为凸集。特别地规定，空集是凸集。
​        Definition 6.3 (半空间的定义)  设\(\mathbf{a}\in\mathbf{R}^n\) 且 \(\mathbf{a}\neq \mathbf{0},b\in{\mathbf{R}^1}\) ，则集合\(\{\mathbf{X}|\mathbf{a}^T\mathbf{X}\geq{b},\mathbf{X}\in{R^n}\}\) 称为\(\mathbf{R}^n\) 中的一个半空间。
​        容易地验证，空间\(\mathbf{R}^n\)、半空间、超平面、直线、点、球都是凸集。
​        定理 6.1 任意一组凸集的交集仍然是凸集。
​        证 明： 设\(C=\cap_{i\in I}C_i\) ,其中\(I\)是\(\{C_i\}\) 的下标集，\(C_i\) 都是凸集。任取\(\mathbf{X}_1,\mathbf{X}_2\in{C}\) , 则对于任意\(i\in{I}\) 都有\(\mathbf{X}_1,\mathbf{X}_2\in \mathbf{C}_i\)。任取\(\alpha_1,\alpha_2\in{[0,1]}\) 且\(\alpha_1+\alpha_2=1\)，因为\(C_i\) 是凸集，有 \(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2\in{C_i}\)。于是，\(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2\in \cap_{i\in{I}}C_i=C\)，即\(\mathbf{C}\) 是凸集。
2.凸函数（Convex Function）

​        Definition 6.4 （凸函数的定义） 设\(f:\mathbf{C}\subseteq\mathbf{R}^n\rightarrow\mathbf{R}^1\) , 其中\(\mathbf{C}\) 为凸集。若对于任意两点\(\mathbf{X}_1,\mathbf{X}_2\in{C}\) 和任意一对满足\(\alpha_1+\alpha_2=1\) 的数\(\alpha_1,\alpha_2\in[0,1]\) ，都有 \(f(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2)\leq \alpha_1f(\mathbf{X}_1)+\alpha_2f(\mathbf{X}_2)\) ，则称\(f\) 为定义在\(\mathbf{C}\) 上的凸函数。若对于任意一对满足\(\alpha_1+\alpha_2=1\)的数\(\alpha_1,\alpha_2\in(0,1)\) 都有：

\[f(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2)f(\mathbf{X}_1)+\nabla f(\mathbf{X_1})^T(\mathbf{X}_2-\mathbf{X}_1) \tag{4}\]
证 明： （1）必要性证明：已知\(f\)是\(\mathbf{C}\)上的凸函数，证明式（3）。由凸函数定义可知，对满足\(\alpha_1+\alpha_2=1\) 的任意正数\(\alpha_1,\alpha_2\in[0,1]\)都有

\[f(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2)\leq\alpha_1f(\mathbf{X}_1)+\alpha_2f(\mathbf{X}_2) \tag{5}\]
令\(\alpha_2=t\)，则\(\alpha_1=1-t\)，代入上式中，整理得到：

\[\frac{f(\mathbf{X}_1+t(\mathbf{X}_2-\mathbf{X}_1))-f(\mathbf{X}_1)}{t}\leq f(\mathbf{X}_2)-f(\mathbf{X}_1) \tag{6}\]
令 \(t\rightarrow{0}\) ,由\(f\)的可微性，利用一阶Taylor展开式，方向导数定义及式（6）可得：

\[\nabla f(\mathbf{X}_1)^T(\mathbf{X}_2-\mathbf{X}_1)\leq {f(\mathbf{X}_2)-f(\mathbf{X}_1)} \tag{7}\]
必要性得证；
充分性证明： 任取一对正数\(\alpha_1,\alpha_2\in[0,1]\) ,且\(\alpha_1+\alpha_2=1\)，考虑点 \(\mathbf{X}=\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2\) 根据充分性假设，应有：

\[\begin{aligned}&f(\mathbf{X}_1)\geq f(\mathbf{X})+\nabla f(\mathbf{X})^T(\mathbf{X}_1-\mathbf{X})\\&f(\mathbf{X}_2)\geq f(\mathbf{X})+\nabla f(\mathbf{X})^T(\mathbf{X}_2-\mathbf{X})\end{aligned}\tag{8}\]
两式分别乘以\(\alpha_1\) 和\(\alpha_2\) 后相加，得到：

\[\alpha_1f(\mathbf{X}_1)+\alpha_2f(\mathbf{X}_2)\geq f(\mathbf{X})+\nabla f(\mathbf{X})^T(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2-\mathbf{X})=f(\alpha_1\mathbf{X}_1+\alpha_2\mathbf{X}_2) \tag{9} \]
由凸函数定义可知，\(f\) 是\(\mathbf{C}\)上的凸函数。
​        （2）命题（2）充分性可仿照命题（1）的充分性证得；
​        必要性：因为严格凸函数本身是凸函数，所以\(\forall \mathbf{X}_1,\mathbf{X}_2\in{\mathbf{C}}\) ,且\(\mathbf{X}_1\neq\mathbf{X}_2\) 都有

\[f(\mathbf{X}_2)\geq f(\mathbf{X}_1)+\nabla f(\mathbf{X}_1)^T(\mathbf{X}_2-\mathbf{X}_1) \tag{10}\]
以下证明式中只能取">"号，假设存在\(\mathbf{X}_1,\mathbf{X}_2\in{\mathbf{C}}\) 且\(\mathbf{X}_1\neq\mathbf{X}_2\) ,满足

\[f(\mathbf{X}_2)=f(\mathbf{X}_1)+\nabla f(\mathbf{X}_1)^T(\mathbf{X}_2-\mathbf{X}_1) \tag{11}\]
取\(\mathbf{X}=\frac{1}{2}\mathbf{X}_1+\frac{1}{2}\mathbf{X}_2\) ,由\(f\) 的严格凸性，有：

\[f(\mathbf{X}_3)