《优化理论基础》PPT课件.ppt

《《优化理论基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《优化理论基础》PPT课件.ppt（169页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、30 一月 20231第第3章章 优化设计理论基础优化设计理论基础 30 一月 2023230 一月 2023330 一月 2023430 一月 20235f(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*30 一月 2023630 一月 20237二维无约束最优化设计问题几何意义二维无约束最优化设计问题几何意义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)O

2、f(X)x2x1X*30 一月 2023830 一月 2023930 一月 20231030 一月 20231130 一月 20231230 一月 202313x1x2f(x)f(x)g(x)g1(x)g2(x)O30 一月 20231430 一月 202315x2x1X*1g4(X)g3(X)g1(X)g1(X)X*20.25f(X)=12.253.846.25f(X)=912123O30 一月 202316二维目标函数等值线形态分析二维目标函数等值线形态分析30 一月 202317X 1*x1x201123X 2*X 3*x1x2012323456X 1*30 一月 2023183-2 约

3、束最优解和无约束最优解约束最优解和无约束最优解 二维优化问题进行几何描述二维优化问题进行几何描述n例例 对二维优化问题对二维优化问题进行几何描述进行几何描述。30 一月 202319约束线、可行域、目标函数等值线、约约束线、可行域、目标函数等值线、约束极值点束极值点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)=-

4、x12+x2-1 0 求其最优解求其最优解X*和和f(X*)。30 一月 20232030 一月 202321x1x2x2x1f(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)D30 一月 2023223-3 局部最优解和全域最优解局部最优解和全域最优解 30 一月 20232330 一月 202324X2*X1*f(X)x2x130 一月 20232530 一月 20232630 一月 20232730 一月 2023283-4 无约束目标函数的极值点存在条件无约束目标函数的

5、极值点存在条件 一、函数的极值与极值点一、函数的极值与极值点以一元函数为例说明函数的极值与极值点。以一元函数为例说明函数的极值与极值点。如图所示为定义在区间如图所示为定义在区间 a，b上的一元函数上的一元函数f(X)30 一月 20232930 一月 202330f(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)为最小。为最小。30 一月 202331n因因此此x(

6、1)与与x(2)即即为为函函数数的的极极大大点点与与极极小小点点，统称为函数统称为函数f(x)的极值点。的极值点。nf(x(1)与与f(x(2)相应地为函数的极大值与极相应地为函数的极大值与极小值，统称为函数小值，统称为函数f(x)的极值。的极值。30 一月 202332n需要注意，这里所谓需要注意，这里所谓极值极值是相对于是相对于点点的附近邻域各点而言的，仅具有局部的的附近邻域各点而言的，仅具有局部的性质，所以这种极值又称为性质，所以这种极值又称为局部极值局部极值。30 一月 202333n函数的最大值与最小值是指整个区间而函数的最大值与最小值是指整个区间而言的。言的。n如图中函数的最大值为

7、如图中函数的最大值为f(b)，函数的最小，函数的最小值为值为f(a)。函数的极值并不一定是最大值。函数的极值并不一定是最大值或最小值。或最小值。30 一月 202334二、极值点存在的条件二、极值点存在的条件 (一一)一元函数一元函数(即单变量函数即单变量函数)的情况的情况 (1)极值点存在的必要条件极值点存在的必要条件30 一月 202335在高等数学中已经学过：如果函数在高等数学中已经学过：如果函数f(x)的一的一阶导数阶导数f(x)存在，则欲使存在，则欲使x*为极值点的必为极值点的必要条件为：要条件为：f(x*)030 一月 202336仍以图中所示一元函数为例，由图可见，仍以图中所示一

8、元函数为例，由图可见，在在x(1)与与x(2)处的处的f(x(1)与与f(x(2)均等于零，均等于零，即函数在该两点处的切线与即函数在该两点处的切线与x轴平行。但轴平行。但使使f(x)0的点并不一定都是极值点。的点并不一定都是极值点。30 一月 20233730 一月 202338f(x)xf(a)f(x(1)f(x(2)x(1)f(x(3)f(b)x(3)x(2)abn使使函函数数f(x)的的一一阶阶导导数数f(x)0的的点点称称为为函数的函数的驻点驻点。n极值点极值点(对存在导数的函数对存在导数的函数)必为驻点必为驻点n驻点不一定是极值点驻点不一定是极值点n驻驻点点是是否否为为极极值值点点

9、可可以以通通过过二二阶阶导导数数f(x)来判断。来判断。30 一月 202339(2)极值点存在的充分条件极值点存在的充分条件 n若在驻点附近若在驻点附近 f(x)0则该点为极大点；则该点为极大点；若在驻点附近若在驻点附近 f(x)0则该点为极小点。则该点为极小点。30 一月 202340在图中的在图中的x(3)附近，其右侧附近，其右侧f(x)0，但其，但其左侧左侧f(x)0，因此它不是极值点。可见，因此它不是极值点。可见，函数二阶导数的符号成为判断极值点的函数二阶导数的符号成为判断极值点的充分条件充分条件。30 一月 202341函数的偏导数函数的偏导数n偏导数是指在某坐标轴方向函数值的变化

10、率偏导数是指在某坐标轴方向函数值的变化率n连续可微的连续可微的 n 维函数维函数 f(X)=f(x1,x2,xn)，在点，在点 X(K)=x1(K),x2(K),xn(K)T的一阶偏导数表示的一阶偏导数表示为为 ，三、多元函数的方向导数、梯度和赫赛矩阵三、多元函数的方向导数、梯度和赫赛矩阵函数的梯度函数的梯度 n维函数的梯度是函数各维一阶偏导数组成的维函数的梯度是函数各维一阶偏导数组成的向量向量30 一月 202343梯度的模是函数各维一阶偏导数平方和的梯度的模是函数各维一阶偏导数平方和的开方开方梯度与它的模的比值称为梯度的单位向量梯度与它的模的比值称为梯度的单位向量30 一月 202344函

11、数梯度的性质函数梯度的性质1、函函数数的的梯梯度度 f(X(K)是是函函数数在在点点X(K)的的最最速速上上升升方方向向，而而负负梯梯度度-f(X(K)是是函函数数在在点点X(K)的最快下降方向。的最快下降方向。函函数数的的梯梯度度随随着着点点 X(K)在在设设计计空空间间的的位位置置不不同同而而异异，这这只只是是反反映映了了函函数数在在点点X(K)邻域内函数的局部性质。邻域内函数的局部性质。30 一月 2023452、函函数数梯梯度度的的模模 是是在在点点X(K)函函数数变变化化率的最大值。率的最大值。3、函数的梯度、函数的梯度 f(X(K)与在点与在点X(K)的函数的函数等值面正交。与点等

12、值面正交。与点X(K)的函数等值面相切的函数等值面相切方向的函数变化率为零。方向的函数变化率为零。30 一月 20234630 一月 202347X(K)x1x2O上升方向上升方向变化率为零的方向变化率为零的方向（切线方向）下降方向下降方向最速下降方向最速下降方向最速上升方向最速上升方向（法线方向）f(X(K)f(X(K)30 一月 202348注意，注意，函数函数f(X)在某点在某点X(K)的梯度向量的梯度向量 f(X(K)仅反映仅反映f(X)在在点点X(K)附近极小邻域的性质因而是一种局部性质。附近极小邻域的性质因而是一种局部性质。函数在定义域内的各点都各自对应着一个确定的梯度函数在定义域

13、内的各点都各自对应着一个确定的梯度 。函数的赫森矩阵函数的赫森矩阵 函数的二阶偏导数矩阵函数的二阶偏导数矩阵它是一个它是一个nn阶的对称矩阵阶的对称矩阵30 一月 202349赫森矩阵正定和负定的判定赫森矩阵正定和负定的判定如果赫森矩阵行列式各阶主子式全部大于零，即如果赫森矩阵行列式各阶主子式全部大于零，即30 一月 202350n则它是正定的。则它是正定的。n如果如果各阶主子式是相间的一负一正，各阶主子式是相间的一负一正，则它则它是负定的。是负定的。30 一月 202351n设设f(x)为定义在为定义在X D Rn中的中的n元函数。元函数。向量向量X的分量的分量x1,x2,xn，就是函数的自

14、，就是函数的自变量。变量。n设设x(k)为定义域内的为定义域内的个点，且在该点有个点，且在该点有连续的连续的n1阶偏导数，则在该点附近可阶偏导数，则在该点附近可用泰勒级数展开，如取到二次项用泰勒级数展开，如取到二次项 30 一月 202352多元函数的极值条件多元函数的极值条件30 一月 202353如用向量矩阵形式表示，则上式可写为如用向量矩阵形式表示，则上式可写为 30 一月 202354可简写为可简写为 30 一月 202355式中式中 30 一月 202356 f(X(k)是函数是函数f(X)在点在点X(k)的一阶偏导数矩阵，称为函数在该点的的一阶偏导数矩阵，称为函数在该点的梯度梯度。

15、2f(X(k)是函数是函数f(X)在点在点X(k)的二阶偏的二阶偏导数组成的，导数组成的，n n阶对称矩阵，或阶对称矩阵，或称为称为f(X(k)的的赫森赫森(Hessian)矩阵矩阵，记，记作作H(X(k)。30 一月 202357n公式中只取到公式中只取到泰勒级数泰勒级数二次项，称为函二次项，称为函数的二次近似表达式。数的二次近似表达式。n极值点存在的必要条件。极值点存在的必要条件。n元函数在定义元函数在定义域内极值点域内极值点X*存在的存在的必要条件必要条件 30 一月 202358n即即对对每每一一个个变变量量的的一一阶阶偏偏导导数数值值必必须须为为零，或者说梯度为零零，或者说梯度为零(

16、n维零向量维零向量)。n与一元函数对应，满足梯度为零只是多与一元函数对应，满足梯度为零只是多元函数极值点存在的必要条件，而并非元函数极值点存在的必要条件，而并非充分条件；充分条件；30 一月 202359n满足满足 f(X*)的点的点X*称为称为驻点驻点n驻点驻点是否为是否为极值点极值点，尚须通过二阶偏导，尚须通过二阶偏导数矩阵来判断。数矩阵来判断。30 一月 202360极值点存在充分条件极值点存在充分条件 n如如何何判判断断多多元元函函数数的的一一个个驻驻点点是是否否为为极极值值点点呢呢?将多元函数将多元函数f(X)在驻点在驻点X*附近用附近用泰勒公式泰勒公式的二次式近似地表示，则由式得的

17、二次式近似地表示，则由式得 30 一月 202361由由X*为为驻点驻点，f(X*)=0，于是有，于是有30 一月 202362在在X*点附近的邻域内，若对一切的点附近的邻域内，若对一切的X恒有恒有 亦即亦即 30 一月 202363 则则X*为为极小点极小点 否则，当恒有否则，当恒有 则则X*为为极大点极大点 根据矩阵理论知，由式得极小点的根据矩阵理论知，由式得极小点的充分条充分条件件为：为：30 一月 202364亦即驻点亦即驻点赫森矩阵赫森矩阵H(X*)必须为正定必须为正定 n同理知极大点的同理知极大点的充分条件充分条件为：为：30 一月 202365亦即驻点亦即驻点赫森矩阵赫森矩阵H(

18、X*)必须为负定必须为负定。n而当而当 30 一月 202366nn亦即驻点赫森矩阵亦即驻点赫森矩阵H(X*)既非正定，又非负定，而是不定，既非正定，又非负定，而是不定，f(X)在在X*处无极值。处无极值。n至于对称矩阵正定、负定的检验，由线至于对称矩阵正定、负定的检验，由线性代数可知：对称矩阵性代数可知：对称矩阵 30 一月 202367nn正定的条件是它的行列式正定的条件是它的行列式|A|A|的顺序主子式全部大于零，即的顺序主子式全部大于零，即30 一月 202368 n负定的条件是它的行列式负定的条件是它的行列式|A|中一串主子中一串主子式为相间的一负一正的，即式为相间的一负一正的，即

19、30 一月 202369n 至此，完全不难自行归纳得出无约束目至此，完全不难自行归纳得出无约束目标函数极值点存在的充分必要条件和用标函数极值点存在的充分必要条件和用数学分析作为工具对数学分析作为工具对n维无约束优化问题维无约束优化问题寻求最优解。寻求最优解。30 一月 202370无约束目标函数的极值条件无约束目标函数的极值条件 n必要条件必要条件：在点在点X*=x1*,x2*,xn*T的一阶的一阶偏导数为零（即梯度向量为零向量）偏导数为零（即梯度向量为零向量）30 一月 202371n充分条件充分条件：如果它的二阶偏导数矩阵如果它的二阶偏导数矩阵（即赫森矩阵）是负定的，则为极大点；（即赫森矩

20、阵）是负定的，则为极大点；如果它的二阶偏导数矩阵是正定的，则如果它的二阶偏导数矩阵是正定的，则为极小点。为极小点。30 一月 202372求三维函数的极值点。求三维函数的极值点。解解：根据三维函数存在极值的必要条件，根据三维函数存在极值的必要条件，令梯度为零令梯度为零 30 一月 202373联解得到联解得到30 一月 202374计算点计算点 的赫森矩阵的赫森矩阵 赫森矩阵行列式各阶主子式赫森矩阵行列式各阶主子式 30 一月 20237530 一月 202376赫森矩阵是正定的，赫森矩阵是正定的，是极小点。是极小点。对应的目标函数值对应的目标函数值30 一月 20237730 一月 2023

21、783-5 函数的凸性函数的凸性 30 一月 202379x1x2x1x2OODX(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)为非凸集为非凸集30 一月 202380凸集的概念凸集的概念30

22、 一月 20238130 一月 202382凸集凸集非凸集非凸集凸集凸集30 一月 202383二、凸函数二、凸函数30 一月 202384凸函数的概念凸函数的概念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)f(x*)(a)(b)n用一元函数来说明函数的凸性。用一元函数来说明函数的凸性。n如图所示，图如图所示，图(a)在在x(1)、x(2)区间曲线为下区间曲线为下凸的，图凸的，图(b)的曲线是上凸的，它们的极的曲线是上凸的，它们的极值点值点(极小点或极大点极小点或极大点)在区间内都是唯一在区间内都是唯一的。的。n这样

23、的函数称为具有凸性的函数，或称这样的函数称为具有凸性的函数，或称为单峰函数。为单峰函数。30 一月 20238530 一月 20238630 一月 202387Of(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、函数，也就是单峰函数。也就是单峰函数。30 一月 202388n 若将式若将式 中的符号中的符号“”改为改为“”n则称函数则称函数f(X)为为严格凸函数严格凸函数。30 一月 20238930 一月 202390n 若若将将式式 中中的的符符号号“”改改为为“”，函函数曲线上凸数曲线上凸(有极大点有极大点)n通通常常称称为为凹凹函函数数。显显然然，若若为为凸凸函函数数，则则-f(X)凹函数。凹函数。30 一月 202391 三、凸函数的基本性质三、凸函数的基本性质 1）若若函函数数f1(X)和和f2(X)为为凸凸集集上上的的两两个个凸凸函数，对任意正数函数，对任意正数a和和bf(X)af1(X

25、)+bf2(X)仍为仍为D集上的集上的凸函数凸函数；30 一月 2023922)若若X(1)与与X(2)为凸函数为凸函数f(X)中的两个中的两个最小点，则其连线上的一切点也都是最小点，则其连线上的一切点也都是f(X)的最小点。的最小点。30 一月 202393四、凸函数的判定四、凸函数的判定 判判别别法法1：若若函函数数f(X)在在D上上具具有有连连续续一一阶阶导导数数，而而D为为D1内内部部的的一一个个凸凸集集，则则f(X)为为D上上的的凸凸函函数数的的充充分分必必要要条条件件为为：对对任任意的意的X(1)与与X(2)，恒有，恒有 30 一月 202394判判别别法法2：若若函函数数f(X)

26、在在凸凸集集D上上存存在在二二阶阶导导数数并并且且连连续续时时，对对f(X)在在D上上为为凸凸函函数数的充分必要条件为：的充分必要条件为：对对于于任任意意的的X D，f(X)的的赫赫森森矩矩阵阵H(X)处处是正半定矩阵。处处是正半定矩阵。30 一月 202395n若赫森矩阵若赫森矩阵H(X)对一切对一切X D都是正定的，都是正定的，则则f(X)是是D上的严格凸函数，反之不一定上的严格凸函数，反之不一定成立。成立。30 一月 202396五、函数的凸性与局部极值及全域最优值五、函数的凸性与局部极值及全域最优值之间的关系之间的关系 设设f(X)为定义在凸集为定义在凸集D上的一个函数，一上的一个函数

27、，一般来说，般来说，f(X)的极值点不一定是它的最优点。的极值点不一定是它的最优点。但是，若但是，若f(X)为凸集为凸集D上的一个凸函数，则上的一个凸函数，则f(X)的任何极值点，同时也是它的最优点。若的任何极值点，同时也是它的最优点。若f(X)还是严格凸函数，则它有唯一的最优点。还是严格凸函数，则它有唯一的最优点。30 一月 202397六六 约束极值点存在条件约束极值点存在条件 1 有约束的极值问题有约束的极值问题 30 一月 202398gi(X)0不等式约束，不等式约束，hj(X)=0等式约束等式约束30 一月 202399 在约束条件下求得的函数极值点，称为约束极值点。2 不等式约束

28、问题的一阶最优性条件不等式约束问题的一阶最优性条件 30 一月 2023100起作用约束起作用约束不起作用约束不起作用约束 30 一月 2023101x1x2x2x1f(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表示表示30 一月 2023102或或 在优化实用计算中常需判断和在优化实用计算中常需判断和检查某个可行点是否约束极值点，检查某个可行点是否约束极值点，这通常借助于这通常借助于库恩库恩-塔克塔克(KuhnTucker)条件

29、条件(简称简称K-T条件条件)来进行。来进行。30 一月 2023103 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)线性无关线性无关30 一月 202310430 一月 2023105gi(iI)在X(k)处也可微，可写成等价形式 ni I时，时，gi 0，wi0ni I时，时，gi=0

30、，对，对wi无限制无限制nwi g(X(k)=0，i=1，2，m称为互补松称为互补松弛条件弛条件；nwi 0，i=1，2，m，亦称拉格朗日乘，亦称拉格朗日乘子。子。30 一月 2023106 等式约束性问题的最优性条件几何意义是明显的：考虑等式约束性问题的最优性条件几何意义是明显的：考虑一个约束的情况：一个约束的情况：最优性条件即：最优性条件即：30 一月 2023107-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 一般约束问题的一阶最优性条件一般约束问题的

31、一阶最优性条件 30 一月 2023108 如果如果x*是是l.opt.,对每一个约束函数来说，只对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：有当它是起作用约束时，才产生影响，如：30 一月 2023109g2(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(

32、k)处连续处连续nhj(X(k)(j=1，2，l)在在X(k)处连续可微处连续可微30 一月 202311030 一月 2023111gi(iI)在X(k)处也可微，可写成等价形式 30 一月 2023112wi g(X（k）)=0，i=1，2，m仍称为互补松弛条件 n可以对可以对K-T条件用图形来说明。如果条件用图形来说明。如果X(k)是一个局部极小点，则该点的目标函数是一个局部极小点，则该点的目标函数梯度梯度 f(X(k)应落在该点诸约束面梯度应落在该点诸约束面梯度 gi(X(k)、hj(X(k)在设计空间所组成的锥在设计空间所组成的锥角范围内。角范围内。30 一月 202311330 一

33、月 2023114如图所示，图如图所示，图(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)30 一月 2023115123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T30 一月 2023116用用K-T条件求解：条件求解：30 一月 202311730 一月 2023118可能的可能的K-T点出现在下列情况

34、：点出现在下列情况：两约束曲线的交点：两约束曲线的交点：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点。点。30 一月 2023119下面举几个情况：下面举几个情况：g1与与g2交点：交点：x=(2,1)TS，I=1,2 则则w3=w4=0 解解30 一月 202312030 一月 202312130 一月 2023

35、12230 一月 2023123七七 最优化设计的数值计算迭代方法最优化设计的数值计算迭代方法 n无约束优化问题和约束优化问题当其数无约束优化问题和约束优化问题当其数学模型确定以后求其最优解，实质上都学模型确定以后求其最优解，实质上都属于目标函数的极值问题。属于目标函数的极值问题。n两者的优化求解方法联系紧密，其中无两者的优化求解方法联系紧密，其中无约束优化方法又是优化方法中最基本的约束优化方法又是优化方法中最基本的方法。方法。30 一月 2023124迭代算法的概念迭代算法的概念 迭代法是一种重要的逐次逼近的方法。迭代法是一种重要的逐次逼近的方法。这种方法用某个固定格式反复计算和校正这种方法

36、用某个固定格式反复计算和校正所求问题的近似解（如方程的根、函数的所求问题的近似解（如方程的根、函数的极值点等），使之逐次精确化，最后得到极值点等），使之逐次精确化，最后得到满足精度要求的结果。满足精度要求的结果。求一维方程求一维方程 在在 附近的一个根。附近的一个根。解：可将方程改写为下列形式解：可将方程改写为下列形式 用所给的初始值用所给的初始值 近似代入上式的右近似代入上式的右端得到第一个近似解端得到第一个近似解 由于由于 和和 有较大偏差，再将有较大偏差，再将 作为初作为初始值，并且重复上面的计算步骤，如此继始值，并且重复上面的计算步骤，如此继续下去。这种逐步逼近的过程称作迭代过续下去。

37、这种逐步逼近的过程称作迭代过程。程。30 一月 2023126n该例求解该一维方程迭代格式是该例求解该一维方程迭代格式是n随着迭代次数逐渐增大，直至相邻两次迭代点随着迭代次数逐渐增大，直至相邻两次迭代点 的偏差小于预先给定的精度值为止。的偏差小于预先给定的精度值为止。30 一月 2023127n无约束最优化算法，每次迭代都按无约束最优化算法，每次迭代都按选定方向选定方向S和一合适的步长和一合适的步长 向前搜索，向前搜索，可以写出迭代过程逐次搜索新点的向量可以写出迭代过程逐次搜索新点的向量方程式方程式 30 一月 2023128n迭代过程的每一步向量方程式，都可写成如下迭代过程的每一步向量方程式

38、，都可写成如下的迭代格式的迭代格式 30 一月 2023129 式中：式中：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)。为实现。为实现极小化

39、，目标函数的值应一次比一极小化，目标函数的值应一次比一次减小，即次减小，即30 一月 2023130nf(X(0)f(X(1)f(X(k)f(X(k1)n直至迭代计算满足一定的精度时，则认直至迭代计算满足一定的精度时，则认为目标函数值近似收敛于其理论极小值。为目标函数值近似收敛于其理论极小值。30 一月 202313130 一月 2023132优化迭代算法的分类优化迭代算法的分类n 搜索算法是一种迭代算法，搜索方向和步长因搜索算法是一种迭代算法，搜索方向和步长因子构成了每一次迭代的修正量，表明它们是决定算子构成了每一次迭代的修正量，表明它们是决定算法好坏的重要因素。法好坏的重要因素。n 在搜索

40、方向上，使目标函数取得极小值的步长在搜索方向上，使目标函数取得极小值的步长因子，称为该方向上最优步长因子。在优化设计中，因子，称为该方向上最优步长因子。在优化设计中，求解最优步长因子主要采用数值解法，即利用计算求解最优步长因子主要采用数值解法，即利用计算机通过反复的迭代计算，求解出最优步长因子的近机通过反复的迭代计算，求解出最优步长因子的近似值。似值。n 目前已有很多优化方法，各种方法的区别就在目前已有很多优化方法，各种方法的区别就在于确定方向和步长因子的方法不同。于确定方向和步长因子的方法不同。30 一月 2023133 1、直接搜索法直接搜索法n 这这种种方方法法只只需需要要进进行行函函数

41、数值值的的计计算算与与比比较较来来确确定定优优化化的的方方向向和和步步长长。例例如如一一维维搜搜索索中中的的黄黄金金分分割割法法、二二次次插插值值法法等等，在在多多维维问问题题中中的的随随机机方向法、共轭方向法和复合形法等。方向法、共轭方向法和复合形法等。30 一月 20231342、间接搜索法间接搜索法n 这种方法需要利用函数的一阶或二阶偏这种方法需要利用函数的一阶或二阶偏导数矩阵来确定优化方向和步长，例如导数矩阵来确定优化方向和步长，例如梯度法以负梯度矢量方向为搜索方向，梯度法以负梯度矢量方向为搜索方向，就需要计算函数的一阶偏导数矩阵。牛就需要计算函数的一阶偏导数矩阵。牛顿法则同时需要求出

42、目标函数的一阶偏顿法则同时需要求出目标函数的一阶偏导数矩阵和二阶偏导数矩阵的逆阵才能导数矩阵和二阶偏导数矩阵的逆阵才能确定迭代方向和步长。确定迭代方向和步长。30 一月 2023135n 数值计算迭代方法：数值计算迭代方法：n直直接接从从目目标标函函数数f(X)出出发发，构构造造一一种种使使目目标标函函数数值值逐逐次次下下降降逼逼近近，利利用用计计算算机机进进行迭代格式行迭代格式n一一步步步步搜搜索索、调调优优并并最最后后逼逼近近到到函函数数极极值点或达到最优点值点或达到最优点30 一月 2023136n根根据据确确定定搜搜索索方方向向和和步步长长的的方方法法不不同同，数数值值计计算算寻寻优优

43、可可有有许许多多方方法法，但但其其共共同同点是：点是：1)要要具具有有简简单单的的逻逻辑辑结结构构并并能能进进行行同同一一迭迭代格式的反复的运算：代格式的反复的运算：30 一月 20231372)这种计算方法所取得的结果不是理论精这种计算方法所取得的结果不是理论精确解，而是近似解确解，而是近似解.其精度是可以根据需要加以控制的。其精度是可以根据需要加以控制的。30 一月 2023138n 一、迭代法的基本思想及其格式一、迭代法的基本思想及其格式n迭代法是适应于计算机工作特点的一种数迭代法是适应于计算机工作特点的一种数值计算方法。值计算方法。n其基本思想是：在设计空间从一个初始设其基本思想是：在

44、设计空间从一个初始设计点计点X(0)开始，应用某一规定的算法，沿开始，应用某一规定的算法，沿某一方向某一方向S(0)和步长和步长(0)产生改进设计的新产生改进设计的新点点X(1)，使得，使得f(X(1)f(X(0)，30 一月 2023139n然后再从点然后再从点X(1)开始，仍应用同一算法，开始，仍应用同一算法，沿某一方向沿某一方向S(1)和步长和步长(1)，产生又有改，产生又有改进的设计新点进的设计新点X(2)，使得，使得f(X(2)f(X(1)，这样一步一步地搜索下去。，这样一步一步地搜索下去。30 一月 2023140n使目标函数值步步下降，直至得到满足使目标函数值步步下降，直至得到满

45、足所规定精度要求的、逼近理论极小点的所规定精度要求的、逼近理论极小点的X*点为止。点为止。n这种寻找最优点的反复过程称为数值迭这种寻找最优点的反复过程称为数值迭代过程。下图为二维无约束最优化迭代代过程。下图为二维无约束最优化迭代过程示意图过程示意图30 一月 202314130 一月 2023142x1x2OX*X(4)X(3)X(2)X(1)X(0)二、迭代计算的终止准则二、迭代计算的终止准则 n希望迭代过程进行到最终迭代点到达理希望迭代过程进行到最终迭代点到达理论极小点论极小点n或者使最终迭代点与理论极小点之间的或者使最终迭代点与理论极小点之间的距离足够小到允许的精度才终止迭代。距离足够小

46、到允许的精度才终止迭代。30 一月 2023143n实际上对于一个待求的优化问题，其理实际上对于一个待求的优化问题，其理论极小点并不知道。论极小点并不知道。n只能从迭代过程获得的迭代点序列只能从迭代过程获得的迭代点序列X(0)，X(1)，X(k)，X(k+1)，所提供的信所提供的信息息30 一月 2023144n根据一定的准则判断出已取得足够精确根据一定的准则判断出已取得足够精确的近似极小点时，迭代即可终止。的近似极小点时，迭代即可终止。n最后所得的点即认为是接近理论极小点最后所得的点即认为是接近理论极小点的近似极小点。对无约束最优化问题常的近似极小点。对无约束最优化问题常用的迭代过程终止准则

47、一般有以下几种。用的迭代过程终止准则一般有以下几种。30 一月 2023145 1)点距准则点距准则 n当相邻两迭代点当相邻两迭代点 X(k)，X(k+1)之间的距离之间的距离已达到充分小时，即小于或等于规定的某已达到充分小时，即小于或等于规定的某一很小正数一很小正数 时，迭代终止。时，迭代终止。30 一月 2023146一般用两个迭代点向量差的模来表示，即一般用两个迭代点向量差的模来表示，即 也可用迭代点在各个坐标轴上的分量来表示30 一月 20231472)函数下降量准则函数下降量准则 当当相相邻邻两两迭迭代代点点X(k)，X(k+1)的的目目标标函函数数值值的的下下降降量量已已达达到到充

48、充分分小小时时，即即小小于于或或等等于于规规定定的的某某一一很很小小正正数数 时时，迭迭代代终止。终止。30 一月 2023148一一般般用用目目标标函函数数值值下下降降量量的的绝绝对对值值来来表表示示，即即30 一月 2023149当|f(X(k)|1 或或用用目目标标函函数数值值下下降降量量的的相相对对值值来来表表示，即示，即30 一月 2023150当|f(X(k)|1 3)梯度准则梯度准则 当目标函数在迭代点当目标函数在迭代点X(k)的梯度已达到充的梯度已达到充分小时，即小于或等于规定的某一很小正数分小时，即小于或等于规定的某一很小正数 时，迭代终止；时，迭代终止；一般用梯度向量的模来

49、表示，即一般用梯度向量的模来表示，即 30 一月 2023151n 根据不同的优化方法和具体设计问题对根据不同的优化方法和具体设计问题对精度的要求而定。精度的要求而定。n一般来说，这几个迭代过程终止准则都一般来说，这几个迭代过程终止准则都分别在某种意义上反映了逼近极值点的分别在某种意义上反映了逼近极值点的程度，满足其中任一个迭代终止准则，程度，满足其中任一个迭代终止准则，都可以认为目标函数都可以认为目标函数f(X(k+1)收敛于函数收敛于函数f(X)的极小值的极小值 30 一月 2023152 上列几种迭代终止准则上列几种迭代终止准则,除梯度准则仅除梯度准则仅用于那些需要计算目标函数梯度的最优

50、用于那些需要计算目标函数梯度的最优化方法中外，其余并无特别规定必须选化方法中外，其余并无特别规定必须选用哪一种。用哪一种。30 一月 2023153n有时为了防止函数变化剧烈点距准则失有时为了防止函数变化剧烈点距准则失效效(见图见图(a)n或当函数变化缓慢时函数下降量准则失或当函数变化缓慢时函数下降量准则失效效(见图见图(b)，这时往往将点距准则和函，这时往往将点距准则和函数下降量准则结合起来，使同时成立数下降量准则结合起来，使同时成立n迭代终止准则并不限于上列几种迭代终止准则并不限于上列几种30 一月 2023154说明说明30 一月 2023155 xf(X)Of(X(k)f(X(k+1)