《机械优化设计》-第二-五讲

1、第二章 优化设计的数学基础,一、等值（线）面,对于可计算的函数 f(x)，给定一个设计点 X(k)(x1(k),x2(k), ,xn (k)，f(x)总有一个定值c 与之对应；而当f(x)取定值 c 时，则有无限多个设计点X(i)(x1(i), x2(i), ,xn(i) ) （i=1,2, ）与之对应，这些点集构成一个曲面，称为等值面。,当 c 取c1,c2, 等值时，就获得一族曲面族，称为等值面族。,当f(x)是二维时，获得一族等值线族； 当f(x)是三维时，获得一族等值面族； 当f(x)大于三维时，获得一族超等值面族。,等值线的“心” （以二维为例）,第二章 优化设计的数学基础,一个“心

2、”：单峰函数的极（小）值点，是全局极（小）值点。 没有“心”：线性函数的等值线是平行的，无“心”，认为极值点在无穷远处。,多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。,第二章 优化设计的数学基础,等值线的分布规律： 等值线越内层其函数值越小（对于求目标函数的极小化来说） 沿等值线密的方向，函数值变化快；沿等值线疏的方向，函数值变化慢。 对于有心的等值线来说，其等值线簇的中心就是一个相对极小点；而对于无心的等值线簇来说，其相对极小点就是在无穷远了。,第二章 优化设计的数学基础,二、梯度,方向导数： 二维

3、问题中，f (x1,x2 ) 在 X(0) 点沿方向 s的方向导数为：,其中：,是 X(0)点的梯度。,S 为s方向的单位向量， 。,为 S 的方向角,方向导数,为梯度,在方向 s 上的投影。,第二章 优化设计的数学基础,梯度的性质：, 梯度的模因点而异，即函数f(x)在不同点的最大增长率不同。 梯度方向是X(0)点处指向函数变化率最大的方向，是函数的一种局部性质，只反映X(0)点邻近的函数性质； 梯度方向与过该点的等值线的切线是正交的，是过该点的等值线的法线方向； 正梯度方向是函数值最速上升的方向，负梯度方向是函数值最速下降的方向。,梯度方向的几何意义,第二章 优化设计的数学基础,梯度方向与

4、等值线的关系,第二章 优化设计的数学基础,对于 n 维问题的梯度,第二章 优化设计的数学基础,例2-1求函数 在 处函数变化率最大的方向和数值。,解 函数变化率最大的方向就是梯度方向，用单位向量 表示，其数值就是梯度的模。计算如下：,第二章 优化设计的数学基础,三、多元函数的泰勒展开,n 维函数 f(x) 在 x(k) 点的台劳展开式:,二阶近似式：,其中：增量, X (k) =x1 (k) , x2 (k) , xn (k) T,梯度,Hesse 矩阵,第二章 优化设计的数学基础,例2-2 求二元函数 在 点处的二阶泰勒展开式,解 二阶泰勒展开式为,将 的具体数值代入，有,第二章 优化设计的

5、数学基础,此函数的图像是以 点为顶点的旋转抛物面。,对于二次型函数，当对任何非零向量 使,则二次型函数正定， 为正定矩阵。,四、Hesse 矩阵与正定,Hesse 矩阵的特性：是实对称矩阵。,对于二次型函数，当对任何非零向量 使,第二章 优化设计的数学基础,Hesse 矩阵的特性：是实对称矩阵。,Hesse 矩阵的正定性：,H(x*)正定， 是 x* 为严格极小值点的充分条件； H(x*)半正定, 是 x* 为极小值点的充分条件； H(x*)负定， 是 x* 为严格极大值点的充分条件； H(x*)半负定, 是 x* 为极大值点的充分条件。,H是正定矩阵的充要条件是它的所有主子式都大于0; H是

6、负定矩阵的充要条件是它的所有奇数阶主子式都小于0，并且它的所有偶数阶主子式都大于0； H是半正定矩阵的充要条件是它的所有主子式都大于等于0； H是半负定矩阵的充要条件是它的所有奇数阶主子式都小于等于0，并且它的所有偶数阶主子式都大于等于0；,无约束优化问题是使目标函数取得极小值，极值条件是指目标函数取得极小值时极值点应满足的条件。,对一元函数，取极值的必要条件是,取极值的充分条件是在驻点附近，若 ，则该点为极大点，若 ，则该点为极小点。,五 无约束优化问题的极值条件,对二元函数，取极值的必要条件是,判断从上述必要条件求得的是否为极值点，需要建立极值的充分条件。,即,二元函数在某点处取得极值的充

7、分条件是要求在该点处的海森矩阵为正定。,极值的充分条件为,(2-7),正定。,依此类推，多元函数 在 点处取极值的必要条件为,第二章 优化设计的数学基础,例2-3 求函数 的极值。,解 首先，根据极值的必要条件求驻点。,得驻点为,再根据极值的充分条件，判断此点是否为极值点。由于,第二章 优化设计的数学基础,的一阶主子式和二阶主子式分别为,故 为正定矩阵 为极小点，相应的极值为 。,六、凸集、凸函数与凸规划,设 为n维设计空间中的一个集合，若其中任意两点 的连线都包含在该集合内，就称该集合是n维设计空间的一个凸集。,第二章 优化设计的数学基础,凸集具有以下性质：,1、若 是一个凸集， 是一个实数

8、， 是凸集 中的动点，即 ，则集合,还是凸集。,2、若 是凸集， 分别是凸集 中的动点，即 ， ， 则集合,还是凸集。,3、任何一组凸集的交集还是凸集。,第二章 优化设计的数学基础,设 为定义在n维设计空间中一个凸集 上的函数，若对任何实数 及 域中任意两点 存在如下关系： 则称为 定义在凸集 上的凸函数。,凸函数,一元函数 若在a，b内为凸函数，其函数曲线上任意两点所连的直线段不会落在曲线弧段以下，即函数值总是小于或等于直线段上相应的纵坐标值。,第二章 优化设计的数学基础,第二章 优化设计的数学基础,凸函数的基本性质：,若f(x)是定义在凸集D上的严格凸函数，则f(x)在D上的一个极小点，

9、也就是全局最小点。 凸函数的线性组合仍然为凸函数。 设x(1), x(2)为凸函数 f(x)上的两个最小点，则其连线上的任意点也都是最小点。,凸性函数的判定（判别函数为凸函数的条件）,按梯度判断凸性：设f(x)是定义在凸集 D上具有连续一阶导数的函数，则f(x)在D上为凸函数的充要条件是：对于任意的 x(1),x(2)D 都有 成立。,按二阶偏导数判断凸性：设 f(x) 是定义在凸集D上具有连续二阶导数的函数，则f(x)在D上为凸函数的充要条件是：f(x)的Hesse矩阵处处半正定。若Hesse矩阵处处正定，则f(x)为严格凸函数。,第二章 优化设计的数学基础,凸规划,对于约束优化问题,若 、

10、 都为凸函数，则称此问题为凸规划。,1.若给定一点 ，则集合 为凸集。此性质表明，当 为二元函数时其等值线呈现大圈套小圈形式。,凸规划的性质,第二章 优化设计的数学基础,2. 可行域 为凸集。,3.凸规划的任何局部最优解就是全域最优解。,目标函数是非凸函数（图 a），或可行域是非凸集（图 b）：,则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。,p,Q,Q,p,第二章 优化设计的数学基础,无约束优化设计问题最优解：,不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成无约束问题最优解。

11、 x*为无约束极小点的充要条件（1） ；(2)Hesse矩阵 为正定。,第二章 优化设计的数学基础,约束优化设计问题最优解：,满足约束条件，使目标函数达到最小值的一组设计变量， 即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成约束问题最优解。,其中 是约束最优点，而 是无约束最优点。,第二章 优化设计的数学基础,等式约束优化问题的极值条件,求解等式约束优化问题,其思路就是将其转化成无约束优化问题，导出极值存在的条件。数学上有两种处理方法：消元法和拉格朗日乘子法。,约束优化问题可分为等式约束与不等式约束优化问题。,第二章 优化设计的数学基础,消元法,为了便于理解，先讨论二元函数

12、只有一个等式约束的情况,用消元法求解就是根据等式约束条件，将一个变量表示成另一个变量的函数关系 ，然后将其代入到目标函数 中消去 ，变成一元函数 ，从而将等式约束优化问题转化成无约束优化问题。目标函数通过消元由二元函数变成一元函数，由二维变成一维。,第二章 优化设计的数学基础,对于 维情况,由 个约束方程将 个变量中的前 个变量用其余 个 变量表示，既有,将这些函数关系代入到目标函数中去，得到只含 共 个变量的函数 ，从而可以利用无约束优化问题的极值条件求解。,第二章 优化设计的数学基础,拉格朗日乘子法,拉格朗日乘子法与消元法相反，是通过增加变量将等式约束优化问题转化成无约束优化问题。对于具有

13、 个等式约束的 维优化问题。,构造如下形式的新的目标函数：,式中的 就是原目标函数 的等式约束条件，而待定系数 称为拉格朗日乘子, 称为拉格朗函数。因为 ，所以求 的极值就相当于求原目标函数 的极值。这样就把求等式约束优化问题转化成求有l+n个变量的无约束优化问题。由 具有极值的必要条件,第二章 优化设计的数学基础,可得l+n个方程，从而解得 和 共l+n个未知变量的值。由上述方程组求得的 是函数 极值点的坐标值。,第二章 优化设计的数学基础,从上述分析过程可以看出求解等式约束优化问题，可通过把目标函数改造成如下形式的新的目标函数。,从而将等式约束优化问题转化成无约束优化问题。这种方法称为拉格

14、朗日乘子法.,第二章 优化设计的数学基础,例2-4 用拉格朗日乘子法计算约束条件为 和目标函数为 的极值点坐标。,第二章 优化设计的数学基础,解 改造目标函数,解前两式得,代入第三式得 ，因此得极值点 的坐标为,第二章 优化设计的数学基础,2.6不等式约束优化问题极值条件,K-T ( Kuhn-Tucker 库恩-塔克) 条件,2.6.1 一元不等式约束问题极值条件,第二章 优化设计的数学基础,1. 有一个适时约束时：,从数学上定义，当从 x(k)点出发不存在一个 S 方向能同时满足： ; ，即 ， 则获得最优解：x(k)为最优点 x*，f(x(k)为最优值 f(x*)。,从几何上看，当从 x

15、 (k)点出发不存在一个 S 方向能同时满足：,与x(k)点目标函数的负梯度方向成锐角，即沿 S 方向目标函数值下降； 与x(k)点约束函数的梯度方向成钝角，即保证 S方向上各点在可行域内。 此时，获得最优解 x(k) 为最优点 x*， f(x(k)为最优值 f(x*)。,2.6.2 库恩-塔克条件（K-T条件）,几何意义,第二章 优化设计的数学基础,相反，当从 x(k)点出发，存在一个 S 方向能同时满足： 和 时，则 x(k) 不是最优点。,从几何上看，当从 x(k)点出发存在一个 S 方向能同时满足： 与x(k)点目标函数的负梯度方向成锐角，即沿 S 方向目标函数值下降； 与x(k)点约

16、束函数的梯度方向成钝角，即保证 S方向上各点在可行域内。 此时，x(k)不是最优点 x*。,第二章 优化设计的数学基础,2. 有二个适时约束时：,x(k)成为约束最优点 x* 的必要条件为:,即不存在一个 S 方向能同时满足：,几何上 位于 和 所张的扇形子空间内。,第二章 优化设计的数学基础,相反，不符合以上条件：,不能表达成 和 的线性组合。,即存在一个 S 方向能同时满足：,几何上 不位于 和 所张的扇形子空间内。则 x(k) 点不是最优点。,第二章 优化设计的数学基础,K-T 条件（扩展至 m 个适时约束）：,设某个设计点 x(k)，其适时约束集为,且 为线性独立，则 x(k)成为约束

17、最优点的必要条件是目标函数的负梯度向量可表示为适时约束梯度向量的线性组合，即 ，其中 。,几何上，x(k)成为约束最优点（极小点）x*时，目标函数的负梯度向量位于 m 适时约束梯度向量所张成的子空间内。,第二章 优化设计的数学基础,K-T条件对于约束优化设计问题的重要性在于 （1） 可以通过这个条件检验设计点x*是否为约束极小点，因此它可以成为某些迭代算法的一种收敛条件； （2） 可以检验一种搜索方法是否合理，如果用这种迭代方法求得的最优点符合K-T条件，则方法可以认为是可行的。,第二章 优化设计的数学基础,3）构建方程组：按K-T条件，x(k)点应满足 4）该方程组存在唯一解，解方程组得到一组乘子 ， 若其中 ，则点是约束极小点，否则不是约束极小点