最优化方法介绍

最优化方法主要内容1、线性规划算法2、无约束非线性优化算法3、约束非线性优化算法Chap1预备知识.,...,1,0)(;,...,1,0)(s.t.)(minmmixcmixcxfeieiRxn(p)一、最优化问题的一般形式：决策变量，目标函数，约束函数（等式，不等式）、条件。线性、非线性规划，二次规划；约束、无约束优化………二、可行解与可行域三、（严格）局部极小点与（严格）全局极小点四、向量范数、矩阵范数1、向量范数定义三条件：2、常见向量范数：p||||||||||||||||213、诱导矩阵范数五、线性空间、欧式空间六、梯度、Hesse阵例求下列函数的梯度与Hesse阵.)()2(;)()1(AxxxfxaxfTT七、方向导数1、定义：对于若极限,0d||||)()(lim0daxfdxfd存在，称该极限值为)(xf在处沿方向的一阶方向导数，记为xddxf)(定理1若函数具有连续的一阶偏导数，则)(xf它在处沿方向的一阶方向导数为xd||||),()(ddxfdxf在处沿的方向的变化率xd方向导数几何意义：函数)(xf梯度方向是函数值变化最快的方向2、二阶方向导数：对于若极限,0d||||)()(lim0daxfddxfdd存在，称该极限值为在处沿方向的二)(xf阶方向导数，记为xd22)(dxf定理2若函数具有连续的二阶偏导数，则)(xf它在处沿方向的二阶方向导数为xd||||,||||)()(222ddddxfdxf在处沿的方向的凹凸性和弯曲程度xd二阶方向导数几何意义：函数)(xf八.凸集与凸函数1.凸集（1）凸组合：已知，nRX任取k个点，Xxi如果存在常数0ia，),,2,1(ki11kiia，使得xxakiii1，则称x为ix),,2,1(ki的凸组合。（2）凸集：设集合nRX，如果X中任意两点的凸组合仍然属于X，则称X为凸集。(3)凸集的顶点：不能表示成另外两个点的严格凸组合。（4）凸集的方向、极方向定理3设是非空闭凸集，若，则存在唯一DDy的点，使得它与的距离最短，且满足Dxy.,0,Dxxyxx定理4（凸集分离定理）设是非空闭凸集，若，则存在DDy0,cRcn和，使得R.,DxycxcTT2.凸函数设RRXfn:，任取Xxx21,，如果1,0,2121iiaaa，有)()())((22112211xfaxfaxaxaf，则称f为X上的（严格）凸函数。例子：2)(xxf凹函数？水平集：fXxxfxD,,)(|{是凸函数}。性质：水平集一定是凸集。3.凸函数的性质定理5.凸函数的局部极小点就是全局极小点。4.凸函数的判断条件定理6.)(xf是凸集X上的凸函数的充要条件是Xxx21,)()()()(12112xxxfxfxfT.定理7.设)(xf在凸集X上有二阶连续偏导数，则)(xf是凸函数的充要条件是Xx，有)(2xf半正定。例：正定二次函数cxbAxxxfTT21)(，其中A是正定矩阵。例：3123222121622)(xxxxxxxxf5.凸规划（1）Dxtsxf..)(min其中)(xf是凸函数，D是凸集。（2）)(minxf0)(0)(0)(0)(..11xhxhxgxgtskl其中)(,)(xgxfi是凸函数，)(xhj是线性函数。