二章优化设计的理论与数学基础.ppt

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