机械优化设计-第二章优化设计的数学基础

1、机械优化设计第二章第二章 优化设计的数学基础优化设计的数学基础一、多元函数的方向导数和梯度一、多元函数的方向导数和梯度二、多元函数的泰勒展开二、多元函数的泰勒展开三、无约束优化问题的极值条件三、无约束优化问题的极值条件四、凸集、凸函数与凸规划四、凸集、凸函数与凸规划五、等式约束优化问题的极值条件五、等式约束优化问题的极值条件六、不等式约束优化问题的极值条件六、不等式约束优化问题的极值条件机械优化设计1 1、方向导数、方向导数01020,xxx 二元函数在点处的偏导数偏导数的定义是：10101201020011(,),limxxf xx xfxxfxx20102021020022(,),limx

2、xf xxxfxxfxx 01020,xxx二元函数在点处沿某一方向 d的变化率，其定义为 010120210200(,),limdxf xx xxf xxfdd 方向导数方向导数 一、多元函数的方向导数和梯度一、多元函数的方向导数和梯度),(21xxf),(21xxf机械优化设计X1X10X20X2X0X1X2d21Od图图1 1 二维空间中的方向二维空间中的方向= 010120210200(,),limdxf xx xxf xxfdd 011cosxfx022cosxfx+偏导数与偏导数与方向导数方向导数的关系的关系机械优化设计n n元函数在点元函数在点x x0 0处沿处沿d d方向的方向

3、导数方向的方向导数inixinxxxxxfxfxfxfdfncoscoscoscos1122110000机械优化设计2 2、二元函数的梯度、二元函数的梯度000011221212coscos+ cos,cosxxxxfffffdxxxx0010122(),Txxfxfff xfxxx令 梯度梯度000()() cos(, )Txff xdf xf dd 21coscosd机械优化设计 当梯度方向和当梯度方向和d d方向重合时，方向导数值方向重合时，方向导数值最大，即梯度方向是函数值变化最快方向，最大，即梯度方向是函数值变化最快方向，而梯度的模就是函数值变化率的最大值。而梯度的模就是函数值变化率

4、的最大值。000()() cos(, )Txff xdf xf dd 22210)(xfxfxf梯度的模：梯度的模：机械优化设计多元函数的梯度多元函数的梯度Txnxnxfxfxfxfxfxfxf0021210)(),cos()()(cos00100dfxfdxfxfdfTinixix机械优化设计2/1210)()(0 xniixfxf多元函数的梯度的模：多元函数的梯度的模： 函数的梯度方向函数的梯度方向与函数的等值面相垂直与函数的等值面相垂直，也，也就是和等值面上过就是和等值面上过x0 x0的一切曲线相垂直。的一切曲线相垂直。 由于梯度的模因点而异，即函数在不同点处由于梯度的模因点而异，即函数

5、在不同点处的最大变化率是不同的。因此，梯度是函数的一的最大变化率是不同的。因此，梯度是函数的一种种局部性质局部性质。机械优化设计梯度的两个重要性质：梯度的两个重要性质： 函数在某点的函数在某点的梯度不为零，则必与过该点的等值面垂直梯度不为零，则必与过该点的等值面垂直（即为过点的等值线的法线方向）；（即为过点的等值线的法线方向）； 梯度方向具有最大变化率方向梯度方向具有最大变化率方向 正梯度方向是函数值最速上升的方向，正梯度方向是函数值最速上升的方向， 负梯度方向是函数值最速下降的方向负梯度方向是函数值最速下降的方向。机械优化设计2121242)(xxxfxfxf42242)(211xxxf例例

6、1 1：求二次函数求二次函数44,1222121xxxxxfT2 , 3在点在点处的梯度。处的梯度。 解：解：在点在点T2 , 3处的梯度为：处的梯度为：机械优化设计例例2 2：试试求二次函数求二次函数2221212143,xxxxxxfTx1 , 00在点在点处的最速下降方向，并求沿这个方向移动一个单位长处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。度后新点的目标函数值。 解：解：21146xxxf21224xxxf242446)(102121102102121xxxxxxxxxfxfxfPTx 1 , 00则函数在则函数在 处的最速下降方向为处的最速下降方向为机械优化

7、设计该方向上的单位向量为该方向上的单位向量为551552)2(424)()(2200 xfxfe55115525515521001exx1x新点新点5252643)(12221211xxxxxxf该点函数值该点函数值机械优化设计常用梯度公式：常用梯度公式：QXXfQXXXfQXXfXXXfbXfXbXfXfCXfTTT2)()()4(2)()() 3()()()2(0)()()() 1 (为对称矩阵，常数注意：梯度为向量注意：梯度为向量二次型二次型机械优化设计二、多元函数的泰勒展开二、多元函数的泰勒展开 f x0 xx在在 点处的泰勒展开为：点处的泰勒展开为： 200012f xf xfxxf

8、xx 其中其中2200,xxxxxx 1、一元函数一元函数机械优化设计2 2、二元函数、二元函数11102220,xxxxxx其中：其中：.2! 21),(,222222121221212221120102100000 xxfxxxxfxxfxxfxxfxxfxxfxxxxx二元函数二元函数 在在 点处的泰勒展开式为：点处的泰勒展开式为：)(xf),(20100 xxx机械优化设计上式写成矩阵形式：上式写成矩阵形式：2122221221221221212100021)()(xxxfxxfxxfxfxxxxxfxfxfxfxx机械优化设计02221222122120)(xxfxxfxxfxfxG

9、令令 xxGxxxfxfxfTT0002121xxx 0 xG21,xxf上式可写成上式可写成称为函数称为函数 在在 点处的点处的海赛（海赛（Hessian）矩阵）矩阵),(20100 xxx参见教材例题参见教材例题P30机械优化设计海赛矩阵海赛矩阵是由函数是由函数 在点在点 处的二阶偏处的二阶偏导数组成的方阵。由于函数的二次连续性，有：导数组成的方阵。由于函数的二次连续性，有：),(21xxf0 x212122xxfxxf)(0 xG2221222122120)(xfxxfxxfxfxG所以所以 矩阵为矩阵为对阵方阵。对阵方阵。机械优化设计海赛矩阵海赛矩阵222212222221221221

10、22120)(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxG3 3、多元函数、多元函数 xxGxxxfxfxfTT00021其中：梯度其中：梯度Txnxfxfxfxf0210)(泰勒展开式泰勒展开式机械优化设计若将函数的泰勒展开式只取到线性项，即取若将函数的泰勒展开式只取到线性项，即取 )(000 xxxfxfxzT xz0 x则则 是过点是过点 和函数和函数 所代表的超曲面相所代表的超曲面相切的切平面。切的切平面。 xf若将函数的泰勒展开式取到二次项时，则得到二若将函数的泰勒展开式取到二次项时，则得到二次函数形式，在线性代数中将二次齐次函数称为次函数形式，在线性代数中将二次齐

11、次函数称为二次型。二次型。矩阵形式矩阵形式 GxxxfTG-对称矩阵对称矩阵机械优化设计当对任何非零向量当对任何非零向量x x使使 0GxxxfT则二次型函数正定，则二次型函数正定，G G为正定矩阵。为正定矩阵。机械优化设计海赛矩阵的特征：是实对称矩阵。海赛矩阵的特征：是实对称矩阵。0)det(G0)det(G0)det(G4 4、海赛矩阵与正定、海赛矩阵与正定矩阵矩阵正定正定的充要条件：矩阵的充要条件：矩阵G的各阶顺序主子式为正，即的各阶顺序主子式为正，即矩阵矩阵负定负定的充要条件：矩阵的充要条件：矩阵G G的的奇数阶主子式奇数阶主子式主子式主子式偶数阶主子式偶数阶主子式海赛矩阵的正定性：海

12、赛矩阵的正定性：)(xG正定正定- 为全局极小值点的充分条件为全局极小值点的充分条件x)(xG负定负定- 为全局极大值点的充分条件为全局极大值点的充分条件x机械优化设计例例3 3 判定矩阵判定矩阵 是否正定？是否正定？010401023136032336066解：解：该对称矩阵的三个主子式依次为：该对称矩阵的三个主子式依次为：401023136G故可知矩阵故可知矩阵G是正定的。是正定的。机械优化设计定理：定理：若二次函数若二次函数 中中Q Q正定，正定，则它的等值面是同心椭球面族，且中心为则它的等值面是同心椭球面族，且中心为cbXQXXXfT21)(bQX1证明：证明：作变换作变换 ，代入二次

13、函数式中：，代入二次函数式中：bQYX1cbQYbbQYQbQYT)()()(21111)()(1bQYfYcbQbQYYTT12121QYYT210YbQX1结论：结论：Q为正定矩阵的二次型为正定矩阵的二次型 的等值面是以的等值面是以 的同心椭球面族。原二次函数就是以的同心椭球面族。原二次函数就是以 为中心的同心为中心的同心椭球面族，椭圆中心为极小值点。椭球面族，椭圆中心为极小值点。机械优化设计例例4 把二次函数把二次函数 化为矩阵向量形式并检验化为矩阵向量形式并检验Q是否正定，如正定，试用公式是否正定，如正定，试用公式 求这个函数的极小点。求这个函数的极小点。bQX121312123222

14、132154323),(xxxxxxxxxxxxf32132132133323123222113121132121xxxbbbxxxgggggggggxxxXbQXXxxxfTT21),(321TbQX7 . 07 . 68 . 21054b401023136Q解：解：与题中函数比较各系数得：与题中函数比较各系数得：由计算知由计算知Q Q正定，极小点正定，极小点机械优化设计三、无约束优化问题的极值条件三、无约束优化问题的极值条件1 1、一元函数、一元函数 f x0 xx对于可微的一元函数对于可微的一元函数 判断在判断在 处是否取得极处是否取得极值的过程：值的过程： 00fx00fx则则 为极小

15、点。为极小点。0 x00fx0 x00fx逐次检验其更高阶导数逐次检验其更高阶导数的符号，开始不为零的的符号，开始不为零的导数阶数若为偶次，则导数阶数若为偶次，则为极值点，若为奇次，为极值点，若为奇次，则为拐点。则为拐点。 则则 为极大点。为极大点。机械优化设计2 2、二元函数、二元函数 01020,xxx定理定理1：若二元可微函数若二元可微函数 在在 处处取得极值的取得极值的必要条件必要条件是：是：),(21xxf00021xxxfxf即即0)(0 xf凡满足上式的点称为函数的凡满足上式的点称为函数的驻点驻点（零向量）（零向量）机械优化设计如下图所示的二元函数，在如下图所示的二元函数，在M0

16、点虽有点虽有 和和 是个驻点，但它不是极值点。是个驻点，但它不是极值点。 0 xf0yf机械优化设计01020,xxx定理定理2：若二元可微函数若二元可微函数 在在 的的某个邻域取得极小值的某个邻域取得极小值的充分条件充分条件是要求在该点附是要求在该点附近的一切点均满足：近的一切点均满足：),(21xxf0),(),(201021xxfxxf若函数存在连续的一阶及二阶偏导数，当满足若函数存在连续的一阶及二阶偏导数，当满足0),(, 0),(2010201021xxfxxfxx则泰勒展开式的函数增量近似式（略三阶以上则泰勒展开式的函数增量近似式（略三阶以上高阶微量）为：高阶微量）为：机械优化设计

17、0),(),(2),(21),(),(2),(21),(),(),(),(222010 212010 212010 222010 212010 212010 220101201020102122212122212121xxxfxxxxfxxxfxxxfxxxxfxxxfxxxfxxxfxxfxxfxxxxxxxxxx),(),(),(2010 2010 2010 222121xxfCxxfBxxfAxxxx令令则则0221222121xCxxBxA0, 0CBBAA可见，函数增量的性态与可见，函数增量的性态与A,B,C的值有关。可以证明，当满的值有关。可以证明，当满足以下条件时，足以下条件时，

18、 为极小值（证明略）。为极小值（证明略）。),(2010 xxf此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。机械优化设计结论：结论： 二元函数在某点取得二元函数在某点取得极小值极小值的的充分条件充分条件是要是要求求该点处的海赛矩阵为正定该点处的海赛矩阵为正定。0()0f x02210 xfx 2221122222120ffxx xG xffx xx 且且 01020,xxx 对于二元函数对于二元函数 在在 处取得极处取得极值的值的充分必要条件充分必要条件是：是：),(21xxf参见教材例题参见教材例题P32P3

19、2 机械优化设计3、多元函数、多元函数对于多元函数对于多元函数 若在若在 处取得处取得极值极值，则，则),(21nxxxfx必要条件：必要条件：充分条件：充分条件：xnnnnnxfxxfxxfxxfxfxxfxxfxxfxfxG2222122222212212212212)(0)(21Txnxfxfxfxf正定正定或负定或负定机械优化设计四、凸集、凸函数与凸规划四、凸集、凸函数与凸规划 当极值点当极值点x x* *能使能使f(xf(x* *) )在整个可行域中为最小值时，即在整个可行域中为最小值时，即在整个可行域中对任一在整个可行域中对任一x x都有都有f(x)=f(xf(x)=f(x* *)

20、,),则则x x* *为为全域最优全域最优点（全域极小点）。点（全域极小点）。若若f(xf(x* *) )为局部可行域中的极小值而非为局部可行域中的极小值而非整个可行域的最小值时，则称整个可行域的最小值时，则称x x* *为为局部最优点或相对最优局部最优点或相对最优点点。优化的目标是全域最优点。为了判断某个极值点是否。优化的目标是全域最优点。为了判断某个极值点是否为全域最优点，研究函数的凸性是必要的。为全域最优点，研究函数的凸性是必要的。 函数的凸性表现为函数的凸性表现为单峰性单峰性。对于具有凸性特点的函数。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优亦是全来说，其极值点

21、只有一个，因而该点既是局部最优亦是全域最优点。域最优点。为了研究函数的凸性，下面引入为了研究函数的凸性，下面引入凸集凸集的概念：的概念：机械优化设计1 1、凸集、凸集12,xR xR01如果对一切如果对一切 及一切满足及一切满足12(1)xxyR的实数的实数 ，点点 则称集合则称集合R为为凸集凸集，否则称为非凸集。，否则称为非凸集。y yx x2 2x x1 1llllxxyx122若若y y是是x x1 1和和x x2 2连线上的点，则有连线上的点，则有整理后即得整理后即得21)1 (xxy机械优化设计凸集的凸集的性质：性质：若若D为凸集，为凸集， 为一个实数，则集合为一个实数，则集合 仍是

22、凸集；仍是凸集；若若D和和F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；任何一组凸集的积（或交）仍是凸集。任何一组凸集的积（或交）仍是凸集。D机械优化设计2 2、凸函数、凸函数 具有凸性（表现为单峰性）或只有唯一的局部具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：峰函数。其数学定义是： 设设f(x)f(x)为定义在为定义在n n维欧式空间中的一个凸集维欧式空间中的一个凸集D D上上的函数，如果对于任何实数的函数，如果对于任何实数 以及对以及对D D中任意两点中任意两点x

23、x1 1，x x2 2恒有：恒有：1212(1)(1)fxxf xf x f x则则 为为D D上的凸函数，若不满足上式，则为上的凸函数，若不满足上式，则为凹函数。凹函数。如式中的等号去掉，则称其为严格凸如式中的等号去掉，则称其为严格凸函数。函数。) 10(机械优化设计 1212(1)(1)fxxf xf x凸函数的凸函数的几何意义几何意义：在函数曲线上取任意两点连：在函数曲线上取任意两点连成一直线段，则该线段上任一点的纵坐标值必大成一直线段，则该线段上任一点的纵坐标值必大于或等于该点处的原函数值。于或等于该点处的原函数值。llxfxfyxf)()()(121)()1 ()(21xfxfyy)

24、(xfx2xx1xof1f2flxxlxx212,机械优化设计凸函数的性质凸函数的性质1）若）若f(x)为定义在凸集为定义在凸集D上的一个凸函数，对于任上的一个凸函数，对于任意实数意实数a0，则，则af(x)也是凸集也是凸集D上的凸函数；上的凸函数；2）定义在凸集）定义在凸集D上的两个凸函数上的两个凸函数f1(x),f2(x)，其和，其和f1(x)+f2(x)亦为该凸集上的一个凸函数；亦为该凸集上的一个凸函数；3）若）若f1(x),f2(x)为定义在凸集为定义在凸集D上的两个凸函数，上的两个凸函数， 为两个任意正数，则为两个任意正数，则 仍为仍为D上上的凸函数。的凸函数。,)()(21xfxf

25、机械优化设计3 3、凸性条件、凸性条件（1）根据一阶导数（函数的梯度）来判断函数的凸性）根据一阶导数（函数的梯度）来判断函数的凸性设设f(x)f(x)为定义在凸集为定义在凸集R R上，且具有连续的一阶导数上，且具有连续的一阶导数的函数，则的函数，则f(x)f(x)在在R R上为凸函数的上为凸函数的充要条件充要条件是对凸是对凸集集R R内任意不同两点内任意不同两点 、 ，下面不等式，下面不等式恒成立。恒成立。1x2x 21211Tf xf xxxf x机械优化设计（2 2）根据二阶导数（海赛矩阵）根据二阶导数（海赛矩阵) )来判断函数的凸性来判断函数的凸性设设f(x)f(x)为定义在凸集为定义在

26、凸集R R上且具有连续二阶导数的函数，则上且具有连续二阶导数的函数，则f(x)f(x)在在R R上为凸函数的上为凸函数的充要条件充要条件为：为：海赛矩阵在海赛矩阵在R R上处处半正定。对于严格的凸函数，其充上处处半正定。对于严格的凸函数，其充要条件为海赛矩阵为正定。要条件为海赛矩阵为正定。当海赛矩阵当海赛矩阵G G的主子式的主子式: : det(G det(G) )0 0时，矩阵正定时，矩阵正定 det(G)0 det(G)0 时，矩阵半正定时，矩阵半正定 det(Gdet(G) )0 0时，矩阵负定时，矩阵负定 det(G)0det(G)0时，矩阵半负定时，矩阵半负定G(xG(x* *) )

27、正定，正定， 是是 x x* * 为全局极小值点的充分条件为全局极小值点的充分条件；G(xG(x* *) )半正定半正定, , 是是 x x* * 为局部极小值点的充分条件；为局部极小值点的充分条件；G(xG(x* *) )负定，负定， 是是 x x* * 为全局极大值点的充分条件；为全局极大值点的充分条件；G(xG(x* *) )半负定半负定, , 是是 x x* * 为局部极大值点的充分条件为局部极大值点的充分条件。说明：说明：机械优化设计4 4、凸规划、凸规划对于约束优化问题对于约束优化问题min fX. .st0jgX (1,2,3,)jm fXjgX(1,2,3,)jm若若、都为凸函

28、数，则称此问题为凸规划。都为凸函数，则称此问题为凸规划。机械优化设计凸规划的性质：凸规划的性质：2 2）可行域）可行域 为凸集。为凸集。 1,2,.,0jjmgxRx3 3）凸规划的任何局部最优解就是全局最优解。）凸规划的任何局部最优解就是全局最优解。1 1）若给定一点）若给定一点 ，则集合，则集合 为凸集。为凸集。 0f xf xRx0 x机械优化设计五、等式约束优化问题的极值条件五、等式约束优化问题的极值条件 min f x. .st 0khx 等式约束优化问题：等式约束优化问题： 求解等式约束化问题的理论基础是导出极值求解等式约束化问题的理论基础是导出极值存在的条件。存在的条件。), 2

29、 , 1(mk机械优化设计1 1、消元法（降维法）、消元法（降维法）2 2、拉格朗日乘子法（升维法）、拉格朗日乘子法（升维法）思想思想: : 通过增加变量将等式约束化问题变成无约通过增加变量将等式约束化问题变成无约束化问题。束化问题。 1,2,)kkl（ 1,lkkkF XfxhX引入引入拉格朗日乘子拉格朗日乘子，并构成一个，并构成一个新的目标函数新的目标函数拉格朗日函数拉格朗日函数拉格朗日乘子拉格朗日乘子新目标函数的极值的新目标函数的极值的必要条件：必要条件：0iFx0kF参见教材例题参见教材例题机械优化设计六、不等式约束优化问题的极值条件六、不等式约束优化问题的极值条件库恩库恩塔克条件（塔

30、克条件（K-TK-T条件）条件） 不等式约束的多元函数极值的必要条件是著名不等式约束的多元函数极值的必要条件是著名的的库恩库恩塔克（塔克（Kuhn-TuckerKuhn-Tucker）条件）条件, ,它是非线性它是非线性优化问题的重要理论。优化问题的重要理论。 为了便于理解库恩为了便于理解库恩塔克条件，首先分析一塔克条件，首先分析一元函数在给定区间的极值条件。元函数在给定区间的极值条件。机械优化设计 min f x. .st 10gxax 20gxxb1 1、一元函数在给定区间上的极值条件、一元函数在给定区间上的极值条件一元函数一元函数f(x)f(x)在区间在区间a,ba,b 的极值问题，可表

31、示为：的极值问题，可表示为：求解思想求解思想: :引入松弛变量使不等式约束变成等式约束，再引入松弛变量使不等式约束变成等式约束，再利用拉格朗日乘子法求解等式约束的极值问题。利用拉格朗日乘子法求解等式约束的极值问题。机械优化设计 2211111,0h x agxaaxa 2221211,0hx bgxbxbb这样可以转化为拉格朗日函数：这样可以转化为拉格朗日函数： 11121 11221221121,()F x a bf xh x ahx bf xaxaxbb 12, 是对应于不等式约束的拉格朗日乘子，是对应于不等式约束的拉格朗日乘子，其值均为非负的。其值均为非负的。 设设 为松弛变量，则上两个

32、不等式可写为松弛变量，则上两个不等式可写为如下两个等式：为如下两个等式：11,ba机械优化设计12120dgdgdfdxdxdx 110gx 220gx1020 f x,a b对于一元函数对于一元函数 在给定区间在给定区间上的极值条件，可完整的表示为：上的极值条件，可完整的表示为：结论：结论：机械优化设计从以上分析可以看出，对应于不起作用的约束的从以上分析可以看出，对应于不起作用的约束的拉格朗日乘子拉格朗日乘子取零值取零值，因此可以引入起作用约束，因此可以引入起作用约束的下标集合。的下标集合。 0,1,2jgxjJ xj一元函数在给定区间的极值条件，可以改写为：一元函数在给定区间的极值条件，可

33、以改写为：极值条件中只考虑起作用的约束和相应的乘子。极值条件中只考虑起作用的约束和相应的乘子。 000jjj JjjdgdfdxdxgxjJjJ机械优化设计2 2、库恩、库恩塔克条件塔克条件10(1,2, )mjjjiif xgxinxx0(1,2,)jjgxjm0(1,2,)jjm 库恩库恩塔克条件（塔克条件（K-T条件）可表述为：条件）可表述为：对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题： min f x. .st), 2 , 1(0)(mjxgj机械优化设计库恩库恩塔克条件表明：塔克条件表明：如点如点 是函数是函数 的极值点，要么的极值点，要么 （此时（此时 ）或者目标函数的负梯度等于起作）或者目标函数的负梯度等于起作用约束梯度的非负线性组合用约束梯度的非负线性组合 （此时（此时 ）。）。 )(xf0)(xfx0ju0ju10(1,2, )mjjjiif xgxinxx0(1,2,)jjgxjm0(1,2,)jjm机械优化