二次规划_1_——Lagrange方法
二次规化是非线性规化中的一种特殊情形，其目标函数是二次实函数，约束是线性的。考试中会考到四种方法，分别为：Lagrange方法、起作用集方法、直接消去法和广义消去法。前两种在教材上有详细描述，后面两种出现在PPT上面。本节先介绍最简单的方法：Lagrange方法。
一、Lagrange方法适用情形
Lagrange方法适用于具有等式线性约束的二次规化问题： m i n 1 2 x T H x + c T x s . t . A x = b min \ \ \ \frac{1}{2}x^T Hx+c^Tx \\ s.t. \ \ \ Ax=b min 21xTHx+cTxs.t. Ax=b
二、Lagrange方法推导
首先定义Lagrange函数，将约束式和目标函数进行合成：
L
(
x
,
λ
)
=
1
2
x
T
H
x
+
c
T
x
−
λ
T
(
A
x
−
b
)
L(x,\lambda)=\frac {1}{2}x^THx+c^Tx-\lambda^T(Ax-b)
L(x,λ)=21xTHx+cTx−λT(Ax−b) 之后令L函数关于
x
x
x和
λ
\lambda
λ的梯度分别为0，即
▽
x
L
(
x
,
λ
)
=
0
\triangledown_x L(x,\lambda)=0
▽xL(x,λ)=0,
▽
λ
L
(
x
,
λ
)
=
0
\triangledown_\lambda L(x,\lambda)=0
▽λL(x,λ)=0，可以得到：
H
x
+
c
−
A
T
λ
=
0
−
A
x
+
b
=
0
Hx+c-A^T\lambda=0 \\ -Ax+b=0
Hx+c−ATλ=0−Ax+b=0 将
x
x
x和
λ
\lambda
λ视为变量，写成矩阵形式则为：
[
H
−
A
T
−
A
0
]
[
x
λ
]
=
[
−
c
−
b
]
\begin{bmatrix} H&-A^T \\ -A&0 \end{bmatrix}\begin{bmatrix} x\\ \lambda \end{bmatrix}=\begin{bmatrix} -c\\ -b \end{bmatrix}
[H−A−AT0][xλ]=[−c−b] 其中左侧矩阵称为Lagrange矩阵。可以发现，如果两侧同时左乘Lagrange矩阵的逆，则可以直接得到
x
x
x和
λ
\lambda
λ的解，接下来定义逆阵：
[
H
−
A
T
−
A
0
]
T
=
[
Q
−
R
T
−
R
S
]
\begin{bmatrix} H&-A^T \\ -A&0 \end{bmatrix}^T=\begin{bmatrix} Q&-R^T \\ -R&S \end{bmatrix}
[H−A−AT0]T=[Q−R−RTS] 逆阵快速计算方法如下：
Q
=
H
−
1
−
H
−
1
A
T
(
A
H
−
1
A
T
)
−
1
A
H
−
1
R
=
(
A
H
−
1
A
T
)
−
1
A
H
−
1
S
=
−
(
A
H
−
1
A
T
)
−
1
Q=H^{-1}-H^{-1}A^T(AH^{-1}A^T)^{-1}AH^{-1} \\ R=(AH^{-1}A^T)^{-1}AH^{-1}\\ S=-(AH^{-1}A^T)^{-1}
Q=H−1−H−1AT(AH−1AT)−1AH−1R=(AH−1AT)−1AH−1S=−(AH−1AT)−1 好吧这个是真的不好记，我的方法如下：先记S，之后以H逆为中心元素左组合右组合，左组合先乘到右边，右组合后乘到左边，最后用H逆减去。
最后根据左乘后的式子进行求解
x
x
x和
λ
\lambda
λ：
[
x
‾
λ
‾
]
=
[
Q
−
R
T
−
R
S
]
[
−
c
−
b
]
\begin{bmatrix} \overline{x}\\ \overline{\lambda} \end{bmatrix}=\begin{bmatrix} Q&-R^T \\ -R&S \end{bmatrix}\begin{bmatrix} -c\\ -b \end{bmatrix}
[xλ]=[Q−R−RTS][−c−b]
三、Lagrange方法另一种表现形式
之所以提这个是因为起作用集方法中，乘子
λ
\lambda
λ的解算用到了公式，所以在本节末尾给出。
回顾上面的求解过程会发现，所有的运算都是在二次规划中系数的基础上进行的，通过给定的系数直接解算
x
x
x和
λ
\lambda
λ。考虑如果给定了一个可行点
x
(
k
)
x^{(k)}
x(k)，则可以按照下面公式直接求解，其本质是上一个求解公式的变形。
x
‾
=
x
(
k
)
−
Q
g
k
λ
‾
=
R
g
k
\overline{x}=x^{(k)}-Qg_k \\ \overline{\lambda}=Rg_{k}
x=x(k)−Qgkλ=Rgk 最后的公式在起作用集方法中有重要应用。