最优化_第2章 优化设计的数学基础

第二章优化设计的数学基础2.1多元函数的导数与梯度2.4凸集、凸函数与凸规划2.2多元函数的泰勒展开2.3无约束优化极值条件2.5等式约束优化极值条件2.6不等式约束优化极值条件§2.1多元函数的导数与梯度一、方向导数二元函数f(x1，x2)在X(0)的偏导数为：1(0)(0)(0)(0)(0)11212011(,)(,)()limxXfxxxfxxfxxx分别表示沿坐标轴x1和x2方向在X(0)处的f(X)变化率。2(0)(0)(0)(0)(0)12212022(,)(,)()limxXfxxxfxxfxxxf(X)在X0点沿d方向的方向导数:(0)(0)(0)(0)(0)1122120,,limdXfxxxxfxxfdd§2.1多元函数的导数与梯度表示沿d方向在X(0)处的f(X)变化率。Δddθ2Δx2Δx1x1x20x1(0)x2(0)X(0)θ1(0)(0)(0)(0)11212101(0)(0)(0)(0)1122112202,,lim,,limddfxxxfxxxxdfxxxxfxxxxxd(0)1Xfx1cos(0)22cosXfxn维函数f(X)在X(0)点沿d方向的方向导数:(0)(0)(0)(0)(0)12112cosccooscossnniiinXXXXXfffdxxfxfx§2.1多元函数的导数与梯度x1x2x3x2(0)x1(0)x3(0)0X(0)θ2θ1dθ3二、梯度对于二维函数f(X)在X(0)点处的梯度:(0)(0)12,TXfxfxfXxx设12coscosd为d方向的单位向量，则有(0)(0)(0)(0)1212coscosTXXXffffXddxx§2.1多元函数的导数与梯度投影形式：(0)(0)TXffXdd(0)cos,fXfd§2.1多元函数的导数与梯度cos,1fd方向导数最大值发生在:结论:d方向取梯度方向时,函数值的变化率最大。可见梯度方向是函数值变化最大的方向§2.1多元函数的导数与梯度(0)0Xfdcos,0fdx1x20-▽f(X(0))▽f(X(0))最速上升方向最速下降方向下降方向上升方向d:等值线的切线方向，X(0)函数值变化率为零的方向(0)cos,fXfd进一步推导到n维:(0)(0)12,,...nTXffffXxxx沿d方向的方向向量即(0)(0)TXffXdd(0)cos,fXfd12coscos...cosnd§2.1多元函数的导数与梯度梯度重要性质：①梯度是X(0)点处最大的方向导数；②梯度方向是过点的等值线的法线方向；③梯度是X(0)点处的局部性质；④梯度指向函数变化率最大的方向；⑤正梯度方向是函数值最速上升的方向，负梯度方向是函数值最速下降的方向。§2.1多元函数的导数与梯度x1x20X(0)▽f(X(0))-▽f(X(0))最速上升方向最速下降方向下降方向上升方向变化率为零的方向例:求函数f(X)=x12+x22-4x1+4在点[3,2]T的梯度。112224()2fxxfXxfx(0)1(0)2242()24XxfXx在点X(0)=[3,2]T处的梯度为：解：§2.1多元函数的导数与梯度12121264,42fXfXxxxxxx1212112(0)0121021644422xxxxfXxxxfXxxfXx例：试求目标函数f(X)=3x12-4x1x2+x22在点X(0)=[0,1]T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。函数在X(0)=[0,1]T处的最速下降方向是解：由于§2.1多元函数的导数与梯度(1)(0)225505511151555XXe(0)(0)224252514255fXefX(0)(1)2211222634|255XfXxxxx新点是这个方向上的单位向量是：§2.1多元函数的导数与梯度§2.2多元函数的泰勒展开0'0''0212fxfxfxxfxx一元函数泰勒展开:(0)(0)(0)(0)121212122221122221122(0)(0)(0),2XXXXXfffxxfxxxxxxfffxxxxxxxx，二元函数泰勒展开:§2.2多元函数的泰勒展开(0)(0)TT(0)121,()()2fxxfXfXXXGXX二元函数泰勒展开矩阵形式:其中:称为海赛（Hessian）矩阵(0)222112(0)222212()XffxxxGXffxxx§2.2多元函数的泰勒展开(0)(0)TT(0)1()()()2fXfXfXXxGXXn元函数泰勒展开矩阵形式:2222112122222122(0)222212(0)()nnnnnXfffxxxxxfffxxxxxGXfffxxxxx§2.3无约束优化问题的极值条件'0fX一元函数极值条件:''0fX必要条件极小值''0fX极大值''0fX偶次阶导数不为零为极值点奇次阶导数不为零为拐点§2.3无约束优化问题的极值条件120ffxx二元函数极值必要条件:()0fX即:二元函数极值充分条件:海塞矩阵各阶主子式均大于零。2210fx2221122222120ffxxxffxxx§2.3无约束优化问题的极值条件求函数f(X)=x12+x22-4x1-2x2+5的极值解：1）根据极值的必要条件求驻点112224()22fxxfxxfx0(0)(0)1(0)221xXx222112(0)22221220()02ffxxxGXffxxx(0)22120Xfx(0)20()4002GX2）利用海塞矩阵判断驻点是否为极值点§2.3无约束优化问题的极值条件一阶主子式：二阶主子式：(0)21X为极值点，f(X(0))=0为极值2122(0)222211222221222212(0)()0nnnnnXfxxfxxGXfffxffxxxxffxxxxxx2212122222122(0)222221221(0)()0nnnnnXffxxxxfffxxxxxGXfffxxxxfxx§2.3无约束优化问题的极值条件n元函数极值充分条件:海塞矩阵为正定。2222112122222122(0)222212(0)()0nnnnnXfffxxxxxfffxxxxxGXfffxxxxx函数f(X)在X*附近的一切X均满足不等式*fXfX函数f(X)在X*处取得局部极小值，称X*为局部极小点。而优化问题一般是要求目标函数在某一区域内的全局极小点。§2.4凸集、凸函数与凸规划一、凸集一个点集（或区域），如果连接其中任意两点的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。§2.4凸集、凸函数与凸规划x1x20凸集非凸集x1x2yx2x1x1x20y凸集性质:1)凸集乘一个实数后依然是凸集2)两个凸集的和依然是凸集3)两个凸集的交集还是凸集§2.4凸集、凸函数与凸规划0A2AA+BAB0AB二、凸函数x1、x2为凸集域内的任意两点，如存在不等式：§2.4凸集、凸函数与凸规划121211fxxfxfx称f(x)是定义在凸集上的一个凸函数。x1x2xab121fxfx（）121fxx0xf(x)三、凸性条件1.一阶导数判断21211Tfxfxxxfx2.二阶导数（Hessian矩阵)判断§2.4凸集、凸函数与凸规划Hessian矩阵G(X)在R上处处半正定。主子式0时矩阵正定主子式≥0时矩阵半正定主子式＜0时矩阵负定主子式≤0时矩阵半负定四、凸规划对于约束优化问题minfX..st0jgX1,2,...,jm若，fXjgX都为凸函数，则此问题为凸规划。§2.4凸集、凸函数与凸规划凸规划的任何局部最优解就是全局最优解等式约束优化形式：求解消元法拉格朗日乘子法minfX..st0khX1,2,...,kl§2.5等式约束优化极值条件1.消元法（降维法）§2.5等式约束优化极值条件12min,,nfxxx..st12,,0knhxxx1,2,...,kl降维处理：1112221212,,,,,,llnllnllllnxxxxxxxxxxxx1.消元法（降维法）§2.5等式约束优化极值条件2123min23fXxxx..st120xx降维处理：12xx方法直观易理解，但是实际操作很困难2223min23fXxxx变为无约束优化问题：2、拉格朗日乘子法（升维法）改造后优化模型：§2.5等式约束优化极值条件原优化模型：1,lkkkFXfXhX拉格朗日函数待定系数minfX..st0khX1,2,...,kl2、拉格朗日乘子法（升维法）§2.5等式约束优化极值条件1,lkkkFXfXhX0(1,2,)iFinx0(1,2,)kFkln+l个方程n+l个未知变量例:用拉格朗日乘子法求下列问题的最优解2212121212min()60104..()80fXxxxxxxsthXxx2212121212(,)()()60104(8)LXfXhXxxxxxxxx1211020Lxxx解构造拉格朗日函数1280Lxx212420Lxxx令▽L=0,得到求解得：****12533()17xxfX一、一元函数在给定区间上的极值条件§2.6不等式优化极值条件minfX..st10gXax20gXxb引入松弛变量a1,b1，将不等式约束变成等式约束。2211111,0hXagXaaxa