二次规划

其中这些问题在我考研的时候也想清楚了，只是读研以来一开始做的是进化算法，后来又做的深度学习，都是理论性不太强的方向。这些东西有点忘了，现在看到书突然一下记起来了，便做个笔记吧。

• 注：如何理解线性变换？向量经过可逆线性变换以后，向量还是那个向量，只不过换了一组基向量（或者说换了一个坐标系统）相当于换了一种表达方式。但是向量假如经过线性变换不是可逆的，那么这个变换过后就产生了信息丢失，比如一个向量$(1,1)$(1,1)经过一个不满秩的线性变换以后就变回不来了，向量就不是那个向量了。
  
• 定义：一类典型的优化问题，目标函数是变量的二次函数，而约束条件使变量的线性不等式
  $\min \frac1 2x^TQx+c^Tx \\ s.t.Ax\le b$min21​xTQx+cTxs.t.Ax≤b
  其中$x$x为d维向量，$Q\in\mathbb{R}^{d\times d}$Q∈Rd×d为实对称矩阵
• 我们知道$Q$Q的特征向量实质上是一组基向量，那么$x$x可以转换为这组特征向量的线性组合。假如Q是正定的，那么
  $x^TQx = x^{\prime T}Q^{\prime}x^\prime$xTQx=x′TQ′x′
  其中$Q^\prime$Q′为一个对角阵，元素为$Q$Q的特征值，$x^\prime$x′为通过线性变换后得到的向量。其中
  $Q = M^TQ^\prime M, x^\prime = Mx$Q=MTQ′M,x′=Mx
  可以看成是一个特征分解的过程。

1. 假如$Q$Q是正定的（即Q的特征值都是大于0的），则二次规划具有全局唯一解$x' = 0$x′=0，根据$x'$x′求出$x$x即可。试想一下，$Q'$Q′是一个对角阵且对角元素全大于0，则$x^{\prime T}Q^{\prime}x^\prime$x′TQ′x′展开必然是这样一种形式（懒得敲公式了我擦…直接写出来拍照吧）
   
2. 假如$Q$Q是半正定的（即Q的特征值都是大于或等于0的），且约束条件的可行域$Ax\le b$Ax≤b不为空，并且目标函数在此可行域具有下界，则二次规划具有局部最优。假如不存在约束条件，则最优解有无数个，只要令特征值为0对应的$x'$x′的元素为0即可（其他元素随你喜欢，天马行空都可以哈哈），这个也很好解释，也就是我懒得写的公式上边有些$q_i'=0$qi′​=0，其余的$q_i'>0$qi′​>0，只需要$q_i'>0$qi′​>0对应的$x_i'=0$xi′​=0即可，$q_i'=0$qi′​=0对应的$x_i'$xi′​=天马行空。
3. 假如$Q$Q是非正定矩阵，则…天马行空，有很多局部最优解，是一个np难问题

• 注意：在最优化问题中，只有hessian矩阵不定时才会出现鞍点（半正定也不会）！