非线性规划.ppt

文档介绍：第四节非线性规划模型的解
•二次插值法
•最速下降法
•罚函数法
非线性规划模型的一般形式:
一、无约束模型:
二、有约束模型:
则称为局部最优解,
或局部解;
则称为整体最优解,
或最优解或解
一、无约束模型的解
沿某直线方向求目标函数的极小值点,称为一维搜索。
高维问题可通过一系列的一维搜索,求出其近似最优解。
一维搜索
沿某些方向作一维搜索
化为无约束问题
讨论顺序:
1. 一维搜索(二次插值法)
单峰函数
或
过三点作抛物线:
有
故方程组有唯一解,且
即抛物线的开口向上。
令
得极小值点
再从中选出满足前面不等式的三点,
重复前面的过程,直到满足终止条件:
则
注:迭代时,若出现退化情形
可取
继续迭代。
#
2. 最速下降法
f (X)
D= -f (X)
第1步求新点
设f(X) 可微,给定初始点X1,>0,每次沿使f 下降得最快的负梯度方向 D=-f (X)搜索,直到满足终止条件为止。
第k次迭代
令
注意: k不是步长(因Dk不是单位向量),
且非负(否则,不是下降得最快的方向)。
得新点
设已得Xk
第2步验证终止条件
否则,将Xk+1作为新的出发点, 作为新的迭代方向,进行下一次迭代。
有结论:
因为
可见,搜索路线呈之字形。
该法的优点是:不论维数多高,每次迭代只沿一个方向搜索。
“较圆”时,则收敛得较快;
“较扁”时,则收敛得较慢。
当目标函数等值线
•
实际中,前面阶段可用最速下降法,
后面阶段用旋转方向法。
缺点是:收敛速度“前快后慢”。
例求解
解
因
<
所以令
则有
由
得新点:
第1步
第2步
因
<
令
沿方向搜索,得
迭代:
经5次迭代后得解点
而本题的精确最优解是:
。