文档介绍：运筹学非线性规划126-7
约束优化的KKT条件
KKT条件：
约束优化的KKT条件
KKT条件：
该问题最优解：
运筹学非线性规划126-7
约束优化的KKT条件
KKT条件：
约束优化的KKT条件
KKT条件：
该问题最优解：
二次规划
二次规划与线性规划问题的不同之处仅仅在于目标函数也包括 和 项。用矩阵符号表示二次规划问题：
用向量元素表示：
半正定矩阵：如果对任何非零向量 ，都有 成立，且有非零向量 ，使 ，则称矩阵A为半正定矩阵。
二次规划
例如
此时：
二次规划
对于二次规划的KKT条件（以上题为例）
KKT条件：
将不等式变为等式。
二次规划
注意此时条件2与条件4可表示为：
对于每个配对—— ——其中的两个变量称为互补变量。这些条件得到一个新的组合约束
称为互补约束。
二次规划
整个条件集合的简便形式
用矩阵符号表示：
二次规划
改进的单纯形法
引入人工变量 ，相当于应用单纯形法求解以下的线性规划问题
满足从KKT条件得到的线性规划约束，但也包括这些人工变量。
同原单纯形法相比，修改发生于：
限制-输入规则：当你选择一个输入基变量时，考虑排除互补变量已经是一个基变量的任一非基变量；选择应该是根据单纯形表的一般标准从其他非基变量中做出的。
二次规划
依旧用本节刚开始的例子说明这种方法
在引入所需人工变量后，用改进的单纯形法显性说明的线性规划问题是
附加的互补约束用限制-输入规则，算法自动的执行该约束。
二次规划
改进单纯形法对二次规划例子的应用
迭代
基变量
方程
Z
x1
x2
u1
y1
y2
v1
z1
z2
右端项
0
Z
(0)
-1
0
-4
-3
1
1
0
0
0
-45
z1
(1)
0
4
-4
1
-1
0
0
1
0
15
z2
(2)
0
-4
8
2
0
-1
0
0
1
30
v1
(3)
0
1
2
0
0
0
1
0
0
30
1
Z
(0)
-1
-2
0
-2
1
1/2
0
0
1/2
-30
z1
(1)
0
2
0
2
-1
1/2
0
1
1/2
30
x2
(2)
0
-1/2
1
1/4
0
-1/8
0
0
1/8
3+3/4
v1
(3)
0
2
0
-1/2
0
1/4
1
0
-1/4
22+1/2
二次规划
改进单纯形法对二次规划例子的应用
迭代
基变量
方程
Z
x1
x2
u1
y1
y2
v1
z1
z2
右端项
2
Z
(0)
-1
0
0
-5/2
1
3/4
1
0
1/4
-7-1/2
z1
(1)
0
0
0
5/2
-1
-3/4
-1
1
3/4
7+1/2
x2
(2)
0
0
1
1/8
0
-1/16
1/4
0
1/16
9+3/8
x1
(3)
0
1
0
-1/4
0
1/8
1/2
0
-1/8
11+1/4
3
Z
(0)
-1
0
0
0
0
0
0
1
1
0
u1
(1)
0
0
0
1
-2/5
-3/10
-2/5
2/5
3/10
3
x2