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

1、,第二章 优化设计的数学基础,一、多元函数的方向导数和梯度,二、多元函数的泰勒展开,三、无约束优化问题的极值条件,四、凸集、凸函数与凸规划,五、等式约束优化问题的极值条件,六、不等式约束优化问题的极值条件,1、方向导数,二元函数,在,点处的偏导数的定义是：,二元函数,在,点处沿某一方向,的变化率，其定义为,方向导数,一、多元函数的方向导数和梯度,=,+,偏导数与方向导数的关系,n元函数在点x0处沿d方向的方向导数,2、二元函数的梯度,令,梯度,当梯度方向和d方向重合时，方向导数值最大，即梯度方向是函数值变化最快方向，而梯度的模就是函数值变化率的最大值。,梯度的模：,多元函数的梯度,多元函数的梯

2、度的模：,函数的梯度方向与函数的等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。 由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,梯度的两个重要性质： 函数在某点的梯度不为零，则必与过该点的等值面垂直（即为过点的等值线的法线方向）； 梯度方向具有最大变化率方向 正梯度方向是函数值最速上升的方向， 负梯度方向是函数值最速下降的方向。,解：,解：,则函数在 处的最速下降方向为,该方向上的单位向量为,新点,该点函数值,常用梯度公式：,注意：梯度为向量,二次型,二、多元函数的泰勒展开,在 点处的泰勒展开为：,其中,1、一元函数,2、二元函数,其中：,

3、二元函数 在 点处的泰勒展开式为：,上式写成矩阵形式：,令,上式可写成,称为函数 在 点处的 海赛（Hessian）矩阵,参见教材例题P30,海赛矩阵是由函数 在点 处的二阶偏导数组成的方阵。由于函数的二次连续性，有：,所以 矩阵为对阵方阵。,海赛矩阵,3、多元函数,其中：梯度,泰勒展开式,若将函数的泰勒展开式只取到线性项，即取,则 是过点 和函数 所代表的超曲面相切的切平面。,若将函数的泰勒展开式取到二次项时，则得到二次函数形式，在线性代数中将二次齐次函数称为二次型。,矩阵形式,-对称矩阵,当对任何非零向量x使,则二次型函数正定，G为正定矩阵。,海赛矩阵的特征：是实对称矩阵。,4、海赛矩阵与

4、正定,矩阵正定的充要条件：矩阵G的各阶顺序主子式为正，即,矩阵负定的充要条件：矩阵G的,奇数阶主子式,主子式,偶数阶主子式,海赛矩阵的正定性：,正定- 为全局极小值点的充分条件,负定- 为全局极大值点的充分条件,例3 判定矩阵 是否正定？,解：该对称矩阵的三个主子式依次为：,故可知矩阵G是正定的。,定理：若二次函数 中Q正定，则它的等值面是同心椭球面族，且中心为,证明：作变换 ，代入二次函数式中：,结论：Q为正定矩阵的二次型 的等值面是以 的同心椭球面族。原二次函数就是以 为中心的同心椭球面族，椭圆中心为极小值点。,例4 把二次函数 化为矩阵向量形式并检验Q是否正定，如正定，试用公式 求这个函

5、数的极小点。,解：,与题中函数比较各系数得：,由计算知Q正定，极小点,三、无约束优化问题的极值条件,1、一元函数,对于可微的一元函数 判断在 处是否取得极值的过程：,则 为极小点。,逐次检验其更高阶导数的符号，开始不为零的导数阶数若为偶次，则为极值点，若为奇次，则为拐点。,则 为极大点。,2、二元函数,定理1：若二元可微函数 在 处取得极值的必要条件是：,即,凡满足上式的点称为函数的驻点,（零向量）,如下图所示的二元函数，在M0点虽有 和 是个驻点，但它不是极值点。,定理2：若二元可微函数 在 的某个邻域取得极小值的充分条件是要求在该点附近的一切点均满足：,若函数存在连续的一阶及二阶偏导数，当

6、满足,则泰勒展开式的函数增量近似式（略三阶以上高阶微量）为：,令,则,可见，函数增量的性态与A,B,C的值有关。可以证明，当满足以下条件时， 为极小值（证明略）。,此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。,结论：,二元函数在某点取得极小值的充分条件是要求该点处的海赛矩阵为正定。,且,对于二元函数 在 处取得极值的充分必要条件是：,参见教材例题P32,3、多元函数,对于多元函数 若在 处取得极值，则,必要条件：,充分条件：,正定 或负定,四、凸集、凸函数与凸规划,当极值点x*能使f(x*)在整个可行域中为最小值时，即在整个可行域中对任一x都有f(x)=f(x*),则x*为

7、全域最优点（全域极小点）。若f(x*)为局部可行域中的极小值而非整个可行域的最小值时，则称x*为局部最优点或相对最优点。优化的目标是全域最优点。为了判断某个极值点是否为全域最优点，研究函数的凸性是必要的。,函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优亦是全域最优点。,为了研究函数的凸性，下面引入凸集的概念：,1、凸集,如果对一切 及一切满足,的实数 ，点 则称集合,为凸集，否则称为非凸集。,若y是x1和x2连线上的点，则有,整理后即得,凸集的性质：,若D为凸集， 为一个实数，则集合 仍是凸集； 若D和F均为凸集，则其和（或并）仍是凸集； 任何一组凸

8、集的积（或交）仍是凸集。,2、凸函数,具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：,设f(x)为定义在n维欧式空间中的一个凸集D上的函数，如果对于任何实数 以及对D中任意两点x1，x2恒有：,则 为D上的凸函数，若不满足上式，则为凹函数。如式中的等号去掉，则称其为严格凸函数。,凸函数的几何意义：在函数曲线上取任意两点连成一直线段，则该线段上任一点的纵坐标值必大于或等于该点处的原函数值。,凸函数的性质,1）若f(x)为定义在凸集D上的一个凸函数，对于任意实数a0，则af(x)也是凸集D上的凸函数； 2）定义在凸集D上的两个凸函数f1(x

9、),f2(x)，其和f1(x)+f2(x)亦为该凸集上的一个凸函数； 3）若f1(x),f2(x)为定义在凸集D上的两个凸函数， 为两个任意正数，则 仍为D上的凸函数。,3、凸性条件,（1）根据一阶导数（函数的梯度）来判断函数的凸性,设f(x)为定义在凸集R上，且具有连续的一阶导数 的函数，则f(x)在R上为凸函数的充要条件是对凸 集R内任意不同两点 、 ，下面不等式恒成立。,（2）根据二阶导数（海赛矩阵)来判断函数的凸性,设f(x)为定义在凸集R上且具有连续二阶导数的函数，则f(x)在R上为凸函数的充要条件为：,海赛矩阵在R上处处半正定。对于严格的凸函数，其充要条件为海赛矩阵为正定。,当海赛

10、矩阵G的主子式: det(G)0时，矩阵正定 det(G)0 时，矩阵半正定 det(G)0时，矩阵负定 det(G)0时，矩阵半负定,G(x*)正定， 是 x* 为全局极小值点的充分条件； G(x*)半正定, 是 x* 为局部极小值点的充分条件； G(x*)负定， 是 x* 为全局极大值点的充分条件； G(x*)半负定, 是 x* 为局部极大值点的充分条件。,说明：,4、凸规划,对于约束优化问题,若,、,都为凸函数，则称此问题为凸规划。,凸规划的性质：,2）可行域 为凸集。,3）凸规划的任何局部最优解就是全局最优解。,1）若给定一点 ，则集合 为凸集。,五、等式约束优化问题的极值条件,等式约

11、束优化问题：,求解等式约束化问题的理论基础是导出极值存在的条件。,1、消元法（降维法）,2、拉格朗日乘子法（升维法）,思想: 通过增加变量将等式约束化问题变成无约束化问题。,引入拉格朗日乘子,，并构成一个,新的目标函数,拉格朗日函数,拉格朗日乘子,新目标函数的极值的必要条件：,参见教材例题,六、不等式约束优化问题的极值条件,库恩塔克条件（K-T条件）,不等式约束的多元函数极值的必要条件是著名的库恩塔克（Kuhn-Tucker）条件,它是非线性优化问题的重要理论。,求解思想:引入松弛变量使不等式约束变成等式约束，再利用拉格朗日乘子法求解等式约束的极值问题。,1、一元函数在给定区间上的极值条件,一

12、元函数f(x)在区间a,b的极值问题，可表示为：,存在极值的必要条件可表示为：,从式中可以看出，对应于不起作用的约束的拉格朗日乘子取零值，因此可以引入起作用约束的下标集合。,一元函数在给定区间的极值条件，可以改写为：,极值条件中只考虑起作用的约束和相应的乘子。,2、库恩塔克条件,库恩塔克条件（K-T条件）可表述为：,对于多元函数不等式的约束优化问题：,库恩塔克条件表明：,如点 是函数 的极值点，要么 （此时 ）或者目标函数的负梯度等于起作用约束梯度的非负线性组合 （此时 ）。,库恩塔克条件的几何意义：在约束极小值点 处，函数 的负梯度一定能表示成起作用约束在该点梯度（法向量）的非负线性组合。,从图中可以看出，,处在,和,即线性组合的系数为正，是在,取得极值的必要条件。,角锥之内，,同时具有等式和不等式约束的优化问题：,库恩塔克条件（K-T条件）：,库恩塔克条件是多元函数取得约束极值的必要条件，可用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,对于