运筹学 非线性规划 课件.ppt

《运筹学 非线性规划 课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非线性规划约束问题：D称为可行域。无约束问题：运用最小二乘思想，可将其化为三维空间的无约束非线性规划问题，即例.多参数曲线拟合问题已知热电阻R与温度t的函数关系为其中x1,x2,x3是待定参数。通过试验，得到R和t的15组数据:i12…15ti5055…120Ri3478028610…33071.基本概念迭代算法：i)给定初始点x0,设k=0;ii)按照某种规则确定搜索方向pk;iv)计算iii)按照某种规则确定搜索步长tk;v)判断xk+1是否满足终止准则：是，x*=xk+1，终止;否，k=k+1，转步骤ii）。xkpkxk+1

2、tk可行下降方向迭代算法中如何确定搜索步长tk？(1)定步长，即取tk等于某一常数。(2)可接受点法，即任意选取能使目标函数值下降的tk。(3)（精确）一维搜索，即求解一元函数极小化问题：若迭代点列{xk}有子序列收敛于问题的解x*，则称该迭代算法收敛。若对于任意初始点x0，迭代算法收敛，则称为全局收敛；若仅当x0属于x*的某个邻域时，迭代算法收敛，则称为局部收敛。若迭代算法产生的点列{xk}满足称为下降算法。终止准则：xkxk+1x*xkxk+1x*算法分类需要利用函数的解析性质（导数和高阶导数）的算法，如梯度法、牛顿法。解析法

3、：对函数的解析性质没有要求，只需利用函数值的算法，如0.618法、单纯形替换法。直接法：凸规划二次规划极小点的判定条件函数在极小点附近的等值线为近似的同心椭圆。正定二次函数有唯一极小点两个结论：2.一维搜索在迭代法中确定搜索步长tk需要一维搜索：考虑一元函数极小化问题：方法:如何确定一个包含极小点的区间？首先定出一个包含f(t)的极小点的区间，然后不断缩小区间的长度，当区间充分小时，取其中的一点作为近似极小点。进退法:从一点出发，按一定的步长寻找函数值呈现“高-低-高”的三点，若一个方向不成功，就退回来，然后沿相反方向寻找。任取初

4、始点t0,计算f(t0),取步长h>0,计算f(t0+h),若f(t0)>f(t0+h),令t1=t0+h,h=2h,计算f(t1+h),若f(t1)>f(t1+h),令t2=t1+h,h=2h,计算f(t2+h),如此继续下去,直到对某个k得到f(tk)

5、tk-h)>f(tk),此时得到一个包含极小点的区间[tk-h,tk–1]。黄金分割法（0.618法）解一元函数极小化问题假设：f(t)在[a,b]上是单谷函数，即f(t)在[a,b]上有唯一极小点（设为t*）且.....在[a,b]上任取两点t1

6、-1)2在[0,3]上的极小点。解.3.最速下降法（梯度法）注：在极小点附近，目标函数可用二次函数近似，因此等值面近似为椭球面，上述性质说明最速下降法的搜索路径呈直角锯齿状：最速下降方向只是目标函数的局部下降最快方向，最速下降算法收敛速度慢，但具有整体收敛性。近似最佳步长：右端为二次函数，时达到最小。4.共轭方向法注：共轭是正交的推广。性质：共轭向量组一定线性无关。正定二次函数的共轭方向法：其中A正定。性质：共轭方向法用于正定二次函数，则至多经过n次迭代即得极小点。问题：如何选择一组共轭方向？共轭梯度法：以已知迭代点处的梯度方向为

7、基础产生共轭方向。因此共轭梯度法的搜索方向：共轭梯度法用于正定二次函数时具有性质：为了将共轭梯度法用于非二次函数，需消去公式中的A。5.牛顿法在xk附近，f(x)有近似式：牛顿法的迭代公式牛顿方向(1)若f(x)为正定二次函数，则牛顿法只需一步迭代即得极小点，因为此时有f(x)=g(x)，所以(2)牛顿法具有二阶收敛速率，但要求初始点选在极小点附近。几点说明：6.单纯形替换法单纯形替换法是直接法，只需利用函数值。何谓单纯形?一维单纯形：线段二维单纯形：三角形三维单纯形：四面体如何构造单纯形?算法思想：给定初始点x0，并构造初始单纯

8、形S0，然后进行单纯形替换迭代，迭代包括反射步、延伸步、收缩步或棱长减半等类型。xhxrxhxexrxhxrxcxhxrxc单纯形替换法的计算步骤：