一、 凸集

1. 凸集与仿射集的关系

• 说道凸集，就不得不提到仿射集的概念。
• 仿射集：
  • 通过集合C中任意两个不同点的直线仍在集合C内，则称集合C为仿射集（例如直线和平面）。
    
  • 设X₁和X₂是定义在集合C中任意两个不同的点，即X₁ ≠ X₂，并且 X₁，X₂ ∈ C，θ⊆R，对θ都有θX₁ + (1-θ)X₂ ∈ C，则称C为一个仿射集。
  • 若对上面定义增加一个条件0 ≤ θ ≤1，则C为一个凸集。
  • 因为仿射集的条件比凸集的条件强，因此仿射集必然是凸集。

2. 凸集相关概念

• 保凸运算：
  1.凸集与凸集的交集还是凸集；
  2.仿射变换，即线性变换；
  3.透视变换；
  4.投射变换。
• 保凸算子：
  • 凸函数的非负加权和
  • 凸函数和仿射函数的复合
  • 凸函数的逐点最大值，逐点上确界
    f(x) = max( f₁(x),f₂(x),f_k(x)…f_n(x) )
    f(x) = sup g(x,y)

二、凸函数

1. 定义

• 若一个函数满足：
  1.定义域是凸集
  2.f(ax₁ + (1-a)x₂) <= af(x₁) + (1-a)f(x₂)  其中：∑a₁=1，a₁ >= 0   那么该函数为凸函数。
  示例：$f(\frac {x_1+x_2}{2})≤\frac {f(x_1)+f(x_2)}{2}$f(2x1​+x2​​)≤2f(x1​)+f(x2​)​
  

2. 性质

• 凸函数的局部极小值就是全局最小值
• 凸函数Hessian矩阵半正定
• Q为半正定对称阵，f(x) = x^TQx为凸函数
• f(x)为凸函数，f(E(x)) <= E(f(x))   (Jesson不等式)其中E(x)是x的期望
  Hessian矩阵半正定：
  • 特征值：向量变换的大小；

3. 凸函数举例

• 指数函数f(x) = e^x
• 幂函数f(x) = x^a
• 负对数函数f(x) = -logx
• 负熵函数f(x) = xlnx
• 范数f(x) = ||x||
• 最大值函数f(x) = max(x₁,x₂,…,x_n)

4. 海森矩阵与泰勒展开式

4.1 定理

• 设n是一个正整数，如果定义在一个包含a的区间上的函数f在a点处n+1次可导，那么对于这个区间上的任意x，都有：
  $f(x) = f(a)+\frac {f\prime(a)}{1！}(x-a)+\frac {f^{(2)}(a)}{2！}(x-a)^2+...+\frac {f^{(n)}(a)}{n！}(x-a)^n+R_n(x)$f(x)=f(a)+1！f′(a)​(x−a)+2！f(2)(a)​(x−a)2+...+n！f(n)(a)​(x−a)n+Rn​(x)
• 其中多项式称为函数在a处的泰勒展开式，剩余的R_n(x)是泰勒公式的余项，是(x-a)ⁿ的高阶无穷小。

4.2 二元泰勒展开

$f(x)=f(x_0)+\triangledown f(x_0)^T\triangle x+\frac {1}{2} \triangle x^TG(x_0)\triangle x+...$f(x)=f(x0​)+▽f(x0​)T△x+21​△xTG(x0​)△x+...

4.2 多元泰勒展开

三、凸优化

1. 凸优化问题的基本形式

• miniminze        f₀(x)，x ∈ Rⁿ
  subject  to        f_i(x) ≤ 0，i = 1,…,m
                          h_j(x) = 0，j = 1,…,n
• 其中f_i(x)为凸函数，h_j(x)为仿射函数。
• 凸优化问题的可行域为凸集，凸优化问题的局部最优解即为全局最优解。

2. 借助拉格朗日函数做优化

• Lagrange函数：
  $L(x,\lambda,\nu)=f_0(x)+\displaystyle\sum_{i=1}^m \lambda _if_i(x)+\displaystyle\sum_{j=1}^n \nu_j h_j(x)$L(x,λ,ν)=f0​(x)+i=1∑m​λi​fi​(x)+j=1∑n​νj​hj​(x)
• Lagrange对偶函数：
  $g(\lambda,\nu)=inf(L(x,\lambda,\nu))=inf[f_0(x)+\displaystyle\sum_{i=1}^m \lambda _if_i(x)+\displaystyle\sum_{j=1}^n \nu_j h_j(x)]$g(λ,ν)=inf(L(x,λ,ν))=inf[f0​(x)+i=1∑m​λi​fi​(x)+j=1∑n​νj​hj​(x)]