最优化二次规划（课堂PPT）

1、1最优化最优化主讲：刘陶文课件制作：刘陶文课件制作：刘陶文唯楚有材唯楚有材 於斯为盛於斯为盛学好最优化，走遍天下都不怕学好最优化，走遍天下都不怕2第十一章第十一章 二次规划二次规划二次规划是最简单的非线性规划问题).( , , 1, 0, , , , ,. . )(minmmmEibxamIibxatsxqQxxxfiTiiTiTTRbqRaQnini,对称半正定阶矩阵其中二次规划一般形式：3IibxabxaEibxaaxfxi*Ti*i*ii*Tii*TiiIEi*i* , 0)( , 0 , 0 (11.2) , 0 0)( :Lagrange ) 1 .11( *满足乘子存在的最优解是问

2、题设4 , , , 21212121111111EImmmEmITmTmTmETmTTIAAAbbbbbbbbaaaAaaaA记0)(, ).( )( ).( *IITIIIIEETbxAbxAbxAAxf可以写成向量形式：则.) 3 .11( ,是一线性方程组当只有等式约束时5第一节 等式约束二次规划考虑凸二次规划)4 .11( s.t. 21)(minbAxxqQxxxfTT).( ,)( KKT bqxAAQbAxAxfTT或条件为其QxfxLQqQxxfx)(),( ,)( 半正定这里6),LFD),( |), LFD(DxxSAdRdDxn（由于AdddxLdQddxTT ,),(

3、:满足二阶充分条件为mnmnmnmnnmnnmnmnzyyyZydRyyyyAdRdRzzzZzzzmnAAdmArA-2211-T-21)-(-21-21zz ),( , 0:) , , ,( , , , ,: .-)(0 ,)( 使得存在向量则对任意的并令交基础解系为设解空间的一组正的维数为的核空间解空间的则齐次线性方程组行满秩即假定7.).(, ).(, 1 . 1 .11有惟一解因此线性方程组非奇异的系数矩阵线性方程组则若二阶充分条件成立行满秩设矩阵定理AAQAT:,KKT)4 .11(有下面的结论系统解的存在性的关于问题.0 , 0 -正定即矩阵于从而二阶充分条件等价QZZRyQdd

4、QZyZyTmnTTT矩阵矩阵或既约的投影为等式二次规划问题我们称HessianHessian)4 .11(QZZT8.).( ,仅有零解组只需证明齐次线性方程非奇异证明：为证明系数矩阵vdAAQT.(11.5),)6 .11(. 0,0 , 0 0)( 0 , 0- ,)6 .11(),(212211T唯一解有故故系数矩阵非奇异只有零解即方程组从而得线性无关即向量组满秩由于然后推出由二阶充分条件得即有则的解是设vaaaAQdavavavvAdvAdvAdQddAdvAQdvdmmmTTTTT9:1 . 1 .11,Hessian可以等价描述为定理矩阵利用投影.)5 .11(,Hessian)

5、4 .11(, 2 . 1 .11有惟一解则线性方程组正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT: KKT, , .KKT ,ACQ,点也必定是其最优解一定条件下在反之点必定是从而二次规划的最优解成立故数是线性的由于二次规划的约束函众所周知.)4 .11()5 .11(),(Hessian )4 .11( , 3 . 1 .11的惟一全局最优解的惟一解是问题方程组则线性或二阶充分条件成立正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT10.)4 .11()5 .11(),(Hessian )4 .11( , 3 . 1 .11的惟一全局最优解的惟一解是问题方程组则线性或二阶充

6、分条件成立正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT.KKT , ,KKT)4 .11(,KKT)4 .11(,2 . 1 .111 . 1 .11,*其全局最优解就是点我们只需证明因此点优解必定是其的最问题而由第九章知点有惟一的问题知或定理由定理证明：在定理条件下xx0 0 ,- , .|: *AddxxdxxDxbAxRxDn且则令且对于任意的设可行域. 0QddT由二阶充分条件知：11dqQxdqQxQddxxqxxQxxxQxxxqQxxxqQxxxfxfTTTTTTTTTT)( )( )()( )()( )()(* ,KKT TAqQxx使得故存在乘子点是由于Adxfxf

7、T*)()( 所以. ,*是全局最优解因此 x12.).(, ,无解或有无界解问题则不正定时但二阶条件不成立或注意：当QZZDT.)()(21)(21)(, 0,0 , 0,Z ) 1 (22T即目标函数无下界且使得及则对令此时使得存在即有负特征值不定若xfxfQZuZuxfQdddxfDdxDxZudQZuZuuQZTTTTT.(11.4) )()( , 0 ,0 , 0,Z )2(T的解无界因而且使得及则令类似地使得则存在半正定但不正定若xfdxfDdxDxZudQZuZuuQZTT13(11.7) s.t. .)(min 1 . 1 .11xxxxxxxxxxxxxxxxxf：考察如下二

8、次规划问题例bAqQ , , , 解：14xxx 0011000101114211025201126 KKT系统为：则该问题的* , :KKTx点及乘子为求得TZdddddAd , 得基础解系令得：由421252126 Q013 QZZT是最优解所以*x15)5 .11(KKT)4 .11(,系统等价于解解等式二次规划问题由上面的分析知.5b)( :).(bqxAAQT系数矩阵对称改写成我们将),(,个负特征值个正特征值但不正定易验证系数矩阵非奇异在二阶充分条件下mn对角矩阵下三角矩阵这里BLLBLAAQTT,0 ,如对称分解先对系数矩阵进行不定16zxLyBzbqLyT 再依次解方程组：17

9、第二节 解二次规划的有效集法二次规划来求解成一系列等式规划转化将含不等式约束的二次 思想思想| )( , iTibxaEIixAxDx处的有效集记设:KKT) 1 .11(,KKT,)2 .11(,*条件满足子的最优解等价于存在乘是即若点等价因此它的最优解与是凸规划问题半正定时当xQ)( ,*(*xIiaqQxixAiii其中）18)( ,*(*xIiaqQxixAiii其中）:KKTKKTKKT,点问题的划点也是下列等式二次规条件的上述显然(11.8) )(,s.t.21)(min*xAibxaxqQxxxfiTiTT.KKT) 1 .11(, 0: Lagrange,KKT)8 .11(,

10、点即最优解的则得到满足乘子并且点的如果我们求得因此Iii? )(,)8 .11(*xA即索引集中的约束关键：如何确定难啊)( *xAAk来估计构造索引集序列称为工作集kA19? )( )( *xAAxAAkk或那如何判断索引集序列:请看我给大家慢慢讲解:)8 .11()( ,的近似及问题构造工作集设kkkxAADx(11.10) ,s.t.21)(minkiTiTTAibxaxqQxxxf:,KKT) 1 .11(KKT)10.11(即可得到解的判别准则条件比较的条件与的然后将)( ,*(*xIiaqQxixAiii其中）kAiiiaqQx :KKT ).(条件为的20.) 1 .11(, 0

11、 :Lagrange (11.10) )2( ; )10.11( ) 1 ( : ).( , 1 . 2 .11)(的最优解是原二次规划问题则满足乘子的的最优解是问题如果满足设定理）kkkikkkkkxIAixxAADx)( ,*(*xIiaqQxixAiii其中）.KKT) 1 .11(KKT)10.11(, 0 ,)(条件的条件就等价于的我们只需补充事实上定理的结论是显然的kkiAIi) ,1 . 2 .111（可行点即集并产生新的可行点则我们需修正工作的两个条件不全满足当定理kkkkxxAA21 , ; , 0 :,111)(11iAAbxaAiiAAAAdDdxxxkkikTikkkk

12、ikkkkkkkk则如果则如果是可行方向修正方法：如下我们修改问题为计算可行方向.10)11(,kd得到代入问题即令.10),11( ,-dxxxxdkk(11.11) , 0s.t.)(21)(minkTiTkTAidadxfQddxf面的定理：等价于下因此定理的解是问题于的解等价是问题容易看出的解为设 11.2.1 . )11.11( 0)10.11(,)11.11(kkkdxd22.) 1 .11(, 0 :Lagrange (11.11) )2( ; )11.11( 0 ) 1 ( : ).( , 1 . 2 .11)(的最优解是原二次规划问题则足满乘子的的最优解问题是如果满足设定理）

13、kkkikkkkkxIAidxAADx ;, 0 (2) , 0: , 0 (1) :,) 1 .11(,1,. 2 .111)(kkkkkikkkkAxdAIAidAx也许修正点此时必须产生新的可行此时只修改满足但此时必须修正工作集的最优解不是原问题则不全满足如果定理中的两个条件依据定理的具体计算及新的可行点作集新的工出现如果上述两种情形之一下面我们来讨论11,kkxA230: , 0 (1) )(kikkIAid满足但情形0 (2) kd情形 0,| minarg , , )10.11( 0)()(11IAjiiAAxxxdkkjkjkkkkkk这里此时令的最优解是表明: , 10 )(1

14、Ddxxakkkkk使得首先计算步长ikTikTikTikkTikTikkikTikTikkTiikTikTikkTikkkbxadaxadxadaAIiAIibdaxadxaEibdaxadxadxAi)( 0,0, ,)( ,)( ,0, 得对时但当即满足可行性对时当24(11.12) min )( ,:kTikkTikTiikTikTiiikTikTikkTikTikdaAIidaxabdaxabbdaxadxadaAIi且从而即有要使的情况且下面我们考虑(11.13) ,min ,kTikkTikTiikkkkkdaAIidaxabDdx且应取步长要使因此kkkkikTikAAiAAb

15、xaAIib111 , , )(否则则使得如果25)( (2) )( ) 1 ( :11111kkkkkkxfxfxAAAx）满足和由上面的方法确定的,0 :)2(显然成立时当对于kd0)(21 ,)11.11(,0 kTkkTkkkdxfQdddd则必有的解是问题由于时当)( )(2121)()( 21)()()( kkTkkkkTkkTkkkkTkkkTkkkkkkxfQddQdddxfxfQdddxfxfdxf从而262., 1: ., , .,)13.11(, 0 :42;, 1: ,0,|minarg , , STOP;, , 0, , 0 :3;,(11.11) :2; 0 ),(

16、, 1 )( 1 .111111)()(11)()(000转步令否则令使得存在如果然后令计算步长则由如果步转步其中令否则那么得解时当如果步及乘子得解求解子问题步令给定初始可行点：步二次规划的有效集法算法kkAAiAAbxaAIidxxdkkIAjiiAAxxxIAidAidkxAADxkkkkikTikkkkkkkkkjkjkkkkkkkikkkik意注; ,),(, )(000也许是不同的及运行产生的序列算法但不同的可以取在算法中kkAxAxAAa27规划子问题：解一个可行的线性的选取方法关于初始可行点 : )(0 xbEibxaIiezIibzxaEibzxatszexRxiTiiiiTiiiiTiTn ),( sign , ,1) , 1, (1, ,. . min :),( iiT其中构造子问题如下不可行假定给定点., ,max ,|,| , :, IixabzEibxazxxTiiiiTii可行解上述线性规划子问题有显然28 , . .)(min : 1 . 2 .11xxxxtsxxxxxf规划问题用有效集法解下列二次例10 ,01 ,11321aaa解： ,)( )(,00 )()(