等式约束二次规划——变量消除法和KKT法
基本思想
如果遇到这种简单的问题：
m
i
n
x
1
2
+
x
2
2
+
x
1
+
2
x
2
s
.
t
.
x
1
+
x
2
=
1
\begin{aligned} &min x^2_1+x^2_2+x_1+2x_2 \\ &s.t. x_1+x_2=1 \end{aligned}
min x12+x22+x1+2x2s.t. x1+x2=1
基本的思想就有两个，第一种是消除一个变量，这样就可以很简单的求解出来：
m
i
n
(
1
−
x
2
)
2
+
x
2
2
+
1
−
x
2
+
2
x
2
\begin{aligned} &min (1-x_2)^2+x^2_2+1-x_2+2x_2 \end{aligned}
min (1−x2)2+x22+1−x2+2x2
第二种就是可以使用拉格朗日法，这最后可以推导出KKT条件:
m
i
n
x
1
2
+
x
2
2
+
x
1
+
2
x
2
+
λ
(
x
1
+
x
2
−
1
)
min x^2_1+x^2_2+x_1+2x_2+λ(x_1+x_2-1)
min x12+x22+x1+2x2+λ(x1+x2−1)
对于等式约束的二次规划方法，这两种思路都可以求解，把上面的问题变成更高级更抽象的形式：
m
i
n
1
2
x
T
Q
x
+
c
T
x
s
.
t
.
A
x
=
b
\begin{aligned} &min \frac{1}{2}x^TQx+c^Tx\\ &s.t. Ax=b \end{aligned}
min 21xTQx+cTxs.t. Ax=b
变量消除法
这种方法对应的是上一章说的第一种思想，基本推导思路其实是一样的，只不过变成了更高级的矩阵形式，相同的推导还有线性规划中的单纯形方法。
一般来说，等式约束中的
A
A
A是一个扁长的矩阵，也就是说虽然这个是等式，但是满足它的也有很多很多的解。最简单的例子就是上一章的
x
1
+
x
2
=
1
x_1+x_2=1
x1+x2=1。所以这里我们和上一章思路一样，使用某些变量表示其他变量，然后变成无约束二次规划进行求解。无约束二次规划——共轭梯度法
对 A x = b Ax=b Ax=b的求解
如果熟悉单纯形法的意义和推导，其实就是一模一样的。
首先将矩阵分块,等式写成：
(
B
,
N
)
(
x
b
x
n
)
=
b
(B,N)\left( \begin{array}{c} x_b\\ x_n \end{array} \right)=b
(B,N)(xbxn)=b
这里
x
b
x_b
xb是一组基，对应的矩阵B是一个方阵，而且应该是可逆的。那么后面的工作就是做一个简单的移项:
B
x
b
+
N
x
n
=
b
x
b
=
B
−
1
b
−
B
−
1
N
x
n
Bx_b+Nx_n=b\\ x_b=B^{-1}b-B^{-1}Nx_n
Bxb+Nxn=bxb=B−1b−B−1Nxn
这样原变量就可以写成：
x
=
(
x
b
x
n
)
=
(
B
−
1
b
−
B
−
1
N
x
n
x
n
)
=
(
B
−
1
b
0
)
+
(
−
B
−
1
N
I
)
x
n
x=\left( \begin{array}{c} x_b\\ x_n \end{array} \right)=\left( \begin{array}{c} B^{-1}b-B^{-1}Nx_n\\ x_n \end{array} \right)=\left( \begin{array}{c} B^{-1}b\\ 0 \end{array} \right)+\left( \begin{array}{c} -B^{-1}N\\ I \end{array} \right)x_n
x=(xbxn)=(B−1b−B−1Nxnxn)=(B−1b0)+(−B−1NI)xn
即写成了一个类似于
x
=
x
0
+
Z
x
n
x=x_0+Zx_n
x=x0+Zxn的形式，这样我们将其代入进去，并使用无约束方法求解，就能解出答案
唯一解条件
我们将
x
=
x
0
+
Z
x
n
x=x_0+Zx_n
x=x0+Zxn带入到目标函数中：
1
2
(
x
0
+
Z
x
n
)
T
Q
(
x
0
+
Z
x
n
)
+
c
T
(
x
0
+
Z
x
n
)
\frac{1}{2}(x_0+Zx_n)^TQ(x_0+Zx_n)+c^T(x_0+Zx_n)
21(x0+Zxn)TQ(x0+Zxn)+cT(x0+Zxn)
这里面
x
0
x_0
x0是已知的，
x
n
x_n
xn是未知的，并且这里再次省略常数项，他就变成了如下的形式：
1
2
x
n
T
(
Z
T
Q
Z
)
x
n
+
c
T
Z
x
n
\frac{1}{2}x_n^T(Z^TQZ)x_n+c^TZx_n
21xnT(ZTQZ)xn+cTZxn
对其求导等于零：
(
Z
T
Q
Z
)
x
n
+
b
1
=
0
(Z^TQZ)x_n+b_1=0
(ZTQZ)xn+b1=0
如果想要其有唯一最优解，也就必须要满足
Z
T
Q
Z
Z^TQZ
ZTQZ为正定。
KKT法
由于这个是凸二次规划问题，其KKT点就是全局解，所以可以考虑用KKT条件对其求解。这里可以直接使用KKT的五行公式，但是由于没有不等式，所以其实会简化不少。也可以从拉格朗日法推导出来，为了和第一章的思路一致，这里简单推导一下
拉格朗日法到KKT点
1
2
x
T
Q
x
+
c
T
x
+
λ
T
(
A
x
−
b
)
\frac{1}{2}x^TQx+c^Tx+λ^T(Ax-b)
21xTQx+cTx+λT(Ax−b)
将其对
x
x
x求导等于零，得出：
Q
x
+
c
+
A
T
λ
=
0
Qx+c+A^Tλ=0
Qx+c+ATλ=0
对
λ
λ
λ求导等于零，得出：
A
x
−
b
=
0
Ax-b=0
Ax−b=0
将其合写成矩阵的形式：
(
Q
A
T
A
0
)
n
+
m
(
x
λ
)
=
(
−
c
b
)
\left( \begin{array}{c} Q&A^T\\ A&0 \end{array} \right)_{n+m}\left( \begin{array}{c} x\\ λ \end{array} \right)=\left( \begin{array}{c} -c\\ b \end{array} \right)
(QAAT0)n+m(xλ)=(−cb)
这样将这个方程组求解之后就可以求得最优解。
两种方法的比较
我们假设原来的变量为
n
n
n个，矩阵
A
A
A的秩为
r
(
A
)
=
m
r(A)=m
r(A)=m。第一种方法其实是转化成了一个
n
−
m
n-m
n−m维的问题，也就是说求解
n
−
m
n-m
n−m个方程组就能解决这个问题。而第二个方法是将其转化成一个
n
+
m
n+m
n+m维的问题，即
n
n
n个变量，
m
m
m个乘子。
如果建模建出来的问题就只需要求解一次等式二次规划问题，那么哪一个其实都可以求解，如果维数太大，建议用第一种方法。
如果需要多次求解，需要用到乘子的信息，那就推荐用KKT方法，比如不等式约束的二次规划问题。