好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

《工程最优化》第五章.ppt

50页
  • 卖家[上传人]:飞***
  • 文档编号:2609405
  • 上传时间:2017-07-25
  • 文档格式:PPT
  • 文档大小:1.01MB
  • / 50 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 本章要点:单纯形单纯形搜索法的基本思想共轭方向、共轭方向法的基本定理Powell共轭方向法的基本思想最速下降法的基本思想及特点Newton法基本思想及特点牛顿方向Marquardt法基本思想最小二乘问题共轭梯度法基本思想拟Newton法的基本思想,第五章 无约束非线性问题的解法,§5.1 直接搜索法,优点:计算不太复杂;易于实施与快速调试;所需的准备时间较少,§5.1.1 单纯形搜索法,1962年由Spendley, Hext和Himsworth提出,80年代得到证明,,(一)单纯形,空间中最简单、其 “维数”与空间维数相同的图形,n维空间中具有n+1个顶点的 “n维超多面体” 称为n维单纯形,如果各顶点间的距离(棱长)相等,则称为正规单纯形,(二)单纯形法的基本思想,初始单纯形,,以 min f(x1, x2)为例 ,说明迭代过程,,,,,,,fH > fG > fL,,,反射PR,fRfR 扩张失败 PS =PR,PS,,,,,,,fS

      这n+1个点应使x(1)-x(0), x(2)-x(0),…, x(n)-x(0)线性无关,否则是退化的单纯形,例如:对二维,三点不能在一条直线时; 对三维,四点不能在同一平面上,(三)单纯形搜索法的算法,给定一个最大迭代次数KM,令迭代次数计数变量K=0,1、给定初始点x(0), 用下列两种方法之一构造初始单纯形,棱长为h的正规单纯形,2、计算函数值fi = f (x(i)),(i=0,1,2,…,n),并比较大小,找出最差点 x(H),次差 点x(G) 和最好点x(L),即,计算除去x(H)后的形心 x(F),3、按终止准则判断是否已达到精度要求,若已达到,停止计算,否则转4,4、求反射点x(R),5、将fR 与fL ,fG 和fH 作比较,(1)若fR

      几点说明:,1、关于初始步长h的选取 (一般可取0.5≤h<15),(1) 开始取h为1.6~2;,(2) 进行到发现fH- fL 已 很小,但尚未达到精度,这时取x(0)= x(L), 重新开始, 并取步长为: 当离精度要求已不远时,h=0.5~1; 当离精度要求还很远时,h≥ 22、终止准则 P109,3、扩张因子 r =1.2~2,,,,例5.1.1 用单纯形搜索法求解 min f(x) =60-10x1-4x2+x12 +x22-x1x2 设x(0)=[0, 0]T , e(1) = [1, 0]T, e(2) = [0, 1]T, 取h=2, =0.5, =2, =1, 终止准则为|(fH-fL)/fL|<0.001,,,,,,,,,,,,§5.1.3 Powell共轭方向法(方向加速法), 1964年由Powell提出,后经Zangwoll(1967年)和Brent(1973年)改进, 是迄今为止最有效的直接搜索法 该算法有效地利用了迭代过程中的历史信息,建立起能加速收敛的方向, 有理论基础,以二次对称函数 f(x) = c + bTx + 1/2 xTAx 为模型进行研究。

      为什么选择二次函数作为模型 ?,1、在非线性目标函数中,最简单的是二次函数,故任何对一般函数有效 的方法首先应对二次函数有效;,2、在最优点附近,非线性函数可用一个二次函数作近似,故对二次函数 使用良好的方法,通常对一般函数也有效;,,3、很多实际问题的目标函数是二次函数一)共轭方向,设A是n×n阶对称正定矩阵,p(0), p(1)为两个n维向量,若 成立 p(0)T A p(1) = 0 则称向量p(0)与p(1)为A共轭或A正交,称该两向量的方向为A共轭方向若 A=I(单位矩阵),p(0)T p(1) = 0,即p(0)与p(1)是正交的共轭”是“正交”概念的推广,=||p(0)||.||p(1)||cosθ,例:,? 共轭方向有什么用 ?,(二)共轭方向法的基本定理,定理5.1.1:设A为n×n阶对称正定矩阵,p(0), p(1),…, p(n-1)为n个相互A共轭 的n维非零向量(即p(i)0, i=0,1,…, n-1, 且p( i )T A p( j ) = 0,i j), 则此向量系必线性无关。

      推 论: 在n维空间中,互相共轭的非零向量的个数不超过n个定理5.1.2:若p(0), p(1), …, p(n-1)是n个非零的A共轭向量,则二次目标函数 f(x) = c + bTx + 1/2 xTAx的最优点 x*为,! 可得到非二次函数最优点的一个近似点;其中A是Hesse矩阵!,? 上式用于非二次函数,可否得到最优点 ?,定理5.1.3:,设A为n阶对称正定矩阵,对于二次目标函数f(x) = c + bTx + 1/2 xTAx,从任意初始点x(0)出发,逐次进行一维搜索,即 min f ( x( i )+ t p( i ) ) = f ( x( i )+ti p( i ) ) i≥0 若搜索方向p(0), p(1), …, p(n-1)是非零的A共轭向量,则至多进行n次迭代必可得到极小点x* ,即有 x( i+1) =x( i ) +ti p( i ) , i =0,1,…,n-1 x* = x( k ) , 0≤k≤n,上述搜索方法具有二次收敛性,? 对非二次函数,采用上述方法,n 次迭代是否也可得到极小点 ?,? 如何简便地找出n个A共轭的向量 ?,定理5.1.4:,假设1. n元函数f(x) = c + bTx + 1/2 xTAx 中的矩阵A是对称正定的;2. 向量p(0), p(1), …, p(m-1) (m

      已知前m个共轭方向,就可以找到第m+1个共轭方向,,,,,(三)Powell共轭方向法的基本思想,…………………………………………………………………………………………………………,,,一边搜索,一边找共轭方向,共分n个阶段,每一阶段都进行n+1次搜索,最后产生一个共轭方向,二维空间中的Powell方法示意,,,,,,,以二次函数f(x1 , x2 ) 为例,,,如果是二次函数,则x* 即为极小点,(四)Powell方法的原始算法,开始,几点说明,1、迭代中逐次产生的是共轭方向,是较好的搜索方向,所以Powell法又称 方向加速法;,2、原始算法仅有理论意义因为只有在每次搜索均为一维完全精确搜索的条件下,每个阶段产生的方向才是共轭方向,对二次函数才能在n个阶段内得到极小点但实际一维搜索都是近似的,产生的方向不一定共轭,有时甚至是线性相关的,导致搜索空间降维,这时将找不到真正的极小点对于一般函数, n个阶段迭代后一般得不到极小点,但由于共轭方向的个数只有n个, 如果继续按上述方法迭代, 产生的方向就不再是相互共轭方向了, 收敛速度会变慢.,(五)原始算法一种简便改进,重新开始:每进行n个阶段的迭代,或当收敛速度变慢时,以当前点为起点, 回到第一步重新开始,(六)改进的Powell算法,1. 基本思想 :,为克服搜索方向的线性相关性,Powell对原始算法进行了改进。

      如何判定方向组是“最相互共轭”的 ?,定理5.1.5 设A是n阶对称正定矩阵,方向组p(0), p(1), …,p(n-1) 按下式意义是规范化的: p( i )T A p( i ) = 1, ( i=0,1,…, n-1), 置Q=[ p(0), p(1), …,p(n-1) ],则方向组p(0), p(1), …,p(n-1) 相互A共轭的充要条件为: 行列式 |Q| 的值达到它的最大值改进Powell算法的理论基础,在每个阶段产生新的方向p后, 更换方向组的方法不是一律去掉第一个方向p(0), 而是有选择地去掉某个方向 p(J), 原则是使新的方向组“ 最相互共轭”,§5.2 梯度法,直接搜索法收敛速度一般比较慢,需要计算大量的函数值梯度反映了函数值变化的规律,充分利用梯度信息构造算法,能加速收敛使用函数的梯度(一阶导数)或Hesse矩阵(二阶导数)的优化算法称为梯度法,目标:求出平稳点 (满足f(x)=0的x * )由于 f(x)=0 一般是非线性方程组,解析法往往行不通, 所以梯度法通常也是逐次逼近的迭代法,假定: f(x)和 2f(x)连续存在,§5.2.1 最速下降法(Cauchy法),1847年Cauchy提出。

      特点是直观易懂,但收敛速度慢,(一)基本思想,x(k+1) = x(k) + tk p(k),瞎子下山:由于他看不到哪里是山谷,不可能沿直接指向山谷的路线走,他只能在当前位置上,靠手杖作局部探索,哪里最陡就往哪里前进一步,然后在新的位置上再用手杖寻找最陡方向,再下降一步这就是最速下降法的形象比喻多变量最优化迭代解法的一般迭代公式,迭代公式 x(k+1) = x(k) -tk f(x(k) ),,(二)算法,开始,,,,,,,两维情形下最速下降法搜索路径,(三)最速下降法的搜索路径呈直角锯齿形,tk,1、优点:计算简单,需记忆的容量小;对初始点要求低,稳定性高;远离极小点时收敛快,常作为其它方法的第一步2、缺点:收敛速度较慢(线性或不高于线性)原因是最速下降方向只有在该点附近有意义尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时,收敛更慢例5.2.1 用最速下降法求函数 f (x1, x2)=x12+4x22 的极小点,(迭代两次), 并验证相邻两个搜索方向是正交的初始点取为x(0)=[1,1]T 解:梯度 f (x)=[2x1, 8x2 ]T 。

      1. 第一次迭代: f ( x(0) )=[2, 8 ]T , x(1) = x(0) + t0 p(0) = x(0) - t0  f (x(0))= [1,1]T - t0 [2, 8 ]T,。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.