无约束非线性规划.ppt

无约束非线性规划本章内容第一节:最优性条件现有多元函数f(x1x2…xn)若点x(0)=(x10x20…xn0)T存在一邻域(x(0))使对任意x(x(0))均有f(x(0))f(x)则称x(0)是f(x)的局部极小点。利用局部极小点的一阶必要条件求多元函数极值问题往往化成求解求解无约束非线性规划问题常用数值解法中的迭代法1.迭代法的基本思想：给定f(x)的极小点位置的一个初始估计x(0)依次计算产生一系列点x(k)（12…)希望点列x(k)的极限x*就是f(x)的一个极小点。计算公式：2.选择搜索方向和步长的原则：（1）目标函数值逐次减小这种算法称为下降算法。3.迭代法的基本步骤：(1)选择初始点x(0);(2)如已得到的迭代点x(k)不是最优解确定从x(k)点出发的搜索方向d(k)使f(x)沿d(k)方向可以找到x(k+1)目标函数有所下降。(3)在射线x(k)+d(k)(0)上选取步长k使第二节：一维搜索二、一维搜索的方法：三、一维搜索的基本思想：2.一维搜索的基本思想（1）确定初始单谷区间（2）根据区间消去法原理逐步缩小此区间（3）根据迭代精度要求确定最优解的近似值(1)确定初始单谷区间的进退法Step3.产生新的探测点a3＝a1＋hf3＝f(a3);Step4.比较函数值f2与f3：（a）如f2<f3则初始区间得到；h>0时[ab]=[a1a3];h<0时[ab]=[a3a1];（b）如f2>f3加大步长h＝2ha1=a2a2=a3转step3继续探测(2)消去法的基本原理四、黄金分割法（0.618法）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段与原来区间的三段具有相同的比例分布黄金分割法要求插入两点：黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度将赋以0.618。a黄金分割法例1用黄金分割法求解下列问题k五、牛顿法得对牛顿法的几何解释f()的极小点*应满足极值必要条件f’(*)=0。所以求f()的极小点也就是求解方程f’()=0的根。在k处用一抛物线k()代替曲线f()相当于用一斜线k’()代替曲线f’()。抛物线顶点k+1作为一个近似点应处于斜线k’()与轴的交点处。这样各个近似点是通过对f’()作切线求得与轴的交点而找到的所以牛顿法又称作切线法。牛顿法的计算步骤牛顿法的特点牛顿法最大的优点是收敛速度快。但是在每一点处都要计算函数的二阶导数因而增加了每次迭代的工作量。特别是用数值微分代替二阶导数时舍人误差会影响牛顿法的收敛速度。牛顿法要求初始点选得比较好（离极小点不能太远）否则有可能使极小化序列发散或收敛到非极小点。练习第三节：最速下降法和共轭梯度法一、最速下降法求解问题其中在第三步中可以直接使用精确线搜索。例2用最速下降法求的极小点。迭代两次计算各迭代点的函数值、梯度及其模并验证相邻两个搜索方向是正交的。其中0由由验证相邻两个搜索方向的正交性最速下降法的优点程序设计简单计算量小存储量小对初始点没有特别要求．有着很好的整体收敛性即使对一般的目标函数它也整体收敛．最速下降法的缺点：最速下降法是线性收敛的并且有时是很慢的线性收敛结论：最速下降法是基本算法之一而非有效的实用算法．最速下降法的本质是在迭代点处用线性函数来近似目标函数要想得到快速算法需要考虑对目标函数的高阶逼近．练习：用最速下降法求解二、共轭梯度法对于二次函数问题：如何构造出两两Q-共轭的方向？推导过程：可以证明在中途不停机的情况下这样得到的p1p2…pn是两两Q-共轭的因此x(n+1)一定是原问题的最优解。精确线搜索结果的推导对于一般可微函数的f(x)在每一迭代点x(k)可以近似的视为二次函数为了保证算法具有某种收敛性注意到共轭梯度法的第一步和最速下降法相同最速下降法具有收敛性。通常采用如下的起点周期性变化的共轭梯度法：从初始点x(1)出发依次用共轭梯度法产生迭代点x(2)x(3)…x(n+1)后以x(n+1)作为新的x(1)周期性重复以上步骤。例3用共轭梯度法求解停止迭代x(2)即为所求极小点一、牛顿法对于一般二阶连续可微函数在x(k)的局部若f(x)是一元函数则牛顿法就是用切线法解方程f’(x)=0在实际使用牛顿法时如何合适选取初始点是一个难以解决的问题。当f(x(