文档介绍：规划模型专题二非线性规划
第1页，本讲稿共60页
第一部分 非线性规划
前面有老师介绍了线性规划问题，典型的问题“下料问题”、“运输问题”等，这些问题都比较简单。但实际中的问题不仅仅是简单的线性规划问题，可能是比较繁杂的非线年的题目建模不难，只是在条件的考虑上和建模中目标函数的表达方面较难一点。但在当时不然。
是一个带不等式约束的非线性规划问题。
而且不可能转化成线性的形式。
第19页，本讲稿共60页
若目标函数或约束条件中含有非线性函数，则称这种模型问题为非线性规划（Non-Linear Prog-ramming），简记为NLP。
NLP的一般形式
其中，
中至少有一个是
非线性函数。
第20页，本讲稿共60页
无约束极值问题是NLP的一种特殊形式
如数据拟合的最小二乘问题就是一个无约束极值问题。
其思想是：观察点（实验数据点）到曲线的距离的平方之和最小
二、无约束极值问题
第21页，本讲稿共60页
理论上无约束极值问题可化成求解
即解一个 n 元方程组，且往往是非线性方程组。
而一般说来，非线性方程组的求解并不比求无约束极值容易。
第22页，本讲稿共60页
求解无约束极值问题的基本方法：迭代法
从一个给定的初始可行点 出发，依次
产生一个可行点列
的一个极小值点,
恰好是
使得某个
基本思路：
或
收敛于
,
称具有这种性质的算法
是收敛的.
第23页，本讲稿共60页
由
迭代到
时,
记
即
其中向量
为搜索方向,
实数
称为步长,
确定以后,
由
可唯一地确定
从
出发就可确定点列
第24页，本讲稿共60页
迭代的方法很多,
各种迭代法的区别在于选取
的方式不同,
而
尤为关键.
一般要求
递减,
具有这种性质的算法叫做下降
算法.
下面介绍的迭代法均为下降算法
第25页，本讲稿共60页
若已得
下降得最多,
并确定了
的可行下降方向
上选取步长
则在射线
使
且使
即求
求
的过程称为一维搜索.
1. 下降算法
第26页，本讲稿共60页
于是一维搜索归结为求解一维无约束极值问题:
其算法有Newton法、平分法、黄金分割法
（）、分数法（Fibonacci法）、抛物线法（二次插值法）等，
前两种算法需计算
的导数，
后三种算法只需计算
的函数值。
下面仅介绍Newton法，对其他方法的了解可参考有关书籍。
第27页，本讲稿共60页
按
给定初始可行点 和控制误差 ，
迭代格式
迭代，
当
时，
即求得
的最优解的近似解
停止计算。
Newton 法介绍
第28页，本讲稿共60页
♂一个好的算法必须以较快的速度收敛到
最优解。
设算法产生的点列
收敛于最优解
若存在
及
使
则称
为 p 阶收敛的。
该算法也是 p 阶收敛的。
第29页，本讲稿共60页
称为线性收敛；
当
且
时，
称为超线性收敛；
当
时，
称为平方收敛；
当
时，
第30页，本讲稿共60页
一个算法是否收敛，
往往与
的选取有关
① 若当
充分接近
时，
由算法产生的点列
才收敛于
则称该算法为具有局部收敛
性的算法；
② 若对
则称该算法为具有全局收敛性的算法。
由算法产生 的点列
均收敛
于
第31页，本讲稿共60页
Newton法是平方收敛的，具有局部收敛性；抛物线法是超线性收敛的，具有全局收敛性；平分法、黄金分割法、分数法是线性收敛的，具有全局收敛性。
常见一维搜索算法的收敛性
第32页，本讲稿共60页
当
具有多个极小值点时，
则算法求得
的往往是
的一个局部极小值点。
此时可
改变
的取值，重新迭代求解。
若求得多个极小值点，则从中选择一个
较满意的结果。
♂说明：
第33页，本讲稿共60页
在多数情况下，一维搜索的一个基本工具，
而此时一维搜索的精度并不要求很高，故一维
搜索实现的方便性更重要些。
第34页，本讲稿共60页
1847年Cauchy提出了第一个无约束极值问题的算法——梯度法或最速下降法：
其中
给定初始点
和控制误差
求
当
时，
即得
的最优解
的近似解
停止计算。
2. 梯度法
第35页，本讲稿共60页
该算法具有全局收敛性，是线性收敛的，但有时是很慢的线性收敛，这似乎与“最速下降”矛盾。其实不然，最速下降方向函数在某点处的局部性质，对局部来说是最速下降方向，对全局来说却不一定是最速下降方向，故梯度法不是有效的实用算法。
通过对它改进或利用