【最优化笔记1】引论知识（凸集与凸函数）

凸集与凸函数

1. 凸集

定义 ：设$\Omega$$\subset$$R^n$,如果对于任意的点$x,y\in \Omega$,连接点$x,y$的线段上的一切点都在$\Omega$中，则称$\Omega$是一个凸集。其具体数学判别式为：
对于 $\forall$$x,y\in \Omega$, $\forall$$\mu \in [0,1]$,恒有$\mu$$x+(1-\mu )y\in \Omega$,则$\Omega$为一个凸集。
$e.g.$ : 单点集，$R^n$.

定理1(常考)：集合$\Omega$$\subset$$R^n$为凸集的充要条件是：点$x^{(i)}\in \Omega (i=1,2,...,p)$的任意凸组合${}^{[1]}$仍包含在$\Omega$中。
$[1]$凸组合：设实数$a_i\ge 0$ $(i=1,2,...,p),{\sum }_{i=1}^p{a}_i=1$,$x^{(i)}\in R^n(i=1,2,...,p)$,则称$x={\sum }_{i=1}^p{a}_i{x}^{(i)}$为点$x^{(1)},x^{(2)},...,x^{(p)}$的一个凸组合。
充分性性显然。
必要性如下

定理2：任意一组凸集的交集仍为凸集。

2. 凸函数

定义：设$f(x)$是定义在非空凸集$\Omega$$\subset$$R^n$上的函数，若对于$\forall$$x,y\in \Omega ,\forall \lambda \in [0,1]$，不等式$f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)$恒成立，则称$f(x)$是$\Omega$的凸函数。
从函数图像上看，则函数图象总是在切线(或切平面)的上方。
注：凸函数的非负线性组合仍未凸函数。(使用定义易证明)。

定理1(凸函数的充要条件1):定义在非空凸集$\Omega$$\subset$$R^n$上的$f(x)$为凸函数的充要条件是：
对于$\forall$$x,y\in \Omega$，都有：$f(y)-f(x)\ge (\nabla f(x){)}^T(y-x)$

定理2(凸函数的充要条件2)：定义在非空凸集$\Omega$$\subset$$R^n$上的$f(x)\in C^2$(即$f(x)$是二阶连续可微的)，$f(x)$为凸函数的充要条件是：
$f(x)$的海赛矩阵$F={\nabla }^{2}f(x)$在整个$\Omega$上是半正定的。
(正定则为严格凸函数,逆定理一般不成立)。

3. 凸规划

定义：目标&约束函数在可行解R上为凸函数，则这样的优化问题称为凸规划问题(与线性规划问题没有关系)。

定理1：凸规划问题的可行集R为凸集。
定理2：对于凸规划问题，目标函数$f(x)$的任一局部极小点都是$f(x)$在非空可行集R上的全局极小点。
（证明常考，用反证法证明)。
（若凸规划的问题的目标函数$f(x)$在非空可行集R上是严格凸函数，则该优化问题的全局极小点是唯一的)。

第一节，完。