最优化：二次规划

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕第十一章二次规划二次规划是最简单的非线性规划问题).(},,1,{0,},,,{,..)(minmmmEibxamIibxatsxqQxxxfiTiiTiTTRbqRaQnini,,,对称半正定阶矩阵其中二次规划一般形式：IibxaλλbxaEibxaaλxfxi*Ti*i*ii*Tii*TiiIEi*i*,0)(,0,0(11.2),00)(:Lagrange)1.11(**满足乘子存在的最优解是问题设,,,21212121111111EImmmEmITmTmTmETmTTIAAAbbbbbbbbaaaAaaaA记0)(,,).()().(******IITIIIIEETbxAbxAbxAAxf可以写成向量形式：则.)3.11(,是一线性方程组当只有等式约束时第一节等式约束二次规划考虑凸二次规划)4.11(s.t.21)(minbAxxqQxxxfTT).(,)(KKTbqxAAQbAxAxfTT或条件为其QxfxLQqQxxfx)(),(,)(半正定这里),LFD),(}|{),LFD(DxxSAdRdDxn（由于AdddxLdQddxTT,),(:满足二阶充分条件为mnmnmnmnnmnnmnmnzyyyZydRyyyyAdRdRzzzZzzzmnAAdmArA--2211-T-21)-(-21-21zz),,,(,0:),,,(,,,,:.-)(0,)(使得存在向量则对任意的并令交基础解系为设解空间的一组正的维数为的核空间解空间的则齐次线性方程组行满秩即假定.).(,).(,,1.1.11有惟一解因此线性方程组非奇异的系数矩阵线性方程组则若二阶充分条件成立行满秩设矩阵定理AAQAT:,KKT)4.11(有下面的结论系统解的存在性的关于问题.0,0-正定即矩阵于从而二阶充分条件等价QZZRyQddQZyZyTmnTTT矩阵矩阵或既约的投影为等式二次规划问题我们称HessianHessian)4.11(QZZT.).(,仅有零解组只需证明齐次线性方程非奇异证明：为证明系数矩阵vdAAQT.(11.5),,)6.11(.0,,,,,0,00)(0,0-,)6.11(),(212211T唯一解有故故系数矩阵非奇异只有零解即方程组从而得线性无关即向量组满秩由于然后推出由二阶充分条件得即有则的解是设vaaaAQdavavavvAdvAdvAdQddAdvAQdvdmmmTTTTT:1.1.11,Hessian可以等价描述为定理矩阵利用投影.)5.11(,Hessian)4.11(,2.1.11有惟一解则线性方程组正定矩阵影的投若二次规划问题行满秩设矩阵定理QZZAT:KKT,,.KKT,ACQ,,点也必定是其最优解一定条件下在反之点必定是从而二次规划的最优解成立故数是线性的由于二次规划的约束函众所周知.)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,**其全局最优解就是点我们只需证明因此点优解必定是其的最问题而由第九章知点有惟一的问题知或定理由定理证明：在定理条件下xx00,-,}.|{:**AddxxdxxDxbAxRxDn且则令且对于任意的设可行域.0QddT由二阶充分条件知：dqQxdqQxQddxxqxxQxxxQxxxqQxxxqQxxxfxfTTTTTTTTTT)()()()()()()()(***************,,KKTTAqQxx使得故存在乘子点是由于AdxfxfT**)()(所以.,*是全局最优解因此x.).(,,无解或有无界解问题则不正定时但二阶条件不成立或注意：当QZZDT.)()(21)(21)(,,0,,,0,0,,Z)1(22T即目标函数无下界且使得及则对令此时使得存在即有负特征值不定若xfxfQZuZuxfQdddxfDdxDxZudQZuZuuQZTTTTT.(11.4))()(,,0,,0,0,Z)2(T的解无界因而且使得及则令类似地使得则存在半正定但不正定若xfdxfDdxDxZudQZuZuuQZTT(11.7)s.t..)(min1.1.11xxxxxxxxxxxxxxxxxf：考察如下二次规划问题例bAqQ,,,解：xxx0011000101114211025201126KKT系统为：则该问题的**,:KKTx点及乘子为求得TZdddddAd,得基础解系令得：由421252126Q013QZZT是最优解所以*x)5.11(KKT)4.11(,系统等价于解解等式二次规划问题由上面的分析知.5b)(:).(bqxAAQT系数矩阵对称改写成我们将),(,,个负特征值个正特征值但不正定易验证系数矩阵非奇异在二阶充分条件下mn对角矩阵下三角矩阵这里BLLBLAAQTT,0,如对称分解先对系数矩阵进行不定zxLyBzbqLyT再依次解方程组：第二节解二次规划的有效集法二次规划来求解成一系列等式规划转化将含不等式约束的二次思想}|{)(,iTibxaEIixAxDx处的有效集记设: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来估计构造索引集序列称为工作集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)((的最优解是原二次规划问题则满足乘子的的最优解是问题如果满足设定理）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),0s.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也许修正点此时必须产生新的可行此时只修改满足但此时必须修正工作集的最优解不是原问题则不全满足如果定理中的两个条件依据定理的具体计算及新的可行点作集新的工出现如果上述两种情形之一下面我们来讨论11,,kkxA0:,0(1))(kikkIAid满足但情形0(2)kd情形}0,|{minarg}{\,,)10.11(0)()(11IAjiiAAxxxdkkjkjkkkkkk这里此时令的最优解是表明:,10)(1Ddxxakkkkk使得首先计算步长ikTikTikTikkTikTikkikTikTikkTiikTikTikkTikkkbxadaxadxadaAIiAIibdaxadxaEibdaxadxadxAi)(0,,0,\,)(,)(,0,,得对时但当即满足可行性对时当(11.12)\min)(,:\kTikkTikTiikTikTiiikTikTikkTikTikdaAIidaxabdaxabbdaxadxadaAIi且从而即有要使的情况且下面我们考虑(11.13)\,min,,kTikkTikTiikkkkkdaAIidaxabDdx且应取步长要使因此kkkkikTikAAiAAbxaAIib111},{,,\)(否则则使得如果)(((2))()1(:11111kkkkkkxfxfxAAAx）满足和由上面的方法确定的,,0:)2(显然成立时当对于kd0)(21,)11.11(,0kTkkTkkkdxfQdddd则必有的解是问题由于时当)