文档介绍：第十二章 非线性规划
整理课件
2022/9/6
回顾最优条件
单变量非约束
多变量非约束
有约束的,但只有非负约束
充分条件可能是:是凹函数
最优性的必要条件第十二章 非线性规划
整理课件
2022/9/6
回顾最优条件
单变量非约束
多变量非约束
有约束的,但只有非负约束
充分条件可能是:是凹函数
最优性的必要条件:
整理课件
一般约束问题
充分条件可能是:是凹函数并且是凸函数()
最优性的必要条件:KKT条件
整理课件
最优性的充要条件
问题
最优性的必要条件
充要条件可能是
单变量非约束
是凹函数
多变量非约束
是凹函数
有约束的,但只有非负约束
是凹函数
一般约束
KKT条件
是凹函数并且
是凸函数()
整理课件
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