化工数值计算-7

过程最优化,7.1 单变量函数的最优化方法 单变量最优化是指对一元函数实现优化的 过程,它既是一种实际常用的优化方法,而且也是 多元函数最优化方法的基础。,求一元函数f(x)的极小值的方法有两类。对于简 单的一元函数,由极值理论可知,求极值问题可转 化为求方程根的问题,这种方法就是微分法或间 接法。然而,对于实际工程问题,进行化工单元过 程最优化时所建立的目标函数往往是无法求导 的,故而只能用不求导数的直接法求解。本章主 要讨论工程上常用的直接法:区间消去法和插值,法。 无论用哪种方法寻求一元函数的极值,必须预先 给定目标函数的极小值点所在的一个区间XA, XB。尽管对于某些工程优化问题,根据工程经验 即可确定出初始的搜索区间,但是,通常都需要确 定出此搜索区间。下面首先介绍一种区间搜索,方法。 7.1.1 搜索区间的确定 7.1.1.1 方法概要 设一元函数f(x)具有极小值点xm,且点x0xm,现取初始搜索步长为h, 按下述变步长方法确定搜索区间: 取点xA=x0和xC =x0 +h并计算相应的函数值f(xA)和f(xC)。, 若f(xA)f(xC)见图7-1(a),则将步长h减半,取xB =x0 +h/2并计算f (xB)。若f(xA)f(xB),则x0,x0 +h就是一个搜索区间,否则继续将步长 减半直至f(xA)f(xB)。,图7-1 变步长法确定搜索区间, 若f(xA)f(xC)见图7-1(b),则将步长h加倍,取xB =x0 +h和xC =x0 +2h 并计算f(xB)和f(xC)。若f(xC)f(xB),则x0,x0 +2h就是一个搜索区间,否 则继续将步长加倍,直至函数值上升。 利用这种方法可确定出搜索区间xA,xC,并获得其间的一点xB且满 足f(xA)f(xB)f(xC),可用于插值法中初始三点的选取。 7.1.1.2 程序框图 图7-2为确定一元函数f(x)极小值点的搜索区间xA,xC及xAxBxC、f,(xA)f(xB)f(xC)的计算程序框图。,图7-2 为确定区间xA,xC及xAf(xB)f(xC)的计算程序框图,程序框图中的主要变量: A 搜索初始点x0(要求x0xm) H 初始搜索步长 XA 搜索区间左端点 XC 搜索区间右端点 XB 搜索区间的中间一点,可作为极小值点的近似值,FA 搜索区间左端点函数值 FC 搜索区间右端点函数值 FB 搜索区间的中间一点函数值,且FAFBFC 7.1.1.3 计算实例,7.1.2 区间消去法菲波那西法和黄金分割法 7.1.2.1 方法概要 所谓区间消去法是通过不断地压缩函数极小值点存在的区间来确 定最优点的一种优化方法。 设一元函数f(x)在给定区间a, b内有一极小值点。先在区间a, b 内选取如下两点:,其中系数Î(0, 0.5)。由式(7-1a)和式(7-1b)可知,c、d两点是把原区 间a, b作对称分割的两个分点,如图7-1所示。计算函数在这些分 点上的值并进行比较: 若f(c)f(d),则函数极小值点必在区间a, d内,如图7-3(a),从而可 消去区间d, b;令a1 =a,b1 =d,则a, d构成一个新的搜索区间a1, b 1。, 若f(c)f(d),则函数极小值点必在区间c, b内,如图7-3(b),从而可 消去区间a, c;令a1 =c,b1 =b,则c, b构成一个新的搜索区间a1, b 1。,图7-3 区间消去法的示意,如此反复进行下去,函数极小值点所在的区间an, bn的长度将愈来 愈短,直到满足给定的精度要求ïan-bnï( 为给定的一个小量)。 为减少计算工作量,可充分利用已有的计算结果。因此,可将上次 对称分割的两个分点c、d中落入新区间a1, b1内部的那个分点取 作下次对称分割的两个分点之一。如何确定下次对称分割的配置 系数i呢? 例如,对图7-3(a),c =a + (b-a),c是落在新区间a1, b1内的分点,将c 取为新的分点之一d1,根据式(7-1b),有d1 =b1-1(b1-a1),其中1为新的,配置系数,因而可得: 又 a1 =a,b1 =d =b-(b-a) 则可得 1= (7-2) 这样,另一新分点应为:c1 =a1 + 1(b1-a1),计算函数值f(c1),就可以与f (d1)=f(c)(此函数值上次已算出)进行比较,以确定再次被缩短了的,新搜索区间a2, b2。 对图7-3(b),d是落在新区间a1, b1内的分点,将d取为新的分点之一c 1,完全类似地可求出此时的配置系数'1仍与式(7-2)相同。 亦即新区间a1, b1的对称分割配置系数及分割点为,若以n表示第n次分割所用的配置系数,则显然有关系式: 现在的问题是怎样才能比较简便地给出一组满足式(7-3)的配置系 数1,2,n,以便按这组系数去分割区间,寻求极小值点时可以 提高效率,节省计算量?下面就来介绍两种最常用的方法。 (1)菲波那西(Fibonacci)法 菲波那西法利用了菲波那西数列。该,数列中各数的值满足下列递推关系: 即该数列值为,若令 i= (i=0,1,2,n-1)(7-5) 则有 = = = =i+1 由此可见,可用菲波那西数列按式(7-5)构成区间消去法的配置系 数i数列(分数序列,其值是变化的)。 由式(7-5)可知,只有确定出分割次数n,才能确定出i系数。这可根,据需要的精度来确定式(7-5)中的参数n。设初始区间的长度为L=b -a,则经过一次分割后新区间的长度为L1 =(1-1)L,若以Ln-1表示n-1次 分割后所得到的区间长度,则有,对于给定的精度要求,则选择n使FnL/即可。 由上述可见,菲波那西法限定了试验次数n。然而,在相同的计算次 数下,它比其他方法得到的精度都高,或者说在同样的精度要求下 它所需的计算次数最少。所以,菲波那西法是一个效率高的方 法。 (2)黄金分割法(0.618法) 菲波那西法的缺点是必须预先规定次数 (由要求的搜索精度来确定),这给应用上带来一定的不便,因为在计 算的后一阶段有时可能改变所要求的精度。此外,菲波那西法的,配置系数为分数序列,且在计算过程中为变数,也较麻烦。 假定每次分割的配置系数均相等,则由式(7-3)可得: 以及1-0.618,即著名数学家华罗庚教授发明的0.618法,又称为,黄金分割法。 黄金分割法不必预先规定试验次数,且配置系数是固定值,算法简 单,其效率也很高,但比菲波那西法稍低一点。 7.1.2.2 程序框图 (1)菲波那西法 图7-4为菲波那西法的通用计算程序框图,分为数 据输入、形成菲波那西数列和区间消去三个步骤。,程序框图中的主要变量如下: XA 搜索区间的起始端点 XB 搜索区间的终了端点 E 给定的精度 F 一维数组,存放菲波那西数列 XC 对称分割的左端点,XD 对称分割的右端点 XM 极小值点 YC、YD、YM 相应点的函数值 (2)黄金分割法 图7-5为黄金分割法的通用计算程序框图,其 中的主要变量与图7-4相同。 7.1.2.3 计算实例,7.1.3 插值法 7.1.3.1 方法概述 所谓插值法就是将目标函数f(x)用一个低次多项式函数p(x)来逼 近,然后就以比较容易计算的p(x)的极小值点来近似目标函数f(x) 的极小值点,并通过多次迭代逐步逼近的方法来得到满足给定精 度要求的近似解。 常用的插值法有二次插值法和三次插值法,它们分别对应于取逼,近多项式为二次多项式和三次多项式。三次插值法收敛较快,但 它需要计算目标函数的导数,计算比较麻烦,二次插值法计算比较 简单,这里只介绍二次插值法。 设单峰目标函数f(x)在区间xA,xC中存在极小值,且f(x)在三点xA fB fC。利用这三点及其相应的 函数值作二次插值,即逼近函数为:,故有 函数的极小值点应满足,即 由方程组(7-7)和式(7-8)可解得:,通常一次逼近结果不能满足给定的精度要求,而需作多次逼近,这 时可比较函数值fm =f(xm)和fB的大小,然后取其中较小的点及其两相 邻点作为新的三点再进行函数逼近;如此反复逐步逼近直至达到 精度要求,通常其判据取相邻两次逼近函数的极小值点之差小于 给定小量,即当满足条件 时迭代结束。,7.1.3.2 程序框图 图7-7为二次插值法的通用计算程序,分为数据输入、确定初始三 点和二次插值三部分。初始三点(即搜索区间)的确定采用子程序 SEARCH,参见图7-2。函数f(x)的计算可安排子程序F。,图7-7 二次插值法的通用计算程序框图,程序框图中的主要变量: X0 初值 H 搜索步长 E 给定精度 XA 搜索区间左端点 XC 搜索区间右端点,XB 搜索区间的中间一点,可作为极小值点的初始近似值 FA、FB、FC 搜索区间各点函数值且FAFBFC XM 目标函数的极小值点 FM 极小值点的函数值 7.1.3.3 计算实例,7.2 无约束多变量函数最优化的单纯形法 在化工优化设计中,多数是多变量目标函数 的最优化问题。其最优化求解方法可分为两类: 直接法和间接法。如果目标函数f(x1,x2,xn)可 以求导数,则可以采用间接法;但由于化工过程优,化设计中目标函数多数较为复杂,一般较难或无 法求导数,故只能用直接搜索优化的方法。直接 法没有严格的理论基础,且计算量大,但是这种方 法无需对目标函数进行求导,程序原理简单,较容 易实现,对于求解化工优化设计的问题已具有足 够的精确度。,本节介绍无约束条件的多变量优化方法单 纯形法(simplex method)。 7.2.1 方法概述 所谓单纯形是指由n维空间中n+1个点的集合所形成的几何 图形,而这n+1个点叫做单纯形的顶点,例如,三角形是二维空 间中的单纯形,四面体是三维空间中的单纯形。若单纯形中 任意两个顶点间的距离都相等,则称这种单纯形为正规单纯,形。 利用单纯形法实现最优化的基本思想是:从n维空间中一个任 意形状的初始单纯形出发,先计算其n+1个顶点上函数的值, 并确定其中函数值为最大、次大和最小的点,然后通过反 射、扩张、压缩等操作求出一个新的较好点,并用它来取代 最大函数点构成新的单纯形,或者通过向最小函数点收缩形 成新的单纯形,如此反复迭代,单纯形不断更新、逐步向最优 点移动,围绕最优点收缩,从而逐步逼近极小值点。,下面以二元函数f(X),其中X为二维空间上的点,即X=(x1,x2)为 例,说明怎样实现单纯形的转换。 首先在(x1,x2)平面上给定不共线的三点X(1)、X(2)和X(3)构成初 始单纯形(见图7-8)。假设其中最大函数点X(h)=X(3),次大函数 点X(s)=X(2)、最小函数点X(l)=X(1)。现在进行反射,即将X(h)点经 过除它以外的其余点的形心进行反射,在这里,形心点是线段 X(1)X(2)的中心点X(0)=(X(1)+X(2)/2,得到的反射点为,式中,称为反射系数,通常取=1。 反射以后可能有四种不同情况,应采取四种不同步骤。 如果f(X(4)f(X(l),即反射点的函数值比最小值点的还小,则 沿X(0)X(4)的连线延伸可望函数值会进一步减小,因此,沿此方 向扩张,令,式中,1称为扩张系数,通常取=2。 若f(X(5)f(X(4),则以X(5)代替X(h),得到以X(1)、X(2)、X(5)为顶点的 新单纯形;反之,扩张失败,以X(4)代替X(h),得到以X(1)、X(2)、X(4) 为顶点的新单纯形。 如果f(X(l)f(X(4)f(X(s),即反射点的函数值在最小点和次,大点函数值之间,则用X(4)代替X(h),得到以X(1)、X(2)、X(4)为顶点 的新单纯形。 如果f(X(s)f(X(4)f(X(h),即反射点的函数值在最大点和次 大点函数值之间,这表明反射后只有轻微改进,这时,可进行压 缩,以检查是否有更好的点已被越过,令,