优化设计的理论与数学基础

《优化设计的理论与数学基础》由会员分享，可在线阅读，更多相关《优化设计的理论与数学基础（37页珍藏版）》请在装配图网上搜索。

1、第二章 优化设计的理论与数学基础 1、一元函数 f(x)在 k点的泰勒展开式 f(x)=f(x(k)+ f(x(k)(x- x(k)+ f”(x(k) (x- x(k)2/2! 2、多元函数 f(x)在 k点的泰勒展开式及海赛（ Hessian) 矩阵 F(x)=F (x(k)+ FT x- x(k)+ x- x(k)T 2F x- x(k)/2 梯度 F = 海赛矩阵 H(x)= 2F = 2.1 目标函数的泰勒（ Taylor)展开式 3、二次型函数 F(x)=xTAx 对于二次函数 F(x)=xTAx。 若对于任意不为零的 x=x1,x2,xn,恒有 F(x)0,则相应的系数矩阵 A 称

2、为 正定矩阵 。 若恒有 F(x) 0,则称 A为 半正定矩阵 。 2.2 目标函数的等值线（面） 设 n维目标函数 F(x)=F(x1,x2,xn),在 n维设计 空间的任意一点 x有确定的函数值 F; 反之，对 于某一确定的函数值将有若干个设计点 xi(i=1,2,)与之相应。 如果是连续问题，将有 无限多个确定的设计点对应同一个函数值，则 这些设计点在设计空间中构成的点集称为等值 面（三维空间）、超等值面（四维以上）。对 于二维问题，则称等值线。 2.3 无约束优化最优解的条件 一、一元函数极值条件 对于连续可微的一元函数 f(x),如在 x*点有极值， 其必要条件为： f (x*)=0

3、 若 x*为有极小值点，其充分条件为： f ”(x*)0 二、二元函数极值条件 对于连续可微函数 F(x)=F(x1,x2)在 x*点有极 值，其必要条件为： F(x*)= 三、多维函数极值条件 对于连续可微函数 F(x)=F(x1,x2， , xn)在 x*点有 极值，其必要条件为： F(x*)= 当海赛矩阵正定时，点 x*为极小值 2.4 凸集与凸函数 2.4.1凸集与非凸集 2.4.2 凸函数 一、凸函数的数学定义 : 若 F(x)满足： 则称 F(x)为定义在凸集上的凸函数 二、凸函数的基本性质 1）若 F(x)为凸函数，则 F(x)也是凸函数。 为 任意正实数。 2) 若 F(x1)

4、、 F(x2)为凸函数，则 F(x1)+F(x2) 也是凸函数。 3) 若 F(x1)、 F(x2)为凸函数，则 F(x1)+ F(x2) 也是凸函数。 三、凸函数的判别法 ： 海赛矩阵半正定 四、局部极小点与全局极小点 包括无约束优化与约束优化问题在内，用优化方法所求出的点 一般都是局部极小点，称为 局部最优点 ；而我们所需要的是整体 极小点，称为 全局最优点 。 )()1()()1( 2121 xFxFxxF 2.5 关于优化方法中搜寻方向的理论基 础 对任何一个优化方法的研究都离不开初始点 x(0) 的选取、搜寻方向 S的确定以及步长 a的确定。或 称 初始点 x(0)、搜寻方向 S以及

5、 步长 a为优化方法 的三要素。而尤以搜寻方向 S为关键 ,它是优化方 法特性以及优劣的根本标志。不同的优化方法取 不同的方向 S，它是矢量，在 n维优化方法中 , S=S1 S2 Sn。以下说明产生搜寻方向的 数学理论基础。 由目标函数的等值线上可大致的看出函数的变化情况， 而三维以上的超等值面是不能画出来的。为了确切表达函数 在某一点的变化形态则要用微分的办法具体分析。 一、方向导数 导数是描写函数变化率的一个量。设有连续可微的 n维目标 函数 F（ x） F（ x）在点 的一阶偏导数为 ， ， 它们分别表示函数 F（ x）在点 沿各座标轴方向的变化率。 2.5.1函数的最速下降方向 以二

6、维函数 F（ x）为例，见图。从 点，沿某一方向 （与 ox1， ox2轴夹角分别为 ， ）前进到点 其增量 其模长 函数 F（ x）在 点沿 S方向的方向导数为 或记为 方向导数 表示函数 F（ x）在点 沿 S方向的变化率。图中，过 o， 两点连线所竖立的垂直 平面与函数 F（ x）曲面交线 mm，该曲线在 k点的斜率即为 函数 F（ x）沿 S方向的导数。 沿 S方向的导数为 n维函数 F（ x）在点 + 式中 ， 为 方向 S和各座标轴的夹角 。 称 cos ， cos ， ， cos 为 矢量 S的方向余铉。 上式可简写为 或 为函数 F（ x）在点 的梯度，记作 gradF（ ），

7、 矢量的模长为 简记为 定义矢量： 是方向 S的单位矢量，其模长为 将方向导数式 写为 用记号 ， S表示矢量 与 S之间的夹角，则 表示的方向导数又可写为 二、函数的最速下降方向 函数 F（ x）在 点变化率的值取决于方向 S，不同 方向变化率大小不同 -1cos ,S 1,当方向 S与梯度 矢量方向一致时，方向导数 达到最大值，即函数的 变化率最大，其值为梯度的模长 梯度优化设计的几个重要特征 梯度是在设计空间里的一个矢量。该矢量的方向是指 矢量的最速上升方向， 即在梯度方向函数的变化率最大 函数在某点的梯度矢量指出了该点极小邻域内函数的 最速上升方向，因而只有局部性。函数在其定义域范围

8、内的各点都对应着一个确定的梯度 ， 即不同点 x的最速上 升方向不同 函数最速下降方向，在优化设计理论中占有重要地位。 函数负梯度 - 必为函数最速下降方向， 不同设计点 函数 F（ x）具有各自的最速下降方向 函数 F（ x）在 点的梯度 矢量是函数等值线（面）在该 点的法矢量 以二维函数为例，如图 取函数值为 Fk及 Fk+F，等值线 为 x1ox2平面上相对应的两条曲线 过等值线上点 ，沿 S方向的 方向导数为 对于上述两条等值线，函数的增量为定 F，而 过 点的最大方向导数必沿着等值线间距离 最短的方向，既沿着 | S|最小的方向，必为 过 点等值线的法线方向 2.5.2 共轭方向 共

9、轭方向 是指若干个方向矢量组成的方向组，各方向具有 某种共同的性质，他们之间存在着特定的关系。 一 、 共轭方向的基本概念 首先以二元二次函数为例予以说明共轭方向概念，设函数 式中 2*2阶对称 正定矩阵 函数 F（ x）的梯度为 F（ x） =Ax+B 由于函数 F（ x）中的 A矩阵对称正定，所以等值线为一组椭圆， 如右图 按任意给定的方向 S1，做 F（ x） =F1与 F（ x） =F2两条等 值切线，两切线互为平行，切点 分别为 ， 。连接两切点构 成新的矢量 函数 F（ x）在两点处的梯度 分别为 将上两式相减，得 按梯度的特性 ， 梯度是等值线的法矢量 ，所以 ， 点的梯度必须与

10、矢量 S1相垂直，因正交矢量点积为 0，故 有： 或 将式 带入上式，有 综上所述 ， 两个二维矢量 S1， S2，对于 2 2阶对称正定 矩阵 A，如能满足式，称矢量 S1与 S2对 A共轭 - 推广到 n维设计空间，若有两个 n维矢量 S1、 S2，对 n n阶 对称正定矩阵 A能满足： 称 n维空间矢量 S1， S2对 A共轭 ，记作 共轭矢量代表的方向称为共轭方向 在两个矢量相共轭的基础上，定义共轭矢量如下 ： 设 A为 n n阶实对称矩阵，有一组非 0的 n维矢量 S1， S2 ， Sq， 若满足 ij 则称矢量系 Si（ i=1， 2qn ）对于矩阵 A共轭 二、共轭矩阵的几个性质

11、 共轭矢量之所以引起优化研究者的重视，因为它的某些 性质对提高优化方法的收敛速率极为有效。 矢量 S1与 S2正交关系，是矢量 S1与 S2对 A共轭的特殊情形 对于式，如果矩阵 A是单位矩阵 E时，则矢量 S1与 S2的共轭 就是矢量的正交 即为 也可以说，矢量共轭的概念实际上就是正交概念的广义化。 在某一 空间里对矩阵 A共轭的两矢量，可通过尺度变换成为 另一 空间里的两个正交矢量。 对于由 k个非零矢量 S1， S2S k组成的矢量系 Si，若 存在着 ij 称该矢量为 正交矢量系 显然，在 n维设计空间里，单位坐标矢量系： e1， e2e n 为正交矢量系 若矢量系 S1， S2S n

12、对于对称正定矩阵 A共轭，则它 必为线性独立（线性无关）矢量系。 对于 n维设计空间而言 ， 线性独立矢量系中的矢量个数不能超过维数 n，即共轭矢量 系中矢量个数最多等于 n。 对于矢量系的线性独立问题简述如下 : 设有非零矢量系： S1， S2S n，若存在一组不全为 零的实数 1， 2， n， 使 成立，则该矢量系称为 线性相关矢量系 。 如果只有在 1= 2= n=0，即系数全部为零才有 上式成立，则该矢量系为 线性独立矢量系 在式线性相关矢量系中，若某矢量 Si的系数 i0， 则可写成 可知， 线性相关矢量系中 Si可表示为其余矢量的线性组合。 任意两个矢量 S1与 S2，如果它们是共

13、线的，则矢量 S1 与 S2必线性相关。因为对于共线两矢量 S1与 S2，一定可以 找到系数 1与 2，使 在二维平面里，由三个及三个以上的矢量组成的矢量系 ，也必定是线性相关的。例如二维平面的三个矢量 取一组系数 1=1， 2=1/4， 3=1，使 矢量系 Si（ i=1， 2， 3）是线性相关的，由下图说明 将 S3用 S1与 S2的线性组合表示为 可见，同一平面上任意三个矢量必定线性相关。 在三维空间里的三个矢量，只要他们不共面，则必线性独 立；若三维空间中有任意四个矢量，则矢量系必线性相关。 可以得出结论： 当矢量系中矢量的数目超过 设计空间的维数时，矢量系必线 性相关 非零矢量构成的

14、正交矢量系 必线性独立。正交矢量系中矢量 的数目不能超过矢量系所在的空 间的维数 三、关于二次收敛性问题 对于二元二次正定函数 F（ x），取一组共轭矢量 S1与 S2，其中矢量之一通过等值曲线中心。 二元二次正定目标函数的等值线为一组同心的椭圆，其 中心是函数的极小点 。 按共轭方向的性质： 任意做两条平行线，与椭圆组中 的两椭圆切于 点 ， 该两点 必通过椭圆的中心； 或者说，过 椭圆中心做任意直线与任意两个 椭圆相交，通过交点作椭圆切线 必互相平行 )1(x )2(x 对以上结论的证明： 为简化，设目标函数为二次齐次函数，等值线中心在坐 标原点。 展开 函数值分别为 d1， d2的两条等

15、值线 ， ，方程为： 等值线任意点切线斜率为 ，可对上式求导而得， 则切线斜率为 过点 椭圆切线斜率分别记为 K1， k2，则有： 当所引的两条直线平行，且切于等值线（椭圆 )于点 , ,则该两条切线斜率相等， k1=k2，即 分别将切点 与坐标原点相连接，两直线 ox1， ox2 的斜率分别记为 )1(x )2(x )1( 1 )1( 20 1 x xk )2( 1 )2( 20 2 x xk 如果有 ，说明两点连线必通过坐标原点 o（椭圆中心） 将式写成 0201 kk 或 将上式展开整理后得 由于函数 F（ x1， x2）是二次齐次函数，图形为椭圆，所以 ，则必有 。 由此证明得出，点

16、， 连线必定通过椭圆中心点 o。 若在切于椭圆的直线上取方向 S1，连接两个切点 ， 为方向 S2，则 S1， S2为共轭方向。如果从某任意初始点 出发，依次沿方向 S1， S2做两次一维搜索，即可达到椭圆 中心 此函数 F（ x）的极小点。 对于一般的二元二次正定函数 ， 按其共轭方向进行两次搜索也必定达到函数的极小点。此情 况目标函数等值线仍是椭圆，但其中心不在坐标原点。 二次收敛性是指一种算法，如果对于二次正定函数，从理论 上只要进行有限次一维搜索 ， 就可以达到理论极小点，把这种算 法称为具有 二阶收敛性（二次收敛性） 或 有限步收敛法。 对于一般的 n元二次正定函数 F（ x），依次

17、按共轭矢量系 （ S1， S2 Sn）中各矢量方向进行 n维一次搜索，就可达等值 线（椭圆）中心 理论极小值点 。 例题 2：设二维目标函数 ，给定方向 S1=e1， 初始点 。求与 S1相共轭的 S2，并求函数的极小点。 解 ： 第一个搜索方向 。 函数的海塞矩阵 对称正定。 可知函数 F（ x）为二次正定函数，如果按共轭方向 S1， S2，进行两次一维搜索就达到目标函数的极小点 x*。 从 点沿 S1方向求极小点 ，即 沿 S1 方向 则 任取初始点 ，沿 S1方向一维搜索求得该方向极小 点 按的做法 求与 S1相共轭的方向 S2 核验计算 矢量 S1与 S2为对 A矩阵共轭 从 点出发，沿 S2方向作一维搜索， 得极小点 如右图所示。