二次规划(Quadratic programming)与拉格朗日乘法(Lagrange multiplier)
二次规划具体来说就是一个优化过程，首先有一个二次型的目标函数，然后给定一些线性约束后对这个二次函数再服从线性约束的情况下进行优化(求最大或最小值的解)
二次规划的定义
定义一个n个变量与m个限制的二次规划问题，则我们可以得到
在Ax\leq b的限制条件下，找到一个n维向量x使得f(x) = (1/2)x^TQx+c^Tx为最小，这里的n维向量x就是这个二次规划问题的解
还有一些关于二次规划问题的结论:
如果Q是半正定矩阵，则f(x)为凸函数
如果Q是正定矩阵，那么全局最小值就是唯一的
如果Q=0，二次规划问题就会变为一个线性规划问题
如果至少有一个向量x满足约束条件而且f(x)在可行域又下界，则二次规划问题有个全局最小值x
拉格朗日乘数法求解二次规划问题
给定一个目标函数f(x)，并且满足约束g(x)=0 则：
\begin{matrix}min&f(x)\\s.t.&g(x)=0\end{matrix}
这个问题实际上可以描述为求f(x)在g(x)=0时的局部极值，所以可以引入拉格朗日乘数\lambda 来进行求解：
L(x,\lambda)=f(x)+\lambda g(x)
接下来对L(x,\lambda)求偏导等于0，则可求的局部最小值
\begin{aligned}&\nabla_{\mathbf{x}}L={\frac{\partial L}{\partial\mathbf{x}}}=\nabla f+\lambda\nabla g=0\\&\nabla_{\lambda}L={\frac{\partial L}{\partial\lambda}}=g(\mathbf{x})=0\end{aligned}
这里的\nabla_x和\nabla_{\lambda}代表的就是在x和\lambda 方向上的梯度，也就是偏导
例子1
\begin{array}{c}min&x_1^2+x_2^2\\s.t.&x_1+x_2=1\end{array}
这其中的目标函数为f(x) = x_1^2+x_2^2,约束条件为g(x)=1-x_1-x_2
标准化二次规划问题
我们也可以把这个二次规划问题写为标准形式f(x) = (1/2)x^TQx+c^Tx和Ax=b
首先确定矩阵Q和向量c：
x_1^2+x_2^2=\frac{1}{2}\begin{pmatrix}x_1&x_2\end{pmatrix}\begin{pmatrix}2&0\\0&2\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}
所以可以得出
Q=\begin{pmatrix}2&0\\0&2\end{pmatrix}\\c=\begin{pmatrix}0\\0\end{pmatrix}
然后确定约束矩阵A和向量b:
x_1+x_2=\begin{pmatrix}1&1\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=1
所以可以得出
A=\begin{pmatrix}1&1\end{pmatrix}\\b=(1)
使用拉格朗日乘数法进行求解
首先构造拉格朗日函数
L = x_1^2+x_2^2+ \lambda(1-x_1-x_2)
其KKT(Karush-Kuhn-Tucker Conditions)条件(对L进行求导)为:
2x_{1}-\lambda=0\\2x_{2}-\lambda=0\\1-x_{1}-x_{2}=0
则可以求解得到\lambda^*=1,x_1^*=0.5,x_2^*=0.5
例子2
\begin{array}{ll}{min\quad x_{1}^{2}+x_{2}^{2}}\\{s.t. x_{1}+x_{2}=1; x_{2}<3}\end{array}
标准化二次规划问题
我们也可以把这个二次规划问题写为标准形式f(x) = (1/2)x^TQx+c^Tx和Ax=b与Gx\leq h
首先确定矩阵Q和向量c：
x_1^2+x_2^2=\frac{1}{2}\begin{pmatrix}x_1&x_2\end{pmatrix}\begin{pmatrix}2&0\\0&2\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}
所以可以得出
Q=\begin{pmatrix}2&0\\0&2\end{pmatrix}\\c=\begin{pmatrix}0\\0\end{pmatrix}
然后确定等式约束矩阵A和向量b:
x_1+x_2=\begin{pmatrix}1&1\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=1
所以可以得出
A=\begin{pmatrix}1&1\end{pmatrix}\\b=(1)
然后确定不等式约束矩阵G和向量h:
x_1+x_2=\begin{pmatrix}0&1\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}\leq3
所以可以得出
G=\begin{pmatrix}0&1\end{pmatrix}\\h=(3)
使用拉格朗日乘数法进行求解
首先构造拉格朗日函数
L\left(x_1,x_2,\lambda,\mu\right)=x_1^2+x_2^2+\lambda\left(1-x_1-x_2\right)+\mu\left(x_2-3\right)
其KKT(Karush-Kuhn-Tucker Conditions)条件(对L进行求导)为:
\begin{aligned} \frac{\partial L}{\partial x_{i}}& =0,i=1,2, \\ x_{1}+x_{2}& =1 \\ x_{2}-3& \leq0 \\ \mu & \geq0 \\ \mu\left(x_{2}-3\right)& =0. \end{aligned}
求解偏导可得：
\frac{\partial L}{\partial x_1}=2x_1-\lambda=0\quad,\quad\frac{\partial L}{\partial x_2}=2x_2-\lambda+\mu=0 \\ x_{1}=\frac{\lambda}{2} , x_{2}=\frac{\lambda}{2}-\frac{\mu}{2}
带入x_1+x_2=1可以得到：
x_{1}=\frac{\mu}{4}+\frac{1}{2} , x_{2}=-\frac{\mu}{4}+\frac{1}{2}
又由于x_2<3可以得到\mu>-10,但是由于我们已经有\mu\ge 0所以可以忽略这项约束，又由于\mu(x_2-3)=0,所以得到\mu =0和x_2 =3两个条件，但是后者和x_1+x_2=1冲突，所以需要舍弃(这里的冲突原因不是很清楚，大概就是说常见的情况下x的值需要非负，所以排除负数值)，因此我们可以得到解\lambda^*=1,\mu^*=0,x_1^*=0.5,x_2^*=0.5
参考
https://zh.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92
https://blog.csdn.net/weixin_47932058/article/details/124429510
