《二章优化设计的理论与数学基础.ppt》由会员分享，可在线阅读，更多相关《二章优化设计的理论与数学基础.ppt（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称为正定矩阵。 若恒有F(
2、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 若x*为有极小值点，其充分条件为： f ”(x*)0,二、二元函数
3、极值条件 对于连续可微函数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)、 F(x2)为凸函数，则F(x1)+F(x2) 也是凸函数。 3) 若F(x1)、 F(x2)为
4、凸函数，则F(x1)+F(x2) 也是凸函数。 三、凸函数的判别法：海赛矩阵半正定 四、局部极小点与全局极小点 包括无约束优化与约束优化问题在内，用优化方法所求出的点一般都是局部极小点，称为局部最优点；而我们所需要的是整体极小点，称为全局最优点。,2.5 关于优化方法中搜寻方向的理论基础,对任何一个优化方法的研究都离不开初始点x(0) 的选取、搜寻方向S的确定以及步长a的确定。或 称初始点x(0)、搜寻方向S以及步长a为优化方法 的三要素。而尤以搜寻方向S为关键,它是优化方 法特性以及优劣的根本标志。不同的优化方法取 不同的方向S，它是矢量，在n维优化方法中, S=S1 S2 Sn。以下说明产
5、生搜寻方向的 数学理论基础。,由目标函数的等值线上可大致的看出函数的变化情况，而三维以上的超等值面是不能画出来的。为了确切表达函数在某一点的变化形态则要用微分的办法具体分析。,一、方向导数,导数是描写函数变化率的一个量。设有连续可微的n维目标 函数F（x）,F（x）在点 的一阶偏导数为,，,它们分别表示函数F（x）在点 沿各座标轴方向的变化率。,2.5.1函数的最速下降方向,以二维函数F（x）为例，见图。从 点，沿某一方向 （与ox1，ox2轴夹角分别为 ， ）前进到点,其增量,其模长,函数F（x）在,点沿S方向的方向导数为,或记为,方向导数,表示函数F（x）在点,沿S方向的变化率。图中，过o
6、，,两点连线所竖立的垂直 平面与函数F（x）曲面交线mm，该曲线在k点的斜率即为 函数F（x）沿S方向的导数。,沿S方向的导数为,n维函数F（x）在点,+,式中，,为方向S和各座标轴的夹角。称cos,，cos,，cos,为矢量S的方向余铉。,上式可简写为,或,为函数F（x）在点,的梯度，记作gradF（,），,矢量的模长为,简记为,定义矢量：,是方向S的单位矢量，其模长为,将方向导数式,写为,用记号,，S表示矢量,与S之间的夹角，则 表示的方向导数又可写为,二、函数的最速下降方向,函数F（x）在 点变化率的值取决于方向S，不同 方向变化率大小不同,-1cos ,S1,当方向S与梯度 矢量方向一
7、致时，方向导数 达到最大值，即函数的 变化率最大，其值为梯度的模长,梯度优化设计的几个重要特征,梯度是在设计空间里的一个矢量。该矢量的方向是指 矢量的最速上升方向，即在梯度方向函数的变化率最大,函数在某点的梯度矢量指出了该点极小邻域内函数的 最速上升方向，因而只有局部性。函数在其定义域范围 内的各点都对应着一个确定的梯度，即不同点x的最速上 升方向不同,函数最速下降方向，在优化设计理论中占有重要地位。 函数负梯度- 必为函数最速下降方向，不同设计点 函数F（x）具有各自的最速下降方向,函数F（x）在 点的梯度 矢量是函数等值线（面）在该点的法矢量,以二维函数为例，如图,取函数值为Fk及Fk+F
8、，等值线 为x1ox2平面上相对应的两条曲线 过等值线上点 ，沿S方向的 方向导数为,对于上述两条等值线，函数的增量为定F，而过 点的最大方向导数必沿着等值线间距离最短的方向，既沿着| S|最小的方向，必为过 点等值线的法线方向,2.5.2 共轭方向,共轭方向是指若干个方向矢量组成的方向组，各方向具有 某种共同的性质，他们之间存在着特定的关系。,一、共轭方向的基本概念,首先以二元二次函数为例予以说明共轭方向概念，设函数,式中,2*2阶对称 正定矩阵,函数F（x）的梯度为,F（x）=Ax+B,由于函数F（x）中的A矩阵对称正定，所以等值线为一组椭圆， 如右图,按任意给定的方向S1，做 F（x）=
9、F1与F（x）=F2两条等 值切线，两切线互为平行，切点 分别为 ， 。连接两切点构 成新的矢量,函数F（x）在两点处的梯度 分别为,将上两式相减，得,按梯度的特性，梯度是等值线的法矢量，所以 ， 点的梯度必须与矢量S1相垂直，因正交矢量点积为0，故 有：,或,将式带入上式，有 ,综上所述，两个二维矢量S1，S2，对于22阶对称正定 矩阵A，如能满足式，称矢量S1与S2对A共轭,- ,推广到n维设计空间，若有两个n维矢量S1、S2，对nn阶 对称正定矩阵A能满足：,称n维空间矢量S1，S2对A共轭，记作,共轭矢量代表的方向称为共轭方向,在两个矢量相共轭的基础上，定义共轭矢量如下：,设A为nn阶
10、实对称矩阵，有一组非0的n维矢量S1， S2，Sq，若满足,ij,则称矢量系Si（i=1，2qn）对于矩阵A共轭,二、共轭矩阵的几个性质,共轭矢量之所以引起优化研究者的重视，因为它的某些 性质对提高优化方法的收敛速率极为有效。,矢量S1与S2正交关系，是矢量S1与S2对A共轭的特殊情形,对于式，如果矩阵A是单位矩阵E时，则矢量S1与S2的共轭 就是矢量的正交,即为,也可以说，矢量共轭的概念实际上就是正交概念的广义化。 在某一空间里对矩阵A共轭的两矢量，可通过尺度变换成为 另一 空间里的两个正交矢量。,对于由k个非零矢量S1，S2Sk组成的矢量系Si，若 存在着,ij,称该矢量为正交矢量系,显然
11、，在n维设计空间里，单位坐标矢量系：e1，e2en 为正交矢量系,若矢量系S1，S2Sn对于对称正定矩阵A共轭，则它 必为线性独立（线性无关）矢量系。对于n维设计空间而言， 线性独立矢量系中的矢量个数不能超过维数n，即共轭矢量 系中矢量个数最多等于n。,对于矢量系的线性独立问题简述如下:,设有非零矢量系：S1，S2Sn，若存在一组不全为 零的实数1， 2， n，使,成立，则该矢量系称为线性相关矢量系。,如果只有在 1= 2= n=0，即系数全部为零才有 上式成立，则该矢量系为线性独立矢量系,在式线性相关矢量系中，若某矢量Si的系数 i0， 则可写成,可知，线性相关矢量系中Si可表示为其余矢量的
12、线性组合。,任意两个矢量S1与S2，如果它们是共线的，则矢量S1 与S2必线性相关。因为对于共线两矢量S1与S2，一定可以 找到系数 1与 2，使,在二维平面里，由三个及三个以上的矢量组成的矢量系 ，也必定是线性相关的。例如二维平面的三个矢量,取一组系数 1=1， 2=1/4， 3=1，使,矢量系Si（i=1，2，3）是线性相关的，由下图说明,将S3用S1与S2的线性组合表示为,可见，同一平面上任意三个矢量必定线性相关。,在三维空间里的三个矢量，只要他们不共面，则必线性独 立；若三维空间中有任意四个矢量，则矢量系必线性相关。,可以得出结论：,当矢量系中矢量的数目超过 设计空间的维数时，矢量系必
13、线 性相关 非零矢量构成的正交矢量系 必线性独立。正交矢量系中矢量 的数目不能超过矢量系所在的空 间的维数,三、关于二次收敛性问题,对于二元二次正定函数F（x），取一组共轭矢量S1与 S2，其中矢量之一通过等值曲线中心。,二元二次正定目标函数的等值线为一组同心的椭圆，其 中心是函数的极小点。 按共轭方向的性质： 任意做两条平行线，与椭圆组中 的两椭圆切于,点 ， 该两点 必通过椭圆的中心；或者说，过 椭圆中心做任意直线与任意两个 椭圆相交，通过交点作椭圆切线 必互相平行,对以上结论的证明：,为简化，设目标函数为二次齐次函数，等值线中心在坐 标原点。,展开,函数值分别为d1，d2的两条等值线，方
14、程为：,等值线任意点切线斜率为 ，可对上式求导而得，,则切线斜率为,过点,椭圆切线斜率分别记为,K1，k2，则有：,当所引的两条直线平行，且切于等值线（椭圆)于点 , ,则该两条切线斜率相等，k1=k2，即,分别将切点 与坐标原点相连接，两直线ox1，ox2 的斜率分别记为,如果有 ，说明两点连线必通过坐标原点o（椭圆中心） 将式写成,或,将上式展开整理后得,由于函数F（x1，x2）是二次齐次函数，图形为椭圆，所以 ，则必有 。 由此证明得出，点 ， 连线必定通过椭圆中心点o。,若在切于椭圆的直线上取方向S1，连接两个切点 ， 为方向S2，则S1，S2为共轭方向。如果从某任意初始点 出发，依次
15、沿方向S1，S2做两次一维搜索，即可达到椭圆 中心此函数F（x）的极小点。,对于一般的二元二次正定函数 ， 按其共轭方向进行两次搜索也必定达到函数的极小点。此情 况目标函数等值线仍是椭圆，但其中心不在坐标原点。,二次收敛性是指一种算法，如果对于二次正定函数，从理论 上只要进行有限次一维搜索，就可以达到理论极小点，把这种算 法称为具有二阶收敛性（二次收敛性）或有限步收敛法。,对于一般的n元二次正定函数F（x），依次按共轭矢量系 （S1，S2Sn）中各矢量方向进行n维一次搜索，就可达等值 线（椭圆）中心理论极小值点。,例题2：设二维目标函数 ，给定方向S1=e1，,初始点 。求与S1相共轭的S2，并求函数的极小点。,解：,第一个搜索方向 。,函数的海塞矩阵 对称正定。,可知函数F（x）为二次正定函数，如果按共轭方向S1， S2，进行两次一维搜索就达到目标函数的极小点x*。,从 点沿S1方向求极小点 ，即,沿S1 方向,则,任取初始点 ，沿S1方向一维搜索求得该方向极小,点 按的做法,求与S1相共轭的方向S2,核验计算,矢量S1与S2为对A矩阵共轭, 从 点出发，沿S2方向作一维搜索， 得极小点,如右图所示。,