《最优化二次规划讲稿.ppt》由会员分享，可在线阅读，更多相关《最优化二次规划讲稿.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于最优化二次规划第一页，讲稿共三十页哦第十一章第十一章 二次规划二次规划二次规划是最简单的非线性规划问题).(,1,0,.)(minmmmEibxamIibxatsxqQxxxfiTiiTiTTRbqRaQnini,对称半正定阶矩阵其中二次规划一般形式：第二页，讲稿共三十页哦IibxabxaEibxaaxfxi*Ti*i*ii*Tii*TiiIEi*i*,0)(,0 ,0 (11.2),0 0)(:Lagrange )1.11(*满足乘子存在的最优解是问题设第三页，讲稿共三十页哦 ,21212121111111EImmmEmITmTmTmETmTTIAAAbbbbbbbbaaaAaaaA记0
2、)(,).()().(*IITIIIIEETbxAbxAbxAAxf可以写成向量形式：则.)3.11(,是一线性方程组当只有等式约束时第四页，讲稿共三十页哦第一节 等式约束二次规划考虑凸二次规划)4.11(s.t.21)(minbAxxqQxxxfTT).(,)(KKT bqxAAQbAxAxfTT或条件为其QxfxLQqQxxfx)(),(,)(半正定这里第五页，讲稿共三十页哦),LFD),(|),LFD(DxxSAdRdDxn（由于AdddxLdQddxTT ,),(:满足二阶充分条件为mnmnmnmnnmnnmnmnzyyyZydRyyyyAdRdRzzzZzzzmnAAdmArA-22
3、11-T-21)-(-21-21zz ),(,0:),(,:.-)(0 ,)(使得存在向量则对任意的并令交基础解系为设解空间的一组正的维数为的核空间解空间的则齐次线性方程组行满秩即假定第六页，讲稿共三十页哦.).(,).(,1.1.11有惟一解因此线性方程组非奇异的系数矩阵线性方程组则若二阶充分条件成立行满秩设矩阵定理AAQAT:,KKT)4.11(有下面的结论系统解的存在性的关于问题.0 ,0 -正定即矩阵于从而二阶充分条件等价QZZRyQddQZyZyTmnTTT矩阵矩阵或既约的投影为等式二次规划问题我们称HessianHessian)4.11(QZZT第七页，讲稿共三十页哦.).(,仅有
4、零解组只需证明齐次线性方程非奇异证明：为证明系数矩阵vdAAQT.(11.5),)6.11(.0,0 ,0 0)(0 ,0-,)6.11(),(212211T唯一解有故故系数矩阵非奇异只有零解即方程组从而得线性无关即向量组满秩由于然后推出由二阶充分条件得即有则的解是设vaaaAQdavavavvAdvAdvAdQddAdvAQdvdmmmTTTTT第八页，讲稿共三十页哦:1.1.11,Hessian可以等价描述为定理矩阵利用投影.)5.11(,Hessian)4.11(,2.1.11有惟一解则线性方程组正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT:KKT,.KKT ,ACQ,点也必定
5、是其最优解一定条件下在反之点必定是从而二次规划的最优解成立故数是线性的由于二次规划的约束函众所周知.)4.11()5.11(),(Hessian)4.11(,3.1.11的惟一全局最优解的惟一解是问题方程组则线性或二阶充分条件成立正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT第九页，讲稿共三十页哦.)4.11()5.11(),(Hessian)4.11(,3.1.11的惟一全局最优解的惟一解是问题方程组则线性或二阶充分条件成立正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT.KKT,KKT)4.11(,KKT)4.11(,2.1.111.1.11,*其全局最优解就是点我们只需证明
6、因此点优解必定是其的最问题而由第九章知点有惟一的问题知或定理由定理证明：在定理条件下xx0 0 ,-,.|:*AddxxdxxDxbAxRxDn且则令且对于任意的设可行域.0QddT由二阶充分条件知：第十页，讲稿共三十页哦dqQxdqQxQddxxqxxQxxxQxxxqQxxxqQxxxfxfTTTTTTTTTT)()()()()()()()(*,KKT TAqQxx使得故存在乘子点是由于AdxfxfT*)()(所以.,*是全局最优解因此 x第十一页，讲稿共三十页哦.).(,无解或有无界解问题则不正定时但二阶条件不成立或注意：当QZZDT.)()(21)(21)(,0,0 ,0,Z )1(2
7、2T即目标函数无下界且使得及则对令此时使得存在即有负特征值不定若xfxfQZuZuxfQdddxfDdxDxZudQZuZuuQZTTTTT.(11.4)()(,0 ,0 ,0,Z )2(T的解无界因而且使得及则令类似地使得则存在半正定但不正定若xfdxfDdxDxZudQZuZuuQZTT第十二页，讲稿共三十页哦(11.7)s.t.)(min 1.1.11xxxxxxxxxxxxxxxxxf：考察如下二次规划问题例bAqQ ,解：第十三页，讲稿共三十页哦xxx 0011000101114211025201126 KKT系统为：则该问题的*,:KKTx点及乘子为求得TZdddddAd ,得基础
8、解系令得：由421252126 Q013 QZZT是最优解所以*x第十四页，讲稿共三十页哦)5.11(KKT)4.11(,系统等价于解解等式二次规划问题由上面的分析知.5b)(:).(bqxAAQT系数矩阵对称改写成我们将),(,个负特征值个正特征值但不正定易验证系数矩阵非奇异在二阶充分条件下mn对角矩阵下三角矩阵这里BLLBLAAQTT,0 ,如对称分解先对系数矩阵进行不定第十五页，讲稿共三十页哦zxLyBzbqLyT 再依次解方程组：第十六页，讲稿共三十页哦第二节 解二次规划的有效集法二次规划来求解成一系列等式规划转化将含不等式约束的二次 思想思想|)(,iTibxaEIixAxDx处的有
9、效集记设:KKT)1.11(,KKT,)2.11(,*条件满足子的最优解等价于存在乘是即若点等价因此它的最优解与是凸规划问题半正定时当xQ)(,*(*xIiaqQxixAiii其中）第十七页，讲稿共三十页哦)(,*(*xIiaqQxixAiii其中）:KKTKKTKKT,点问题的划点也是下列等式二次规条件的上述显然(11.8)(,s.t.21)(min*xAibxaxqQxxxfiTiTT.KKT)1.11(,0:Lagrange,KKT)8.11(,点即最优解的则得到满足乘子并且点的如果我们求得因此Iii?)(,)8.11(*xA即索引集中的约束关键：如何确定难啊)(*xAAk来估计构造索引
10、集序列称为工作集kA第十八页，讲稿共三十页哦?)()(*xAAxAAkk或那如何判断索引集序列:请看我给大家慢慢讲解:)8.11()(,的近似及问题构造工作集设kkkxAADx(11.10),s.t.21)(minkiTiTTAibxaxqQxxxf:,KKT)1.11(KKT)10.11(即可得到解的判别准则条件比较的条件与的然后将)(,*(*xIiaqQxixAiii其中）kAiiiaqQx :KKT).(条件为的第十九页，讲稿共三十页哦.)1.11(,0 :Lagrange(11.10)2(;)10.11()1(:).(,1.2.11)(的最优解是原二次规划问题则满足乘子的的最优解是问题
11、如果满足设定理）kkkikkkkkxIAixxAADx)(,*(*xIiaqQxixAiii其中）.KKT)1.11(KKT)10.11(,0 ,)(条件的条件就等价于的我们只需补充事实上定理的结论是显然的kkiAIi),1.2.111（可行点即集并产生新的可行点则我们需修正工作的两个条件不全满足当定理kkkkxxAA第二十页，讲稿共三十页哦 ,;,0:,111)(11iAAbxaAiiAAAAdDdxxxkkikTikkkkikkkkkkkk则如果则如果是可行方向修正方法：如下我们修改问题为计算可行方向.10)11(,kd得到代入问题即令.10),11(,-dxxxxdkk(11.11),0
12、s.t.)(21)(minkTiTkTAidadxfQddxf面的定理：等价于下因此定理的解是问题于的解等价是问题容易看出的解为设 11.2.1 .)11.11(0)10.11(,)11.11(kkkdxd第二十一页，讲稿共三十页哦.)1.11(,0 :Lagrange(11.11)2(;)11.11(0)1(:).(,1.2.11)(的最优解是原二次规划问题则足满乘子的的最优解问题是如果满足设定理）kkkikkkkkxIAidxAADx;,0 (2),0:,0 (1):,)1.11(,1,.2.111)(kkkkkikkkkAxdAIAidAx也许修正点此时必须产生新的可行此时只修改满足但此
13、时必须修正工作集的最优解不是原问题则不全满足如果定理中的两个条件依据定理的具体计算及新的可行点作集新的工出现如果上述两种情形之一下面我们来讨论11,kkxA第二十二页，讲稿共三十页哦0:,0 (1)(kikkIAid满足但情形0 (2)kd情形 0,|minarg ,)10.11(0)()(11IAjiiAAxxxdkkjkjkkkkkk这里此时令的最优解是表明:,10)(1Ddxxakkkkk使得首先计算步长ikTikTikTikkTikTikkikTikTikkTiikTikTikkTikkkbxadaxadxadaAIiAIibdaxadxaEibdaxadxadxAi)(0,0,)(,
14、)(,0,得对时但当即满足可行性对时当第二十三页，讲稿共三十页哦(11.12)min )(,:kTikkTikTiikTikTiiikTikTikkTikTikdaAIidaxabdaxabbdaxadxadaAIi且从而即有要使的情况且下面我们考虑(11.13),min ,kTikkTikTiikkkkkdaAIidaxabDdx且应取步长要使因此kkkkikTikAAiAAbxaAIib111 ,)(否则则使得如果第二十四页，讲稿共三十页哦)(2)()1(:11111kkkkkkxfxfxAAAx）满足和由上面的方法确定的,0 :)2(显然成立时当对于kd0)(21 ,)11.11(,0
15、kTkkTkkkdxfQdddd则必有的解是问题由于时当)()(2121)()(21)()()(kkTkkkkTkkTkkkkTkkkTkkkkkkxfQddQdddxfxfQdddxfxfdxf从而第二十五页，讲稿共三十页哦2.,1:.,.,)13.11(,0:42;,1:,0,|minarg ,STOP;,0,0:3;,(11.11):2;0),(,1 )(1.111111)()(11)()(000转步令否则令使得存在如果然后令计算步长则由如果步转步其中令否则那么得解时当如果步及乘子得解求解子问题步令给定初始可行点：步二次规划的有效集法算法kkAAiAAbxaAIidxxdkkIAjiiA
16、AxxxIAidAidkxAADxkkkkikTikkkkkkkkkjkjkkkkkkkikkkik意注;,),(,)(000也许是不同的及运行产生的序列算法但不同的可以取在算法中kkAxAxAAa第二十六页，讲稿共三十页哦规划子问题：解一个可行的线性的选取方法关于初始可行点 :)(0 xbEibxaIiezIibzxaEibzxatszexRxiTiiiiTiiiiTiTn ),(sign ,1),1,(1,.min :),(iiT其中构造子问题如下不可行假定给定点.,max ,|,|,:,IixabzEibxazxxTiiiiTii可行解上述线性规划子问题有显然第二十七页，讲稿共三十页哦 ,.)(min :1.2.11xxxxtsxxxxxf规划问题用有效集法解下列二次例10 ,01 ,11321aaa解：,)()(,00)()()(xAAxfx取初始可行点)()(,:d解得 ,.min ddtsdddd第一次迭代：解子问题第二十八页，讲稿共三十页哦,)(,)()()(AAxfxx故 .mindtsdddd第二次迭代：解子问题 ,;,)()()()(dadaxabdaTTTT2,1,)(,)()()()(AAxfdxx020 )1(d解得第二十九页，讲稿共三十页哦感谢大家观看感谢大家观看第三十页，讲稿共三十页哦