5-最优化-二次规划解析

第五章二次规划二次规划是最简单的非线性规划问题1111min()2..0,{1,2,,}(5.1)0,{1,2,,}TTTiiTiifxxQxqxstaxbiImaxbiEmmmRbqRaQnini,,,对称半正定阶矩阵其中二次规划一般形式：**(5.1)Lagrange:()00,(5.2)0,**iiiEIT*iiT**iiixfxλaaxbiEaxbλ设是问题的最优解存在乘子满足0,()0,*T*iiiλaxbiI,,,21212121111111EImmmEmITmTmTmETmTTIAAAbbbbbbbbaaaAaaaA记******(5.2)()00(5.3)0,0,()0TEETIIIIIIfxAAxbAxbAxb则可以写成向量形式：,(5.3).当只有等式约束时是一线性方程组第一节等式约束二次规划考虑凸二次规划1min()(5.4)2s.t.TTfxxQxqxAxbKKT()0,0(5.5)0TTfxAAxbxqQAbA其条件为或QxfxLQqQxxfx)(),(,)(半正定这里),LFD),(}|{),LFD(DxxSAdRdDxn（由于AdddxLdQddxTT,),(:满足二阶充分条件为mnmnmnmnnmnnmnmnzyyyZydRyyyyAdRdRzzzZzzzmnAAdmArA--2211-T-21)-(-21-21zz),,,(,0:),,,(,,,,:.-)(0,)(使得存在向量则对任意的并令交基础解系为设解空间的一组正的维数为的核空间解空间的则齐次线性方程组行满秩即假定5.1.1,,(5.5)0,(5.5).TAQAA定理设矩阵行满秩若二阶充分条件成立则线性方程组的系数矩阵非奇异因此线性方程组有惟一解(5.4)KKT,:关于问题的系统解的存在性有下面的结论.0,0-正定即矩阵于从而二阶充分条件等价QZZRyQddQZyZyTmnTTT(5.4)HessianHessianTZQZ我们称为等式二次规划问题的投影矩阵或既约矩阵,0(5.6)00.TdQAvA证明：为证明系数矩阵非奇异只需证明齐次线性方程组仅有零解T112212(,)(5.6),-0,0()00,0,,,,,0.(5.6),,(5.5).TTTTTmmmdvQdAvAddQddAvAdvdAvvavavaQdAaaav设是的解则即有由二阶充分条件得然后推出由于满秩即向量组线性无关从而得即方程组只有零解故系数矩阵非奇异故有唯一解Hessian,5.1.1:利用投影矩阵定理可以等价描述为5.1.2,(5.4)Hessian,(5.5).TAZQZ定理设矩阵行满秩若二次规划问题的投影矩阵正定则线性方程组有惟一解:KKT,,.KKT,ACQ,,点也必定是其最优解一定条件下在反之点必定是从而二次规划的最优解成立故数是线性的由于二次规划的约束函众所周知5.1.3,(5.4)Hessian(),(5.5)(5.4).TAZQZ定理设矩阵行满秩若二次规划问题的投影矩阵正定或二阶充分条件成立则线性方程组的惟一解是问题的惟一全局最优解5.1.3,(5.4)Hessian(),(5.5)(5.4).TAZQZ定理设矩阵行满秩若二次规划问题的投影矩阵正定或二阶充分条件成立则线性方程组的惟一解是问题的惟一全局最优解**,5.1.15.1.2,(5.4)KKT,(5.4)KKT,,KKT.xx证明：在定理条件下由定理或定理知问题有惟一的点问题的最优解必定是其点因此我们只需证明点就是其全局最优解00,-,}.|{:**AddxxdxxDxbAxRxDn且则令且对于任意的设可行域.0QddT由二阶充分条件知：dqQxdqQxQddxxqxxQxxxQxxxqQxxxqQxxxfxfTTTTTTTTTT)()()()()()()()(***************,,KKTTAqQxx使得故存在乘子点是由于AdxfxfT**)()(所以.,*是全局最优解因此x.).(,,无解或有无界解问题则不正定时但二阶条件不成立或注意：当QZZDT.)()(21)(21)(,,0,,,0,0,,Z)1(22T即目标函数无下界且使得及则对令此时使得存在即有负特征值不定若xfxfQZuZuxfQdddxfDdxDxZudQZuZuuQZTTTTTT(2)Z,0,0,,0,,()()(5.4).TTQZuuZQZudZuxDxdDfxdfx若半正定但不正定则存在使得类似地令则及使得且因而的解无界22112132223312313235.1.1min()322.522833(5.7)s.t.30fxxxxxxxxxxxxxxxxx例考察如下二次规划问题：bAqQ,,,解：xxx0011000101114211025201126KKT系统为：则该问题的**,:KKTx点及乘子为求得TZdddddAd,得基础解系令得：由421252126Q013QZZT是最优解所以*x,(5.4)KKT(5.5)由上面的分析知解等式二次规划问题等价于解系统(5.5):(5.5b)0TxqQAbA我们将改写成系数矩阵对称),(,,个负特征值个正特征值但不正定易验证系数矩阵非奇异在二阶充分条件下mn对角矩阵下三角矩阵这里BLLBLAAQTT,0,如对称分解先对系数矩阵进行不定zxLyBzbqLyT再依次解方程组：第二节解二次规划的有效集法二次规划来求解成一系列等式规划转化将含不等式约束的二次}|{)(,iTibxaEIixAxDx处的有效集记设:KKT)1.11(,KKT,)2.11(,**条件满足子的最优解等价于存在乘是即若点等价因此它的最优解与是凸规划问题半正定时当xQ)(,**(***xIiaqQxixAiii其中）)(,**(***xIiaqQxixAiii其中）:KKTKKTKKT,点问题的划点也是下列等式二次规条件的上述显然*1min()(5.8)2s.t.,()TTTiifxxQxqxaxbiAx,(5.8)KKT,Lagrange:0,,(5.1)KKT.iiI因此如果我们求得的点并且乘子满足则得到的点即最优解*(5.8),()?Ax关键：如何确定中的约束即索引集)(*xAAk来估计构造索引集序列称为工作集kA?)()(**xAAxAAkk或那如何判断索引集序列:请看我给大家慢慢讲解,()(5.8):kkkxDAAx设构造工作集及问题的近似1min()(5.10)2s.t.,TTTiikfxxQxqxaxbiA(5.10)KKT(5.1)KKT,:然后将的条件与的条件比较即可得到解的判别准则)(,**(***xIiaqQxixAiii其中）(5.10)KKT:0kiiiAQxqa的条件为(()5.2.1,().:(1)(5.10);(2)(5.10)Lagrange:0,(5.1).kkkkkkikkxDAAxxiAIx）定理设如果满足是问题的最优解的乘子满足则是原二次规划问题的最优解)(,**(***xIiaqQxixAiii其中）(),,0,\(5.10)KKT(5.1)KKT.kikiIA定理的结论是显然的事实上我们只需补充的条件就等价于的条件115.2.1,,)kkkkAAxx当定理的两个条件不全满足则我们需修正工作集并产生新的可行点即（可行点}{,,};{\,0:,111)(11iAAbxaAiiAAAAdDdxxxkkikTikkkkikkkkkkkk则如果则如果是可行方向修正方法：,(5.10)kd为计算可行方向我们修改问题如下-,(5.10),kkdxxxxd令即代入问题得到1min()()(5.11)2s.t.0,TTkTikfxdQdfxdadiA(5.11),,(5.10)0(5.11).5.2.1kkkdxd设的解为容易看出是问题的解等价于是问题的解因此定理等价于下面的定理：(()5.2.1,().:(1)0(5.11);(2)(5.11)Lagrange:0,(5.1).kkkkkkikkxDAAxdiAIx）定理设如果满足是问题的最优解的乘子满足则是原二次规划问题的最优解()15.2.1,,(5.1),:(1)0,:0,(2)0,,;kkkkkikkkkxAdiAIAdxA依据定理如果定理中的两个条件不全满足则不是原问题的最优解此时必须修正工作集但满足此时只修改此时必须产生新的可行点也许修正的具体计算及新的可行点作集新的工出现如果上述两种情形之一下面我们来讨论11,,kkxA0:,0(1))(kikkIAid满足但情形0(2)kd情形11()()0(5.10),,\{}argmin{|0,}kkkkkkkkjjkdxxxAAiijAI表明是的最优解此时令这里:,10)(1Ddxxakkkkk使得首先计算步长ikTikTikTikkTikTikkikTikTikkTiikTikTikkTikkkbxadaxadxadaAIiAIibdaxadxaEibdaxadxadxAi)(0,,0,\,)(,)(,0,,得对时但当即满足可行性对时当\0:0,()min\0(5.12)TkikTTTikkikikiTiikTikTTiikkikTikiIAadaxdaxadbbaxadbaxiIAadad下面我们考虑且的情况要使即有从而且,,min1,\0(5.13)kkkkTTiikkkikTikxdDbaxiIAadad因此要使步长应取且kkkkikTikAAiAAbxaAIib111},{,,\)(否则则使得如果)(((2))()1(:11111kkkkkkxfxfxAAAx）满足和由上面的方法确定的,,0:)2(显然成立时当对于kd0)(21,)11.11(,0kTkkTkkkdxfQdddd则必有的解是问题由于时当)()(2121)()(21)()()(kkTkkkkTkkTkkkkTkkkTkkkkkkxfQddQdddxfxfQdddxfxfdxf从而000()()115.1()1,(),0;2:(5.11),;3:0,0,,,STOP;,,