![约束最优化的理论与方法_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/7/1f1cce44-8fba-4933-bd75-50f6aacf374e/1f1cce44-8fba-4933-bd75-50f6aacf374e1.gif)
![约束最优化的理论与方法_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/7/1f1cce44-8fba-4933-bd75-50f6aacf374e/1f1cce44-8fba-4933-bd75-50f6aacf374e2.gif)
![约束最优化的理论与方法_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/7/1f1cce44-8fba-4933-bd75-50f6aacf374e/1f1cce44-8fba-4933-bd75-50f6aacf374e3.gif)
![约束最优化的理论与方法_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/7/1f1cce44-8fba-4933-bd75-50f6aacf374e/1f1cce44-8fba-4933-bd75-50f6aacf374e4.gif)
![约束最优化的理论与方法_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/7/1f1cce44-8fba-4933-bd75-50f6aacf374e/1f1cce44-8fba-4933-bd75-50f6aacf374e5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第七章第七章约束最优化的理论约束最优化的理论与方法与方法一般形式的约束最优化问题一般形式的约束最优化问题min( )f x. .( )0,ist c xiE( )0,ic xiI |( )0,;( )0,iiXx c xiE c xiI可行域可行域min( )nx Rf x一般形式的无约束最优化问一般形式的无约束最优化问题题*xX*()( ),f xf xxX 全局极小点全局极小点设设则称则称x*为问题的为问题的全局极小点全局极小点;如果如果成立,成立,*()( ),f xf xxX xx 则称则称x*为为严格全局极小点严格全局极小点.进一步,如果进一步,如果成立,成立,(总体极小点总体极小点
2、)*,xX设*2( , ) |.N xxx x*()( ),(,)f xf xxN xX 局部极小点:局部极小点:如果对于某一如果对于某一成立,成立, 则称则称 x*是问题的是问题的局部极小点局部极小点,0 有其中其中则称则称x*为为严格局部极小点严格局部极小点.进一步,如果进一步,如果成立,成立,*()( ),(,),f xf xxN xX xx 全局极小点是局部极小点全局极小点是局部极小点有效约束、无效约束与内点、边界点有效约束、无效约束与内点、边界点有效有效(起作用起作用)约束:约束:对于可行点对于可行点 , ,x在点xxxx0)(xci0)(xci( )0ic x 若0)(xci( )
3、0ixc x 称 是约束如果如果0)(xci就称不等式约束就称不等式约束在点在点是有效约束。是有效约束。并称可行点并称可行点位于约束位于约束的边界。的边界。无效约束:无效约束:对于可行点对于可行点就称不等式约束就称不等式约束是无效约束是无效约束的内点的内点. .E E: :等式约束指标集等式约束指标集I I: :不等式约束指标集不等式约束指标集( ) |( )0,iI xi c xiI( )( )A xEI xnxR x点处的有效约束集点处的有效约束集( (有效集有效集) )( ),( )ic x iA x是在是在x点处的有效约束点处的有效约束( ),( )ic x iA x是在是在x点处的非
4、有效约束点处的非有效约束假设已知有效约束假设已知有效约束A(x)min( )f x. .( )0,ist c xiE( )0,ic xiImin( )f x. .( )0,( *)ist c xiA x定理定理(一阶必要条件)(一阶必要条件)1:DnfDRR设在开集 上连续可微,若min( )()0.nx RxDf xg x是的局部极小点,则定理定理(凸最优性定理)(凸最优性定理)11:.nfDRRfC设是凸函数,且则()0.xg x是总体极小点min ( )nx Rf x定理定理(二阶必要条件)(二阶必要条件)1:DnfDRR设在开集 上二阶连续可微,若min( )()0,()0( ( *)
5、.nx RxDf xg xG xG x是的局部极小点,则正半定定理定理(二阶充分条件)(二阶充分条件)1:DnfDRR设在开集 上二阶连续可微,()0().xDfg xG x则是 的一个严格局部极小点的充分条件是和是正定矩阵2( )f xC*()0f x2*()f x*xmin( )f x设函数设函数,若若,并且并且半正定,则半正定,则是是的局部最优解的局部最优解。 *xmin( )f x*x设设是是的局部最优解,则在的局部最优解,则在处的下降方向一定不是可行方向。处的下降方向一定不是可行方向。 定义定义设f(x)为定义在空间nR上的连续函数,点_nxR,若对于方向nsR存在数0使成立_()(
6、 ),(0, ),f xsf x则称s为f(x)在_x处的一个下降方向下降方向.在点_x处的所有下降方向的全体记为_( ).D x定理定理设函数f(x)在点_x处连续可微,如存在非零向量nsR使成立_( )0Tf xs则s是f(x)在点_x处的一个下降方向.给出了在给出了在f(x)连续可微是下降方向同函数连续可微是下降方向同函数f(x)的梯度的梯度 之间的关系之间的关系. .( )f x( ) |( )0TD xd df x下降方向集下降方向集序列可行方向序列可行方向*,0,(1,2,). .nkkxXdRdkst设如果 序列和*.dXx则称 是 在 处的序列可行方向*( *):SFD xXX
7、x,在 处的所有序列可行方向组成的集合*,kkxdXkk,00kkdd具有和,可行方向可行方向*,0,0, . .nxXdRst设如果*,0, xtdXt *.dXx则称 是 在 处的可行方向*( *, ):FD x XXx在 处的所有可行方向组成的集合线性化可行方向线性化可行方向*,0,nxXdR设如果*()0,;Tidc xiE*.dXx则称 是 在 处的线性化可行方向( *, ):LFD x X*()0,Tidc x*Xx在 处的所有线性化可行方向组成的集合12(,)Tdd d1 1223( )iiiic xa xa xa1122( )(,)iTiiadc xd da*();iI x11
8、12223( *)()()iiiic xdaxdaxda( *)( )Tiic xdc x如果所有的约束函数都在如果所有的约束函数都在*xX处可微,处可微,则有则有( *, )( *, )( *, )FDx XSFDx XLFDx X*,0, xtdXt *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向可行方向可行方向线性化可行方向线性化可行方向( *,)( *,)FD xXSFD xX( *,)( *,)dFD xXdSFD xX ,2kkkdd( *,)( *,)SFD xXLFD xX( *,)( *,)dSFD
9、 xXdLFD xX *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向线性化可行方向线性化可行方向0d 0d *kkxdX( *)( *)( *)Tikkikkic xdc xdc x引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在处可微,kx则所有可行序列d的序列可行方向 满足*()0,(,)Tdf xdSFD xX *(,)()SFD xXD x在局部极小点处没有可行下降方向在局部极小点处没有可行下降方向证明证明
10、: :反证法反证法. .假设存在可行序列假设存在可行序列kx的序列可行方向的序列可行方向d*.( )0,( ,),Tst df xdSFD x X 并且序列并且序列*lim.kkxx*()()()()(|)Tkkkf xf xxxf xoxx*|*|kkkxxddxx*() |()(|)Tkkf xxxdf xoxxk 0*()()kf xf xk 矛盾矛盾引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在处可微,则必有*()0,(,)Tdf xdFD xX *(,)()FD xXD x在局部
11、极小点处没有可行下降方向在局部极小点处没有可行下降方向FarkasFarkas引理引理设nmRA为nm 矩阵,,nRb 则下述两组方程中有且仅有一组有解:0 ,0 ,(1)TAxb x,0 ,(2)TA yby其中.,mnRyRxFarkasFarkas引理在最优化理论研究中起重要作用引理在最优化理论研究中起重要作用Farkas引理的另一种形式引理的另一种形式设设l. l是两个非负整数,是两个非负整数,a0,ai (i=1,l)和和bi (i=1,l)是是Rn中的向量,则线性方程组和不等式组中的向量,则线性方程组和不等式组0,1, ,Tid ail 0,1, ,Tid bil00Td a 无解
12、当且仅当存在实数无解当且仅当存在实数(1, )(1, )iiilil和 非 负 实 数使得使得011.lliiiiiiaabKKTKKT定理定理*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在的邻域内一阶连续可微.()CQ如果约束规范条件min( )f x. .( )0,ist c xiE( )0,ic xiI( *,)( *,)SFD xXLFD xX*. .ist则存在成 立*1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI驻点条件驻点条件可行性条件可行性条件乘子非负条件乘子非负条件互补松弛条件互补松弛
13、条件KKTKKT条件条件1, l1,lm 13122min. .00 xstxxx2x1x*(0,0)Tx *10()1c x*20()1c x *1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI*1()0f x ( *,) |0LFD xXd d( *,) |,00SFD xXd d最优点不一定是最优点不一定是KKTKKT点点2221232221123212314253min( )32. .( )30( )0( )0( )0( )0f xxxxstc xxxxcxxxc xxcxxc xx *(1,1,1,)KKTTx 验证最
14、优点是否为点.*1,2I ( *)( 6, 2, 4)Tf x 1( *)(2,2,2)Tc x2( *)( 1,1,0)Tc x 12621022104200 1222 证明证明*1( *)()miiif xc x*0,iiI*()0,iic xiI*(,)dSFD xX设*x 是局部极小点*()0,(,)Tdf xdSFD xX ( *,)( *,)SFD xXLFD xX*(,)dLFD xX*()0,;Tidc xiE*()0,();Tidc xiI x*()0Tdf x*()dD x*(,)LFD xX方程组无解方程组无解*(),0() . .iiR iEiI xst*()( *)(
15、)()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x*0, ()iiI I x令* ()()iii I I xc x*1()miiic x1, El1,Ilm *1()()miiif xc x*0,iiI *()( *)0iiI xc x* ()0iiI I x*()0,.iic xiI 线性函数约束规范条件线性函数约束规范条件(LFCQ):*()()ic xiEI x所有的约束函数都是线性函数.线性无关约束规范条件线性无关约束规范条件(LICQ):*()()ic xiE
16、I x约束函数的梯度线性无关.可以证明可以证明(1) 如果如果LFCQ成立,则成立,则CQ成立成立(2) 如果如果LICQ成立,则成立,则CQ成立成立定理定理: :*xX设是约束优化问题的局部极小点,LGCQLICQ如果成立或者成立,KKT.则条件成立一阶最一阶最优性充优性充分条件分条件定理定理*,xX设*( )( )if xc xx如果和都在 处可微,并且有*()0,0(,)Tdf xdSFD xX 成立,*.x则 是问题的一个严格局部极小点证明证明: :*.x假设 不是严格局部极小点. .kxX st则*()()kf xf x*,1,2,kkxx xx k且有不失一般性,我们可假定不失一般
17、性,我们可假定*2|kkkxxddxx*2|kkxx*( , )d SFD x X*2()()()()Tkkkkf xf xdf xo*()f x0*()0Tkdf x*()0Tdf xk 矛盾矛盾*2()|()0,( *),0TiiFdLFDc xdiI x 线性化零约束方向集线性化零约束方向集2*2*2*1(,)()()mxxiiiL xf xc x 定理定理( (二阶必要性条件二阶必要性条件) )*x设 是约束优化问题的局部极小点,*Lagrange是相应的乘子.LICQ如果成立,则2*2(,)0,().TxxdL xddF 定理定理( (二阶充分性条件二阶充分性条件) )*KKTx设
18、是一个点,*是相应的如果2*2(,)0,(),0,TxxdL xddFd Lagrange乘子.*.x则 是问题的严格局部极小点 7.2 7.2 二次罚函数方法二次罚函数方法设法将约束问题求解转化为无约束问题求解设法将约束问题求解转化为无约束问题求解具体说:具体说:根据约束的特点,构造某种惩罚函数,根据约束的特点,构造某种惩罚函数,然后把它加到目标函数中去,将约束问题的然后把它加到目标函数中去,将约束问题的求解化为一系列无约束问题的求解求解化为一系列无约束问题的求解二次罚函数法引例:引例: 求解等式约束问题求解等式约束问题: :222121,minxxxxf02.21xxt s解解: :图解法求出最优解图解法求出最优解 .1 , 1*Tx 构造:构造:22,2121222121xxxxxxxxF但是但是21,xxF性态极坏,性态极坏, 无法用有效的无约束无法用有效的无约束优化算法求解优化算法求解设想构造:设想构造:2221212;2Q xxxxx其中其中求解此无约束问题得:求解此无约束问题得: 12221xx当当时时, 有:有: TTTxxxx1 , 1,*2*121是一个非常大的正数是一个非常大的正数等式约束问题等式约束问题 1minnRxxf .0istcxiE二次罚函数二次罚函数 21;( )2ii EQ xfxcx 0ic x 如果0
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 空气动力学方程:RANS方程:RANS方程的数学基础
- 中职教育二年级全学期《城市轨道交通类-运营服务 AFC大面积故障应急处理》教学课件
- 小学二年级下学期科学《力与形变》教学课件
- 隧道洞身开挖工程专项的施工方案设计
- 能源大数据应用开发技能竞赛理论考试题库-上(单选题)
- 第十八届“振兴杯”全国青年职业技能大赛(职工组)物联网安装调试员决赛试题库-上(单选题)
- 2024年广西职业院校技能大赛中职组《中式烹饪》赛项考试题库及答案
- (新版)工程船舶机电工(初级)职业资格考试题库(含答案)
- C语言程序设计班级档案管理系统
- 如何做好采购工作
- 空调自控系统安装确认(IQ)方案
- TECO-N310系列变频器参数设定说明
- 有机化学ppt课件(完整版)
- 机械与电气识图教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案课件合集
- 食堂会计核算与会计科目
- 企业注销登记申请书
- JJG 672-2018 氧弹热量计检定规程-(高清现行)
- AHM910航空地面支持设备基本要求
- 船用海水淡化装置的工作原理与实例教学课件(32张)
- 五年级英语上册教学课件:五上M3U1外研版(三起)
- DB11_T1832.1-2021 建筑工程施工工艺规程第1部分:地基基础工程
评论
0/150
提交评论