第三章 优化设计问题的理论基础

本章介绍一下与最优化有关的知识。主要包括：a.函数的凸性b.无约束函数的极值点存在的条件c.约束极值点存在的条件d.最优化设计的数值计算迭代方法关于多元函数的数学预备知识一、函数的梯度多元函数12()(,,,)nffxxxXT12[,,,]nnxxxEX在X点可微，称12(),,,TnffffxxxX为函数在X点的梯度（向量）。梯度的大小——梯度的模22212()nffffxxxX——向量梯度的特点（2）梯度方向是函数f（X）在点X处取值增长最快的方向。（1）梯度方向沿f（X）等值面的法线方向；()()ffnXXτ()CfX等值面X()()()cosffflnXXl=Xf(X)沿方向l的方向导数nnτ等值面Xlθ()0,()()ffflnXXl=Xn是沿法线当的单位向量()fX——f(x)沿梯度方向的变化率。可见，负梯度方向是其在X处下降最快的方向。使f(X)值下降（减小）的方向S须与梯度的内积小于零T()0fXSnτ等值面XSθ90°例：求函数221212()6830fxxxxX在点T[2,3]X的梯度2221112122222122222212()()()()()()()()()()nnnnnnfXfXfXxxxxxxfXfXfXfXxxxxxxfXfXfXxxxxxx二、Hessian（赫森）矩阵设f(X)在X点二阶可微，称为f(X)在X点的Hessian（赫森）矩阵，记为()HX或2()fX显然，当二阶偏导数连续时，H(X)为对称矩阵。举例讨论三、矩阵的正定和负定111212122212nnnnnnaaaaaaAaaa1112121222111211212212000,,,nnnnnnaaaaaaaaaaaaaa正定的条件是A的顺序主子式全部大于零。即负定的条件是A的顺序主子式为相同的一负一正。即111212122211121121221200(1)0,,,nnnnnnnaaaaaaaaaaaaaa四、多元函数的二阶Taylor展开一元函数f(x)在x0的二阶Taylor展开000001()()()()()()2fxfxfxxxfxxx多元函数f(X)在(0)X作二阶Taylor展开(0)T(0)(0)(0)T(0)()()()()1()()()2fffHXXXXXXXXXXmin()s.t.()0(1,2,,)()0(1,2,,)nEuvfgumhvpXXXX优化问题的数学模型§3.1局部最优解与全局最优解最优性条件？唯一性？局部最优？全局最优？一、定义：局部最优解——D内局部范围内的最小值{()0,(1,2,,);()0,(1,2,,)}uvDgumhvpXXX可行域全局最优解——可行域上的最小值min()DfXX优化问题的数学模型的其余形式二、凸集、凸函数与凸规划凸集设D是En中的点集，若对任意两点有(1)(2)(1),(01)XXXD则称D为凸集。En及空集属于凸集。(1)(2),XXD(1)X2x凸集非凸集(2)X(1)X(2)X凸函数f(X)定义于D上，D是非空凸集。对D中任意两点。(1)(2),XX均有实数λ∈[0,1](1)(2)(1)(2)((1))()(1)()fXXfXfX成立，则称f(X)为D上的凸函数。若不等式严格成立，则称为严格凸函数。一般，线性函数为凸函数。定义于实轴上的一元线性函数f(x)凸函数xyy=f(x)例：定义于[a,b]上的一元函数f(x)凸函数xyab非凸函数xyabDD()()fXfX若函数在凸集上存在二阶导数并且连续时，对在凸集上为凸函数的充分必要条件是：D()XfXHX对于任意的，的赫森矩阵（）处处是半正定矩阵。凸函数的判定DS()HXXfX若赫森矩阵（）对一切都是正定的，则是凸集上的严格凸函数。反之则不成立。例试判断函数22122112()210460D(1,2)}ifxxxxxxxxi在＝｛－上的凸性。2211122222122()()21()()=12()()fXfXxxxxHXfXfXfXxxxx解：利用Hessian矩阵来进行判别111211212220,30aaaaaHesse矩阵是正定的，为严格凸函数。凸规划对优化问题若可行域D为凸集，目标函数为D上的凸函数，则该问题称为凸规划问题。定理1.若优化问题min()s.t.()0(1,2,,)nEufgumXXX其中，f(X)，-gu(X)为En中的凸函数，有以下结果成立min()DfXX（1）可行解集为凸集；（2）任何局部最优解就是全局最优解；（3）最优解集合D*是凸集。2121212min()1()S.t.1000XEfXxxxxxx例线性规划问题为凸规划问题，定理1的结论完全适用。结论：定理2对优化问题min()s.t.()0(1,2,,)nEufgumXXX其中，f(X)为严格凸函数，-gu(X)为En中的凸函数，若上述问题存在最优解，则最优解是唯一的。2221212112221232min()685S.t.()10()4/40()0XEfXxxxxgXxxgXxxgXx例、考虑优化问题可见，只有上述定理2中的凸规划问题，局部最优解就是全局最优解。实际问题很复杂，不需要也很难说明问题是凸规划问题，如何找到比较满意的解答？§3－2无约束函数的极值点存在的条件1、一元函数（1）极值点存在的必要条件x*为极值点的必要条件为：*'()0fx此条件为必要条件，满足上式的点为驻点，是否是极值点，必须通过函数的二阶导数来进行判断。（2）极值点存在的充分条件若在驻点附近有：，则该点为极大点；''()0fx若，则该点为极小点。''()0fx极值点存在的必要条件****12X()()()(),,,nnfXfXfXfXxxx*元函数在定义域内极值点存在的必要条件为0即函数在该点的梯度为零。该点也成为驻点，是否为极值点则必须通过赫森（Hessian）矩阵来判断。2、多元函数极值点存在的充分条件()Taylorf*将在驻点附近作二泰勒级数展开XX****2**()()[()]()1+()()()2TTffffXXXXXXXXXX此式可以化简为****1()()()()()2TfXfXXXHXXX*****XX()()01()()()02TfXfXXXHXXXX*若在点附近的邻域内，对一切，恒有即则为极小点。由矩阵理论可知，极小点的充分条件为2***,1()()()0niijjijijfXxxxxxxHessian矩阵为正定。极大点的充分条件为2***,1*()()()0H()niijjijijfXxxxxxxX亦即赫森矩阵必须为负定。2***,1**()()()0H()niijjijijfXxxxxxxXX亦即赫森矩阵既非正定，也非负定，那么函数在处没有极值。例求函数22212323312()252263fXxxxxxxxx的的的极值点和极值。解：1212321233()()0()+2=0()+26=0()+2+2=0fxfXfXxxxfXxxxfXxxxx函数的极值点必须满足：＝即＝4＝10－＝2将方程联立求解，有1231,1,2xxx再由赫森矩阵来判断是否为极值点。2*2*2*1112132*2*2**2*2122232*2*2*313233()()()()()()()()()()()402=0102222fXfXfXxxxxxxfXfXfXHXfXxxxxxxfXfXfXxxxxxx由顺序主子式111213111211212223212231323340400240,,aaaaaaaaaaaaaa赫森矩阵正定。驻点X*＝[1,1,-2]T为极小点，函数的极小值为*()0fX§3－3约束优化问题的最优性条件1、起作用约束与不起作用约束考虑不等式约束()0(1,2,,)ugumX设X(k)是可行解，如果()i()0kgX则称gi(X)为X(k)的起作用约束；()i()0kgX如果，则称gi(X)为X(k)的不起作用约束。X(k)的起作用约束下标集()I={()0,1im}kiigX2、Kuhn-Tucker条件（K－T条件，库恩－塔克条件）min()s.t.()0(1,2,,)()0(1,2,,)nEuvfgumhvpXXXX若X*是上述优化问题的局部最优解，记该点的起作用约束为I，则目标函数在X*的梯度可以表示成起作用不等式约束函数的梯度与等式约束函数梯度的线性组合，即考虑优化问题1()()()puujuuIjfggXXX其中，u是一组非负乘子。必要条件几何解释见教材。例：设下列优化问题2221212221122123142min()6413S.t.()50()240()0()0XEfXxxxxgXxxgXxxgXxgXx判定(1)TX[2,1]是否是K－T点？，最优解？(2)TX[0,2]？§3－4最优化设计的数值算法无约束优化问题和约束优化问题当其数学模型确定后求其最优解。◎最优化问题解法分为两类：解析法和数值算法。解析法主要指根据最优性条件求解。◎优化方法一般指数值算法，其中的一类算法称为搜索算法，其具有共性。自初始点开始，找到(0)X(1)(2)(n)XXXX使(0)(1)(2)(n)(X)(X)(X)(X)(X)fffff下降算法迭代法几何表示等值线x200()S0()X1()X2()X3()X*X(1)1S，22()Sx1一、迭代法过程与格式迭代法过程1((1)(0)(0)0(2)(1)1))))(((1=1,2,kkkkXXXXSSSXXkX(k)——第k次迭代点X(k＋1)——第k次迭代后产生的点S(k)——第k次迭代的搜索方向，是向量αk——第k次迭代的步长因子，是标量1.点距准则(1)()kkXX为实现目标函数值的极小化，迭代计算应满足：(0)(1)()(1)()()()()kkfXfXfXfX直至迭代满足一定的精度时，则认为目标函数值近似收敛于理论极小值。二、迭代计算的终止准则ε为很小的正数。2.函数下降量准则(1)()(1)()()()()()()()kkkkkfXfXfXfXfX某一很小的正数或3.梯度准则()()kfX某一很小的正数一般来说，满足其中任一个迭代终止准则，都可以结束迭代计算。