问题

$\mathop{min}\limits_{X}g(X) = \frac{1}{2}X^TGX+X^TC$Xmin​g(X)=21​XTGX+XTC

s.t.$a_i^TX = b_i,i\in E$aiT​X=bi​,i∈E
$a_i^TX \geq b_i,i\in F$aiT​X≥bi​,i∈F

KKT 矩阵

构造拉格朗日乘子，有
$L(X,\lambda)=\frac{1}{2}X^TGX+X^TC-\lambda^T(AX-b)$L(X,λ)=21​XTGX+XTC−λT(AX−b)
A是m*n大小的，假设m不大于n【n = X的变量数】
那么有

举例

应是采用了这位大佬的例子

呃，这里这位大佬粗心了。K矩阵第四块得是全0的。计算的话就是把初始的X1,X2带进去，计算出来$\lambda1$λ1,$\lambda2$λ2。然后更新。

因为$\lambda$λ没有大于0 的，就不是最优方案。去除$\lambda$λ中最大的$\lambda1$λ1对应的约束3，那么工作集中就剩下约束5。再使用KKT矩阵，计算出$X_2$X2​和$\lambda_2$λ2​，再计算$p_1$p1​,$\alpha_1$α1​

这一步工作集为空啦，就变成无约束优化问题了

这里确定$\alpha_2$α2​用了技巧，先带进约束1计算。发现步子不能迈那么大，就把$p_2$p2​的步子缩小，卡得刚好约束1取等号，并且将约束1添加至工作集

OK，就这样，结束。完整的PDF是Numerical Optimization - Unit 8: Quadratic Programming, Active Set Method, and Sequential Quadratic Programming，作者是Lee,Che-Rung.我会上传