32优化理论基础.pptx

24 四月 202413-1 优化设计问题的几何意义优化设计问题的几何意义一、目标函数的等值面一、目标函数的等值面(线线)n维变量的目标函数，其函数图象只能在维变量的目标函数，其函数图象只能在n+1维维空间中描述出来空间中描述出来 第第3章章 优化设计理论基础优化设计理论基础 24 四月 20242二维无约束最优化设计二维无约束最优化设计24 四月 20243给定一个设计方案，即给定给定一个设计方案，即给定一组一组 x1,x2,xn的值时的值时目标函数目标函数 f(X)=f(x1,x2,xn)必相应有一确定的函数值必相应有一确定的函数值24 四月 20244有无限多组值有无限多组值x1,x2,xn与之对应与之对应 X=x1,x2,xnT在设计在设计空间中对应有一个点集空间中对应有一个点集给定一个给定一个 f(X)该点集是一个曲面该点集是一个曲面(二维是二维是曲线，大于三维称超曲面曲线，大于三维称超曲面)当当f(X)=a时时目标函数的目标函数的等值面（线）等值面（线）24 四月 20245f(X(1)=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2)=a2X(2)=x1(2),x2(2)X(1)=x1(1),x2(1)Of(X)x2x1X*24 四月 20246即即a=a1,a2,an时时f(X)=a1,a2,an 给定一系给定一系列的列的a值值该组超曲面族该组超曲面族一组超一组超曲面族曲面族等值面族等值面族24 四月 20247等值面特性等值面特性即在一个特定的等值面上，尽管即在一个特定的等值面上，尽管设计方案很多，但每一个设计方设计方案很多，但每一个设计方案的目标函数值都是相等的。案的目标函数值都是相等的。二维无约束最优化设计问题几何意义二维无约束最优化设计问题几何意义以以x1,x2和和f(X)为坐标为坐标f(X)=f(x1,x2)为沿轴为沿轴方向的高度方向的高度等值线等值线是是等值面等值面在二维在二维设计空间中的特定形态设计空间中的特定形态f(X(1)=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2)=a2X(2)=x1(2),x2(2)X(1)=x1(1),x2(1)Of(X)x2x1X*24 四月 2024824 四月 20249当给定一系列不同的当给定一系列不同的a值时，可值时，可以得到一组平面曲线：以得到一组平面曲线：f(X)=f(x1,x2)=a1f(X)=f(x1,x2)=a2 这组曲线构成目标函数的这组曲线构成目标函数的等值等值线族线族等值线族等值线族24 四月 202410等值线的分布反映目标函数值的变化等值线的分布反映目标函数值的变化等值线越向里，目标函数值越小等值线越向里，目标函数值越小有中心的曲线族有中心的曲线族目标函数的无约束极小点就是等值线族的一目标函数的无约束极小点就是等值线族的一个共同中心个共同中心X*24 四月 202411几何意义几何意义-求目标函数无约求目标函数无约束极小点也就是求其等值线族的束极小点也就是求其等值线族的共同中心。共同中心。由二维设计空间等值线的讨论，由二维设计空间等值线的讨论，可推广到分析多维问题。可推广到分析多维问题。24 四月 202412注意，对于三维问题在注意，对于三维问题在设计空间中是设计空间中是等值面等值面高于三维的问题在设计高于三维的问题在设计空间中则是空间中则是等值超曲面等值超曲面24 四月 202413例例 二维约束优化问题二维约束优化问题x1x2f(x)f(x)g(x)g1(x)g2(x)O24 四月 202414二维目标函数二维目标函数等值线族等值线族 以点以点(2，0)为圆心，以为半径的一族同心圆为圆心，以为半径的一族同心圆 24 四月 202415x2x1X*1g4(X)g3(X)g1(X)g1(X)X*20.25f(X)=12.253.846.25f(X)=912123O24 四月 202416等值面（线）的形状及其分布规律等值面（线）的形状及其分布规律对于目标函数极小化问题，愈靠近极值点对于目标函数极小化问题，愈靠近极值点的等值面（线）所代表的目标函数值愈小；的等值面（线）所代表的目标函数值愈小；在极值点附近的等值线呈现椭圆形状，其在极值点附近的等值线呈现椭圆形状，其中心就是极值点；中心就是极值点；在等值线较稠密的部位，目标函数值变化在等值线较稠密的部位，目标函数值变化愈迅速；愈迅速；目标函数的非线性程度愈严重，其等值线目标函数的非线性程度愈严重，其等值线的形状愈复杂，且可能存在多个极值点。的形状愈复杂，且可能存在多个极值点。二维目标函数等值线形态分析二维目标函数等值线形态分析24 四月 202417X 1*x1x201123X 2*X 3*x1x20 12323456X 1*24 四月 202418最优点就是目标函数的极值点最优点就是目标函数的极值点实际上就是目标函数等值线的中心实际上就是目标函数等值线的中心 最优点往往是目标函数等值超曲面与约束超曲面的一个最优点往往是目标函数等值超曲面与约束超曲面的一个切点切点而且可能在两个以上约束超曲面的交集上而且可能在两个以上约束超曲面的交集上无约束无约束最优化最优化无论在数学模型还是几何意义上，两者均是不无论在数学模型还是几何意义上，两者均是不同的概念。同的概念。约束约束最优化最优化区别区别3-2 约束最优解和无约束最优解约束最优解和无约束最优解 二维优化问题进行几何描述二维优化问题进行几何描述n例例 对二维优化问题对二维优化问题进行几何描述进行几何描述。24 四月 202419约束线、可行域、目标函约束线、可行域、目标函数等值线、约束极值点数等值线、约束极值点213x221-1-2-3-1-2-4-5x1f(X)X*g1(X)g2(X)0几何意义上来说明约束最优解和无约束最优解几何意义上来说明约束最优解和无约束最优解n设已知目标函数设已知目标函数f(X)=x12+x22-4x1+4，受约受约束于束于g1(X)=x1-x2+2 0 g2(X)=x1 0 g3(X)=x2 0 g4(X)=-x12+x2-1 0 求其最优解求其最优解X*和和f(X*)。24 四月 20242024 四月 202421x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值线6.2543.810.251234O-212X*(1)X*(2)(b)(a)D24 四月 202422二维问题关于约束最优解和无约束最优解几何意义的讨论同样二维问题关于约束最优解和无约束最优解几何意义的讨论同样可推广到高维问题可推广到高维问题n个设计变量个设计变量x1,x2,xn，组成设计空间。在这个空间中的每一，组成设计空间。在这个空间中的每一个点代表一个设计方案，此时个点代表一个设计方案，此时n个变量具有确定的值。个变量具有确定的值。3-3 局部最优解和全域最优解局部最优解和全域最优解 24 四月 202423目标函数不是单峰函数目标函数不是单峰函数有多个极值点有多个极值点X1*,X2*,24 四月 202424X2*X1*f(X)x2x124 四月 202425X1*和和f(X1*)、X2*和和f(X2*)目标函数值是全区域中目标函数值是全区域中所有局部最优解中的最所有局部最优解中的最小者对应的解小者对应的解局部最优解局部最优解全域最优解全域最优解24 四月 202426如图，目标函数如图，目标函数f(X)的等值线绘于图上，有两个不等式约束的等值线绘于图上，有两个不等式约束g1(X)0,g2(X)0构成两个可行域构成两个可行域D1和和D2。24 四月 202427X1*、f(X1*)X2*、f(X2*)X3*、f(X3*)均称均称局部最优解局部最优解。由于由于f(X1*(1)f(X2*(2)f(X3*(3)可知可知X3*(3)为全域极为全域极小点，亦即小点，亦即X3*(3)和和f(X3*(3)为为全域最优解全域最优解。局部最优解局部最优解全域最优解全域最优解24 四月 202428求出全域最优解求出全域最优解只能求出局部最优解只能求出局部最优解期望期望局部最优解之间比较，取最小的一局部最优解之间比较，取最小的一个个实际措施3-4 无约束目标函数的极值点存在条件无约束目标函数的极值点存在条件 一、函数的极值与极值点一、函数的极值与极值点以一元函数为例说明函数的极值与极值点。以一元函数为例说明函数的极值与极值点。如图所示为定义在区间如图所示为定义在区间 a，b上的一元函数上的一元函数f(X)24 四月 20242924 四月 202430f(x)xf(a)f(x(1)f(x(2)x(1)f(x(3)f(b)x(3)x(2)abn 图上有两个特殊点图上有两个特殊点x(1)与与x(2)n在在x(1)附近，函数附近，函数f(x)的值以的值以f(x(1)为最大；为最大；n在在x(2)附近，函数值以附近，函数值以f(x(2)为最小。为最小。24 四月 202431n因因此此x(1)与与x(2)即即为为函函数数的的极极大大点点与与极极小小点点，统称为函数统称为函数f(x)的极值点。的极值点。nf(x(1)与与f(x(2)相应地为函数的极大值与极相应地为函数的极大值与极小值，统称为函数小值，统称为函数f(x)的极值。的极值。24 四月 202432n需要注意，这里所谓需要注意，这里所谓极值极值是相对于是相对于点点的附近邻域各点而言的，仅具有局部的的附近邻域各点而言的，仅具有局部的性质，所以这种极值又称为性质，所以这种极值又称为局部极值局部极值。24 四月 202433n函数的最大值与最小值是指整个区间而函数的最大值与最小值是指整个区间而言的。言的。n如图中函数的最大值为如图中函数的最大值为f(b)，函数的最小，函数的最小值为值为f(a)。函数的极值并不一定是最大值。函数的极值并不一定是最大值或最小值。或最小值。24 四月 202434二、极值点存在的条件二、极值点存在的条件 (一一)一元函数一元函数(即单变量函数即单变量函数)的情况的情况 (1)极值点存在的必要条件极值点存在的必要条件24 四月 202435在高等数学中已经学过：如果函数在高等数学中已经学过：如果函数f(x)的一的一阶导数阶导数f(x)存在，则欲使存在，则欲使x*为极值点的必为极值点的必要条件为：要条件为：f(x*)024 四月 202436仍以图中所示一元函数为例，由图可见，仍以图中所示一元函数为例，由图可见，在在x(1)与与x(2)处的处的f(x(1)与与f(x(2)均等于零，均等于零，即函数在该两点处的切线与即函数在该两点处的切线与x轴平行。但轴平行。但使使f(x)0的点并不一定都是极值点。的点并不一定都是极值点。24 四月 20243724 四月 202438f(x)xf(a)f(x(1)fx(2)x(1)f(x(3)f(b)x(3)x(2)abn使使函函数数f(x)的的一一阶阶导导数数f(x)0的的点点称称为为函数的函数的驻点驻点。n极值点极值点(对存在导数的函数对存在导数的函数)必为驻点必为驻点n驻点不一定是极值点驻点不一定是极值点n驻驻点点是是否否为为极极值值点点可可以以通通过过二二阶阶导导数数f(x)来判断。来判断。24 四月 202439(2)极值点存在的充分条件极值点存在的充分条件 n若在驻点附近若在驻点附近 f(x)0则该点为极大点；则该点为极大点；若在驻点附近若在驻点附近 f(x)0则该点为极小点。则该点为极小点。24 四月 202440在图中的在图中的x(3)附近，其右侧附近，其右侧f(x)0，但其，但其左侧左侧f(x)0，因此它不是极值点。可见，因此它不是极值点。可见，函数二阶导数的符号成为判断极值点的函数二阶导数的符号成为判断极值点的充分条件充分条件。24 四月 202441函数的偏导数函数的偏导数n偏导数是指在某坐标轴方向函数值的变化率偏导数是指在某坐标轴方向函数值的变化率n连续可微的连续可微的 n 维函数维函数 f(X)=f(x1,x2,xn)，在，在点点 X(K)=x1(K),x2(K),xn(K)T的一阶偏导数表的一阶偏导数表示为示为 ，三、多元函数的方向导数、梯度和赫赛矩阵三、多元函数的方向导数、梯度和赫赛矩阵函数的梯度函数的梯度 n维函数的梯度是函数各维一阶偏导数组成的维函数的梯度是函数各维一阶偏导数组成的向量向量24 四月 202443梯度的模是函数各维一阶偏导数平方和的梯度的模是函数各维一阶偏导数平方和的开方开方梯度与它的模的比值称为梯度的单位向量梯度与它的模的比值称为梯度的单位向量24 四月 202444函数梯度的性质函数梯度的性质1、函函数数的的梯梯度度 f(X(K)是是函函数数在在点点X(K)的的最最速速上上升升方方向向，而而负负梯梯度度-f(X(K)是是函函数数在在点点X(K)的最快下降方向。的最快下降方向。函函数数的的梯梯度度随随着着点点 X(K)在在设设计计空空间间的的位位置置不不同同而而异异，这这只只是是反反映映了了函函数数在在点点X(K)邻域内函数的局部性质。邻域内函数的局部性质。24 四月 2024452、函函数数梯梯度度的的模模 是是在在点点X(K)函函数数变变化率的最大值。化率的最大值。3、函数的梯度、函数的梯度 f(X(K)与在点与在点X(K)的函数的函数等值面正交。与点等值面正交。与点X(K)的函数等值面相切的函数等值面相切方向的函数变化率为零。方向的函数变化率为零。24 四月 20244624 四月 202447X(K)x1x2O上升方向上升方向变化率为零的方向变化率为零的方向（切线方向）下降方向下降方向最速下降方向最速下降方向最速上升方向最速上升方向（法线方向）f(X(K)fX(K)24 四月 202448注意，注意，函数函数f(X)在某点在某点X(K)的梯度向量的梯度向量 f(X(K)仅反映仅反映f(X)在点在点X(K)附近极小邻域的附近极小邻域的性质因而是一种局部性质。性质因而是一种局部性质。函数在定义域内的各点都各自对应着一函数在定义域内的各点都各自对应着一个确定的梯度个确定的梯度 。函数的赫森矩阵函数的赫森矩阵 函数的二阶偏导数矩阵函数的二阶偏导数矩阵它是一个它是一个nn阶的对称矩阵阶的对称矩阵24 四月 202449赫森矩阵正定和负定的判定赫森矩阵正定和负定的判定如果赫森矩阵行列式各阶主子式全部大于零，即如果赫森矩阵行列式各阶主子式全部大于零，即24 四月 202450n则它是正定的。则它是正定的。n如果如果各阶主子式是相间的一负一正，各阶主子式是相间的一负一正，则它则它是负定的。是负定的。24 四月 202451n设设f(x)为定义在为定义在X D Rn中的中的n元函数。元函数。向量向量X的分量的分量x1,x2,xn，就是函数的自，就是函数的自变量。变量。n设设x(k)为定义域内的为定义域内的个点，且在该点有个点，且在该点有连续的连续的n1阶偏导数，则在该点附近可阶偏导数，则在该点附近可用泰勒级数展开，如取到二次项用泰勒级数展开，如取到二次项 24 四月 202452多元函数的极值条件多元函数的极值条件24 四月 202453如用向量矩阵形式表示，则上式可写为如用向量矩阵形式表示，则上式可写为 24 四月 202454可简写为可简写为 24 四月 202455式中式中 24 四月 202456 f(X(k)是函数是函数f(X)在点在点X(k)的一阶偏导数矩阵，的一阶偏导数矩阵，称为函数在该点的称为函数在该点的梯度梯度。2f(X(k)是函数是函数f(X)在点在点X(k)的二阶偏的二阶偏导数组成的，导数组成的，n n阶对称矩阵，或阶对称矩阵，或称为称为f(X(k)的的赫森赫森(Hessian)矩阵矩阵，记，记作作H(X(k)。24 四月 202457n公式中只取到公式中只取到泰勒级数泰勒级数二次项，称为函二次项，称为函数的二次近似表达式。数的二次近似表达式。n极值点存在的必要条件。极值点存在的必要条件。n元函数在定义元函数在定义域内极值点域内极值点X*存在的存在的必要条件必要条件 24 四月 202458n即即对对每每一一个个变变量量的的一一阶阶偏偏导导数数值值必必须须为为零，或者说梯度为零零，或者说梯度为零(n维零向量维零向量)。n与一元函数对应，满足梯度为零只是多与一元函数对应，满足梯度为零只是多元函数极值点存在的必要条件，而并非元函数极值点存在的必要条件，而并非充分条件；充分条件；24 四月 202459n满足满足 f(X*)的点的点X*称为称为驻点驻点n驻点驻点是否为是否为极值点极值点，尚须通过二阶偏导，尚须通过二阶偏导数矩阵来判断。数矩阵来判断。24 四月 202460极值点存在充分条件极值点存在充分条件 n如如何何判判断断多多元元函函数数的的一一个个驻驻点点是是否否为为极极值值点点呢呢?将多元函数将多元函数f(X)在驻点在驻点X*附近用附近用泰勒公式泰勒公式的二次式近似地表示，则由式得的二次式近似地表示，则由式得 24 四月 202461由由X*为为驻点驻点，f(X*)=0，于是有，于是有24 四月 202462在在X*点附近的邻域内，若对一切的点附近的邻域内，若对一切的X恒有恒有 亦即亦即 24 四月 202463 则则X*为为极小点极小点 否则，当恒有否则，当恒有 则则X*为为极大点极大点 根据矩阵理论知，由式得极小点的根据矩阵理论知，由式得极小点的充分条充分条件件为：为：24 四月 202464亦即驻点亦即驻点赫森矩阵赫森矩阵H(X*)必须为正定必须为正定 n同理知极大点的同理知极大点的充分条件充分条件为：为：24 四月 202465亦即驻点亦即驻点赫森矩阵赫森矩阵H(X*)必须为负定必须为负定。n而当而当 24 四月 202466n n亦即驻点赫森矩阵亦即驻点赫森矩阵H(X*)既非正定，又非既非正定，又非负定，而是不定，负定，而是不定，f(X)在在X*处无极值。处无极值。n至于对称矩阵正定、负定的检验，由线至于对称矩阵正定、负定的检验，由线性代数可知：对称矩阵性代数可知：对称矩阵 24 四月 202467n n正正定定的的条条件件是是它它的的行行列列式式|A|A|的的顺顺序序主主子子式全部大于零，即式全部大于零，即24 四月 202468 n负定的条件是它的行列式负定的条件是它的行列式|A|中一串主子中一串主子式为相间的一负一正的，即式为相间的一负一正的，即 24 四月 202469n 至此，完全不难自行归纳得出无约束目至此，完全不难自行归纳得出无约束目标函数极值点存在的充分必要条件和用标函数极值点存在的充分必要条件和用数学分析作为工具对数学分析作为工具对n维无约束优化问题维无约束优化问题寻求最优解。寻求最优解。24 四月 202470无约束目标函数的极值条件无约束目标函数的极值条件 n必要条件必要条件：在点在点X*=x1*,x2*,xn*T的一阶的一阶偏导数为零（即梯度向量为零向量）偏导数为零（即梯度向量为零向量）24 四月 202471n充分条件充分条件：如果它的二阶偏导数矩阵如果它的二阶偏导数矩阵（即赫森矩阵）是负定的，则为极大点；（即赫森矩阵）是负定的，则为极大点；如果它的二阶偏导数矩阵是正定的，则如果它的二阶偏导数矩阵是正定的，则为极小点。为极小点。24 四月 202472求三维函数的极值点。求三维函数的极值点。解解：根据三维函数存在极值的必要条件，根据三维函数存在极值的必要条件，令梯度为零令梯度为零 24 四月 202473联解得到联解得到24 四月 202474计算点计算点 的赫森矩阵的赫森矩阵 赫森矩阵行列式各阶主子式赫森矩阵行列式各阶主子式 24 四月 20247524 四月 202476赫森矩阵是正定的，赫森矩阵是正定的，是极小点。是极小点。对应的目标函数值对应的目标函数值24 四月 20247724 四月 202478指全域而言指全域而言局部的性质局部的性质最优值最优值一般来说，在函数定义的区域内部，一般来说，在函数定义的区域内部，最优点必是极值点，反之却不一定。最优点必是极值点，反之却不一定。极值极值3-5 函数的凸性函数的凸性 24 四月 202479x1x2x1x2OODX(2)X(1)X(2)X(1)D(a)(b)一、凸集与非凸集一、凸集与非凸集 n设设D D为为n n维欧氏空间中设计点维欧氏空间中设计点X X的一个集合，的一个集合，若其中任意两点若其中任意两点x x(1)(1)和和x x(2)(2)的连线都在集的连线都在集合中，则称这种集合是合中，则称这种集合是n n维欧氏空间的一维欧氏空间的一个凸集。个凸集。n二维函数的情况如图所示，其中图二维函数的情况如图所示，其中图(a)(a)为为凸集，图凸集，图(b)(b)为非凸集为非凸集24 四月 202480凸集的概念凸集的概念24 四月 202481凸集的定义凸集的定义定义：设集合定义：设集合 S Rn，若若 x(1),x(2)S,0,1，必有，必有 x(1)(1-)x(2)S，则称，则称 S 为凸集。为凸集。规定：单点集规定：单点集 x 为凸集，空集为凸集，空集为凸为凸集。集。注注:x(1)(1-)x(2)=x(2)(x(1)-x(2)是连接是连接 x(1)与与x(2)的线段的线段。24 四月 202482凸集凸集非凸集非凸集凸集凸集24 四月 202483二、凸函数二、凸函数最优值与极值之间的关系最优值与极值之间的关系目标函数的凸性性质目标函数的凸性性质最最优优值值24 四月 202484凸函数的概念凸函数的概念xx(2)x*x(1)Of(x)f(x(1)f(x*)f(x(2)xf(x)x(2)x*x(1)Of(x(1)f(x(2)fx*)(a)(b)n用一元函数来说明函数的凸性。用一元函数来说明函数的凸性。n如图所示，图如图所示，图(a)在在x(1)、x(2)区间曲线为下区间曲线为下凸的，图凸的，图(b)的曲线是上凸的，它们的极的曲线是上凸的，它们的极值点值点(极小点或极大点极小点或极大点)在区间内都是唯一在区间内都是唯一的。的。n这样的函数称为具有凸性的函数，或称这样的函数称为具有凸性的函数，或称为单峰函数。为单峰函数。24 四月 20248524 四月 202486凸函数的定义凸函数的定义 定义：设定义：设f(X)为定义在为定义在n维欧氏空间中一个凸集维欧氏空间中一个凸集D上的函数，若对任何上的函数，若对任何实数实数(0 1)及及D域中任意两点域中任意两点X(1)与与X(2)存在如下关系：存在如下关系：则称函数则称函数则称函数则称函数f f(X X)是定义在凸集是定义在凸集是定义在凸集是定义在凸集D D上的一个上的一个上的一个上的一个凸函数凸函数凸函数凸函数。24 四月 202487Of(x)xx(1)x(k)x(2)f(x(1)f(x(2)f x(1)+(1-)x(2)f(x(1)+(1-)f(x(2)n现用上图所示定义于区间现用上图所示定义于区间a,b的单变量的单变量函数来说明这一概念。函数来说明这一概念。n若连接函数曲线上任意两点的直线段，若连接函数曲线上任意两点的直线段，某一点某一点x(k)的函数值恒低于此直线段上相的函数值恒低于此直线段上相应的纵坐标值时，这种函数就是凸函数，应的纵坐标值时，这种函数就是凸函数，也就是单峰函数。也就是单峰函数。24 四月 202488n 若将式若将式 中的符号中的符号“”改为改为“”n则称函数则称函数f(X)为为严格凸函数严格凸函数。24 四月 20248924 四月 202490区间区间a,b单峰函数单峰函数函数函数f(X)为为凸函数凸函数凸函数凸函数函数函数f(X)为为严格严格凸函数凸函数符号符号“”符号符号“”n 若若将将式式 中中的的符符号号“”改改为为“”，函函数曲线上凸数曲线上凸(有极大点有极大点)n通通常常称称为为凹凹函函数数。显显然然若若为为凸凸函函数数，则则-f(X)凹函数。凹函数。24 四月 202491 三、凸函数的基本性质三、凸函数的基本性质 1）若若函函数数f1(X)和和f2(X)为为凸凸集集上上的的两两个个凸凸函数，对任意正数函数，对任意正数a和和bf(X)af1(X)+bf2(X)仍为仍为D集上的集上的凸函数凸函数；24 四月 2024922)若若X(1)与与X(2)为凸函数为凸函数f(X)中的两个中的两个最小点，则其连线上的一切点也都是最小点，则其连线上的一切点也都是f(X)的最小点。的最小点。24 四月 202493四、凸函数的判定四、凸函数的判定 判判别别法法1：若若函函数数f(X)在在D上上具具有有连连续续一一阶阶导导数数，而而D为为D1内内部部的的一一个个凸凸集集，则则f(X)为为D上上的的凸凸函函数数的的充充分分必必要要条条件件为为：对对任任意的意的X(1)与与X(2)，恒有，恒有 24 四月 202494判判别别法法2：若若函函数数f(X)在在凸凸集集D上上存存在在二二阶阶导导数数并并且且连连续续时时，对对f(X)在在D上上为为凸凸函函数数的充分必要条件为：的充分必要条件为：对对于于任任意意的的X D，f(X)的的赫赫森森矩矩阵阵H(X)处处是正半定矩阵。处处是正半定矩阵。24 四月 202495n若赫森矩阵若赫森矩阵H(X)对一切对一切X D都是正定的，都是正定的，则则f(X)是是D上的严格凸函数，反之不一定上的严格凸函数，反之不一定成立。成立。24 四月 202496五、函数的凸性与局部极值及全域最优值五、函数的凸性与局部极值及全域最优值之间的关系之间的关系 设设f(X)为定义在凸集为定义在凸集D上的一个函数，一上的一个函数，一般来说，般来说，f(X)的极值点不一定是它的最优点。的极值点不一定是它的最优点。但是，若但是，若f(X)为凸集为凸集D上的一个凸函数，则上的一个凸函数，则f(X)的任何极值点，同时也是它的最优点。若的任何极值点，同时也是它的最优点。若f(X)还是严格凸函数，则它有唯一的最优点。还是严格凸函数，则它有唯一的最优点。24 四月 202497六六 约束极值点存在条件约束极值点存在条件 1 有约束的极值问题有约束的极值问题 24 四月 202498gi(X)0不等式约束，不等式约束，hj(X)=0等式约束等式约束24 四月 202499 在约束条件下求得的函数极值点，称为约束极值点。2 不等式约束问题的一阶最优性条件不等式约束问题的一阶最优性条件 24 四月 2024100起作用约束起作用约束不起作用约束不起作用约束 24 四月 2024101x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值线6.2543.810.251234O-212X*(1)X*(2)(b)(a)D起作用约束下标集合用起作用约束下标集合用I表示表示24 四月 2024102或或 在优化实用计算中常需判断和在优化实用计算中常需判断和检查某个可行点是否约束极值点，检查某个可行点是否约束极值点，这通常借助于这通常借助于库恩库恩-塔克塔克(KuhnTucker)条件条件(简称简称K-T条件条件)来进行。来进行。24 四月 2024103 K-T条件可阐述为：条件可阐述为：n如如果果X(k)是是一一个个局局部部极极小小点点，则则该该点点的的目目标标函函数数梯梯度度 f(X(k)可可表表示示成成该该点点诸诸约约束束面梯度面梯度 gi(X(k)的如下线性组合：的如下线性组合：n gi(i I)在在X(k)处可微；处可微；ngi(i I)在在X(k)处连续；处连续；n gi(X(k)(i I)线性无关线性无关24 四月 202410424 四月 2024105gi(iI)在X(k)处也可微，可写成等价形式 ni I时，时，gi 0，wi0ni I时，时，gi=0，对，对wi无限制无限制nwi g(X(k)=0，i=1，2，m称为互补松称为互补松弛条件弛条件；nwi 0，i=1，2，m，亦称拉格朗日乘，亦称拉格朗日乘子。子。24 四月 2024106 等式约束性问题的最优性条件几何意义是明显的：考虑等式约束性问题的最优性条件几何意义是明显的：考虑一个约束的情况：一个约束的情况：最优性条件即：最优性条件即：24 四月 2024107-f(x2*)x2*h(x2*)h(x)-f(x1*)h(x1*)这里 x1*-l.opt.f(x1*)与h(x1*)共线，而x2*非l.opt.f(x2*)与h(x2*)不共线。3 一般约束问题的一阶最优性条件一般约束问题的一阶最优性条件 24 四月 2024108 如果如果x*是是l.opt.,对每一个约束函数来说，只对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：有当它是起作用约束时，才产生影响，如：24 四月 2024109g2(x)=0 x*g1(x)=0g1(x*)=0,g1为起作用约束nK-T条件可阐述为：条件可阐述为：n如如果果X(k)是是一一个个局局部部极极小小点点，则则该该点点的的目目标标函函数数梯梯度度 f(X(k)可可表表示示成成该该点点诸诸约约束束面梯度面梯度 gi(X(k)的如下线性组合：的如下线性组合：n f、gi(i I)在在X(k)处可微处可微ngi(i I)在在X(k)处连续处连续nhj(X(k)(j=1，2，l)在在X(k)处连续可微处连续可微24 四月 202411024 四月 2024111gi(iI)在X(k)处也可微，可写成等价形式 24 四月 2024112wi g(X（k）)=0，i=1，2，m仍称为互补松弛条件 n可以对可以对K-T条件用图形来说明。如果条件用图形来说明。如果X(k)是一个局部极小点，则该点的目标函数是一个局部极小点，则该点的目标函数梯度梯度 f(X(k)应落在该点诸约束面梯度应落在该点诸约束面梯度 gi(X(k)、hj(X(k)在设计空间所组成的锥在设计空间所组成的锥角范围内。角范围内。24 四月 202411324 四月 2024114如图所示，图如图所示，图(a)中设计点中设计点X(k)不是约束极不是约束极值点，图值点，图(b)的设计点的设计点X(k)是约束极值点是约束极值点。X(k)h(X(k)g2(X(k)f(X(k)g1(X(k)g3(X(k)(a)X(k)g2(X(k)g3(X(k)g1(X(k)h(X(k)f(X(k)(b)24 四月 2024115123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T24 四月 2024116用用K-T条件求解：条件求解：24 四月 202411724 四月 2024118可能的可能的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点。点。24 四月 2024119下面举几个情况：下面举几个情况：g1与与g2交点：交点：x=(2,1)TS，I=1,2 则则w3=w4=0 解解24 四月 202412024 四月 202412124 四月 202412224 四月 2024123七七 最优化设计的数值计算迭代方法最优化设计的数值计算迭代方法 n无约束优化问题和约束优化问题当其数无约束优化问题和约束优化问题当其数学模型确定以后求其最优解，实质上都学模型确定以后求其最优解，实质上都属于目标函数的极值问题。属于目标函数的极值问题。n两者的优化求解方法联系紧密，其中无两者的优化求解方法联系紧密，其中无约束优化方法又是优化方法中最基本的约束优化方法又是优化方法中最基本的方法。方法。24 四月 2024124迭代算法的概念迭代算法的概念 迭代法是一种重要的逐次逼近的方法。迭代法是一种重要的逐次逼近的方法。这种方法用某个固定格式反复计算和校正这种方法用某个固定格式反复计算和校正所求问题的近似解（如方程的根、函数的所求问题的近似解（如方程的根、函数的极值点等），使之逐次精确化，最后得到极值点等），使之逐次精确化，最后得到满足精度要求的结果。满足精度要求的结果。求一维方程求一维方程 在在 附近的一个根。附近的一个根。解：可将方程改写为下列形式解：可将方程改写为下列形式 用所给的初始值用所给的初始值 近似代入上式的右近似代入上式的右端得到第一个近似解端得到第一个近似解 由于由于 和和 有较大偏差，再将有较大偏差，再将 作为初作为初始值，并且重复上面的计算步骤，如此继始值，并且重复上面的计算步骤，如此继续下去。这种逐步逼近的过程称作迭代过续下去。这种逐步逼近的过程称作迭代过程。程。24 四月 2024126n该例求解该一维方程迭代格式是该例求解该一维方程迭代格式是n随着迭代次数逐渐增大，直至相邻两次迭代点随着迭代次数逐渐增大，直至相邻两次迭代点 的偏差小于预先给定的精度值为止。的偏差小于预先给定的精度值为止。24 四月 2024127n无约束最优化算法，每次迭代都按无约束最优化算法，每次迭代都按选定方向选定方向S和一合适的步长和一合适的步长 向前搜索，向前搜索，可以写出迭代过程逐次搜索新点的向量可以写出迭代过程逐次搜索新点的向量方程式方程式 24 四月 2024128n迭代过程的每一步向量方程式，都可写成如下迭代过程的每一步向量方程式，都可写成如下的迭代格式的迭代格式 24 四月 2024129 式中：式中：X X(k)(k)第第k步迭代的出发点；步迭代的出发点；X X(k+1)(k+1)第第k步迭代产生出的新点；步迭代产生出的新点；S S(k)(k)是向量，代表第是向量，代表第k步迭代的前进方步迭代的前进方向向(或称搜索方向或称搜索方向)；(k)是标量，代表第是标量，代表第k步沿步沿S(k)方向方向的迭代步长的迭代步长(或称步长因子或称步长因子)。在一系列的迭代计算在一系列的迭代计算k=1,2,过程过程中，产生一系列的迭代点中，产生一系列的迭代点(点列点列)X(0)，X(1)，X(k)，X(k+1)。为实现。为实现极小化，目标函数的值应一次比一极小化，目标函数的值应一次比一次减小，即次减小，即24 四月 2024130nf(X(0)f(X(1)f(X(k)f(X(k1)n直至迭代计算满足一定的精度时，则认直至迭代计算满足一定的精度时，则认为目标函数值近似收敛于其理论极小值。为目标函数值近似收敛于其理论极小值。24 四月 202413124 四月 2024132优化迭代算法的分类优化迭代算法的分类n 搜索算法是一种迭代算法，搜索方向和步长因搜索算法是一种迭代算法，搜索方向和步长因子构成了每一次迭代的修正量，表明它们是决定算子构成了每一次迭代的修正量，表明它们是决定算法好坏的重要因素。法好坏的重要因素。n 在搜索方向上，使目标函数取得极小值的步长在搜索方向上，使目标函数取得极小值的步长因子，称为该方向上最优步长因子。在优化设计中，因子，称为该方向上最优步长因子。在优化设计中，求解最优步长因子主要采用数值解法，即利用计算求解最优步长因子主要采用数值解法，即利用计算机通过反复的迭代计算，求解出最优步长因子的近机通过反复的迭代计算，求解出最优步长因子的近似值。似值。n 目前已有很多优化方法，各种方法的区别就在目前已有很多优化方法，各种方法的区别就在于确定方向和步长因子的方法不同。于确定方向和步长因子的方法不同。24 四月 2024133 1、直接搜索法直接搜索法n 这这种种方方法法只只需需要要进进行行函函数数值值的的计计算算与与比比较较来来确确定定优优化化的的方方向向和和步步长长。例例如如一一维维搜搜索索中中的的黄黄金金分分割割法法、二二次次插插值值法法等等，在在多多维维问问题题中中的的随随机机方向法、共轭方向法和复合形法等。方向法、共轭方向法和复合形法等。24 四月 20241342、间接搜索法间接搜索法n 这种方法需要利用函数的一阶或二阶偏这种