最优化计算方法(工程优化)复习资料课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《最优化计算方法(工程优化)复习资料课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 计算方法 工程 复习资料 课件
- 资源描述:
-
1、 12,0,1,x xD 12(1),0,1,xxD D,nDR空集和单元素集也是凸集。空集和单元素集也是凸集。三角形,矩形,圆,球,凸多边形,第一象限,第一卦限等都三角形,矩形,圆,球,凸多边形,第一象限,第一卦限等都是凸的。是凸的。设设 若集合若集合 中任意两点的连线都属于中任意两点的连线都属于 ,则称,则称 为凸集。为凸集。因为两点因为两点 连线上任一点可以表示为连线上任一点可以表示为 12(1),0,1.xxx 12,x xDDD凸集的几何特征凸集的几何特征凸集的代数特征凸集的代数特征称集合称集合 为凸集为凸集。恒有恒有 证明集合证明集合 S=x Ax=b 是凸集,其中是凸集,其中A为
2、为 m n矩阵,矩阵,b为为m维向量。维向量。0,1,1212(1)(1)(1),AxxAxAxbbb 12,x xS12,Axb Axb即即12(1),xxS所以所以即即S是凸集。是凸集。,nTHx xRc xb 集合集合是凸集是凸集,称为超平面,称为超平面,c为为n维向量。维向量。邻域邻域00,|,0N xx x x 是凸集。是凸集。设设 那么称那么称 是是 的凸组合。的凸组合。121,.,0,1,mmniiix xxRS 是凸集是凸集 S 中任意有限个点的凸组合属于中任意有限个点的凸组合属于 S。1miiix12,.,mx xx 设设 是凸集,则是凸集,则 也是凸集。也是凸集。,AB A
3、B AB,nA BR:,:,.ABab aA bBABa b aA bB 不一定是凸集。不一定是凸集。AB 设集合设集合 D Rn 为凸集,函数为凸集,函数 f:DR,若若 x,y D,(0,1),均有,均有 f(x+(1-)y)f(x)+(1-)f(y),则称则称 f(x)为凸集为凸集 D 上的凸函数。上的凸函数。若进一步有上面不等式以严格不等式成立,则称若进一步有上面不等式以严格不等式成立,则称 f(x)为凸集为凸集 D 上的上的严格凸函数严格凸函数。当当-f(x)为凸函数为凸函数(严格凸函数严格凸函数)时,则称时,则称 f(x)为为凹函数凹函数 (严格凹函数严格凹函数)。严格凸函数严格凸
4、函数凸函数凸函数严格凹函数严格凹函数 设设D Rn 为非空凸集,函数为非空凸集,函数 f:DR 在在 D 上可微,则上可微,则 (1)f在在D上为凸函数上为凸函数 任意任意x,y D,恒有,恒有 f(y)f(x)+f T(x)(y-x)(1)(2)f在在D上为严格凸函数上为严格凸函数 任意任意xy D,恒有,恒有 f(y)f(x)+f T(x)(y-x).(2)证明证明 设设D Rn 为含有内点的非空凸集,为含有内点的非空凸集,函数函数 f:DR在在 D 上二次可微,则上二次可微,则 a)f在在D上为凸函数上为凸函数 x D,2f(x)半正定;半正定;b)若若 x D,2f(x)正定,则正定,
5、则f在在D上为严格凸函数。上为严格凸函数。回忆:回忆:设二次函数设二次函数 (1):若:若 为半定矩阵,为半定矩阵,在在 中为凸函数中为凸函数;(2):若若 为正定矩阵,为正定矩阵,在在 中为严格凸函数。中为严格凸函数。判断判断f(x)=5x12-6x1x2+5x22在凸集在凸集D上是否是凸函数?上是否是凸函数?的顺序主子式都是正的,所以正定,因此的顺序主子式都是正的,所以正定,因此f(x)在凸集在凸集D上是严格凸函数。上是严格凸函数。2106()6 10f x Tf xx AxA()f xnRnR()f xA 考虑如下非线性规划考虑如下非线性规划当当 都是凸函数时都是凸函数时,称规划称规划
6、为凸规划为凸规划(),()(1,2,)if x g x im(1)min(1).0,1,2,if xst gxim 设设(1)为凸规划,则为凸规划,则 i)(1)的可行集的可行集R是凸集;是凸集;ii)(1)的最优解集是凸集;的最优解集是凸集;iii)(1)的任何局部极小点都是全局极小点。的任何局部极小点都是全局极小点。设设(1)为凸规划,若为凸规划,若f(x)在非空可行集在非空可行集R上是严格凸函上是严格凸函 数,则数,则(1)的全局极小点是唯一的。的全局极小点是唯一的。见书中见书中(P24)定理定理 3.11.非线性规划的局部最优解不一定是非线性规划的局部最优解不一定是 全局最优解全局最优
7、解,其可行解和最优解集也其可行解和最优解集也 不一定是凸集不一定是凸集,甚至不是连通集甚至不是连通集.如如 果是凸规划果是凸规划,就有很多好的性质。就有很多好的性质。见书中见书中(P23)定理定理 3.9、3.10.n=1时,是一维无约束优化问题时,是一维无约束优化问题-n1时,是多维无约束优化问题时,是多维无约束优化问题-n元函数元函数求解无约束优化问题求解无约束优化问题min()nx Rf x:nf RR找初始点找初始点判断当前点是否满判断当前点是否满足终止条件足终止条件下一个迭代点下一个迭代点 最优解最优解(a)找初始点找初始点(b)终止条件终止条件(c)迭代格式迭代格式是是否否循循环环
8、kkd1kxkdkdmin()nx Rf x()kkf xdk求目标函数求目标函数 f(x)的极小:的极小:由于这项工作是求以由于这项工作是求以 为变量的一元函数为变量的一元函数的极小点的极小点,故常称这一过程为,故常称这一过程为(精确)一维搜索或(精确)一维搜索或(精确)线搜索或一维最优化(精确)线搜索或一维最优化,确定的步长为最佳步长。,确定的步长为最佳步长。:argmin()kkkf xd()f x1kx1min()kkkkkkkf xdxxd1 T()0.kkf xd 设目标函数设目标函数具有一阶连续偏导数,具有一阶连续偏导数,规则产生规则产生则有则有按下述按下述函数函数 ,则得,则得
9、()()kkf xd min kT+1 T0()()()().kkkkkkkkf xddf xd ()k基本思想:一种试探法:从一点出发,按一定步长搜索新点,基本思想:一种试探法:从一点出发,按一定步长搜索新点,若搜索成功,加大步长继续搜索;若搜索失败,缩小步长小若搜索成功,加大步长继续搜索;若搜索失败,缩小步长小步后退。步后退。步骤步骤1:选取初始点选取初始点 xR,初始步长初始步长 h 0 及精度及精度 0,步骤步骤2:计算:计算步骤步骤3:若:若 搜索成功搜索成功,转步骤转步骤4;否则,搜索失败,;否则,搜索失败,转步骤转步骤5。步骤步骤4:令:令 x:=x+h,转步骤转步骤 2。步骤步
10、骤5:判断:判断 若若 停止迭代,停止迭代,;否则令;否则令 转步骤转步骤 2。缺点:效率低。优点:可以求缺点:效率低。优点:可以求搜索区间搜索区间。1().f x2().f xh21,12:,:2hh?hh,*xx,4hh 注意:初始步长不能选得太小注意:初始步长不能选得太小:设给定初始点:设给定初始点为为 a 及初始步长为及初始步长为 h,求搜索区间求搜索区间c,d 1)前进运算前进运算首先计算首先计算 f(a),f(a+h),如果如果 f(a)f(a+h),则步长加倍则步长加倍,计计算算f(a+3h).若若 f(a+h)=f(a+3h),则则c=a,d=a+3h;否则将步否则将步长再加倍
11、,并重复上面运算长再加倍,并重复上面运算.2)后退运算后退运算如果如果 f(a)f(a+h),则将步长缩为原来的则将步长缩为原来的1/4并改变符号,即并改变符号,即将步长改为将步长改为-h/4,如果如果 f(a)f(a-h/4),则则c=a-h/4,d=a+h;否则否则将步长加倍,并继续后退。将步长加倍,并继续后退。注意注意:1.h 选择要适当选择要适当.(太大含多个单峰区间太大含多个单峰区间,太小迭代次数多太小迭代次数多);2.f(x)单调时无结果单调时无结果,(加迭代次数限制加迭代次数限制);:利用利用“成功成功-失败失败”法求函数法求函数 的搜索区间,的搜索区间,取初始点取初始点 ,步长
12、,步长取初始点取初始点 ,步长,步长3()21f xxx115()(),28f xf()()f xf xh因为,12x 1.2h 12x 1,2h 11()()(0)1,22f xhff搜索成功,步长加倍;11(+2)(3)(3)(1)0,22f xhhf xhff计算()(3)f xhf xh因为,搜索成功,步长加倍;11(3+4)(7)(7)(3)22,22f xhhf xhff计算(3)(7)f xhf xh因为,搜索失败,停止迭代;,7 0,3.xh xh得到搜索区间为得到搜索区间为 0.618法是求单峰函数极值的一种试探法,有的书上也称为区法是求单峰函数极值的一种试探法,有的书上也称
13、为区间收缩法。间收缩法。在搜索区间在搜索区间a,b上插入两个点,将分为三个子区间,通过比较上插入两个点,将分为三个子区间,通过比较2个插入点的函数值的大小,可删去左边或者右边区间,使搜索个插入点的函数值的大小,可删去左边或者右边区间,使搜索区区间缩短。重复上述过程,使搜索区间不断缩短,当区间缩短到一间缩短。重复上述过程,使搜索区间不断缩短,当区间缩短到一定程度时,区间上各点都可以作为极小点的近似。定程度时,区间上各点都可以作为极小点的近似。仅适用于求解单峰函数仅适用于求解单峰函数:设设 f(x)是定义在是定义在a,b上的函数,若上的函数,若 1)x*a,b 是是在在a,b上的最小点上的最小点,
14、2)若对任意若对任意 x1,x2,a x1 f(x2);2 若若x1 x*,则,则 f(x1)f(x2).则称则称 f(x)为为a,b上的单峰函数。上的单峰函数。设设 f:RR 在在a,b 上是单峰函数,上是单峰函数,a x1 x2 b。那么那么 1若若 f(x1)f(x2),则,则 x*x1,b,如左下图如左下图 2若若 f(x1)f(x2),则,则 x*a,x2,如右下图如右下图 a x1 x2 b a x1 x2 b考虑条件:考虑条件:2对称原则:对称原则:x1 a=b-x2 (使(使“坏坏”的情况去掉,区间长度不小于的情况去掉,区间长度不小于“好好”的情况)的情况)3保持缩减比原则保持
15、缩减比原则 t=(保留的区间长度原区间长度保留的区间长度原区间长度)不变。不变。(使每次保留下来的节点,(使每次保留下来的节点,x1或或 x2,在下一次的比较中成,在下一次的比较中成 为一个相应比例位置的节点为一个相应比例位置的节点)。)。推导缩减比推导缩减比 t:如图设第一次保留如图设第一次保留a,x2 (去掉去掉x2,b),第二次第二次保留的长度为保留的长度为,x1,则则 x1 x2 b212(2)xxtbx整理整理:x2=a+t(b-)x1 =a+t(x2-)结合式:结合式:t 2+t 1=0 故故 t0.618注意注意:上式有上式有 t 2=1-t,故有故有 x1=a+(1-t)(b-
16、a)=a+0.328(b-a)x2=a+t(b-a)=a+0.618(b-a)(251舍去负值t 优点:不要求函数可微,且每次迭代只需计算一优点:不要求函数可微,且每次迭代只需计算一 个函数值,计算量小,程序简单个函数值,计算量小,程序简单缺点:收敛速度慢。缺点:收敛速度慢。黄金分割法(黄金分割法(0.618 法)的优缺点法)的优缺点:试用试用0.618法求目标函数法求目标函数 的最优解。的最优解。给定初始区间给定初始区间0,2,收敛精度,收敛精度第一次区间缩短计算过程:第一次区间缩短计算过程:计算两点及对应函数值:计算两点及对应函数值:作数值比较,可见作数值比较,可见 ,再做置换:再做置换:
17、3()21f xxx2:1.236,bx=0.002.0,2ab10.382()0.764,xaba1()0.0821,f x20.618()1.236,xaba2()0.4162,f x12()()f xf x1.2360.002ba20.764,x2()0.0821,f x,0,1.236,a b第二次区间缩短计算过程:第二次区间缩短计算过程:作数值比较,作数值比较,,再做置换:再做置换:10.382()0.472,xaba1()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次区间缩短计算过程:第三次区间缩短计算过程:作数值比较,作数值比较,
18、,再做置换:再做置换:2:0.944,bx20.618()0.944,xaba2()0.0468,f x12()()f xf x0.4720.002ba22,0,1.236,0.764,()0.0821,a bxf x ,0.472,1.236,a b 110.764,()0.0821,xf x 220.764,()0.0821,xf x ,0.472,0.944,a b 各次的迭代结果如下:各次的迭代结果如下:迭代次数迭代次数x1x2f(x1)f(x2)a,b|b-a|第第1次次0.7641.236-0.08210.41260,1.2361.236第第2次次0.4720.7640.1612-
19、0.0821 0.472,1.236 0.788第第3次次0.7640.944-0.0821-0.0468 0.472,0.944 0.472第第4次次0.6520.764-0.0268-0.0821 0.652,0.944 0.292第第5次次0.7640.832-0.0821-0.0881 0.764,0.944 0.230第第6次次0.8320.906-0.0881-0.0683 0.764,0.906 0.124缺点:收敛速度慢缺点:收敛速度慢优点:不要求函数可微,且每次迭代只需计算一个函数优点:不要求函数可微,且每次迭代只需计算一个函数 值,计算量小值,计算量小 设设 f(x)在在
20、a,b上可微,求函数上可微,求函数f在在a,b的极小点,就是求的极小点,就是求函数导数为零的点。如果函数导数为零的点。如果 ,则在,则在(a,b)内一定存在一点内一定存在一点x,使得,使得 。为求极小点,可取。为求极小点,可取 ,若,若 ,x 为最小点为最小点,x=x0;,x0 在上升段在上升段,x*x0,去掉,去掉a,x0.00fx00fx00fx 0,0,fafb 0fx02abx用用 或者或者 作新的区间作新的区间a,b,继续这个过程,继续这个过程,逐步将区间逐步将区间a,b缩小,缩小,当区间当区间a,b的长度充分小时,可将的长度充分小时,可将a,b的中点取做极小的中点取做极小点的近似点
21、的近似点。点。0,a x0,x b优点:计算量较少,而且总能收敛到一个局部极小点。优点:计算量较少,而且总能收敛到一个局部极小点。缺点:收敛速度较慢缺点:收敛速度较慢0=2abx步骤步骤1:计算:计算步骤步骤2:若:若 ,令,令 ,转步骤,转步骤3;若若 ,令,令 ,转步骤,转步骤3;若若 ,停止,停止,。步骤步骤3:若:若 ,则,则 ,停止,否则,转步骤,停止,否则,转步骤1.0ax00fx00fx00fx0bx0*xx|b a*2abx:试用二分法求目标函数试用二分法求目标函数 的最优解。的最优解。给定初始区间给定初始区间0,2,收敛精度,收敛精度在在0,2内有极小点。内有极小点。3()2
22、1f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba,0,1,a b 第一次区间缩短计算过程:第一次区间缩短计算过程:2()32,fxx因为因为所以函数所以函数3()21f xxx0()=(1)10fxf,第二次区间缩短计算过程:第二次区间缩短计算过程:第三次区间缩短计算过程:第三次区间缩短计算过程:2,0,1,()32,a bfxx1,1,2a b 01:,2ax故01,22abx10.004;2ba015()=()024fxf ,3,1,4a b 03:,4ax故03,24abx10.004;4ba035()=()0416fxf ,各次的迭
23、代结果如下:各次的迭代结果如下:迭代迭代9次后,次后,|b-a|=0.003910.004,故故迭代次数迭代次数x0=(a+b)/2f(x0)a,b|b-a|第第1次次x0=110,11第第2次次x0=1/2-5/41/2,11/2第第3次次x0=3/4-5/163/4,11/4第第4次次x0=7/819/643/4,7/81/8第第5次次x0=13/16-0.019513/16,7/81/16第第6次次x0=27/320.013613/16,27/321/32第第7次次x0=53/640.057413/16,53/641/64第第8次次x0=105/1280.018413/16,105/12
24、81/128第第9次次x0=209/256-0.0004209/256,105/1281/256*0.81836.x 对对 f(x)在在 x k 点二阶泰勒展开:点二阶泰勒展开:略去高阶项得略去高阶项得两边对两边对x求导,求导,令令 ,得到,得到 牛顿法是一种函数逼近法,牛顿法是一种函数逼近法,基本思想是:基本思想是:在极小点附近用在极小点附近用函数的二阶泰勒多项式近似代替目标函数,从而求得目标函数函数的二阶泰勒多项式近似代替目标函数,从而求得目标函数的极小点的近似值。的极小点的近似值。221()()()()()()()2kkkkkkf xf xfxxxfxxxo xx21()()()()()
25、()2kkkkkf xf xf xxxfxxx()()()()kkkf xf xfxxx()=0f x()()kkkf xxxfx取取 作为新的迭代点,继续迭代,直到达到精度,这样就得到了作为新的迭代点,继续迭代,直到达到精度,这样就得到了函数函数 f 的一个驻点的一个驻点 。1()=()kkkkf xxxfx*x步骤步骤1:给定初始点:给定初始点 令令 。步骤步骤2:计算:计算 。步骤步骤3:若:若 ,停止,停止,否则转步骤,否则转步骤4。步骤步骤4:计算:计算 令令 ,转步骤,转步骤2。10,xR,1k(),()kkf xfx()kf x*kxx1()=()kkkkf xxxfx1kk 特
展开阅读全文