[toc]
二次规划
二次规划问题（Quadratic Programming，QP）一般描述为：
分类：
- 凸二次规划问题：G半正定，问题有全局解
- 严格凸二次规划问题：G正定，问题有唯一全局解
- 一般二次规划问题：G不定，问题有稳定点或局部解
等式约束二次规划问题
等式而约束二次规划问题形式为：
变量消去方法
- 通过将x的分量分成基本变量$\large{x_B}$与非基本变量$\large{x_N}$两部分，通过等式约束将基本变量用非基本变量表示出；
- 再将基本变量带入目标函数，从而消去基本变量，把问题化为一个关于非基本变量的无约束最优化问题；
- 最后求解无约束最优化问题的方法解之
例如，对X分块，A、G、g对应的也分块，得到
则等式约束化为$A^Tx=b\rightarrow A_B^Tx_B+A_N^Tx_N = b$
所以基本变量为$x_B=A^{-T}_B(b-A^T_Nx_N)$
带入目标函数得到
因为现在问题化为一个关于非基本变量的无约束最优化问题，所以我们只需要找出与$x_N$有关的项，其他均为常数项，最优化问题中不影响结果
找出所有$x_N^TAx_N$形式的项，得到$G_N = G_{NN}+A_NA_B^{-1}G_{BB}A_B^{-T}A_N^T-G_{NB}A_B^{-T}A_N^T - A_NA_B^{-1}G_{BN}$
找出所有$Ax_N$形式的项，得到$g_N =g_N - A_NA_B^{-1}g_B + (G_{NB}-A_NA_B^{-1}G_{BB})A_B^{-T}b$
所以关于非基本变量的无约束最优化问题形式为$q(x_N) = \frac{1}{2}x_N^TG_Nx_N + g_N^Tx_N$
求解该无约束最优化问题$min\ f(x_N)$
若$G_N$正定，则存在唯一解，$x_N^*=-G_N^{-1}g_N$
求$x^*$处的拉格朗日因子$\nabla{f(x^*)=\lambda{A}}$，即
取第一式$A_B^{-1}(G_{BB}x^_B+G_{BN}x_N^+g_B)=\lambda^*$
变量消除法的缺点：当$A_B$接近奇异矩阵时，求解过程的数值不稳定
零空间方法
零空间方法又称为广义变量消去法
像空间R(A)是矩阵的列向量张成的空间，核空间又称为矩阵的零空间N(A^T)
假定A是满秩，则将A分为两个互补的子空间，$R^n=R(A)+N(A^T)$，设$Y=[y_1,..,y_m]$是$R(A)$的一组线性无关向量，$Z=[z_1,…,z_{n-m}]$是$N(A^T)$的一组线性无关向量，我们可以选择$A,Z$使得$[Y\quad{Z}]$非奇异
并满足$A^TY=I,A^TZ=0$
令$x=Yx_y+Zx_z$，则$A^Tx=b$化为$A^TYx_y+A^TZx_z=b$
所以$x_y=b$,则$x=Yb+Zx_z$，带入目标函数，得
其中$Z^TGZ$为简约Hesse矩阵，若$Z^TGZ$正定，该问题的唯一解满足
得到$(Z^TGZ)x_z=-((g+GYb)^TZ)^T = -Z^T(g+GYb)$
最优解$x^=Yb+Zx^_z$,对应的$\lambda^$满足$A\lambda^=Gx^*+g$
两边同左乘$Y^T$得到，$(A^TY)^T\lambda^=Y^T(Gx^+g)$，则$\lambda^=Y^T(Gx^+g)$
零空间法适合解n-m较小的问题
如何选取满足条件的Y和Z：
用QR分解的方法：
$A=Q\begin{bmatrix}R\\0\end{bmatrix}=\begin{bmatrix}Q_1&Q_2\end{bmatrix}\begin{bmatrix}R\\0\end{bmatrix}=Q_1R$
取$Y=Q_1R^{-T},\quad Z=Q_2$，则Y和Z满足条件
一般选取方法：
任意选择满足$\begin{bmatrix}A&V\end{bmatrix}$非奇异的$V\in{R^{n(n-m)}}$,设$\begin{bmatrix}A&V\end{bmatrix}^{-1}=\begin{bmatrix}Y^T\\Z^T\end{bmatrix}$,其中$Y\in{\mathbb{R^{nm}}},Z\in{\mathbb{R^{n*(n-m)}}}$，则Y和Z满足条件
Lagrange方法
等式约束二次规划的Lagrange函数为：
其KKT条件为：
表示为KKT方程组为：
其中$\begin{bmatrix}G&-A\-A^T&0\end{bmatrix}$为KKT矩阵
设A满秩，$Z$满足$AZ=0$，也即$Z$的列组成了A的零空间，那么$Z^TGZ$是正定，则KKT矩阵非奇异且有唯一解，证明如下
如果我们有$\begin{bmatrix}G&-A\-A^T&0\end{bmatrix}
\begin{bmatrix}u\\v\end{bmatrix}=0$
得到$A^Tu=0$
则$\begin{bmatrix}u^T&v^T\end{bmatrix}\begin{bmatrix}G&-A\-A^T&0\end{bmatrix}
\begin{bmatrix}u\\v\end{bmatrix}=u^TGu=0$
则对简约Hesse矩阵$Z^TGZ$，$u^TGu=u^TZ^TGZu=0$，因为$Z^TGZ>0$，所以$u=0$
根据$Gu-Av=0$，得到$Av=0\rightarrow v=0$
设A行满秩，$Z^TGZ$正定，那么$x^*$是二次规划的唯一全局解
对KKT矩阵准三角化
其中
所以
带入KKT矩阵，得到
令
则
所以得到
我们通过Cholesky分解的方法求解这三个方程，算法分为两部分：第一部分对矩阵G和$A^TG^{-1}A$的分解，第二部分为回代、求解。具体步骤如下：
对矩阵G作Cholesky分解，求下三角阵L，得到$G=LL^T$
计算$V=A^TG^{-1}A$，求解三角矩阵方程$LY=A$得到Y，则$V=Y^TY$
在这里，$V=A^TG^{-1}A=A^T(LL^T)^{-1}A=A^TL^{-T}L^{-1}A=(L^{-1}A)^T(L^{-1}A)$
令$L^{-1}A=Y$，得到$LY=A$，求解后得到$Y$，带入就是$V=Y^TY$
对$V=A^TG^{-1}A$作Cholesky分解，使得$V=\tilde{L}\tilde{L}^T$
解方程：$Lu=-g,\quad L^Tw=u$，得到$w$，计算$\tilde{b}=-A^Tw+b$
由于$G=LL^T$，带入$Gw=-g$得到$LL^Tw=-g$
令$u=L^Tw$，则$Lu=-g$，解得$w$，令$\tilde b = -A^Tw+b$
解方程：$\tilde{L}v=\tilde{b},\quad \tilde{L}^T\lambda=v$,得到$\lambda^$，再计算$\tilde{g}=A\lambda^-g$
由于$V=\tilde L\tilde L^T$，带入得$\tilde L\tilde L^T\lambda=\tilde b$
令$v=\tilde L^T\lambda$,则$\tilde Lv=\tilde b$，解得$\lambda$。令$\tilde g = A\lambda^*-g$
解方程:$Ly=\tilde{g},\quad L^Tx=y$得到$x^*$
将$G=LL^T$带入$Gx=\tilde g$，得到$LL^Tx=\tilde g$
令$y=L^Tx$,则$Ly=\tilde g$,解出$x^*$