运筹学 非线性规划 .pptx

《运筹学 非线性规划 .pptx》由会员分享，可在线阅读，更多相关《运筹学 非线性规划 .pptx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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)f(tk+h),此时得到一个包含极小点的区间 tk 1,tk+h;第12页/共40页若一开始 f(t0)f(t0+h),若 f(t1-h)f(tk),此时得到一个包含极小点的区间 tk-h,tk 1。第13页/共40页黄金分割法（0.618 法）解一元函数极小化

5、问题假设：f(t)在a,b 上是单谷函数，即 f(t)在 a,b 上有唯一极小点（设为 t*）且.第14页/共40页在a,b 上任取两点 t1 t2,计算 f(t1)、f(t2)，则.n 次函数值计算可使搜索区间缩短 n-1 次。第15页/共40页下面推导黄金分割法如何选取计算点 t1、t2。两个条件：第16页/共40页第17页/共40页黄金分割法的计算步骤：计算 f(t1)、f(t2)。第18页/共40页黄金分割法的迭代效果：其它试探点算法：Fibonacci 算法第19页/共40页例.用 0.618 法计算 f(t)=(t-1)2 在 0,3 上的极小点。解.第20页/共40页3.最速下降

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

7、向为基础产生共轭方向。第27页/共40页因此第28页/共40页共轭梯度法的搜索方向：共轭梯度法用于正定二次函数时具有性质：为了将共轭梯度法用于非二次函数，需消去公式中的 A。第29页/共40页第30页/共40页5.牛顿法在 x k 附近，f(x)有近似式：牛顿法的迭代公式牛顿方向第31页/共40页(1)若 f(x)为正定二次函数，则牛顿法只需一步迭代即得极小点，因为此时有 f(x)=g(x)，所以(2)牛顿法具有二阶收敛速率，但要求初始点选在极小点附近。几点说明：第32页/共40页6.单纯形替换法单纯形替换法是直接法，只需利用函数值。何谓单纯形?一维单纯形：线段二维单纯形：三角形三维单纯形：四面体第33页/共40页如何构造单纯形?第34页/共40页算法思想：给定初始点 x 0，并构造初始单纯形 S0，然后进行单纯形替换迭代，迭代包括反射步、延伸步、收缩步或棱长减半等类型。x hx r第35页/共40页x hx ex rx hx rx c第36页/共40页x hx rx c第37页/共40页单纯形替换法的计算步骤：第38页/共40页第39页/共40页感谢您的观看！第40页/共40页