最优化理论第1次new_第1页
最优化理论第1次new_第2页
最优化理论第1次new_第3页
最优化理论第1次new_第4页
最优化理论第1次new_第5页
已阅读5页,还剩30页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、最优化基本知识最优化基本知识最优化理论与方法最优化理论与方法应用性最强应用性最强的数学分支的数学分支 -在众多方案在众多方案最优方案最优方案应用领域应用领域 -工程设计、资源分配、生产安排、原料配比、城建规划、军事领域、工程设计、资源分配、生产安排、原料配比、城建规划、军事领域、现代网络等等现代网络等等学科历史学科历史 1717世纪,世纪,NewtonNewton提出极值问题提出极值问题 LagrangeLagrange乘数法乘数法 18471847 CauchyCauchy最速下降法最速下降法 19391939 苏联数学家提出了线性规划苏联数学家提出了线性规划- -解决下料、运输问题解决下料

2、、运输问题 20 20世纪世纪4040年代,年代,DantzigDantzig提出单纯型方法提出单纯型方法独立学科独立学科例例1 1 生产计划问题生产计划问题某工厂用某工厂用 4种资源种资源 3种产品种产品jijcaij 利润种资源产品需要第每单位jdji b i产品产量不超过,种资源总量不超过第如何生产利润最大如何生产利润最大?求解求解: x,x, 3321x种产品的产量分别为:设 xxc 332211ccx目标函数(总利润):约束约束:3 , 2 , 1 03 , 2 , 1 x1,2,3,4i b xxji332211jxjdaaxajjiii使目标函数最大求解:, )x,x,(x x*

3、3*2*1*例例1 1 生产计划问题生产计划问题某工厂用某工厂用 4种资源种资源 3种产品种产品jijcaij 利润种资源产品需要第每单位jdji b i产品产量不超过,种资源总量不超过第数学描述:数学描述:3 , 2 , 1 , 0 3 , 2 , 1 , x 1,2,3,4i , b xx s.t.maxji33221131jxjdaaxaxcjjiiijjj )x,x,(x x*3*2*1*例例2 2 结构设计问题结构设计问题两个构件组成的对称桁架两个构件组成的对称桁架HxEy上限容许应力:弹性模量:材料比重:2求解求解:2/12221)(Tx2 xLG目标函数(总重量):约束约束1:H

4、x 2使桁架重量最小?桁架高度确定钢管直径, 21xx2P2xL2YYY-Y剖面1xT约束约束2:2121222122122221)()(),(xTxxLPTxxxLPSFxx例例2 2 结构设计问题结构设计问题2P2xL2YYY-Y剖面1xT约束约束2:yxTxxLP2121222)(约束约束3:)(8)(2222212xLTxEl钢管不弯曲,即压应力不钢管不弯曲,即压应力不超过临界应力超过临界应力)(8)()(22222122121222xLTxExTxxLP使重量最轻求解:, )x,(x x*2*1*数学描述:数学描述:2/12221)(Tx2in xLGm,. .2Hxts,)(212

5、1222yxTxxLP,)(8)()(22222122121222xLTxExTxxLP0,21xx2.1 2.1 问题描述问题描述 )(minxfnRxIixCixCTSii0)(0)(.00. .) 1()2min(212212221xxxxtsxx例例1x12x1x1C2C)(xf*x2221) 1()2()(xxxf2.2 2.2 连续优化与离散优化连续优化与离散优化 )(minxfnRxIixCixCtsii0)(0)(. .a 有约束优化有约束优化离散优化:有限集合连续优化:无限集合2.3 2.3 有约束优化与无约束优化有约束优化与无约束优化 根据目标函数及约束方程根据目标函数及约

6、束方程:*线性、非线性、凸优化线性、非线性、凸优化*变量个数:变量个数:Large or Small*方程光滑性:可微、不可微方程光滑性:可微、不可微求解方法求解方法:二次规划、罚函数、置信域等二次规划、罚函数、置信域等)(minxfnRxnRxts. .b 无约束优化无约束优化求解方法求解方法:一维搜索、牛顿法、共轭梯度法等一维搜索、牛顿法、共轭梯度法等2.4 2.4 全局优化与局部优化全局优化与局部优化 难题难题上的全局最小点在为称有对每个邻域的,局部优化:上的全局最小点在为称有对每个,全局优化:S)()()(),(|),(,0S)(S)()()(,S)(*xfxxfxfxNSxxxxxN

7、SxxfxfxxfxfSxSxxf非线性问题的非线性问题的解一般为局部解一般为局部解解2.5 2.5 随机优化与确定性优化随机优化与确定性优化 多出现于经济、金融行业,用统计及概率论预测多出现于经济、金融行业,用统计及概率论预测确定确定性优化:模型的值随机优化:模型不确定2.6 2.6 优化算法优化算法 迭代迭代-要求具有:鲁棒性,效率,精度要求具有:鲁棒性,效率,精度实值函数:实值函数:3.1 3.1 向量范数和矩阵范数向量范数和矩阵范数 为向量范数则当且仅当nnnRyxyxyxRxRxxxxRxx,)3(,)2(00;0) 1 (定义:定义: 向量范数向量范数则则x的常用范数有:的常用范数

8、有:pnjpjpjjnjjnjjxxxxxxxx112112211)(max)(nTnRxxxx),.,(21设满足:RRn :范数LLL,21A为为mXn矩阵矩阵3.1 3.1 向量范数和矩阵范数向量范数和矩阵范数 DAADBABAAAxAAx)3(,)3(,)2(,) 1 (定义:定义: 矩阵范数矩阵范数则则A的常用范数有:的常用范数有:njijiTmiijjaxAAAaA121211max)(maxAxARRxnm1max: :向量范数向量范数,范数AAA,21矩阵范数性质矩阵范数性质3.2 3.2 序列的极限序列的极限 定义定义1 *k*k*lim,x, , 0,xxxxxKkKRxR

9、xkknnk记作:收敛到称序列有时,使得存在任给中的向量序列,是定义定义2 的一个聚点是则称,使得在一个子序列中的向量序列,如果存是kKKKnkxxxxxRxjjjlim,定义定义3 序列为称序列有时,使得存在中的向量序列,任给是CauchyxxKlmKRxlnkkmx, , 0定理定理1 的聚点必为极限点序列,则中的是jnjxCauchyRx紧集:有界的闭集邻域的,使得存在开集:均属于中每个收敛序列的极限中的集合,为闭集:SxNxSxSSRSn),(, ;3.3 3.3 梯度、梯度、HesseHesse矩阵、矩阵、TaylorTaylor展开展开 非空实函数nRSxf),((1)梯度:)梯度

10、:Tnxxfxxfxxfxf)(.)(,)()(21)()(,.1,)()(,.1, 221SCfxxxfnjiSxSCfxxfnjSxSfjij存在且连续,记作二次连续可微:存在且连续,记作连续可微:的每一点上连续在连续:(2)Hesse矩阵:矩阵:nnnnnxxfxxxfxxfxxxfxxxfxxfxxxfxxxfxxfxf22222222222222122121222)(.)(,)(.)(.)(,)()(.)(,)()(3.3 3.3 梯度、梯度、HesseHesse矩阵、矩阵、TaylorTaylor展开展开 SxSCfRSxfn*2),(,),(非空实函数(3)Taylor展开:展开

11、:)()()(21)()()()(2*2*xxxxxfxxxxxfxfxfT4.1 4.1 凸集凸集 为凸集则称:有设SSxxSxxifRSn1 , 0,)1 (, ,2121凸集定义:凸集定义:1x2x1x2x的凸组合称为2121,)1 (xxSxx是定点为非零向量,其中,为凸集,验证:例000, 1xddxxL4.1 4.1 凸集凸集 为凸集为凸集为凸集为凸集则有:为实数,设2121211121)4() 3()2() 1 ( ,SSSSSSSxxSRSSn凸集性质:凸集性质:为凸锥为凸集,则称若为锥,则有取任何非负数时,当中每一点,若设集合CCCCxxCRCn,凸锥定义:凸锥定义:bAxx

12、多面集有限个半空间的交称为多面集定义:多面集定义:0, 0, 1, 42212121xxxxxxxS例:1x2x4.1 4.1 凸集凸集 中的极点是称必有为非空凸集设SxxxxSxxxxxifSxS, ,)1 , 0( ,)1 ( ,212121极点定义:极点定义:的极方向为线性组合,则的正的不能表示成两个方向的方向若的方向。为则都有中每一个为非零向量,对于为闭凸集,SddddSSdSdxxSdS21,0 极方向定义:极方向定义:1x2x3x7x5x4x6x4.2 4.2 凸函数凸函数 严格凸函数凸函数为非空凸集设)()1 ()()1 ()()1 ()()1 () 1 , 0(,2121212

13、121xfxfxxfxfxfxxfSxxS定义:定义:1x2xx21)1 (xxx1x2xx21)1 (xxx1x2xx21)1 (xxx凸函数凸函数凹函数凹函数非凸凹函数非凸凹函数4.2 4.2 凸函数凸函数 为凸函数为凸函数,定理miiifffff121, 1凸函数定理凸函数定理SxxxxxfxffffRSTn2112112,),()()()(x ,2为凸函数可微定理矩阵半正定的每一点上在为凸函数二次可微定理Hesse,3SfffRSn是否是凸函数函数例题122),(121222121xxxxxxxf5.1 5.1 无约束问题的最优性条件无约束问题的最优性条件 nRxxf),(min定义定

14、义1的严格局部极小点为则称的和如果对于所有的局部极小点为则称的和对于所有fxxffxxxRxfxxffxxxRxnn*),()(x),()(x, 0定义定义2的总体极小点为则称对于所有fxxffRxn*),()(x 一般情况下一般情况下,可行解是局部极小点可行解是局部极小点,问题是凸性问题时问题是凸性问题时,局部极小点等于总体极小点局部极小点等于总体极小点5.1 5.1 无约束问题的最优性条件无约束问题的最优性条件 )(二阶导数存在连续,而且一阶导数、)()(),()(2xfxGxfxgf) 1 , 0(,)(21)()()()()()() 1 , 0(,)()()(2102tptpxfppx

15、fxfpxfpdttpxfxfpxftptpxfxfpxfTTT二阶连续则有下式成立则有下式成立:5.1 5.1 无约束问题的最优性条件无约束问题的最优性条件 0)(:*1xfDxRRDfn上局部极小点,则是在开集上连续可微,若设定理定理1(一阶必要条件)(一阶必要条件):)(0)(0)(:*2*1半正定,则上局部极小点,是,若在开集上二阶连续可微设xfxfDxRRDfn定理定理2(二阶必要条件)(二阶必要条件):)(0)(0)(:*2*1正定,的充分条件是:为一严格局部极小点,则在开集上二阶连续可微设xfxfxRRDfn定理定理3(二阶充分条件)(二阶充分条件):0)(,:*11xfxCfR

16、RDfn的充要条件是:是总体极小点则是凸函数,且设定理定理4:5.2 5.2 最优化问题的结构最优化问题的结构 )(*0在可行域内xxRxknkkkkkkkpxxkpkx1 则为步长次搜索方向,为第次迭代点,为第设0)(:kTkkkpxfxfp点的下降方向,即在但一定是)顿、共轭梯度方向,(最速下降、牛如果满足条件则停止重复令在某种意义下下降使确定步长方向处的下降方向作为搜索在依一定规则,构造确定方向4-2,)4(,) 3(,)2() 1 (10kkkkkkkpxxfxfpx最优化问题的基本流程:最优化问题的基本流程:)插值步长,(不同方法,,618. 0:Fibonaccik5.3 5.3

17、两种搜索策略:线性搜索与置信域法两种搜索策略:线性搜索与置信域法 kkkpx)(min 0kkkkkkpxfp,再用以下公式求解先确定5.3.1 线性搜索线性搜索位于信赖域内方向先确定信赖域,再求解pkkkpkxpxmp),(min 5.3.2 信赖域方法信赖域方法kxkpfmk新求解下降,减小信赖域,重如果解无法使f也可以为椭球,盒型域信赖域为球,一般情况,, 0,2ppBpfpfpxmkTkTkkk21)(标量标量 向量向量 矩阵(矩阵(Hesse或其它)或其它)5.3 5.3 两种搜索策略:线性搜索与置信域法两种搜索策略:线性搜索与置信域法 kkkpp再步长(信赖域半径),信赖域法:先确

18、定最大再线性搜索:先,5.3.3 二者区别二者区别下降最快方向选择kf-), 0(,)()()(,2221tptpxfpfpxfpxfpfkTkTkk步长方向kTkfppxf 和的变化点沿方向在5.4 5.4 线性搜索中的搜索方向线性搜索中的搜索方向 (1) 最速下降方向最速下降方向:问题求解问题求解5.4 5.4 线性搜索中的搜索方向线性搜索中的搜索方向 (1) 最速下降方向最速下降方向:在单位方向在单位方向p,求解下面问题可以获得最快下降速度求解下面问题可以获得最快下降速度kkkkTkTpffpffpfpptsfp/ -1)cos()cos( )cos(1. . min其解为时最小,即当*

19、xkxpkf缺点缺点: 有时收敛速度很慢有时收敛速度很慢,求解困难求解困难!5.4 5.4 线性搜索中的搜索方向线性搜索中的搜索方向 (2) 牛顿方向牛顿方向:)()(221pmfppfpfpxfkdefTkTkk缺点缺点:kxkpkfkfkkkNkffpppm120)(其显示表达式为:为牛顿方向,求得求导并因此需要修正不存在,必须正定,否则-122kkff5.4 5.4 线性搜索中的搜索方向线性搜索中的搜索方向 (3) 拟牛顿方向拟牛顿方向:10222102)()()()( )()()(pdtxftpxfpxfxfpdttpxfxfpxf问题推导问题推导:矩阵种方法,不求解在拟牛顿法中,构造一,并求逆牛顿法中需要求解Hesse2kf加、减项加、减项kkkxxpxx1,设则有:则有:)(0)(1121kkkkkkkxxxxfffkkkkkffxxf112)(kSky则有:则有:kkkySf25.4 5.4 线性搜索中的搜索方向线性搜索中的搜索方向 (3) 拟牛顿方向拟牛顿方向:人为给定保持低的秩,使得一般通过限制则有矩阵来代替矩阵的近似矩阵选择01, HesseHesseBBBBySBBkkkkkkkkkkySf2kTkTkkkkTkkTkkkkKkTkkKTkkkkkkkKSyyySBSBSSBBBBFGSSSBySBy

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论