仿射集

在n维空间中，对于点的集合C，如果集合中的任意两点x，y，对于任意$\theta$，都有$\theta x + (1-\theta)y \in C$，则集合C是一个仿射集合。即在集合中任意两点连线的直线上的点都在集合中。

凸集

定义

在n维空间中，对于点的集合C，如果集合中的任意两点x，y，对于任意$0\leq\theta\leq1$，都有$\theta x + (1-\theta)y \in C$，则集合C为一个凸集。即在集合中任意两点，其连线线段上的点也都在集合中。

凸集和防射集的定义就是$\theta$的取值范围不同。

常见的凸集

n维实向量空间$R^n$

如果有$x,y \in R^n$，则显然有对于任意$0\leq\theta\leq1$，都有$\theta x + (1-\theta)y \in R^n$。

由此可见，如果一个优化问题是不带约束的优化，则其变量可行域是一个凸集。

仿射子空间${x \in R^n:Ax=b} $

其中A为$m \times n$的矩阵，b为m维列向量。即非齐次线性方程组的解空间。

证明：

如果有$x,y \in R^n$且$Ax=b,Ay=b$，

则对于任意的$0\leq\theta\leq1$，

都有$A(\theta x+(1-\theta)y) = \theta Ax+(1-\theta)Ay=\theta b + (1-\theta)b=b$。

由此可见，如果变量的约束是线性等式约束，则该线性等式确定的可行域是一个凸集。

子空间${x \in R^n:Ax\leq b}$

其中A为$m \times n$的矩阵，b为m维列向量。

证明：

如果有$x,y \in R^n$且$Ax\leq b,Ay\leq b$，

则对于任意的$0\leq\theta\leq1$，

都有$A(\theta x+(1-\theta)y) = \theta Ax+(1-\theta)Ay\leq\theta b + (1-\theta)b=b$

由此可见，如果变量的约束是线性不等式约束，则该线性不等式确定的可行域是一个凸集。

凸集的性质

1、多个凸集的交集仍然是凸集

证明：

假设$C1,C_2,…,C_k$为凸集，他们的交集为$C=\bigcap{i=1}^{k}Ci$，并有$0 \leq \theta \leq 1$,

因为$C_1,C_2,…,C_k$为凸集，所以对于$x,y \in C$，有$\theta x + (1-\theta)y \in C_i, \forall i=1,…,k$

即$\theta x + (1-\theta)y \in C$

2、多个凸集的并集不一定是凸集

凸函数

定义

在函数定义域内，如果对于任意的x和y，以及实数$0 \leq \theta \leq 1$，都满足$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$，则函数为凸函数。可见，凸函数的定义和函数曲线的凹凸性的定义是相反的。

从几何意义上讲，在凸函数上的任意两点的连线线段上的点都在函数的上方。

如果把定义中的$\leq$改为$<$，则称函数是严格凸函数。

对于一元函数，凸函数的二阶判定式为$f’’(x) \geq 0$，严格凸函数的二阶判定式为$f’’(x) > 0$。由此也可见凸函数的定义和函数曲线的凹凸性的定义是相反的。

对于多元函数，如果它是凸函数，则其Hessian矩阵为半正定矩阵。如果是严格凸函数，则其Hessian矩阵为正定矩阵。

凸函数的性质

1、凸函数的非负线性组合仍然是凸函数。

Hessian矩阵

Hessian矩阵是有多元函数的二阶偏导数组成的矩阵。如果一个函数二阶可导，其Hessian矩阵定义为：

$\begin{bmatrix} \frac{\partial^2f}{\partial {x_1}^2} & \frac{\partial^2f}{\partial x_1x_2} & \cdots & \frac{\partial^2f}{\partial x_1x_n} \\ \frac{\partial^2f}{\partial x_2x_1} & \frac{\partial^2f}{\partial {x_2}^2} & \cdots & \frac{\partial^2f}{\partial x_2x_n} \\ \vdots & \vdots & & \vdots \\ \frac{\partial^2f}{\partial x_nx_1} & \frac{\partial^2f}{\partial x_nx_2} & \cdots & \frac{\partial^2f}{\partial {x_n}^2} \end{bmatrix}$

如果多元函数的混合二阶偏导数连续，则其混合二阶偏导数结果与求导次序无关。大多数多元函数的混合二阶偏导数是连续的，所以Hessian矩阵大多是对称矩阵。

根据多元函数的极值判别法，假设多元函数在点M的梯度为0，则M是函数的驻点，如果：

1、Hessian矩阵正定，函数在该点有极小值

2、Hessian矩阵负定，函数在该点有极大值

3、Hessian矩阵既不正定也不负定，则不能确定是否取得极值