最优化二次规划-课件ppt（精）.ppt

最优化主讲:刘陶文课件制作:刘陶文唯楚有材於斯为盛学好最优化,走遍天下都不怕第十一章二次规划二次规划是最简单的非线性规划问题).(},,1,{0,},,,{,..)(min????????????????????????mmmEibxamIibxatsxqQxxxfiTiiTiTT??RbqRaQnini??,,,对称半正定阶矩阵其中二次规划一般形式:IibxaλλbxaEibxaaλxfxi*Ti*i*ii*Tii*TiiIEi*i*???????????????,0)(,0,0(),00)(:Lagrange)(**?满足乘子存在的最优解是问题设?,,,212**********?????????????????????????????????????????????????????????????????????????EImmmEmITmTmTmETmTTIAAAbbbbbbbbaaaAaaaA????记0)(,,).()().(******????????????????????IITIIIIEETbxAbxAbxAAxf???可以写成向量形式:则.)(,是一线性方程组当只有等式约束时第一节等式约束二次规划考虑凸二次规划)()(minbAxxqQxxxfTT???).(,)(KKT??????????????????????????????????????bqxAAQbAxAxfTT??或条件为其QxfxLQqQxxfx?????????)(),(,)(?半正定这里),LFD),(}|{), LFD(DxxSAdRdDxn(由于????????????????AdddxLdQddxTT,),(:满足二阶充分条件为?mnmnmnmnnmnnmnmnzyyyZydRyyyyAdRdRzzzZzzzmnAAdmArA--2211-T-21)-(-21-21zz),,,(,0:),,,(,,,,:.-)(0,)(??????????????????使得存在向量则对任意的并令交基础解系为设解空间的一组正的维数为的核空间解空间的则齐次线性方程组行满秩即假定.).(,).(,,????????????????AAQAT:,KKT)(,0-正定即矩阵于从而二阶充分条件等价QZZRyQddQZyZyTmnTTT?????矩阵矩阵或既约的投影为等式二次规划问题我们称HessianHessian)(QZZT.).(,仅有零解组只需证明齐次线性方程非奇异证明:为证明系数矩阵????????????????????????????????vdAAQT.(),,)(.0,,,,,0,00)(0,0-,)(),(212211T唯一解有故故系数矩阵非奇异只有零解即方程组从而得线性无关即向量组满秩由于然后推出由二阶充分条件得即有则的解是设?????????????vaaaAQdavavavvAdvAdvAdQddAdvAQdvdmmmTTTTT??:,Hessian可以等价描述为定理矩阵利用投影.)(,Hessian)(,: KKT,,.KKT,ACQ,,点也必定是其最优解一定条件下在反之点必定是从而二次规划的最优解成立故数是线性的由于二次规划的约束函众所周知.)()(),(Hessian)(,.)()(),(Hessian)(,,,KKT)(,,KKT)(,,**其全局最优解就是点我们只需证明因此点优解必定是其的最问题而由第九章知点有惟一的问题知或定理由定理证明:在定理条件下xx00,-,}.|{:**?????????QddT由二阶充分条件知: