机械优化设计二优化设计的数学基础课件

机械优化设计第二章第二章 优化设计的数学基础优化设计的数学基础一、多元函数的方向导数和梯度一、多元函数的方向导数和梯度二、多元函数的泰勒展开二、多元函数的泰勒展开三、无约束优化问题的极值条件三、无约束优化问题的极值条件四、凸集、凸函数与凸规划四、凸集、凸函数与凸规划五、等式约束优化问题的极值条件五、等式约束优化问题的极值条件六、不等式约束优化问题的极值条件六、不等式约束优化问题的极值条件机械优化设计1 1、方向导数、方向导数 二元函数在点处的偏导数偏导数的定义是：二元函数在点处沿某一方向 的变化率，其定义为 方向导数方向导数 一、多元函数的方向导数和梯度一、多元函数的方向导数和梯度机械优化设计X1X10X20X2X0X1X2d21Od图图1 1 二维空间中的方向二维空间中的方向=+偏导数与偏导数与方向导数方向导数的关系的关系机械优化设计n n元函数在点元函数在点x x0 0处沿处沿d d方向的方向导数方向的方向导数机械优化设计2 2、二元函数的梯度、二元函数的梯度令 梯度梯度机械优化设计 当梯度方向和当梯度方向和d d方向重合时，方向导数值方向重合时，方向导数值最大，即梯度方向是函数值变化最快方向，最大，即梯度方向是函数值变化最快方向，而梯度的模就是函数值变化率的最大值。而梯度的模就是函数值变化率的最大值。梯度的模：梯度的模：机械优化设计多元函数的梯度多元函数的梯度机械优化设计多元函数的梯度的模：多元函数的梯度的模：函数的梯度方向函数的梯度方向与函数的等值面相垂直与函数的等值面相垂直，也，也就是和等值面上过就是和等值面上过x0 x0的一切曲线相垂直。的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一的最大变化率是不同的。因此，梯度是函数的一种种局部性质局部性质。机械优化设计梯度的两个重要性质：梯度的两个重要性质：函数在某点的函数在某点的梯度不为零，则必与过该点的等值面垂直梯度不为零，则必与过该点的等值面垂直（即为过点的等值线的法线方向）；（即为过点的等值线的法线方向）；梯度方向具有最大变化率方向梯度方向具有最大变化率方向 正梯度方向是函数值最速上升的方向，正梯度方向是函数值最速上升的方向，负梯度方向是函数值最速下降的方向负梯度方向是函数值最速下降的方向。机械优化设计例例1 1：求二次函数求二次函数在点在点处的梯度。的梯度。解：解：在点在点处的梯度为：处的梯度为：机械优化设计例例2 2：试试求二次函数求二次函数在点在点处的最速下降方向，并求沿的最速下降方向，并求沿这个方向移个方向移动一个一个单位位长度后新点的目度后新点的目标函数函数值。解：解：则函数在则函数在 处的最速下降方向为处的最速下降方向为机械优化设计该方向上的单位向量为该方向上的单位向量为新点新点该点函数值该点函数值机械优化设计常用梯度公式：常用梯度公式：注意：梯度为向量注意：梯度为向量二次型二次型机械优化设计二、多元函数的泰勒展开二、多元函数的泰勒展开在在 点处的泰勒展开为：点处的泰勒展开为：其中其中1、一元函数一元函数机械优化设计2 2、二元函数、二元函数其中：其中：二元函数二元函数 在在 点处的泰勒展开式为：点处的泰勒展开式为：机械优化设计上式写成矩阵形式：上式写成矩阵形式：机械优化设计令令上式可写成上式可写成称为函数称为函数 在在 点处的点处的海赛（海赛（Hessian）矩阵）矩阵参见教材例题参见教材例题P30机械优化设计海赛矩阵海赛矩阵是由函数是由函数 在点在点 处的二阶偏导处的二阶偏导数组成的方阵。由于函数的二次连续性，有：数组成的方阵。由于函数的二次连续性，有：所以所以 矩阵为矩阵为对阵方阵。对阵方阵。机械优化设计海赛矩阵海赛矩阵3 3、多元函数、多元函数其中：梯度其中：梯度泰勒展开式泰勒展开式机械优化设计若将函数的泰勒展开式只取到线性项，即取若将函数的泰勒展开式只取到线性项，即取则则 是过点是过点 和函数和函数 所代表的超曲面相所代表的超曲面相切的切平面。切的切平面。若将函数的泰勒展开式取到二次项时，则得到二若将函数的泰勒展开式取到二次项时，则得到二次函数形式，在线性代数中将二次齐次函数称为次函数形式，在线性代数中将二次齐次函数称为二次型。二次型。矩阵形式矩阵形式-对称矩阵对称矩阵机械优化设计当对任何非零向量当对任何非零向量x x使使则二次型函数正定，则二次型函数正定，G G为正定矩阵。为正定矩阵。机械优化设计海赛矩阵的特征：是实对称矩阵。海赛矩阵的特征：是实对称矩阵。4 4、海、海赛矩矩阵与正定与正定矩阵矩阵正定正定的充要条件：矩阵的充要条件：矩阵G的各阶顺序主子式为正，即的各阶顺序主子式为正，即矩阵矩阵负定负定的充要条件：矩阵的充要条件：矩阵G G的的奇数阶主子式奇数阶主子式主子式主子式偶数阶主子式偶数阶主子式海赛矩阵的正定性：海赛矩阵的正定性：正定正定-为全局极小值点的充分条件为全局极小值点的充分条件负定负定-为全局极大值点的充分条件为全局极大值点的充分条件机械优化设计例例3 3 判定矩阵判定矩阵 是否正定？是否正定？解：解：该对称矩阵的三个主子式依次为：该对称矩阵的三个主子式依次为：故可知矩阵故可知矩阵G是正定的。是正定的。机械优化设计定理：定理：若二次函数若二次函数 中中Q Q正定，正定，则它的等值面是同心椭球面族，且中心为则它的等值面是同心椭球面族，且中心为证明：证明：作变换作变换 ，代入二次函数式中：，代入二次函数式中：结论：结论：Q为正定矩阵的二次型为正定矩阵的二次型 的等值面是以的等值面是以 的同心椭球面族。原二次函数就是以的同心椭球面族。原二次函数就是以 为中心的同心为中心的同心椭球面族，椭球面族，椭圆中心为极小值点椭圆中心为极小值点。机械优化设计例例4 把二次函数把二次函数 化为矩阵向量形式并检验化为矩阵向量形式并检验Q是否正定，如正定，试用公式是否正定，如正定，试用公式 求这个函数的极小点。求这个函数的极小点。解：解：与题中函数比较各系数得：与题中函数比较各系数得：由计算知由计算知Q Q正定，极小点正定，极小点机械优化设计三、无约束优化问题的极值条件三、无约束优化问题的极值条件1 1、一元函数、一元函数对于可微的一元函数于可微的一元函数 判断在判断在 处是否取得极处是否取得极值的过程：值的过程：则 为极小点。为极小点。逐次检验其更高阶导数的逐次检验其更高阶导数的符号，开始不为零的导数符号，开始不为零的导数阶数若为偶次，则为极值阶数若为偶次，则为极值点，若为奇次，则为拐点。点，若为奇次，则为拐点。则 为极大点。为极大点。机械优化设计2 2、二元函数、二元函数 定理定理1：若二元可微函数若二元可微函数 在在 处处取得极值的取得极值的必要条件必要条件是：是：即即凡满足上式的点称为函数的凡满足上式的点称为函数的驻点驻点（零向量）（零向量）机械优化设计如下图所示的二元函数，在如下图所示的二元函数，在M0点虽有点虽有 和和 是个驻点，但它不是极值点。是个驻点，但它不是极值点。机械优化设计定理定理2：若二元可微函数若二元可微函数 在在 的的某个邻域取得极小值的某个邻域取得极小值的充分条件充分条件是要求在该点附是要求在该点附近的一切点均满足：近的一切点均满足：若函数存在连续的一阶及二阶偏导数，当满足若函数存在连续的一阶及二阶偏导数，当满足则泰勒展开式的函数增量近似式（略三阶以上则泰勒展开式的函数增量近似式（略三阶以上高阶微量）为：高阶微量）为：机械优化设计令令则则可见，函数增量的性态与可见，函数增量的性态与A,B,C的值有关。可以证明，当满的值有关。可以证明，当满足以下条件时，足以下条件时，为极小值（证明略）。为极小值（证明略）。此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。机械优化设计结论：结论：二元函数在某点取得二元函数在某点取得极小值极小值的的充分条件充分条件是要是要求求该点处的海赛矩阵为正定该点处的海赛矩阵为正定。且且 对于二元函数于二元函数 在在 处取得极处取得极值的值的充分必要条件充分必要条件是：是：参见教材例题参见教材例题P32P32 机械优化设计3、多元函数、多元函数对于多元函数于多元函数 若在若在 处取得处取得极值极值，则，则必要条件：必要条件：充分条件：充分条件：正定正定或负定或负定机械优化设计四、凸集、凸函数与凸规划四、凸集、凸函数与凸规划 当极值点当极值点x*x*能使能使f(x*)f(x*)在整个可行域中为最小值时，即在整个可行域中为最小值时，即在整个可行域中对任一在整个可行域中对任一x x都有都有f(x)=f(x*),f(x)=f(x*),则则x*x*为为全域最优全域最优点（全域极小点）。点（全域极小点）。若若f(x*)f(x*)为局部可行域中的极小值而非为局部可行域中的极小值而非整个可行域的最小值时，则称整个可行域的最小值时，则称x*x*为为局部最优点或相对最优局部最优点或相对最优点点。优化的目标是全域最优点。为了判断某个极值点是否。优化的目标是全域最优点。为了判断某个极值点是否为全域最优点，研究函数的凸性是必要的。为全域最优点，研究函数的凸性是必要的。函数的凸性表现为函数的凸性表现为单峰性单峰性。对于具有凸性特点的函数来。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优亦是全域说，其极值点只有一个，因而该点既是局部最优亦是全域最优点。最优点。为了研究函数的凸性，下面引入为了研究函数的凸性，下面引入凸集凸集的概念：的概念：机械优化设计1 1、凸集、凸集如果如果对一切一切 及一切满足及一切满足的的实数数 ，点点 则称集合则称集合为凸集凸集，否，否则称称为非凸集。非凸集。y yx x2 2x x1 1若若y y是是x x1 1和和x x2 2连线上的点，则有连线上的点，则有整理后即得整理后即得机械优化设计凸集的凸集的性质：性质：若若D为凸集，为凸集，为一个实数，则集合为一个实数，则集合 仍是凸集；仍是凸集；若若D和和F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；任何一组凸集的积（或交）仍是凸集。任何一组凸集的积（或交）仍是凸集。机械优化设计2 2、凸函数、凸函数 具有凸性（表现为单峰性）或只有唯一的局部具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：峰函数。其数学定义是：设设f(x)f(x)为定义在为定义在n n维欧式空间中的一个凸集维欧式空间中的一个凸集D D上上的函数，如果对于任何实数的函数，如果对于任何实数 以及对以及对D D中任意两点中任意两点x x1 1，x x2 2恒有：恒有：则则 为为D D上的凸函数，若不满足上式，则为上的凸函数，若不满足上式，则为凹函数。凹函数。如式中的等号去掉，则称其为严格凸如式中的等号去掉，则称其为严格凸函数。函数。机械优化设计凸函数的凸函数的几何意义几何意义：在函数曲线上取任意两点连：在函数曲线上取任意两点连成一直线段，则该线段上任一点的纵坐标值必大成一直线段，则该线段上任一点的纵坐标值必大于或等于该点处的原函数值。于或等于该点处的原函数值。机械优化设计凸函数的性质凸函数的性质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上上的凸函数。的凸函数。机械优化设计3 3、凸性条件、凸性条件（1）根据一阶导数（函数的梯度）来判断函数的凸性）根据一阶导数（函数的梯度）来判断函数的凸性设设f(x)f(x)为定义在凸集为定义在凸集R R上，且具有连续的一阶导数上，且具有连续的一阶导数的函数，则的函数，则f(x)f(x)在在R R上为凸函数的上为凸函数的充要条件充要条件是对凸是对凸集集R R内任意不同两点内任意不同两点 、，下面不等式，下面不等式恒成立。恒成立。机械优化设计（2 2）根据二阶导数（海赛矩阵）根据二阶导数（海赛矩阵)来判断函数的凸性来判断函数的凸性设设f(x)f(x)为定义在凸集为定义在凸集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(G)det(G)0 0时，矩阵负定时，矩阵负定 det(G)0det(G)0时，矩阵半负定时，矩阵半负定G(x*)G(x*)正定，正定，是是 x*x*为全局极小值点的充分条件为全局极小值点的充分条件；G(x*)G(x*)半正定半正定,是是 x*x*为局部极小值点的充分条件；为局部极小值点的充分条件；G(x*)G(x*)负定，负定，是是 x*x*为全局极大值点的充分条件；为全局极大值点的充分条件；G(x*)G(x*)半负定半负定,是是 x*x*为局部极大值点的充分条件为局部极大值点的充分条件。说明：说明：机械优化设计4 4、凸规划、凸规划对于约束优化问题对于约束优化问题 若若、都为凸函数，则称此问题为凸规划。都为凸函数，则称此问题为凸规划。机械优化设计凸规划的性质：凸规划的性质：2 2）可行域）可行域 为凸集。为凸集。3 3）凸规划的任何局部最优解就是全局最优解。）凸规划的任何局部最优解就是全局最优解。1 1）若给定一点）若给定一点 ，则集合，则集合 为凸集。为凸集。机械优化设计五、等式约束优化问题的极值条件五、等式约束优化问题的极值条件等式等式约束束优化化问题：求解等式约束化问题的理论基础是导出极值求解等式约束化问题的理论基础是导出极值存在的条件。存在的条件。机械优化设计1 1、消元法（降维法）、消元法（降维法）2 2、拉格朗日乘子法（升维法）、拉格朗日乘子法（升维法）思想思想:通过增加变量将等式约束化问题变成无约通过增加变量将等式约束化问题变成无约束化问题。束化问题。引入引入拉格朗日乘子拉格朗日乘子，并构成一个，并构成一个新的目标函数新的目标函数拉格朗日函数拉格朗日函数拉格朗日乘子拉格朗日乘子新目标函数的极值的新目标函数的极值的必要条件：必要条件：参见教材例题参见教材例题机械优化设计六、不等式约束优化问题的极值条件六、不等式约束优化问题的极值条件库恩库恩塔克条件（塔克条件（K-TK-T条件）条件）不等式约束的多元函数极值的必要条件是著名不等式约束的多元函数极值的必要条件是著名的的库恩库恩塔克（塔克（Kuhn-TuckerKuhn-Tucker）条件）条件,它是非线性它是非线性优化问题的重要理论。优化问题的重要理论。为了便于理解库恩为了便于理解库恩塔克条件，首先分析一塔克条件，首先分析一元函数在给定区间的极值条件。元函数在给定区间的极值条件。机械优化设计1 1、一元函数在给定区间上的极值条件、一元函数在给定区间上的极值条件一元函数一元函数f(x)f(x)在区间在区间a,ba,b的极值问题，可表示为：的极值问题，可表示为：求解思想求解思想:引入松弛变量使不等式约束变成等式约束，再引入松弛变量使不等式约束变成等式约束，再利用拉格朗日乘子法求解等式约束的极值问题。利用拉格朗日乘子法求解等式约束的极值问题。机械优化设计这样可以可以转化化为拉格朗日函数：拉格朗日函数：是对应于不等式约束的拉格朗日乘子，是对应于不等式约束的拉格朗日乘子，其值均为非负的。其值均为非负的。设设 为松弛变量，则上两个不等式可写为松弛变量，则上两个不等式可写为如下两个等式：为如下两个等式：机械优化设计对于一元函数于一元函数 在给定区间在给定区间上的极上的极值条件，可完整的表示条件，可完整的表示为：结论：结论：机械优化设计从以上分析可以看出，对应于不起作用的约束的从以上分析可以看出，对应于不起作用的约束的拉格朗日乘子拉格朗日乘子取零值取零值，因此可以引入起作用约束，因此可以引入起作用约束的下标集合。的下标集合。一元函数在给定区间的极值条件，可以改写为：一元函数在给定区间的极值条件，可以改写为：极值条件中只考虑起作用的约束和相应的乘子。极值条件中只考虑起作用的约束和相应的乘子。机械优化设计2 2、库恩、库恩塔克条件塔克条件 库恩库恩塔克条件（塔克条件（K-T条件）可表述为：条件）可表述为：对于多元函数不等式的于多元函数不等式的约束束优化化问题：机械优化设计库恩库恩塔克条件表明：塔克条件表明：如点如点 是函数是函数 的极值点，要么的极值点，要么 （此时（此时 ）或者目标函数的负梯度等于起作）或者目标函数的负梯度等于起作用约束梯度的非负线性组合用约束梯度的非负线性组合（此时（此时 ）。）。机械优化设计机械优化设计库恩库恩塔克条件的塔克条件的几何意义几何意义：在约束极小值点：在约束极小值点 处，函处，函数数 的负梯度一定能表示成起作用约束在该点梯度的负梯度一定能表示成起作用约束在该点梯度（法向量）的非负线性组合。（法向量）的非负线性组合。从图中可以看出，从图中可以看出，处在处在和和即线性组合的系数为正，是在即线性组合的系数为正，是在取得极值的必要条件。取得极值的必要条件。角锥之内，角锥之内，机械优化设计同时具有等式和不等式约束的优化问题：同时具有等式和不等式约束的优化问题：库恩库恩塔克条件（塔克条件（K-T条件）：条件）：机械优化设计 库恩库恩塔克条件是多元函数取得约束极值的塔克条件是多元函数取得约束极值的必要条件必要条件，可用来作为约束极值的判断条件，可用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。又可以来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，符合符合K-T条件的点一定是全局最优点。条件的点一定是全局最优点。这种情况这种情况K-T条件即为多元函数取得约束极值条件即为多元函数取得约束极值的的充分必要条件充分必要条件。机械优化设计例例5 库恩库恩塔克（塔克（K-T）条件应用举例）条件应用举例判断判断 是否为约束最优点？是否为约束最优点？机械优化设计解：解：（1 1）当前点）当前点 为可行点，因满足约束条件为可行点，因满足约束条件（2 2）在）在 起作用约束为起作用约束为 ，因，因（3 3）求各函数梯度：）求各函数梯度：机械优化设计（4 4）求拉格朗日乘子）求拉格朗日乘子由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足是一个局部最优点，因为它满足K-T条件。条件。机械优化设计