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

1、 是以是以数学规划论数学规划论为理论基础，以为理论基础，以计算机计算机为工具的一为工具的一种现代设计方法。种现代设计方法。大多是多变量有约束的非线性规大多是多变量有约束的非线性规划问题，其划问题，其是是求解多变量非线性函数的极值问题求解多变量非线性函数的极值问题。因此，因此，将介绍与此有关的一些将介绍与此有关的一些。主要介绍主要介绍的内容如下的内容如下： 二次型与正定矩阵二次型与正定矩阵 函数的方向导数与梯度函数的方向导数与梯度 函数的泰勒近似展开式和黑塞矩阵函数的泰勒近似展开式和黑塞矩阵 无约束优化问题的极值条件无约束优化问题的极值条件 凸函数与凸规划凸函数与凸规划 约束优化问题的极值条件约

2、束优化问题的极值条件2.1 二次型与正定矩阵二次型与正定矩阵在介绍在介绍优化方法优化方法时，常常是将时，常常是将二次型函数二次型函数作为对象。其原因除了作为对象。其原因除了二次型函数二次型函数在工程优化问题中有在工程优化问题中有较多的应用较多的应用且且比较简单比较简单之外，还因为之外，还因为任何一个任何一个复杂的多元函数复杂的多元函数都可采用都可采用泰勒二次展开式泰勒二次展开式做局部逼近做局部逼近，使，使复复杂函数杂函数简化为简化为二次函数二次函数。因此，需要讨论有关。因此，需要讨论有关二次型函数二次型函数的问题。的问题。 1. 二次型函数二次型函数所谓所谓二次型函数二次型函数是指含有是指含有

3、 n 个实变量个实变量 x1，x2，xn的一个二次的一个二次齐次多项式函数齐次多项式函数，其，其表达式表达式为为2211 112 1 21121 2 1222222112211() nnnnnnnnnnnnnijijijf Xa xa x xa x xa x xa xa x xa x xa x xa xa x x（2-1）式中，式中，aij (i，j = 1, 2, , n)给定的实常数，称为给定的实常数，称为二次型的系数二次型的系数。111 11221221 122221 12211121212221212()()() () , nnnnnnnnnnnininnnnnif Xx a xa x

4、a xx a xa xa xx a xa xa xaaaxaaaxx xxaaax ,iiixxXx 111212122212 nnnnnnaaaaaaAaaa()Tf XX AX则则式式(2-2a)可简记为可简记为 (2-2a)若令若令(2-2b)，可写成矩阵形式，可写成矩阵形式式中，式中，矩阵矩阵A 是由函数是由函数 f (X) 中中各项所含系数所组成的各项所含系数所组成的 nn 阶矩阵阶矩阵。若式中若式中 aij = aji ( i, j = 1, 2, , n)为为常系数常系数，则称，则称式式(2-1)和和式式(2-2a)为为二次型函数二次型函数或简称或简称实二次型实二次型。A 称为称

5、为二次型矩阵二次型矩阵，因为，因为 aij = aji ，所以，所以 A =AT，称为，称为对称矩阵对称矩阵，因此因此。 在采用在采用泰勒二次近似展开式泰勒二次近似展开式讨论讨论函数的极值函数的极值时，常要分析时，常要分析二次型二次型函数函数是否是否正定正定或或负定负定。二次型的正定与负定的定义二次型的正定与负定的定义简述如下：简述如下：2. 正定矩阵正定矩阵如果对于如果对于任意的非零向量任意的非零向量 X = x1, x2, ，xnT，即，即x1，x2，xn不全为零，不全为零，若有若有 XTAX 0，则称，则称此二次型此二次型 f (X)=XTAX 是正定二次是正定二次 型型，其对应的其对应

6、的矩阵矩阵A 称为称为正定矩阵正定矩阵；若有若有 XTAX 0，则称，则称此二次型此二次型 f (X) = XTAX 为半正定二次型为半正定二次型，并称，并称其相应的其相应的矩阵矩阵A为为半正定矩阵半正定矩阵；若有若有XTAX 0，则点为，则点为极小点极小点；若；若 0 f Xf Xf x xf xx若若 f (x1, x2) 在点在点 处处取得极小值取得极小值，则要求在点附，则要求在点附近的一切近的一切 X 均均满足条件满足条件(*)(*)(*)12,TXxx依据依据这一条件这一条件，应有，应有 (*)(*)(*)(*)1()()()() 2Tf Xf XXXH XXX此时，此时，X(*)为

7、极小点为极小点。为使。为使上式成立上式成立，根据，根据二次型的理论二次型的理论可知，只要可知，只要函数的二阶偏导数矩阵函数的二阶偏导数矩阵 （即即黑塞矩阵黑塞矩阵H(X(*)）必须是）必须是正定正定矩阵矩阵。 2(*)()f X由此可得，由此可得，二元函数二元函数 f (x1,x2) 在在点点 X(*) 取得取得极小值极小值的的充分条件充分条件是：是：函数函数 f (x1,x2) 在点在点 X(*) 处的二阶导数矩阵（即黑塞矩阵处的二阶导数矩阵（即黑塞矩阵H(X(*)）为）为正定正定。同理，同理，函数函数在在 X(*) 处取得处取得极大值极大值的的充分条件充分条件是：是：函数函数 f (x1,

8、x2) 在点在点 X(*) 处的黑塞矩阵处的黑塞矩阵 H(X(*) 为为负定负定。 TnxxxX(*)(*)2(*)1(*),上述结论上述结论可推广至可推广至多元函数的极值问题多元函数的极值问题。即多元函数即多元函数 f (x1，x2，xn) 在点在点 取得取得极极小值的充分必要条件小值的充分必要条件是：是：函数函数 f (X) 在该点的在该点的梯度为零梯度为零，二阶偏导数矩阵二阶偏导数矩阵（即（即黑塞矩阵黑塞矩阵H(X(*)）为正定为正定，即，即0)(*)Xf（2-17）（2-18）H(X(*)正定正定TnxxxX(*)(*)2(*)1(*),同理，多元函数同理，多元函数 f (x1，x2，

9、xn) 在点在点取得取得极大值的极大值的是：是：函数函数 f (X)在该点在该点的的梯度为零梯度为零，二阶偏导数矩阵为负定二阶偏导数矩阵为负定。 由于由于一个函数的极小点一个函数的极小点(局部极值点）局部极值点）并不是唯一的，而并不是唯一的，而优化问题优化问题总是期望能获得总是期望能获得函数的全域最小点（全域极值点）函数的全域最小点（全域极值点）。为此，就需知在。为此，就需知在什么情况下什么情况下所获得的所获得的极小点极小点就是就是全域最小点全域最小点，这就涉及到，这就涉及到凸集凸集、凸函凸函数数与与凸规划问题凸规划问题。2.5 凸函数与凸规划凸函数与凸规划1. 凸集凸集设设 D 为为 n 维

10、欧氏空间维欧氏空间Rn中的中的一个集合一个集合。如果在。如果在D内内任取两任取两点点X (1)和和X (2)，其连线上的，其连线上的所有点均在所有点均在D内，则称内，则称这种集合这种集合D为为 n 维欧氏空维欧氏空间间Rn 的的一个凸集一个凸集。图图2-5(a)、(c)是是二维空间的一个凸集二维空间的一个凸集；图图2-5 (b)是是非凸集非凸集。图图2-5 凸集与非凸集凸集与非凸集 X (1)、X (2)两点之间的两点之间的连线连线，可用，可用数学式数学式表达为表达为（2-19）(1)(2)(1)XXXD式中，式中，为由为由01(01)间的间的任意实数任意实数。即对。即对0，1上一切上一切值得

11、到的值得到的点点 X 的全体组成的全体组成X (1)、X (2) 点点 的连线的连线。则则凸集凸集的数学定义式的数学定义式为为X (1)，X (2) DX =X (1) + (1一一) X (2) D，01且且凸函数凸函数的数学定义的数学定义如下：如下：设设 f (X)为定义在凸集为定义在凸集D上的一个函数，上的一个函数，X (1)、X (2) 为为D 上的任意上的任意两点，若对于任意实数两点，若对于任意实数(01)恒有恒有2. 凸函数凸函数(1)(2)(1)(2)(1)()(1) ()fXXf Xf X（2-20）则称则称 f (X)为为凸集凸集D上的上的凸函数凸函数。若若式式(2-20)中

12、的中的 “” 为为 “”，则称，则称 f (X)为为严格凸函数严格凸函数；若若式式(2-20)中不等号反向，即中不等号反向，即 “” 为为 “” ，则称，则称 f (X)为为D上的上的凹凹函数函数。 凸函数凸函数的的几何意义几何意义可用可用一元函数一元函数情形说明，如情形说明，如图图2-6所示，若所示，若函数函数 f (X)在区间在区间a, b内为内为凸函数凸函数，则，则函数函数 f (X)曲线上任意两点所连的直线曲线上任意两点所连的直线不会落在不会落在曲线弧线曲线弧线以下。以下。图图2-6 凸函数的几何意义凸函数的几何意义：(1)设设 f (X)为定义在为定义在凸集凸集D上的一个上的一个凸函

13、数凸函数，则对于，则对于任意实数任意实数( 0)，则，则函数函数 f (X)在在凸集凸集上也是上也是凸函数凸函数；(2)设设 f1(X)和和 f2(X)为定义在为定义在凸集凸集D上的上的两个凸函数两个凸函数，则，则 f1(X)和和 f2(X)的的线性组合函数线性组合函数 f(X) = f1(X) + f2(X)在在D上也是上也是凸函数凸函数； (3)若若 f(X)为定义在为定义在凸集凸集D上的上的函数函数，且存在连续二阶导数，则，且存在连续二阶导数，则 f(X)为为D上的上的凸函数的充要条件凸函数的充要条件是：是： f (X)的的黑塞矩阵黑塞矩阵H(X)处处是半正处处是半正定定的。若的。若黑塞

14、矩阵黑塞矩阵H(X)对一切对一切XD都都正定正定，则，则 f(X)是是D上的上的严格凸函严格凸函数数。利用以上性质利用以上性质，就，就可以判别可以判别。如果如果 f(X)是凸集是凸集D上的上的凸函数凸函数，并且在，并且在D内有内有极小点极小点，则，则极小极小点是唯一的点是唯一的。3. 凸规划凸规划对于约束优化问题对于约束优化问题min f (X) XRns.t. gu (X) 0,u = 1, 2, , m如果如果目标函数目标函数 f(X)和和所有的不等式约束所有的不等式约束gu(X)0（u =1,2, m）均为）均为凸凸函数函数，则称，则称此约束优化问题此约束优化问题为为凸规划凸规划。并需指

15、出的是，如果不等式约。并需指出的是，如果不等式约束的形式为束的形式为gu(X)0，则，则 gu (X)（u =1,2, m）应为）应为凹函数凹函数。为：为：凸规划的任何局部极小解一定是凸规划的任何局部极小解一定是全域最优解全域最优解。 因此，对于因此，对于凸规划问题凸规划问题，只要求出，只要求出一个局部极小解一个局部极小解，它就是全域它就是全域最优解最优解。 所以，所以，优化理论与方法优化理论与方法常限于讨论常限于讨论。需要指出的是需要指出的是，实际工程优化问题实际工程优化问题往往往往不是凸规划问题不是凸规划问题。所以，采用所以，采用常用的优化方法常用的优化方法，求得的最优解求得的最优解往往是

16、往往是局部最优解局部最优解。而且，对于一个复杂的工程优化问题，往往而且，对于一个复杂的工程优化问题，往往难以判断难以判断其是否为凸规划其是否为凸规划问题。问题。为此，在采用为此，在采用迭代方法求解迭代方法求解时，常从时，常从多个初始点多个初始点出发，进行不同出发，进行不同的迭代，以求得多个局部极小点，然后比较这些局部极小点，最后得的迭代，以求得多个局部极小点，然后比较这些局部极小点，最后得到一个到一个近似全域极小点近似全域极小点，作为该，作为该问题的最优解问题的最优解。2.6 约束优化问题的极值条件约束优化问题的极值条件求解求解约束优化问题约束优化问题min(), . . ()0 (1,2,)

17、 ()0 (1,2, )nuvf XXRst gXumh Xvp的实质的实质就是在所有的就是在所有的约束条件约束条件所形成的所形成的可行域内可行域内，求得，求得目标函数的目标函数的，即，即。因而因而约束优化问题约束优化问题比比无约束优化问题无约束优化问题更为复杂。更为复杂。约束优化问题的约束优化问题的极值点极值点可能出现可能出现两种情况两种情况：一种一种是如是如图图2-7(a)所示，即所示，即目标函数目标函数的的极值点极值点X * 处于处于可行域可行域 D之之内内，故，故目标函数的极值点目标函数的极值点X *即为即为该约束优化问题的该约束优化问题的极值点极值点；另一种另一种如如图图2-7(b)

18、所示，即某约束边界所示，即某约束边界 g i (X) = 0 将将目标函数的自目标函数的自然极值点然极值点隔到隔到可行域可行域 D之外之外，因此这时，因此这时约束优化问题的极值点约束优化问题的极值点不是不是目目标函数的标函数的自然极值点自然极值点，而是，而是该约束边界该约束边界g i (X) = 0 与与目标函数等值线的目标函数等值线的切点切点X *。 图图2-7 约束优化问题极值点约束优化问题极值点(a)极值点在可行域内极值点在可行域内 (b)极值点在可行域的边界上极值点在可行域的边界上 min (). . ()0 (1,2, )vf Xst h Xvp1(, )()()pvvvL Xf X

19、h X由由高等数学高等数学可知，对于可知，对于等式约束等式约束优化问题优化问题可建立如下可建立如下拉格朗日函数拉格朗日函数 (2-21)(2-22)12,Tn *(, )0L X*1()()0 (1,2, ,; )pvvvvf Xh Xvp pn不全为零式中，式中， 为为拉格朗日乘子向量拉格朗日乘子向量。令。令 ，得，得(2-23)式式(2-23)就是就是等式约束问等式约束问题在点题在点 X * 取得极值的取得极值的必要条必要条件件。式式(2-23)的的几何意义几何意义可以可以解释解释为：在等式约束的极值为：在等式约束的极值点上，目标函数的负梯度等点上，目标函数的负梯度等于诸约束函数梯度的线性

20、组于诸约束函数梯度的线性组合。合。如如图图2-8所示，在两个等所示，在两个等式约束的交线式约束的交线 E上的上的点点X *，约束函数的梯度与目标函数约束函数的梯度与目标函数的梯度共面，因此的梯度共面，因此，故，故X *就是就是极值点极值点。图图2-8等式约束问题的极值条件等式约束问题的极值条件 min (). . ()0 (1,2,)uf Xst gXum0(1,2,)n uxum2min (). . ()0 (1,2,)un uf Xst gXxum21(, ,)()()muun uuL XXf XgXx对于对于不等式约束不等式约束优化问题优化问题引入引入 m个个松弛变量松弛变量，可将上面的

21、，可将上面的不等式约束不等式约束优化问题优化问题变成变成(2-24)(2-25)建立建立这一问题这一问题的的拉格朗日函数拉格朗日函数式中，式中， 为为松弛变量组成的松弛变量组成的向量向量。12,Tnnn mXxxx(, , )0L XX12()()0()020 (1,2,)muuuun uuun un uLf XgXXLgXxLxumx 则有则有(2-26)0u0n ux()0ugX ()0ugX 式中，当式中，当 时有时有 和和 ，这说明点，这说明点 X 在约束边界在约束边界上，上， 为点为点 X 的的起作用约束起作用约束。 注意到注意到约束条件约束条件为为 “” 的形式，可知约束函数的梯度

22、方向指的形式，可知约束函数的梯度方向指向可行域外，为满足向可行域外，为满足 ， 必须必须大于零大于零；而当；而当 时，有时，有 和和 ，这说明，这说明点点 X 在在可行域内可行域内。 0LX， u0u0n ux()0ugX 令令该拉格朗日函数的该拉格朗日函数的梯度等于零梯度等于零，即使，即使()0()ikg XiI*()()0 0 ()kiii Iikf Xg XiI设设 为点为点 X * 的的 n 个起作用约束个起作用约束，且，且 X * 是极值是极值点，则由点，则由式式(2-26)及其分析可知，必有及其分析可知，必有（2-27）*()0f X0i式式(2-27)就是就是不等式约束优化问题的

23、不等式约束优化问题的极值条件极值条件，称，称Kuhn-Tucker条件条件，简称，简称 K-T条件条件。该条件表明该条件表明，若，若设计点设计点 X *是是函数函数 f (X)的极值点的极值点，要么，要么 （ 如如图图2-9所示，此时所示，此时 ），要么），要么目标函数的负梯度目标函数的负梯度位于诸起作位于诸起作用约束梯度所构成的用约束梯度所构成的夹角夹角或或锥体之内锥体之内。 *()f X*()ig X0i也就是说也就是说，目标函数的负梯度，目标函数的负梯度等于诸起作用约束梯等于诸起作用约束梯度度 的的 非负线性组合（如非负线性组合（如图图2-10所示，此时所示，此时 ）。）。 图图2-9极值点处目标函数极值点处目标函数 图图2-10极值点处目标函数极值点处目标函数 的梯度为零的梯度为零 的梯度不为零的梯度不为零应该指出应该指出，K-T 条件条件是是多元函数取得约束极值的必要条件多元函数取得约束极值的必要条件，既，既可以用来作为可以用来作为约束极值点的判别条件约束极值点的判别条件，又可以用来直接，又可以用来直接求解比较简求解比较简单的约束优化问题单的约束优化问题。但但 K-T条件条件不是不是多元函数取得约束极值的充分条件多元函数取得约束极值的充分条件。只有当目。只有