【教学课件】第二章优化设计的理论与数学基础.ppt

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