第三讲一维优化方法

《第三讲一维优化方法》由会员分享，可在线阅读，更多相关《第三讲一维优化方法（62页珍藏版）》请在金锄头文库上搜索。

1、第三章 一维优化方法济南大学 机械设计系 王桂从1第三章 一维优化方法n本章所解决的基本问题是对一维目标函数 F(x) 求最优点的问题，它虽然是求单变量极值问题，考虑到很多时候函数的求导比较困难，甚至根本不可导，所以在最优化技术中一般不用解析法而是采用直接探索方法求最优点，对单变量直接探索称为一维探索或一维搜索，这种求优的方法称为一维优化方法。n对于多维的优化问题，一般是转化为一维问题处理，所以一维优化方法是用于求解多维优化的基础。2二维优化问题中一维搜索对于任意一次迭代计算，总是 希望从已知的点 x(k) 出发，沿 给定的方向 s(k) 搜索到目标函 数极小值点 x(k+1)，即求参数 a

2、的一个最优步长因子a(k)，使：F(x(k+1) ) = minF(x(k) +a(k) s(k) )这种在给定方向上确定最优步长的过程，在多维优化过程中是多 次反复进行的，所以说一维搜索是解多维优化问题的基础。上述极小化问题实际上是以a为变量的一维优化问题，表示为 ：minf(a)3第三章 一维优化方法ppFibonacciFibonacci法法/ /分数法分数法pp格点法格点法pp黄金分割法黄金分割法*pp二次插值法二次插值法*3.1 3.1 初始搜索区间的确定*3.2 一维搜索的最优化方法pp试探搜索试探搜索pp前进搜索前进搜索pp后退搜索后退搜索u一维搜索一般 分两步进行。第 一步是在

3、s(k)方向 上确定函数值最 小点所在区间， 第二步是求出该 区间内的最优步 长因子a(k)43.1 搜索区间的确定在一维搜索时，需要确定一个搜索区间a，b，此区间必须包含 函数的极小点 x*，因此搜索区间必须是单峰区间，即该区间内的 函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a ，b逐渐缩小，直至足够小，就可以得到近似最优点。5确定初始搜索区间进退法对于比较简单的一维优化问题，其搜索区间 可以根据实际情况确定，但对于多维优化问 题，在每一次一维搜索之前都用人为方法确 定搜索区间是很困难的。所以必须建立一定 的方法，使计算机在优化过程中自动地确定 。6一、试探搜索1、若 y2 y

4、1 ， 则极小点位于x1点左方，应反向后退搜索前 进 搜 索后 退 搜 索x1x1x2x2x3x3h02h0h02h0注意：x1x2互换 后再取x3y1y3 y2y2 y3 y1设函数为 y =f(x) ,给定初始点为x1 ，选定的初始步长为h0。由初始点 x1 沿 x 轴正向取 x2 点，x2=x1+h0，计算 x1 , x2 的函数值 y1 , y2 ， 比较 y1 , y2 的大小，则极小点的位置有如图所示两种情况：7一、前进搜索前 进 搜 索x1x2x3h02h0y1y3 y2令h h0，并使步长加倍 h2h， 取得 x3点，x3 x2+h=x2+2h0，其函数值 y3与y2 比较有如

5、下情况 ：1、若y2 y2 y2y3，则继续前进搜索，各点变换如下：x1 x2 ，y1 y2x2 x3 ，y2 y39三、后退搜索x1x2h02h0注意：x1x2互换 后再取x3y2 y3 y1令 h -h0，并将 x1 与 x2 对调 ，使步长加倍 h2h，取得x3 点， x3 x2+h，其函数值 y3与 y2比较有如下情况：1、若y2 y2 y2y3，则继续后退搜索，各点变换如下：x1 x2 ，y1 y2x2 x3 ，y2 y3x1x2x3h02h0y1y3y2x1x2x3h02h0y1y3y211四、进退法确定搜索区间流程图12例题例题3.1：试用进退法确定函数 f(x) = x2-6x

6、+9 的一维优化搜索区间a ，b，设初始点 x1=0，初始步长 h0=1解：计算过程如下:hh0=1 x2x1+h=1 y1=f(x1)=9, y2=f(x2)=4由于y2y1，作前进搜索： h2h=2 x3x2+h=3 y3=f(x3)=0 比较y2, y3有 y2y3，再做前进搜索x1x2=1, y1y2=4 x2x3=3, y2y3 =0 h2h=4 x3x2+h=7, y3=F(x3)=1613再比较y2，y3有y2y3，则取ax1=1，bx3=7搜索区间a，b为1，7 搜索过程见下图143.2 一维搜索的最优化方法在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在

7、满足收敛精度或迭代精度 的情况下，使其达到包含极小点的一个很小的邻域， 以取得一个近似的最优点。一维优化的方法有如下几种：1. 分数法/Fibonacci法2. 格点法3. 黄金分割法 4. 二次插值法15Fibonacci数列13世纪的意大利数学家斐波那契(Fibonacci)提出了这样一个问题：假定一对兔子在它们出生 整整两个月以后可以生一对小兔子，其后每隔 一个月又可以再生一对小兔子。假定现在在一 个笼子里有一对刚生下来的小兔子，请问一年 以后笼子里应该有几对兔子？16Fibonacci数列斐波那契(Fibonacci)数列：0,1, 1, 2, 3, 5, 8, 13.17Fibona

8、cci数列的性质n数学定义：F0 = 0 ； F1 = 1； Fn = F n - 1 + F n 2， n2 数列Fn 称为Fibonacci 数列，Fn称为第n 个Fibonacci 数，相邻两个Fibonacci 数之比Fn-1/Fn 称为称为 Fibonacci 分数。18一维搜索算法试探法原理试探法主要有：v 斐波那契法（序贯实验法）；v 黄金分割法 (0.618法)19试探法原理在区间 a , b内任取两点 a1 和 b1 ，a1 0 0，确定搜索次数 n 。 23Fibonacci法算法步骤斐波那契法寻优收敛快，计算次数少，然而每 步取点繁琐，且各步缩短率不同。为此，引 出黄金分

9、割法。 第三步：k=n-1时，t1=t2=(a+b)/2，无法比较，此时取24黄金分割法1)若y1 f(x3)，则新区间为a, x1。设区 间缩短率为2。为保持相同的区间缩短率，应有 ： 证明：由此可得： =0.618。因而黄金分割法又称0.618法，是一种 等比例缩短区间的直接搜索法28黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。因而内分点的取点规则为：x1=a+ 0.382(b-a)x2=a+ 0.618(b-a)终止原则：最优解：k 为缩短区间的次数29黄金分割法的搜索过程1、给出初始搜索区间a, b及收敛精度 ；2、按坐标点计算公式计算，并计算相应的函数值；3、缩短搜索

10、区间；4、检查是否满足收敛条件；5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。30黄 金 分 割 法 的 流 程 图31例题例题3.3 试用黄金分割法求目标函数 f(x)=x2-6x+9 的最优解。给定初始 区间1，7，收敛精度=0.4。解：第一次区间缩短计算过程：计算两内点及对应函数值：x1=a+0.382(b-a)=3.292 y1=f(x1)=0.085264 x2=a+0.618(b-a)=4.708 y2=f(x2)=2.917264作数值比较，可见y1x2?f2fP*?f2fP*?x1 xp* f1 fP*x3 x2 f3 f2 x2 xp* f2 fP*x1 x2

11、f1 f2 x2 xp* f2 fP*x3 xp* f3 fP*出口YYYNNNabcd51终止准则及最优解x* xp* (k) f * f (x*)最优解：终止准则：52二 次 插 值 算 法 的 流 程 图说明三点在 一直线上说明xp*落在区 间x1, x3外53例题3.4例题3.4 试用二次插值法求函数 f(x) = (x-3)2 的最优解，初始区间为1 ，7，精度=0.01解解：(1)初始插值节点x1=a=1, f1=f (x1)=4 x2=0.5(a+b)=4, f2=f (x2)=1 x3=b=7, f3=f (x3)=16 (2)计算插值函数的极小点与极小值54例题3.4 (3)

12、 缩短区间因有 ，故有x1=1, f1=4 x2xp*(1) =3, f2=0 x3x2=4, f3=1(4) 重复步骤(2)c1=-1 c2=1 (5) 检查终止条件获得最优解xp*(2) =3fp*(2) =055例题3.5例题3.5 用二次差值法求非二次函数 的最优解。初始 区间端点为a=-0.5, b=2.5。精度要求=0.005(1) 初始插值节点x1=a=-0.5, f1=f (x1)=-0.851279 x2=0.5(a+b)=1 f2=f (x2)=-2.610944 x3=b=2.5, f3=f (x3)=15.615452(2) (2) 计算计算 与与 c1=5.48891

13、0, c2=4.441347解：解：56例题3.5(3) (3) 缩短区间缩短区间因有因有 ， 故取故取 x1=-0.5, f1=-0.851279 x2=0.382067, f2=-20927209 x3=1, f3=-2.610944(4) (4) 对新区间重复步骤二对新区间重复步骤二c1=-1.17311, c2=1.910196(5) (5) 检查终止条件检查终止条件未满足终止条件，返回步骤（未满足终止条件，返回步骤（3 3）57计算次数12345x1 x2 x3 f1 f2 f3 c1 c2 xp* fp*-0.5 1.0 2.5 -0.851279 -2.610944 15.615

14、452 5.488910 4.441347 0.382067 -2.927209-0.5 0.382067 1.0 -0.851279 -2.927209 -2.610944 -1.17311 1.910196 0.557065 -3.040450 0.1749980.382067 0.557065 1.0 -2.927209 -3.040450 -2.610944 0.511811 2.616433 0.593226 -3.046534 0.0361610.557065 0.593226 1.0 -3.040450 -3.046534 -2.610944 0.969682 2.797449 0.605217 -3.047145 0.0119910.593226 0.605217 1.0 -3.046534 -3.047145 -2.610944 1.070840 2.841548 0.608188 -3.047188 0.002971计算结果表58经五次差值计算后，得得最优解59一维优化方法的比较6 格点法的结构及程序很简单,但效率偏低；6 黄金分割法的结构简单，使用可靠，但效率也不高；6 格点法和黄金分割法适于低维优化问题中的一维搜索 ；6 二次插值法在同样搜索次数下，其计算精度更高，但 程序略复杂