凸优化中凸函数定义、直线与线段、凸集、仿射集合、仿射函数

凸优化（Stephen Boyd)中自学部分

凸函数定义

函数$f:\mathbf{R}^{n} \rightarrow \mathbf{R}$f:Rn→R是凸的，如果$f$f在定义域($dom$dom)上是凸集，且对于任意$x,y∈\mathbf{dom}f$x,y∈domf和任意$0⩽θ⩽1$0⩽θ⩽1，有

$f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)$f(θx+(1−θ)y)⩽θf(x)+(1−θ)f(y)。

凸函数示意图，图中点$(x,f(x))$(x,f(x))到$(y,f(y))$(y,f(y))之间的线段都在函数$f$f的图像上方。函数是凸函数，当且仅当其在与其定义域相交的任何直线上都是凸的。

为了理解，补充直线和线段的知识：

直线和线段

设$x_{1} \neq x_{2}$x1​​=x2​为$R^n$Rn空间中的两个点，则$y=\theta x_{1}+(1-\theta) x_{2}, \theta \in \mathbf{R}$y=θx1​+(1−θ)x2​,θ∈R组成一条穿越$x_{1}$x1​ 和$x_{2}$x2​的直线，参数$\theta$θ的值在0和1之间变动。这里的$x_{1}$x1​ 和$x_{2}$x2​可以类比上述提到的$(x,f(x))$(x,f(x))和$(y,f(y))$(y,f(y))。

个人理解：一般我们在实际应用中，用到的凸函数偏多，凹函数可以取负号变换为凸函数。

仿射集合

判断集合$C∈R^n$C∈Rn为仿射集合，则对于任意的$x_{1} ，x_{2}∈C$x1​，x2​∈C及$\theta∈R$θ∈R，有$\theta x_{1}+(1-\theta) x_{2} \in C$θx1​+(1−θ)x2​∈C，也就是$C$C包含了$C$C中任意两点的系数之和为1的线性组合。此概念拓展到多个点也适用。

例子：
线性方程组的解集$C=\{x | A x=b\}$C={x∣Ax=b}是一个仿射集合，其中$A \in \mathbf{R}^{m \times n}$A∈Rm×n,$B \in \mathbf{R}^{m}$B∈Rm.

证明：可设$x_{1} ，x_{2}∈C$x1​，x2​∈C，有$A x_{1}=b, A x_{2}=b$Ax1​=b,Ax2​=b，对于任意$\theta$θ，$A\left(\theta x_{1}+(1-\theta) x_{2}\right)=\theta A x_{1}+(1-\theta) A x_{2}=\theta b+(1-\theta) b=b$A(θx1​+(1−θ)x2​)=θAx1​+(1−θ)Ax2​=θb+(1−θ)b=b，说明任意的仿射组合$\theta x_{1}+(1-\theta) x_{2}$θx1​+(1−θ)x2​也在$C$C中。

凸集

注意：这里的凸集和凸函数不是一个概念。
判断某个集合是否为凸集，看集合中任意两点之间的线段是否在集合中。举个例子：

上图中，（1）包含其边界的六边形是凸的。（2）肾形集合不是凸的，因为图中所示集合中两点间的线段不为集合所包含。（3）仅包含部分边界的正方形不是凸的。

仿射函数

白话理解就是仿射函数是一个线性函数和一个常数的和，也就是具有$f(x)=A x+b$f(x)=Ax+b的形式，其中$A \in \mathbf{R}^{m \times n}$A∈Rm×n,$B \in \mathbf{R}^{m}$B∈Rm。

假设$S \subseteq \mathbf{R}^{n}$S⊆Rn是凸的（即$S$S为凸集），并且$f: \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$f:Rn→Rm是仿射函数，则$S$S在$f$f下的象$f(S)=\{f(x) | x \in S\}$f(S)={f(x)∣x∈S}是凸的。