【深度学习】梳理凸优化问题（五）

约束优化问题

$\begin{array}{rcl}&&min_w\;f(w)\\s.t.\;g_i(w)&\leq&0\;(i=1,...,k)\\h_j(w)&=&0\;(j=1,...,n)\\&& \end{array}$s.t.gi​(w)hj​(w)​≤=​minw​f(w)0(i=1,...,k)0(j=1,...,n)​

注：

• 这是一个最小化问题.
• 不等式约束严格执行的含义是“小于等于号”变成“小于号”。

凸函数

对区间 $[a,b]$[a,b]上定义的函数 f，若它对区间中任意两点$x_1,x_2$x1​,x2​均有：
$f(\frac{x_1+x_2}{2})\le\frac{f(x_1)+f(x_2)}{2}$f(2x1​+x2​​)≤2f(x1​)+f(x2​)​
则称f为区间 [a,b]上的凸函数，这和高数上讲图形的形状时是不同的概念。

形曲线的函数如$f(x)=x^2$f(x)=x2就是凸函数。

对实数集上的函数，可通过求解二阶导数来判别：

• 若二阶导数在区间上非负，则称为凸函数
• 若二阶导数在区间上恒大于0，则称严格凸函数

仿射函数也是凸函数，只是不是严格凸函数。

凸优化问题

凸优化问题是特殊的约束最优化问题。其一般形式形式和约束最优化问题一样。

假设f、g、h在定义域内是连续可微的，且目标函数f和不等式约束函数g是凸函数，等式约束h是仿射函数（线性函数），则这种约束最优化问题称为凸优化问题。
因此凸优化问题特征的重要特征：

• 目标函数f，不等式约束函数g是凸函数
• 等式约束h是仿射函数
• 满足约束最优化问题的一般形式

凸二次规划问题

凸二次规划问题是凸优化问题的一个特殊形式，当目标函数是二次型函数且约束函数 g 是仿射函数时，就变成一个凸二次规划问题。凸二次规划问题的一般形式为:
$min_w\frac12x^TQx+c^Tx\\s.t.\;Wx\leq b$minw​21​xTQx+cTxs.t.Wx≤b

• 若 Q 为半正定矩阵，则上面的目标函数是凸函数，相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。
• 若Q为正定矩阵，则该问题有唯一的全局最小值。 例如，最简单的正定矩阵就是单位矩阵。

凸二次规划问题的特征：

• **目标函数f是二次型函数函数 **
• 等式约束h是仿射函数
• 等式约g是仿射函数
• 满足约束最优化问题的一般形式

常用的二次规划问题求解方法有：

• 椭球法
• 内点法
• 增广拉格朗日法
• 梯度投影法

额外补充

正定和半正定矩阵

这里贴上一个博客的解释，看了比较好理解：https://www.cnblogs.com/marsggbo/p/11461155.html
正定矩阵(PD)

给定一个大小为 n×n 的实对称矩阵 A ，若对于任意长度为 n 的非零向量 X，有 $X^TAX>0$XTAX>0 恒成立，则矩阵 A 是一个正定矩阵。

半正定矩阵(PSD)

给定一个大小为 n×n 的实对称矩阵 A ，若对于任意长度为 n 的非零向量 X，有 $X^TAX\le0$XTAX≤0 恒成立，则矩阵 A 是一个半正定矩阵。

具体解释：以正定矩阵为例，它需要满足 $X^TAX>0$XTAX>0 ,而且我们知道矩阵相乘(如AX)的本质是将向量X按照矩阵A所指定的方式进行变换(你可以通过阅读理解矩阵等系列文章来对矩阵乘法产生更加深刻的理解)。

我们可以记M=AX,那么对于正定矩阵有 $X^TAX=X^TM>0$XTAX=XTM>0 ，看到这有没有想起cos公式呢？如下：

$cos(θ)=\frac{a^Tb}{||a||×||b||}$cos(θ)=∣∣a∣∣×∣∣b∣∣aTb​

所以正定矩阵是个什么意思呢？实际上就是说对于一个向量X,我们希望 X在经过有一个矩阵A的变化后得到的新的向量M和它本身的夹角小于90度。而小于90度背后的含义是变换后的向量M是沿着原向量X的正方向进行缩放的（即 M投影回原向量时方向不变）。

而上面这句话还可以从特征向量的角度进一步理解,在介绍之前我们回顾一下特征值和特征向量的概念：首先一个矩阵A的特征向量x就是表示某个向量会沿着特征向量的方向进行变换（缩放），缩放比例由特征值λ决定。例如：

$A_1=\begin{bmatrix}0.5&0\\0&2\end{bmatrix}$A1​=[0.50​02​]

很简单地可以计算得到A的特征值分别是0.5和2，而它们对应的特征向量分别是$[1,0]^T$[1,0]T和$[0,1]^T$[0,1]T。所以如果一个向量b左乘一个矩阵A，其本质就是将向量b沿着$[1,0]^T$[1,0]T和$[0,1]^T$[0,1]T方向分别放大0.5和2倍。我们假设b=$[2,2]^T$[2,2]T，那么Ab最终得到的向量为$[1,4]^T$[1,4]T，结合下图看更加直观：

我们看上图，如果其中一个特征值小于0，比如$λ1<0$λ1<0那么最终得到的向量Ab−→投射到b→方向的向量与b→反向。综上，要使得变换后的向量M与原向量x夹角小于90度，即映射回原来的向量时保持方向不变，那么就需要特征值大于0，所以这也是为什么正定矩阵的特征值都大于0.

参考文章：
https://www.cnblogs.com/marsggbo/p/11461155.html
https://blog.csdn.net/promisejia/article/details/81241201