第六章控制系统参数优化及仿真ppt精选课件.ppt

《第六章控制系统参数优化及仿真ppt精选课件.ppt》由会员分享，可在线阅读，更多相关《第六章控制系统参数优化及仿真ppt精选课件.ppt（155页珍藏版）》请在三一办公上搜索。

1、,第六章 控制系统参数优化及仿真,仿真是将已知系统在计算机上进行复现，它是分析，设计系统的一种重要实验手段。怎样才能使设计出来的系统在满足一定的约束条件下，使某个指标函数达到极值，这就需要优化的仿真实验。所以仿真技术与优化技术两者关系十分密切。,第六章 控制系统参数优化及仿真,优化技术包括内容很多，本章主要介绍与系统最优化技术有关的参数优化技术方法。 第一节首先对控制系统常用的优化技术做一概括性的叙述。 第二节介绍单变量技术的分割法和插值法。 第三节为多变量寻优技术，介绍工程中常用的最速下降法，共轭梯法和单纯形法。 第四节为随机寻优法。 第五节简单介绍具有约束条件的寻优方法。 第六节介绍含函数

2、寻优的基本方法。 最后向读者介绍了Matlab优化工具箱的使用方法。,6.1 参数优化与函数优化,优化技术是系统设计中带有普遍意义的一项技术,本节首先讨论优化技术中的一些基本定义和问题.一、优化问题数学模型的建立 用优化方法解决实际问题一般分三步进行： (1) 提出优化问题，建立问题的数学模型。 (2)分析模型，选择合适的求解方法。 (3)用计算机求解，并对算法，误差，结果进行 评价。 显然，提出问题，确定目标函数的数学表达式是优化问题的第一步，在某种意义上讲也是最困难的一步。以下分别说明变量，约束和目标函数的确定。,6.1 参数优化与函数优化,(1) 变量的确定变量一般指优化问题或系统中待确

3、定的某些量。例如，在电机的优化设计中，变量可能为电流密度J,磁通密度 B，轴的长度，直径以及其他几何尺寸等。电路的优化设计中要确定的变量主要是电路元件(R,L,C)的数值。对产品设计问题来说，一般变量数较少(例如，几个到几十个)。变量数的多少以及约束的多少表示一个优化问题的规模大小。因此，工程上最优设计问题属于中小规模的优化问题，而生产计划，调度问题中变量数可达几百个几千个，属于大规模优化问题。变量用X表示,，磁通密度,表示，,。,6.1 参数优化与函数优化,(2) 约束条件求目标函数极值时的某些限制称为约束。例如，要求变量为非负或为整数值，这是一种限制；可用的资源常常是有限的(资源泛指人力，

4、设备，原料，经费，时间等等)；问题的求解应满足一定技术要求，这也是一种限制(如产品设计中规定产品性能必须达到的某些指标)。此外，还应满足物理系统基本方程和性能方程(如电路设计必须服从电路基本定律KCL和KVL)。控制系统优化设计则用状态方程和高阶微分和差分方程来描述其物理性质。,6.1 参数优化与函数优化,如果列写出来的约束式，越接近实际系统，则所求得的优化问题的解，也越接近于实际的最优解。等式约束 ：不等式约束：,或,6.1 参数优化与函数优化,(3) 目标函数优化有一定的标准和评价方法，目标函数 是这种标准的数学描述。目标函数可以是效果函数或费用函数， 。用效果作为目标函数时，优化问题是要

5、求极大值，而费用函数不得超过某个上界成为这个优化问题的约束；反之，最优函数是费用函数时，问题变成了求极小值，而效果函数不得小于某个下界就成为这个极小值问题的约束了，这是对偶关系。,6.1 参数优化与函数优化,费用和效果都是广义的，如费用可以是经费，也可以是时间、人力、功率、能量、材料、占地面积或其他资源。而效果可以是性能指标、利润、效益、精确度、灵敏度等等。也可以将效果与费用函数统一起来，以单位费用的效果函数或单位效果的费用函数为目标函数，前者是求极大值，后者是求极小值。 求极大值和极小值问题实际上没有什么原则的区别。因为求 的极小值相当于求- 的极大值，即 。两者的最优值均当 时得到。,6.

6、1 参数优化与函数优化,综上所述，优化问题的数学模型可以表示成如下形式：,(6.1.1),约束条件,6.1 参数优化与函数优化,二、优化问题的分类优化问题可以按下述情况分类：(1)有没有约束？有约束的话是等式约束还是不等式约束？(2)所提问题是确定性的还是随机性的？(3)目标函数和约束式是线性的还是非线性的？(4)是参数最优还是函数最优，即变量是不是时间的函数？(5)问题的模型是用数学解析公式表示还是用网络图表示？在网络上的寻优称为网络优化。限于本书的内容要求，在此只介绍参数优化和函数优化。,6.1 参数优化与函数优化,(1) 参数优化在控制对象已知，控制器的结构、形式已确定的情况下，通过调整

7、控制器的某些参数，使得某个目标函数最优，这就是参数优化问题。例如，图6.1.1所示的控制系统，在某个给定函数 的作用下，测量给定 与输出量 之间的偏差 ，用 作为指标函数，要求调整控制器的参数，使得该指标函数达到最小。,图6.1.1 控制器参数的调整,6.1 参数优化与函数优化,假定控制器有 个可调整参数 显然上述指标是这些参数的函数，即 (6.1.2)现在的问题就是要寻求使 达到极小值的 ，其中 是一个向量。 从数学上讲，参数优化问题是属于普通极值问题。寻找的最优参数不随时间变化，故也属于静态寻优问题。其一般问题形式是： 有一个物理系统，它的数学模型为 ，其中 为 维状态向量； 为 维被寻优

8、参数的向量； 为 维系统运动方程结构向量。要求在满足下列条件下：,6.1 参数优化与函数优化,不等式限制 q维 等式限制 p维 等式终端限制 维(是终端时间)找到一组参数 ，使指标函数 (2) 函数优化 函数优化是控制对象已知，要找最优控制作用 ，以使某个函数指标达到最小，也包括要寻找最优控制器的结构、形式和参数。,6.1 参数优化与函数优化,由于最优控制作用 为时间函数，所以这类问题称为函数优化问题，在数学上称为泛函极值问题，这类问题的一般形式是： 有一个物理系统，它的数学模型为 ，其中 为 维状态向量； 为 维被寻优参数的向量； 为 维系统运动方程结构向量。要求在满足条件下：不等式限制 q

9、维 等式限制 p维 等式终端限制 维找到m维函数 使指标函数,6.1 参数优化与函数优化,函数优化问题从理论上讲可以用变分或极大值原理或动态规划求解。但是在仿真研究中，由于采用的是数值求解，所以通常将其转化为参数优化问题加以解决。出于以上原因，本章的重点主要讨论参数优化问题。三、参数优化方法 系统的参数优化问题求解方法，按其求解方式可分为两类：间接寻优和直接寻优。 (1) 间接寻优 间接寻优就是把一个优化问题用数学方程描述出来，然后按照优化的充分必要条件用数学分析的方法求出解析解，故又称其为解析法。,6.1 参数优化与函数优化,数学中的变分法，拉格朗日乘子法和最大值原理，动态规划等都是解析法，

10、所以也都是间接寻优法。由于在大部分控制系统中目标函数J一般很难写出解析式，而只能在计算动态相应过程中计算出来，所以仿真中一般较少采用间接寻优方法。 (2) 直接寻优法 直接寻优法就是直接在变量空间搜索一组最佳控制变量(又称决策变量，设计变量)。这是一种数值方法，具体办法是，利用目标函数在一局部区域初始状态的性质和已知数值，来确定下一步计算的点，这样一步步搜索逼近，最后接近最优点。,6.2 单变量寻优技术,单变量寻优技术是多变量寻优技术的基础，多变量参数寻优的算法中常常要用到它，因此单变量的寻优方法是解决多变量优化问题的基本方法。本节主要介绍常用的两种单变量寻优方法：分割法和插值法。,6.2 单

11、变量寻优技术,6.2.1 黄金分割法( 法)分割法是单变量函数无约束极值较为有效的一种直接搜索法。这种方法实质上是在搜索过程中不断缩小最优点存在的区域，即通过搜索区间的逐步随小来确定最优点。对多变量函数来说，分割法不十分有效，因为这时消去的不是线段，而是平面、立体或多维空间的一部分。黄金分割法是分割法中的一种有效方法。假定目标函数 ，已知它在区间 有一极小值存在，如图6.2.1(a)所示。为了找到这个极小点 ，可以在距 各 处找两点 ，然后比较它们的目标函数值，如果 ，则令 ，形成新区间 ，然后对这个新区间在距 各 处找两点。由于每次分割区间缩小为原来的 倍( )，若原来区间 为 ，而经过n次

12、分割后区间为 。,6.2 单变量寻优技术,那么 。,选多大适合呢？如果要求 应该是 的对称点，即 ，如图6.2.1(b)所示，则也可以写成下面关系式：,图6.2.1 黄金分割图,6.2 单变量寻优技术,且希望经过分割后其保留点仍处于留下区间的相应位置上，即 在 中的位置与 在 中相仿,且比值相等 (6.2.2)故: , , 因此可以得到： = (6.2.3)取正值 =0.6180339这样，若计算分割后的函数值，则由计算两个点的函数值变为计算一个点的函数值，在一定分割次数内，减少了计算函数的次数。这种分割方法称为黄金分割法。,6.2 单变量寻优技术,图6.2.2表示了黄金分割法程序框图。,6.

13、2 单变量寻优技术,例6.2.1 求目标函数 的最小值，区间缩短的精度 。使用符号：A：初始区间的起点， ； B：初始区间的终点， ； E：允许的精度， 用C语言编写的计算程序清单如下：#include “math.h” #include “stdio.h” main( ),6.2 单变量寻优技术,float x0, x1, x2, x3, x4, e1, e2, q1, q2, q3, q4, q5, m, h0, h, c1, c2;int n;printf(“intput x0, H0,E1, E2, M”);scanf(“%f, %f, %f, %f, %f ”,6.2 单变量寻优技术

14、,p1: x1=x2; q1=q2; x2=x3; q2=q3; x3=x2+h; q3=x3*x3 -10 x3+36; if(q2q3) h=h+h; n=n+1; go to p1; else if(n0)x4=0.5*(x2+x3); q4=x4*x4 10*x4+36;if(q4q2) x3=x4; q3=q4;elsex1=x2; q1=q2; x2=x4; q2=q4; c1=(q3-q1)/(x3-x1) c2=(q2-q1)/(x2-x1)-c1)/(x2-x3);,6.2 单变量寻优技术,if(fabs(c2)e1) if(q4q2) x1=x2; q1=q2; elsex

15、1=x4; q1=q4; h0=m*h0; go to p2;,6.2 单变量寻优技术,rintf(“OPTIM X=%fn”,x4); printf(“OBJ.FUNC=%f”,q4); 计算结果： Q=11, x1=5.000 67, A=5.007 5, B=5.000 63。,6.2 单变量寻优技术,6.2.2 二次插值法 二次插值法是多项式近似法的一种，即用二次的插值多项式拟合目标函数，并用这个多项式的极小点作为目标函数极值的近似。1二次插值法的计算公式假设目标函数 在三个点 的函数值分别为 。可以利用这三个点及相应的函数值作为二次插值公式，令 (6.2.4) 为所求的插值多项式，它

16、应满足条件,(6.2.5),6.2 单变量寻优技术,对多项式(6.2.4)式求导数，并令其为零，得 (6.2.6) (6.2.7) (6.2.7)式就是计算近似极小点的公式。为了确定这个极小点只需算出a1和a2，其算法如下。 从(6.2.5)可求出 (6.2.8),6.2 单变量寻优技术,如果设三个点等距离，即则式(6.2.8)又可写为 (6.2.9)设 为坐标原点，则 (6.2.10),6.2 单变量寻优技术,2. 用外推法求寻优区间外推法是一种寻优极点范围的方法。用二次插值法巡优，有时其最优点存在的范围事先没有给出，因此作为寻优的第一步，首先就是确定寻优区间。其方法如下：设从某点 开始，原

17、始步长为 ，则 ,求目标函数 和 并进行比较。若 ,则将步长加倍，求在, , ,等点处目标函数 的值,直至函数值增加为止，如图6.2.3(a)所示。,6.2 单变量寻优技术,若 ,则求在 , , ,等点处的的值，直至函数值增加为止，如图.2.3(b) 对凸函数来说，最小点必落在 之间，即 , 而且有 (6.2.11),图6.2.3 外推法图示,6.2 单变量寻优技术,此时，若在 与 之间的中点进行第k+1点的计算，即取 (6.2.12)这样共得四个等间距的点 ,它们之间的间距为 当 时 ,;当 时 ， 。比较这四个点的函数值，取函数值最小的 ,则 ，这样就可以得三点 ，以便于构成二次插值函数，

18、并且可以判定 一定在 和 之间。,6.2 单变量寻优技术,3外推二次插值法的程序框图为便于分析将图6.2.4所示的框图分为三部分。其中，图6.2.4(a)为外推法最优点存在的区间；图6.2.4(b)为二次插值法求近似的最有点；图6.2.4(c)是比较 与 ，其比较小者为新的起点，同时缩短步长 ，再重复图6.2.4(a)及(b)两部分。例6.2.2 求目标函数 的最小值。 用C语言编写的程序清单如下： #include “math.h” #include “stdio.h”,6.2 单变量寻优技术,main( ) float x0, x1, x2, x3, x4, e1, e2, q1, q2,

19、 q3, q4, q5, m, h0, h, c1, c2;int n;printf(“input x0, H0, E1, E2, M”)；scanf(“%f, %f, %f, %f, %f”,6.2 单变量寻优技术,p1: x1=x2; q1+q2; x2=x3; q2=q3; x3=x2+h; q3=x3*x3-10*x3+36; if(q2q3) h=h+h; n=n+1; go to p1;else if(n0) x4=0.5*(x2+x3); q4=x4*x4-10*x4+36; if(q4q2) x3=x4; q3=q4;elsex1=x2; q1=q2; x2=x4;q2=q4;

20、 c1=(q3-q1)/(x3-x1); c2=(q2-q1)/(x2-x1)-c1)/(x2-x3,6.2 单变量寻优技术,if(fabs(c2)e1) x1=x2; q1=q2; h0=m*h0; go to p2;elsex4=0.5*(x1+x3-c1/c2); q4=x4*x4-10*x4+36; if(q2e2) q5=e2 else q5=q2;,6.2 单变量寻优技术,if(fabs(q4-q2)/q5=e1) if(q4q2) x1=x2; q1=q2; elsex1=x4;q1=q4; h0=m*h0; go to p2; printf(“OPTIM X=%fn”, x4)

21、; printf(“OBJ.FUNC=%f ”,q4); ,图6.2.4 外推二次插值法的程序框图,当 x0=0.5, h0=1, 0, e1=0.001, e2=1, m=0.1 时，计算结果： optim x=5.0, obj.fucn=11.0,6.3 多变量寻优技术,单变量寻优技术，由于只有一个变量，因此只要在一条线上搜索最优参数就可以了。在变量超过一个以后，就要在多维空间搜索一组最优参数，因此确定寻优方向及寻优步长的问题就比较突出了。根据寻优方向及寻优步长的不同，就有不同的寻优方法。本节将介绍三种方法：最速下降法，共轭梯度法和单纯形法。,6.3 多变量寻优技术,.3.1 最速下降法一

22、、最速下降法的基本思想为了弄清这种寻优方法的基本思想，可以举一个盲人下山的例子。当盲人下山时，眼睛看不见山谷的方位，如何能沿最短路线迅速下降呢？一般盲人只好靠手前后探索试探着前进的方向，哪儿最陡？一定下降的最快，这种寻求最速下降的方向作为搜索的方向，一步步逼近最低点就是最速下降的基本思想。要求多变量函数 的极小点 ，其中 为 维方向，首先从给定的起始点 出发，沿某个有利的方向 进行一维搜索，求得 在方向 上的极小点 ，然后再从 出发，沿某个新的有利方向 进行搜索，求得 在 方向上的近似极小点 。如此继续，直至满足给定的精度为止。,6.3 多变量寻优技术,二、最速下降法的计算方法设目标函数 ，求

23、使目标函数 为最小值的变量 。设 为 维向量，对 存在二阶偏导数。现假设已经迭代到第 步，得到此时刻的 ，考虑 有一个微小的变化，即 (6.3.1) 为 附近的点，其两点的距离为： (6.3.2),6.3 多变量寻优技术,因为 的微小变化，必然引起目标函数 也有一个变化： (6.3.3)所谓 下降最快，及最大变化的问题，经过上述变换，就转化为以下具有约束的极值问题。在下列约束条件下： (6.3.4)通过适当选择 ，使下式极大化 (6.3.5),6.3 多变量寻优技术,具有约束的极值问题可以采样拉格朗日乘子，化为无约束极值问题。设 为拉格朗日乘子，则 (6.3.6)式(6.3.5)对 求偏微分，

24、并令其等于零，有 解出 为 (6.3.7) 将方程(6.3.7)代入(6.3.2)，计算出 因子为,6.3 多变量寻优技术,令： (6.3.9)则 (6.3.10)将(6.3.10)代入(6.3.7)得到 (6.3.11)即，我们可以得到第 步时的 为 (6.3.12),6.3 多变量寻优技术,下面，确定(6.3.12)的正负号。将(6.3.8)式代入(6.3.7)式，得到 (6.3.13)再将上式代入(6.3.5)式得到即： (6.3.14) 因为 是距离，故为正，因此取“”号时，目标函数增加，而取“”号时，对应的目标函数减小。换句话说，沿着目标函数的负梯度方向走，目标函数是减小的。,6.3

25、 多变量寻优技术,又因为，式(6.3.6)对 的二阶偏微分等于 ，为了保证式(6.3.5)中的 沿着负数方向有最大值，即式(6.3.5)有极小值，因此只有 等于正数。我们可在式(6.3.10)中取负号，来保证(6.3.6)对 的二阶偏微分大于零，也就保证式(6.3.5)有极小值。 其中 为迭代步长， 不能选择太小，否则目标函数 下降太慢，但如果 很大，目标函数 可能会出现“上下起伏”现象，因此选择最优步长 应使 在方向的目标函数数值最小，即,6.3 多变量寻优技术,(6.3.15)显然，这是一个单变量寻优问题，即寻找最佳步长 。可以利用上一节所介绍的方法。最速下降法的一般计算关系式为：若出发点

26、为,则 (6.3.16),6.3 多变量寻优技术,式中 梯度向量； 梯度向量模； 梯度方向上的单位向量。 控制迭代的收敛要求可以为 =或 (6.3.17) 式中 梯度误差，它是很小的正数； 目标函数误差，它也是很小的正数。,6.3 多变量寻优技术,最速下降法的程序框图如图6.3.1所示。图6.3.1 最速下降法的程序框图,6.3 多变量寻优技术,用C语言编写的最速下降法的程序清单如下。其中R是梯度模 ；P是梯度方向的单位向量 ；h是步长 ；f是目标函数 。#include “math.h”#include “stdio.h” float x10, y10, p10, f, h; int n;

27、vod fun( ) int i; for(i=1, in; i+) xi=yi-h*pi;,6.3 多变量寻优技术,f=x1*x1+x2*x2-x1*x2-10*x1-4*x2;f=f+60;return;main( )float g10, d10, q, r, e, h1, h2, h3, h4, t, t0, c1, c2, f1, f2, f3, f4, f5, v;int i, k, u;printf(“input n, en”);scanf(“%d, %f”, ,6.3 多变量寻优技术,x1=0; x2=0;p4: g1=2*x1-x2-10;g2=2*x2-x1-4;q=0;fo

28、r(i=1; in;i+) q=gi*gi+q;r=sqrt(q);for(i=1; in;i+) yi=xi;pi=gi/r;if(re)go to p3;else,6.3 多变量寻优技术,t0=1; v=0.1; h1=0; h=h1 fun( ); f1=f; p2: u=0;t=t0; h2=h1+t; h=h2; fun( ); f2=f; if(f1f2) t=t+t; u=u+1; elset=-t; h3=h1; f3=f1; h1=h2;f1=f2;h2=h3;f2=f3; p1: h3=h2+t; h=h3; fun( );f3=f;,6.3 多变量寻优技术,if(f2f3

29、) t=t+t; u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;goto p1; elseif(u0)h4=0.5*(h2+h3); h=h4; fun( ); f4=f; if(f4f2) h3=h4; f3=f4; elseh1=h2; f1=f2; h2=h4; f2=f4; c1=(f3-f1)/(h3-h1);c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);,6.3 多变量寻优技术,if(fabs(c2)e) h1=h2;f1=f2;t0=v*t0; goto p2;elseh4=0.5*(h1+h3-(c1/c2); h=h4;fun( ); f4=f;

30、if(f21) f5=1;else f5=f2;if(fabs(f4-f2)/f5)e)for(i=1; in; i+) xi=yi-h4*pi; goto p4;,6.3 多变量寻优技术,else if(f4f2) h1=h2;f1=f2; else h1=h4;f1=f4; t0=v*t0; goto p2; p3: h=0; fun( );printf(“OBJ.FUNC F=%fn”, f);for(i=1; in; i+),6.3 多变量寻优技术,rintf(“X(%d”, I);printf(“)=%fn”, xi); 最速下降法的搜索方向是所谓的最速下降方向，但是也只能逐次地接近

31、最优点 ，对本例来说，开始搜索时，每次的步长大，目标函数下降也较快，但愈接近极值点，步长 愈来愈小，目标函数的改进也小，其搜索路径如图6.3.2所示。,6.3 多变量寻优技术,图6.3.2 最速下降法收敛曲线,6.3 多变量寻优技术,最速下降法从表面看是个最好的方法，但实际上并非如此。大量的计算实践说明，最速下降法收敛的速度并不快。这主要是因为最速下降法的方向仅仅是指某点附近而言，是一个局部的性质，一旦离开了该点原先的方向就不再保证是最速下降方向了。因此对整个过程来说，它并不总是具有最速下降的性质。尽管如此，最速下降法仍然不失为一种最常用的基本寻优方法。这不仅因为最速下降法每次迭代计算比较简单

32、，记忆容量小，适合计算机运算，而且对初值要求也比较低，在远离极值点时收敛快，所以它也经常与其他寻优方向共同配合，加快寻优速度。,6.3 多变量寻优技术,6.3.2 共轭梯度法轭梯度法是解优化问题的有效方法之一，特别是用于二次泛函指标系统。共轭梯度法程序清单容易实现，具有梯度法优点，而在收敛速度方面比梯度法快。下面分三部分较详细地介绍这种方法，并给出一个实用程序。一、共轭梯度法设 为定义在 维欧氏空间内区域 中的 元函数。向量 的分量 是函数的自变量。设 为 域内的一个点，则函数 可在这个点的附近以泰勒级数展开，且只取其二阶导数项，即：,6.3 多变量寻优技术,(6.3.18)其中: ， 分别为

33、： (6.3.19),6.3 多变量寻优技术,是 在点 处的二阶偏导数矩阵，又称赫森矩阵。 极值点存在的必要条件。 元函数在 域内极值点 存在的必要条件为 (6.3.20)即每个一阶偏导数值都必须为零，或梯度为 维零向量。但这只是必要条件，而不是充分条件，满足上式的点称为驻点。 极值点存在的充分条件。设 为 的驻点，将(6.3.20)式代入(6.3.18)式得,6.3 多变量寻优技术,(6.3.21)欲使 为极小点，只要在 附近，其差 所以必须有 (6.3.22)这就是说，在点 处的赫森矩阵 为正定的，即 为极小点的充分条件。因此利用处的赫森矩阵 的性质即可判断是驻点还是极值点。 二、共轭梯度

34、法的基本思想,6.3 多变量寻优技术,为了改进在极值点附近寻优的收敛速度，就要寻求更好的寻优方法。共轭梯度法是一种有效算法。 首先举例说明共轭方向的意义。如果两个2维向量 与 相互正交，见图6.3.3(a)，则其内积 0，也可以写成 0， 为单位矩阵。于是可以称 与 以单位矩阵互为共轭，可记为 。图6.3.3 共轭方向,6.3 多变量寻优技术,设有二阶对称矩阵 ，如 成立，即 与 相互正交，如图6.3.3(b)所示，则称 与 以 互为共轭，可记为 (6.3.23)对于任意形式的目标函数 ，如将其在 附近展开称泰勒级数，且只取到二次导数项，则得 (6.3.24)式中: 为 在 处的二阶偏导数矩阵

35、，即赫森矩阵。,6.3 多变量寻优技术,因为在极值点 处 ,故 (6.3.25)此式表示函数为二次函数。由此可以看出：任意形式得函数 在极值点附近的特性都近似于一个二次函数。对于二次函数 ，如图6.3.4所示，在初始点 做 的切线向量。设最优点为 ，则连接 与 的向量 与切线 互为共轭。这一点可证明如下。,6.3 多变量寻优技术,在最优点,Q(x*)=0,在 点的梯度切线向量 与梯度向量 互为正交，即而,6.3 多变量寻优技术,即 显然， 与 ，可写成下式：即 与 以 互为共轭。上述性质表明，如果对二次函数,从某点出发，沿共轭方向搜索，可以很快得到函数的极值点.,6.3 多变量寻优技术,三、共

36、轭梯度法的计算方法设 元函数 在极值点附近可用一个二次函数逼近： (6.3.26)式中： 为 维对称矩阵。 = (6.3.27) (6.3.28),6.3 多变量寻优技术,对于两个变量问题，可以用等高线来表示，见图6.3.5。设从某点 出发以 的方向搜索，使 达到极小的点 ，则 为该处等高线的切点。切点的梯度方向为等高线的法线方向，因此,图6.3.4 二次函数中的共轭方向 图6.3.5 两个变量的等高线图,6.3 多变量寻优技术,若从另一点 出发，也以 方向搜索，又得到一个极小点 ,同理也应有 (6.3.29)(6.3.28)式与(6.3.29)式之差为 (6.3.30)若令 ,则 (6.3.

37、31)这就说明 与 以 互为共轭。而 正是 与 两切点连线方向，此方向上的极小点即Q(x)的极小点。,6.3 多变量寻优技术,例 6.3.1目标函数 式中：C=10 4T；A= ，从 出发搜索，求极小点。 解：如果第一次的搜索方向为 ，则它与共轭方向的关系为一个向量的方向可以用单位方向向量E来表示，若 的单位方向向量 即 与轴 平行，因 ,则 (6.3.32),6.3 多变量寻优技术,为了求最优步长 ，将(6.3.31)式代入目标函数，得 (6.3.33)将(6.3.33)式对求导并令其等于零，得 (6.3.34)故： 因此，第一次搜索的结果为,6.3 多变量寻优技术,第二次搜索的方向应为 的

38、共轭方向，即 (6.3.35)得 又有单位向量 (6.3.36)解联立方程(6.3.35)式及(6.3.36)式，得,6.3 多变量寻优技术,因此： (6.3.37)为求最优步长 ，将式(6.3.37)式代入目标函数得 (6.3.38)将(6.3.38)式对 求导，并令其等于零，得 (6.3.39),6.3 多变量寻优技术,得： 因此： 由此可见，因是一个二元的二次函数，只要搜索两个方向 ， 就可以达到极小点，即 8， 6。对于一个 元的二次函数，可以用不超过 次的搜索方向，就可以达到极小点。从上例可知，计算共轭方向时要用矩阵 ，如果已知 ，则计算共轭方向是容易的。例如，当函数为二次函数时，

39、为二次项的常系数矩阵。但当函数为非二次时， 为二阶偏导数矩阵(赫森矩阵)，求起来相当麻烦，尤其当维数很高时更加麻烦。因此，能否避免矩 阵 的直接计算，而用间接的方法确定共轭方向呢？下面介绍一种间接求共轭方向的方法。,6.3 多变量寻优技术,设目标函数为元的二次函数 (6.3.40)设 为n维向量； 为任意给定的起点。 为 次迭代中要寻求得对的共轭方向。依次为沿这些方向求得的近似极小点。因此有 (6.3.41) (6.3.42) 为最优步长，它满足 (6.3.43),6.3 多变量寻优技术,当然，对 也有 (6.3.44)将(6.3.44)式与(6.3.41)式相减，并将(6.3.42)式代入，

40、得 (6.3.45)根据共轭的定义，应有 (6.3.46)将(6.3.45)式代入(6.3.46)式，得 (6.3.47)从(6.3.47)式看出，不计算矩阵A可以求出共轭的方向。,6.3 多变量寻优技术,现从点 开始进行搜索，在确定第一个搜索方向 时，因为除了梯度 可以直接计算外，没有其他有用的信息，因此可取 (6.3.48)将沿 方向作为一位搜索，求最优步长 ,使 (6.3.49) 由此得一新的点 ,并算出 。因为 是点 的法线方向， 而 是 点的切线方向，所以 与 正交，从而也和 正交，即,6.3 多变量寻优技术,为在 和 构成的正交系中寻求共轭方向 ,可令 (6.3.51)共轭方向 为

41、该次的反梯度方向与上次搜索方向得线性组合，这里的问题是选择一个 ，使 与 共轭。根据(6.3.47)式，有 (6.3.52)将(6.3.50)式与(6.3.51)式代入(6.3.52)式中，化简得,6.3 多变量寻优技术,所以有： = (6.3.53)把(6.3.53)式代入(6.3.51)式， 得 (6.3.54)由此可见，通过 与 即可求出共轭方向 .沿此 方向在进行一维搜索求最优步长 ，得到 ，如此进行下去，一般来说有以下的迭代方向： (6.3.55) (6.3.56)所得到的 即为共轭方向。,6.3 多变量寻优技术,按照(6.3.55)式及(6.3.56)式确定搜索方向的算法成为共轭梯

42、度法。其程序框图如图6.3.6所示。,图 6.3.6 共轭梯度法的程序框图,6.3 多变量寻优技术,例6.3.2目标函数 ，设起点为 ，试用共轭梯度法求最小值。解：第一次迭代计算：,6.3 多变量寻优技术,求 得本例题中的 可以用解析法求得 经两次迭代即达到极值点。与一阶梯度法相比其收敛速度较快。,6.3 多变量寻优技术,用C语言编写的共轭梯度法计算程序清单如下： #include “math.h” #include “stdio.h”float x10,y10,p10,f,h;int n;void fun()int i; for(I=1;In,I+) xI=yI+h*pI;f=x1*x1+x

43、2*x2-x1*x2-10*x1-4*x2;f=f+60;return;,6.3 多变量寻优技术,main()float g10,q1,q0,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;int I,k,u;printf(“INPUT N,En”); scanf(“%d,%d”,6.3 多变量寻优技术,for(i=1;If2) t=t+t;u=u+1;else t=-t;h3=h1;f3=f1;h1=h2;f1=f2;h2=h3;f2=f3;,6.3 多变量寻优技术,p1: h3=h2+t;=h3; fun( );f3=f; if(f2f3) t=t+t;

44、u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;goto p1; else if(u0)h4=0.5*(h2+h3);h=h4; fun( );f4=f; if(f4f2) h3=h4;f3=f4; elseh1=h2;f1=f2;h2=h4;f2=f4; c1=(f3-f1)/(h3-h1); c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);,6.3 多变量寻优技术,if(f2f2)h1=h2;f1=f2;else h1=h4;f1=f4;t0=v*t0;goto p2; ,6.3 多变量寻优技术,goto p4;p3: h=0;fun( );printf(“OBJ

45、.FUNC F=%fn”,f);for(I=1;In;I+) printf(“X%d”,I); printf(“=%fn”,xI);,6.3 多变量寻优技术,6.3.3 单纯形法函数 的导数是函数 特性的重要反映，但在许多实际问题中，常常得不到计算 导数的解析式，而只能采用近似的方法，常用方法是有限差分法。用有限差分法计算 的导数不仅误差大，而且要多次计算目标函数，计算工作量很大。为了克服求 导数所带来的问题，提出了松弛法、单纯形法、随机搜索法等方法。这一节介绍工程中常用的单纯形法。从直观上看，如果不计算导数，则可以先算出 在若干个点处的函数值，然后将它们进行比较，从它们之间的大小关系就可以看

46、出函数变化的大致趋势，这样也能为寻求函数的下降方向提供参考。,6.3 多变量寻优技术,例如，图6.3.7所示的情况，变量有两个 ， ，图中画出了 的等高线簇。若先计算1，2，3三点(他们构成一个三角形)的函数值，然后对它们的大小进行比较，其中 最大，故将1点抛弃，在1点的对面取一点4，则构成一个新的三角形再比较各点 的大小，其中 最大，故将2点抛弃，在2点的对面取一点5，这样3，4，5又构成一个新的三角。如此一直循环下去最后可找到最小点。单纯形寻优方法的思想是很简单明了的，但是为了使其比较使用，同时能加快它收敛速度，还要解决一下几个主要问题。,6.3 多变量寻优技术,一、单纯形应由几个点构成

47、对于一般的n元函数 ( 为 维向量)，可取 维空间中 个点， ，构成初始单纯形。这 个点，应使n个向量， ， ， 为线性独立。这就是说，在平面上( )取不同一直线的三点构成单纯形(三角形)，在三维空间( )内取不同的四个点(4面体)。如果点取得少，或n个向量有一部分线性相关，那么就会使搜索极小点的范围局限在一个低维空间内，如果极小点不在这个空间内，就搜索不到了。,6.3 多变量寻优技术,二、单纯形的形状 为了简单起见，单纯形取n个向量为“等长”。 具体来讲，若已选定 ，则 这n个点为 (6.3.57) 其中， 为第 个单位坐标向量，即 (6.3.58) 只有第 个元素为1，其他均为0。,6.3

48、 多变量寻优技术,三、新点的选取根据经验及考虑到计算方便 ，一般新的点取在被抛弃的点的“对面”，称为反射点。以图6.3.8所示为例，假定为要抛弃的点，则新点的坐标应为，坐标可以这样来求：,图6.3.7 单纯形法寻优过程 图6.3.8 反射点的确定,6.3 多变量寻优技术,先求出 及 两个点的中心 ，则 (6.3.59)然后再求其反射点 ，即 (6.3.60)推广到多变量(n维)的情况，则有 , 共 个点，假定其中 点是被抛弃的，那么， 反射点 为 (6.3.61)其中:,6.3 多变量寻优技术,四、关于新点的扩张压缩及单纯形的收敛问题对组成单纯形的(n1)个点，可以定义： 为最坏点(即目标函数

49、 最大的点) 为最好点(即 最小的点)； 为次坏点(即 比 小，但比其他各点的目标函数都大)。如果新的点 的函数值 小于 ，这说明点可能前进得不够，此时可以沿反射方向再多前进一些(称为扩张)，即 (6.3.62),6.3 多变量寻优技术,反之，若按(6.3.61)式找到 ，而 大于 ，这说明 点前进得太远了，需要压缩，即要在 与 的延长线上(即沿原来的反射方向)后退一些，得 (6.3.63) 为压缩因子，它是01之间的一个常数，为了避免 与 重合(即 )，要求 ( 与 重合会使单纯形的空间维数降低，这不利于搜索)。 如果压缩后 仍然大于 ，这说明原先的单纯形取得太大了，可以将他们所有的边都缩小

50、，构成新的单纯形，这叫单纯形的收缩。具体办法是： (6.3.64),6.3 多变量寻优技术,五、什么时候停止搜索若 则说明搜索成功，此时可以认为 即为极小点，而 为极小值。如果经过K次搜索，仍然不能满足上式，说明搜索失败。根据上面的介绍，可画出单纯形法的程序框图，如图6.3.9所示。这个程序基本上包括以下7个部分：(1)计算原始的单纯形；(2)计算原始的单纯形各点的目标函数值；(3)找到最好点 ，最坏点 ，以及次坏点 ；(4)寻优次数 加1，并判断计算是否收敛，若收敛，则打印出结果；,6.3 多变量寻优技术,(5)搜索次数是否超过规定，若已超过，则说明搜索失败，打印出结果，并停止搜索，若未超过