《《优化理论基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《优化理论基础》PPT课件.ppt（169页珍藏版）》请在三一办公上搜索。
1、2023年7月9日星期日,1,第3章 优化设计理论基础,2023年7月9日星期日,2,2023年7月9日星期日,3,2023年7月9日星期日,4,2023年7月9日星期日,5,2023年7月9日星期日,6,2023年7月9日星期日,7,二维无约束最优化设计问题几何意义,2023年7月9日星期日,8,2023年7月9日星期日,9,2023年7月9日星期日,10,2023年7月9日星期日,11,2023年7月9日星期日,12,2023年7月9日星期日,13,2023年7月9日星期日,14,2023年7月9日星期日,15,2023年7月9日星期日,16,二维目标函数等值线形态分析,2023年7月9日
2、星期日,17,2023年7月9日星期日,18,3-2 约束最优解和无约束最优解,二维优化问题进行几何描述,例 对二维优化问题进行几何描述。,2023年7月9日星期日,19,约束线、可行域、目标函数等值线、约束极值点,几何意义上来说明约束最优解和无约束最优解,设已知目标函数f(X)=x12+x22-4x1+4，受约束于g1(X)=x1-x2+20 g2(X)=x1 0 g3(X)=x2 0 g4(X)=-x12+x2-1 0 求其最优解X*和f(X*)。,2023年7月9日星期日,20,2023年7月9日星期日,21,2023年7月9日星期日,22,3-3 局部最优解和全域最优解,2023年7月
3、9日星期日,23,2023年7月9日星期日,24,X2*,X1*,f(X),x2,x1,2023年7月9日星期日,25,2023年7月9日星期日,26,2023年7月9日星期日,27,2023年7月9日星期日,28,3-4 无约束目标函数的极值点存在条件,一、函数的极值与极值点以一元函数为例说明函数的极值与极值点。如图所示为定义在区间 a，b上的一元函数f(X),2023年7月9日星期日,29,2023年7月9日星期日,30,图上有两个特殊点x(1)与x(2)在x(1)附近，函数f(x)的值以f(x(1)为最大；在x(2)附近，函数值以f(x(2)为最小。,2023年7月9日星期日,31,因此
4、x(1)与x(2)即为函数的极大点与极小点，统称为函数f(x)的极值点。f(x(1)与f(x(2)相应地为函数的极大值与极小值，统称为函数f(x)的极值。,2023年7月9日星期日,32,需要注意，这里所谓极值是相对于点的附近邻域各点而言的，仅具有局部的性质，所以这种极值又称为局部极值。,2023年7月9日星期日,33,函数的最大值与最小值是指整个区间而言的。如图中函数的最大值为f(b)，函数的最小值为f(a)。函数的极值并不一定是最大值或最小值。,2023年7月9日星期日,34,二、极值点存在的条件(一)一元函数(即单变量函数)的情况(1)极值点存在的必要条件,2023年7月9日星期日,35
5、,在高等数学中已经学过：如果函数f(x)的一阶导数f(x)存在，则欲使x*为极值点的必要条件为：f(x*)0,2023年7月9日星期日,36,仍以图中所示一元函数为例，由图可见，在x(1)与x(2)处的f(x(1)与f(x(2)均等于零，即函数在该两点处的切线与x轴平行。但使f(x)0的点并不一定都是极值点。,2023年7月9日星期日,37,2023年7月9日星期日,38,使函数f(x)的一阶导数f(x)0的点称为函数的驻点。极值点(对存在导数的函数)必为驻点驻点不一定是极值点驻点是否为极值点可以通过二阶导数f(x)来判断。,2023年7月9日星期日,39,(2)极值点存在的充分条件,若在驻点
6、附近 f(x)0则该点为极大点；若在驻点附近 f(x)0则该点为极小点。,2023年7月9日星期日,40,在图中的x(3)附近，其右侧f(x)0，但其左侧f(x)0，因此它不是极值点。可见，函数二阶导数的符号成为判断极值点的充分条件。,2023年7月9日星期日,41,函数的偏导数偏导数是指在某坐标轴方向函数值的变化率连续可微的 n 维函数 f(X)=f(x1,x2,xn)，在点 X(K)=x1(K),x2(K),xn(K)T的一阶偏导数表示为，,三、多元函数的方向导数、梯度和赫赛矩阵,函数的梯度,n维函数的梯度是函数各维一阶偏导数组成的向量,2023年7月9日星期日,43,梯度的模是函数各维一
7、阶偏导数平方和的开方梯度与它的模的比值称为梯度的单位向量,2023年7月9日星期日,44,函数梯度的性质,1、函数的梯度f(X(K)是函数在点X(K)的最速上升方向，而负梯度-f(X(K)是函数在点X(K)的最快下降方向。函数的梯度随着点 X(K)在设计空间的位置不同而异，这只是反映了函数在点X(K)邻域内函数的局部性质。,2023年7月9日星期日,45,2、函数梯度的模 是在点X(K)函数变化率的最大值。3、函数的梯度f(X(K)与在点X(K)的函数等值面正交。与点X(K)的函数等值面相切方向的函数变化率为零。,2023年7月9日星期日,46,2023年7月9日星期日,47,2023年7月9
8、日星期日,48,注意，函数f(X)在某点X(K)的梯度向量f(X(K)仅反映f(X)在点X(K)附近极小邻域的性质因而是一种局部性质。函数在定义域内的各点都各自对应着一个确定的梯度。,函数的赫森矩阵,函数的二阶偏导数矩阵它是一个nn阶的对称矩阵,2023年7月9日星期日,49,赫森矩阵正定和负定的判定,如果赫森矩阵行列式各阶主子式全部大于零，即,2023年7月9日星期日,50,则它是正定的。如果各阶主子式是相间的一负一正，则它是负定的。,2023年7月9日星期日,51,设f(x)为定义在XDRn中的n元函数。向量X的分量x1,x2,xn，就是函数的自变量。设x(k)为定义域内的个点，且在该点有
9、连续的n1阶偏导数，则在该点附近可用泰勒级数展开，如取到二次项,2023年7月9日星期日,52,多元函数的极值条件,2023年7月9日星期日,53,如用向量矩阵形式表示，则上式可写为,2023年7月9日星期日,54,可简写为,2023年7月9日星期日,55,式中,2023年7月9日星期日,56,f(X(k)是函数f(X)在点X(k)的一阶偏导数矩阵，称为函数在该点的梯度。,2f(X(k)是函数f(X)在点X(k)的二阶偏导数组成的，nn阶对称矩阵，或称为f(X(k)的赫森(Hessian)矩阵，记作H(X(k)。,2023年7月9日星期日,57,公式中只取到泰勒级数二次项，称为函数的二次近似表
10、达式。极值点存在的必要条件。n元函数在定义域内极值点X*存在的必要条件,2023年7月9日星期日,58,即对每一个变量的一阶偏导数值必须为零，或者说梯度为零(n维零向量)。与一元函数对应，满足梯度为零只是多元函数极值点存在的必要条件，而并非充分条件；,2023年7月9日星期日,59,满足f(X*)的点X*称为驻点驻点是否为极值点，尚须通过二阶偏导数矩阵来判断。,2023年7月9日星期日,60,极值点存在充分条件,如何判断多元函数的一个驻点是否为极值点呢?将多元函数f(X)在驻点X*附近用泰勒公式的二次式近似地表示，则由式得,2023年7月9日星期日,61,由X*为驻点，f(X*)=0，于是有,
11、2023年7月9日星期日,62,在X*点附近的邻域内，若对一切的X恒有,亦即,2023年7月9日星期日,63,则X*为极小点,否则，当恒有,则X*为极大点,根据矩阵理论知，由式得极小点的充分条件为：,2023年7月9日星期日,64,亦即驻点赫森矩阵H(X*)必须为正定,同理知极大点的充分条件为：,2023年7月9日星期日,65,亦即驻点赫森矩阵H(X*)必须为负定。,而当,2023年7月9日星期日,66,亦即驻点赫森矩阵H(X*)既非正定，又非负定，而是不定，f(X)在X*处无极值。,至于对称矩阵正定、负定的检验，由线性代数可知：对称矩阵,2023年7月9日星期日,67,正定的条件是它的行列式
12、|A|的顺序主子式全部大于零，即,2023年7月9日星期日,68,负定的条件是它的行列式|A|中一串主子式为相间的一负一正的，即,2023年7月9日星期日,69,至此，完全不难自行归纳得出无约束目标函数极值点存在的充分必要条件和用数学分析作为工具对n维无约束优化问题寻求最优解。,2023年7月9日星期日,70,无约束目标函数的极值条件,必要条件：在点X*=x1*,x2*,xn*T的一阶偏导数为零（即梯度向量为零向量）,2023年7月9日星期日,71,充分条件：如果它的二阶偏导数矩阵（即赫森矩阵）是负定的，则为极大点；如果它的二阶偏导数矩阵是正定的，则为极小点。,2023年7月9日星期日,72,
13、求三维函数的极值点。,解：根据三维函数存在极值的必要条件，令梯度为零,2023年7月9日星期日,73,联解得到,2023年7月9日星期日,74,计算点 的赫森矩阵 赫森矩阵行列式各阶主子式,2023年7月9日星期日,75,2023年7月9日星期日,76,赫森矩阵是正定的，是极小点。对应的目标函数值,2023年7月9日星期日,77,2023年7月9日星期日,78,3-5 函数的凸性,2023年7月9日星期日,79,一、凸集与非凸集,设D为n维欧氏空间中设计点X的一个集合，若其中任意两点x(1)和x(2)的连线都在集合中，则称这种集合是n维欧氏空间的一个凸集。二维函数的情况如图所示，其中图(a)为
14、凸集，图(b)为非凸集,2023年7月9日星期日,80,2023年7月9日星期日,81,2023年7月9日星期日,82,2023年7月9日星期日,83,二、凸函数,2023年7月9日星期日,84,用一元函数来说明函数的凸性。如图所示，图(a)在x(1)、x(2)区间曲线为下凸的，图(b)的曲线是上凸的，它们的极值点(极小点或极大点)在区间内都是唯一的。这样的函数称为具有凸性的函数，或称为单峰函数。,2023年7月9日星期日,85,2023年7月9日星期日,86,2023年7月9日星期日,87,现用上图所示定义于区间a,b的单变量函数来说明这一概念。若连接函数曲线上任意两点的直线段，某一点x(k
15、)的函数值恒低于此直线段上相应的纵坐标值时，这种函数就是凸函数，也就是单峰函数。,2023年7月9日星期日,88,若将式 中的符号“”改为“”则称函数f(X)为严格凸函数。,2023年7月9日星期日,89,2023年7月9日星期日,90,若将式 中的符号“”改为“”，函数曲线上凸(有极大点)通常称为凹函数。显然，若为凸函数，则-f(X)凹函数。,2023年7月9日星期日,91,三、凸函数的基本性质,1）若函数f1(X)和f2(X)为凸集上的两个凸函数，对任意正数a和bf(X)af1(X)+bf2(X)仍为D集上的凸函数；,2023年7月9日星期日,92,2)若X(1)与X(2)为凸函数f(X)
16、中的两个最小点，则其连线上的一切点也都是f(X)的最小点。,2023年7月9日星期日,93,四、凸函数的判定,判别法1：若函数f(X)在D上具有连续一阶导数，而D为D1内部的一个凸集，则f(X)为D上的凸函数的充分必要条件为：对任意的X(1)与X(2)，恒有,2023年7月9日星期日,94,判别法2：若函数f(X)在凸集D上存在二阶导数并且连续时，对f(X)在D上为凸函数的充分必要条件为：对于任意的XD，f(X)的赫森矩阵H(X)处处是正半定矩阵。,2023年7月9日星期日,95,若赫森矩阵H(X)对一切XD都是正定的，则f(X)是D上的严格凸函数，反之不一定成立。,2023年7月9日星期日,
17、96,五、函数的凸性与局部极值及全域最优值之间的关系,设f(X)为定义在凸集D上的一个函数，一般来说，f(X)的极值点不一定是它的最优点。但是，若f(X)为凸集D上的一个凸函数，则f(X)的任何极值点，同时也是它的最优点。若f(X)还是严格凸函数，则它有唯一的最优点。,2023年7月9日星期日,97,六 约束极值点存在条件,1 有约束的极值问题,2023年7月9日星期日,98,gi(X)0不等式约束，hj(X)=0等式约束,2023年7月9日星期日,99,在约束条件下求得的函数极值点，称为约束极值点。,2 不等式约束问题的一阶最优性条件,2023年7月9日星期日,100,起作用约束不起作用约束
18、,2023年7月9日星期日,101,起作用约束下标集合用I表示,2023年7月9日星期日,102,或,在优化实用计算中常需判断和检查某个可行点是否约束极值点，这通常借助于库恩-塔克(KuhnTucker)条件(简称K-T条件)来进行。,2023年7月9日星期日,103,K-T条件可阐述为：如果X(k)是一个局部极小点，则该点的目标函数梯度f(X(k)可表示成该点诸约束面梯度gi(X(k)的如下线性组合：gi(iI)在X(k)处可微；gi(iI)在X(k)处连续；gi(X(k)(iI)线性无关,2023年7月9日星期日,104,2023年7月9日星期日,105,gi(iI)在X(k)处也可微，可
19、写成等价形式,iI时，gi0，wi0iI时，gi=0，对wi无限制wi g(X(k)=0，i=1，2，m称为互补松弛条件；wi 0，i=1，2，m，亦称拉格朗日乘子。,2023年7月9日星期日,106,等式约束性问题的最优性条件几何意义是明显的：考虑一个约束的情况：最优性条件即：,2023年7月9日星期日,107,3 一般约束问题的一阶最优性条件,2023年7月9日星期日,108,如果x*是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：,2023年7月9日星期日,109,g1(x*)=0,g1为起作用约束,K-T条件可阐述为：如果X(k)是一个局部极小点，则该点的
20、目标函数梯度f(X(k)可表示成该点诸约束面梯度gi(X(k)的如下线性组合：f、gi(iI)在X(k)处可微gi(iI)在X(k)处连续hj(X(k)(j=1，2，l)在X(k)处连续可微,2023年7月9日星期日,110,2023年7月9日星期日,111,gi(iI)在X(k)处也可微，可写成等价形式,2023年7月9日星期日,112,wi g(X（k）)=0，i=1，2，m仍称为互补松弛条件,可以对K-T条件用图形来说明。如果X(k)是一个局部极小点，则该点的目标函数梯度f(X(k)应落在该点诸约束面梯度gi(X(k)、hj(X(k)在设计空间所组成的锥角范围内。,2023年7月9日星期
21、日,113,2023年7月9日星期日,114,如图所示，图(a)中设计点X(k)不是约束极值点，图(b)的设计点X(k)是约束极值点。,2023年7月9日星期日,115,2023年7月9日星期日,116,用K-T条件求解：,2023年7月9日星期日,117,2023年7月9日星期日,118,可能的K-T点出现在下列情况：两约束曲线的交点：g1与g2，g1与g3，g1与g4，g2与g3，g2与g4，g3与g4。目标函数与一条曲线相交的情况：g1，g2，g3，g4 对每一个情况求得满足K-T条件的点(x1，x2)T及乘子w1，w2，w3，w4，且wi 0时，即为一个K-T点。,2023年7月9日星
22、期日,119,下面举几个情况：g1与g2交点：x=(2,1)TS，I=1,2 则w3=w4=0 解,2023年7月9日星期日,120,2023年7月9日星期日,121,2023年7月9日星期日,122,2023年7月9日星期日,123,七 最优化设计的数值计算迭代方法,无约束优化问题和约束优化问题当其数学模型确定以后求其最优解，实质上都属于目标函数的极值问题。两者的优化求解方法联系紧密，其中无约束优化方法又是优化方法中最基本的方法。,2023年7月9日星期日,124,迭代算法的概念 迭代法是一种重要的逐次逼近的方法。这种方法用某个固定格式反复计算和校正所求问题的近似解（如方程的根、函数的极值点
23、等），使之逐次精确化，最后得到满足精度要求的结果。,求一维方程 在 附近的一个根。,解：可将方程改写为下列形式 用所给的初始值 近似代入上式的右端得到第一个近似解 由于 和 有较大偏差，再将 作为初始值，并且重复上面的计算步骤，如此继续下去。这种逐步逼近的过程称作迭代过程。,2023年7月9日星期日,126,该例求解该一维方程迭代格式是随着迭代次数逐渐增大，直至相邻两次迭代点 的偏差小于预先给定的精度值为止。,2023年7月9日星期日,127,无约束最优化算法，每次迭代都按选定方向S和一合适的步长向前搜索，可以写出迭代过程逐次搜索新点的向量方程式,2023年7月9日星期日,128,迭代过程的每
24、一步向量方程式，都可写成如下的迭代格式,2023年7月9日星期日,129,式中：X(k)第k步迭代的出发点；X(k+1)第k步迭代产生出的新点；S(k)是向量，代表第k步迭代的前进方向(或称搜索方向)；,(k)是标量，代表第k步沿S(k)方向的迭代步长(或称步长因子)。在一系列的迭代计算k=1,2,过程中，产生一系列的迭代点(点列)X(0)，X(1)，X(k)，X(k+1)。为实现极小化，目标函数的值应一次比一次减小，即,2023年7月9日星期日,130,f(X(0)f(X(1)f(X(k)f(X(k1)直至迭代计算满足一定的精度时，则认为目标函数值近似收敛于其理论极小值。,2023年7月9日
25、星期日,131,2023年7月9日星期日,132,优化迭代算法的分类,搜索算法是一种迭代算法，搜索方向和步长因子构成了每一次迭代的修正量，表明它们是决定算法好坏的重要因素。在搜索方向上，使目标函数取得极小值的步长因子，称为该方向上最优步长因子。在优化设计中，求解最优步长因子主要采用数值解法，即利用计算机通过反复的迭代计算，求解出最优步长因子的近似值。目前已有很多优化方法，各种方法的区别就在于确定方向和步长因子的方法不同。,2023年7月9日星期日,133,1、直接搜索法 这种方法只需要进行函数值的计算与比较来确定优化的方向和步长。例如一维搜索中的黄金分割法、二次插值法等，在多维问题中的随机方向
26、法、共轭方向法和复合形法等。,2023年7月9日星期日,134,2、间接搜索法 这种方法需要利用函数的一阶或二阶偏导数矩阵来确定优化方向和步长，例如梯度法以负梯度矢量方向为搜索方向，就需要计算函数的一阶偏导数矩阵。牛顿法则同时需要求出目标函数的一阶偏导数矩阵和二阶偏导数矩阵的逆阵才能确定迭代方向和步长。,2023年7月9日星期日,135,数值计算迭代方法：直接从目标函数f(X)出发，构造一种使目标函数值逐次下降逼近，利用计算机进行迭代格式一步步搜索、调优并最后逼近到函数极值点或达到最优点,2023年7月9日星期日,136,根据确定搜索方向和步长的方法不同，数值计算寻优可有许多方法，但其共同点是
27、：1)要具有简单的逻辑结构并能进行同一迭代格式的反复的运算：,2023年7月9日星期日,137,2)这种计算方法所取得的结果不是理论精确解，而是近似解.其精度是可以根据需要加以控制的。,2023年7月9日星期日,138,一、迭代法的基本思想及其格式迭代法是适应于计算机工作特点的一种数值计算方法。其基本思想是：在设计空间从一个初始设计点X(0)开始，应用某一规定的算法，沿某一方向S(0)和步长(0)产生改进设计的新点X(1)，使得f(X(1)f(X(0)，,2023年7月9日星期日,139,然后再从点X(1)开始，仍应用同一算法，沿某一方向S(1)和步长(1)，产生又有改进的设计新点X(2)，使
28、得f(X(2)f(X(1)，这样一步一步地搜索下去。,2023年7月9日星期日,140,使目标函数值步步下降，直至得到满足所规定精度要求的、逼近理论极小点的X*点为止。这种寻找最优点的反复过程称为数值迭代过程。下图为二维无约束最优化迭代过程示意图,2023年7月9日星期日,141,2023年7月9日星期日,142,二、迭代计算的终止准则,希望迭代过程进行到最终迭代点到达理论极小点或者使最终迭代点与理论极小点之间的距离足够小到允许的精度才终止迭代。,2023年7月9日星期日,143,实际上对于一个待求的优化问题，其理论极小点并不知道。只能从迭代过程获得的迭代点序列X(0)，X(1)，X(k)，X
29、(k+1)，所提供的信息,2023年7月9日星期日,144,根据一定的准则判断出已取得足够精确的近似极小点时，迭代即可终止。最后所得的点即认为是接近理论极小点的近似极小点。对无约束最优化问题常用的迭代过程终止准则一般有以下几种。,2023年7月9日星期日,145,1)点距准则 当相邻两迭代点 X(k)，X(k+1)之间的距离已达到充分小时，即小于或等于规定的某一很小正数时，迭代终止。,2023年7月9日星期日,146,一般用两个迭代点向量差的模来表示，即,也可用迭代点在各个坐标轴上的分量来表示,2023年7月9日星期日,147,2)函数下降量准则 当相邻两迭代点X(k)，X(k+1)的目标函数
30、值的下降量已达到充分小时，即小于或等于规定的某一很小正数时，迭代终止。,2023年7月9日星期日,148,一般用目标函数值下降量的绝对值来表示，即,2023年7月9日星期日,149,当|f(X(k)|1,或用目标函数值下降量的相对值来表示，即,2023年7月9日星期日,150,当|f(X(k)|1,3)梯度准则 当目标函数在迭代点X(k)的梯度已达到充分小时，即小于或等于规定的某一很小正数时，迭代终止；一般用梯度向量的模来表示，即,2023年7月9日星期日,151,根据不同的优化方法和具体设计问题对精度的要求而定。一般来说，这几个迭代过程终止准则都分别在某种意义上反映了逼近极值点的程度，满足其
31、中任一个迭代终止准则，都可以认为目标函数f(X(k+1)收敛于函数f(X)的极小值,2023年7月9日星期日,152,上列几种迭代终止准则,除梯度准则仅用于那些需要计算目标函数梯度的最优化方法中外，其余并无特别规定必须选用哪一种。,2023年7月9日星期日,153,有时为了防止函数变化剧烈点距准则失效(见图(a)或当函数变化缓慢时函数下降量准则失效(见图(b)，这时往往将点距准则和函数下降量准则结合起来，使同时成立迭代终止准则并不限于上列几种,2023年7月9日星期日,154,说明,2023年7月9日星期日,155,2023年7月9日星期日,156,求解 的极值点和极值。解：的极值点必须满足,
32、解此联立方程得：x1=1,x2=1,x3=-2,即点X=1,1,-2T为一驻点。再利用赫森矩阵H(X*)的性质来判断此驻点是否为极值点。对各变量求二阶偏导数：写出驻点的赫森矩阵,2023年7月9日星期日,157,2023年7月9日星期日,158,将H(X*)记作,2023年7月9日星期日,159,2023年7月9日星期日,160,；,因此，赫森矩阵H(X*)为正定的，驻点X=1,1,-2T为极小点。对应于该极小点的函数极小值,2023年7月9日星期日,161,2 判别函数 在 上是否为凸函数。,2023年7月9日星期日,162,解：利用赫森矩阵来判别：,2023年7月9日星期日,163,因此赫
33、森矩阵是正定的，故f(x)为严格凸函数,3 用K-T条件检验点X(k)=2,0T。是否为目标函数：f(X)=(x1-3)2+x22在不等式约束：g1(X)=4-x12-x20，g2(X)=x20，g3(X)=x1-0.50条件下的约束最优点解：(1)计算点X(k)的诸约束函数值,2023年7月9日星期日,164,2023年7月9日星期日,165,X(k)点是可行点，该点起作用的约束函数是g1(X)和g2(X)(2)求X(k)点的有关诸梯度,2023年7月9日星期日,166,2023年7月9日星期日,167,(3)代入下式，求拉格朗日乘子,2023年7月9日星期日,168,写成线性方程组,解得：1=2=0.5，乘子均为非负，故满足K-T条件，即点为约束极值点。而且，由于是凸函数，可行域为凸集，所以点X(k)也是约束最优点。,2023年7月9日星期日,169,
