无约束优化计算方法ppt课件

1、本次课的主要内容：本次课的主要内容：一维寻优最优化的概念极值存在区间确实定紧缩区间计算原理黄金分割法的由来及其计算步骤0.618法的程序框图第四章第四章 无约束优化计算方法无约束优化计算方法4.1 引言引言一、无约束优化问题的普通方式: 求其最优解 和 的方法,称为无约束优化计算方法分 类非梯度算法随机搜索法、坐标轮换法、Powell法、单纯形法等梯度法、共轭梯度法、牛顿法、修正牛顿法、变尺度法等梯度算法)(minxfnRx)(xfx二、无约束优化问题的普通步骤:1.从某一初始点 开场迭代计算；2.各种方法在 领域内产生新点 ；3.检验点 能否满足最优性条件。函数构造不同迭代终止准那么)0(x

2、)1( kx)(kx)1( kx4.2 单变量优化计算方法单变量优化计算方法即，求优化步长因子 使 沿给定方向到达极小值。 那么称为一维搜索的最优步长因子。求 值的方法称为一维搜索优化计算方法或单变量优化计算方法。)(min)()()()1(kkkffsxx)(k)()()(kkfsx)(k)(k一、概念一维搜索表示图)(xf)()(kf x)(ks)(min)()(kkfsx)(kx)(kks1x2x)(min)()()()1(kkkffsxx 当目的函数可以准确求导时,其最优步长因子可以用解析法求得：)()()()()()()()(kkTkkTkkfsxHssx一维搜索方法包括: 分数法(

3、Fibonacci法)、黄金分割法0.618法、 牛顿法、二次插值法和三次插值法等。一维搜索最优化方法步骤：1、在 方向上确定函数值最小点所在区间2、求出该区间内的最优步长因子)(ksk二、分类及普通步骤4.2.1 搜索区间确实定搜索区间确实定 所谓搜索区间就是沿所谓搜索区间就是沿 方向找出一个单峰区间方向找出一个单峰区间 ,即在该区间内的函数变化只需一个峰值即在该区间内的函数变化只需一个峰值,如下图如下图: 性质：假设在性质：假设在 区间内另取一点区间内另取一点 ，即，即 或或 )(ks31，2321321)()()(321fff31，单峰函数123)(f)()()(1kffx)(2f)(3

4、f)(f)(f 将初始迭代 和 定为搜索区间的左端点 ；用一试探步长 沿 方向挪动一步 并计算其点的函数值 ，假设 那么继续增大步长 ，再计算其函数值 ，与前一点的函数值进展比较，直到相临两点的函数值满足 时为止，即构成了高-低-高的一维函数曲线；最后一点就定为搜索区间的右端点 。 中间点 。)(f)()()(1kffx)(1kx2t)(3it)(21it 正向搜索)(kx)()(kf x0ts012tt)()()(2)(2kktftfsx)()(21tff002tt )(2tf)()(1iitftfit1311t112it321)()()(321fff前进极小点在右方 假设 ，那么步长值 改

5、为 ，即取步长 ，继续计算，直到 为止，也可得到高-低-高的一维函数曲线。将左端点值定为终止点 ，而右端点定为起始点 ，中间点定为 。)()(21tff0t0t012tt)()(1iitftfit13)(f)(3it)(21it2t1 反向搜索1112it321)()()(321fff后退进退法极小点在左方2t)(f1t2t3t11t22t33t外推法确定搜索区间)()(23tftf11t22t33t)()(23tftf向右挪动求新点想一想：想一想： 该方法的程序框图该方法的程序框图高-低-高32312ttttt，新点为为，为即以4.2.2 黄金分割法黄金分割法0.618法法 黄金分割法适用于

6、黄金分割法适用于 区间上的任何单峰函数求区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至极小值问题。对函数除要求单峰外不作其它要求，甚至可以不延续。因此，这种方法的顺应面相当广。可以不延续。因此，这种方法的顺应面相当广。一、区间紧缩原理一、区间紧缩原理 目的函数目的函数 ， 所在搜索区所在搜索区间第一次搜索时定为间第一次搜索时定为 ，求给定方向，求给定方向 上上的最优步长因子。的最优步长因子。 首先在首先在 区间内取两个区间内取两个 值值 , , 且且满足满足 并按一个公比并按一个公比 (0 eps & kfu a=l; %改动区间左端点 l=u; u=a+0.3

7、82*(b-a); else b=u; %改动区间右端点 u=l; l=a+0.382*(b-a); end k=k+1; tol=abs(b-a);endif k=100000 disp(找不到最小值); x=NaN; minf=NaN; return;endx=(a+b)/2;minf=subs(f,findsym(f),x);format short;书本的87页，习题4-1一、根本思想： 利用三点的函数值来构造一个二次插值多项式，以近似的表达原目的函数，并求这个的多项式的极值点作为原函数极小点的近似值。二、原理： 在一维搜索中， 与 均为知，因此目的函数是 的一元函数 如今构造一个二次

8、多项式 逼近目的函数4.2.2 二次插值法近似抛物线法二次插值法近似抛物线法)()()()()()1(fffkkksxx2)(cbap)(kx)(ks二次插值法原理图)(f12p431f2f3f)(f)(p)()()()()()1(fffkkksxx2)(cbap02)(cbddpcbp2，缩短搜索区间的关系，分析舍去区间和比较)()(24ff242fff13思索： 紧缩搜索区间时，有几种情况，书上的程序框图中是怎样处理这个问题的？二次插值程序框图课下作业课下作业 用黄金分割法求函数 的极小点，给定 要求： 1. 手工按黄金分割法计算 2. 至少用一种计算机言语以黄金分割法编程计算243)(3

9、xxxf2 . 0100，hx将一个多维的无约束最优化问题转化为一系列沿将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化问题的求解，因此也称坐标轴方向的一维易优化问题的求解，因此也称降维法。即，将一个降维法。即，将一个n维优化问题转化为依次沿维优化问题转化为依次沿n个坐标方向反复进展一维搜索问题。每次一维搜个坐标方向反复进展一维搜索问题。每次一维搜索时，只允许索时，只允许n个变量的一个改动，其他个变量的一个改动，其他(n-1)个个变量固定不变。变量固定不变。根本原理根本原理1对于对于n个变量的函数，假设在第个变量的函数，假设在第k轮沿着第轮沿着第i个坐个坐标方向进展搜索，其迭代

10、公式为：标方向进展搜索，其迭代公式为：kikikikisxx12求最优搜索步长求最优搜索步长ki计算步骤：计算步骤：3本轮一切方向搜索终了，判别迭代终止条件：本轮一切方向搜索终了，判别迭代终止条件：kkn0 xxknxx 4满足上式：满足上式：否那么，进展下一轮迭代。否那么，进展下一轮迭代。搜索方向与步长确实定1搜索方向确实定对于第k轮第i次的计算1kkkkiiiixxa d第k轮第I次的迭代方向，它轮番取n维坐标的单位向量。0.1.0kiide 搜索步长确实定关于 值通常有以下几种取法1加速步长法2最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即此时可以采用0.618方法或

11、二次插值方法来计算 的值。)( ki图4-12 加速步长法的搜索道路图4-14 最优步长法的搜索道路坐标轮换法存在的问题图4-14 坐标轮换法在各种不同情况下的效能a搜索有效；b搜索低效；c搜索无效 例例 求目的函数求目的函数 的极小点。的极小点。 取初始点取初始点02,2Tx2212( )25fxxx 220122010101010001sxx解：第一轮迭代：解：第一轮迭代：220101225)2()(xf20)(0101f 求最优搜索步长求最优搜索步长2001x020202020102201020sxx20202)2(25)(xf20)(0202f 求最优搜索步长求最优搜索步长0002x沿

12、着第二个坐标方向搜索：沿着第二个坐标方向搜索：00100010111111011sxx判别终止条件，不满足，进展第二轮迭代：判别终止条件，不满足，进展第二轮迭代：21111)()(xf00)(1111f 求最优搜索步长求最优搜索步长0011x12121212111201000sxx21212)(25)(xf00)(1212f 求最优搜索步长求最优搜索步长0012x沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：01012xx00knxx例例3: 用坐标轮换法求下面问题的最优解，给定初用坐标轮换法求下面问题的最优解，给定初始点始点X0=0 0T,精度要求精度要求=0.160410)(212122

13、21xxxxxxxf0010011)1(11)1(0)1(1)0()1(1SXXXX6010)(min121)1(1XF解解: 第一轮迭代第一轮迭代求最优步长，即极小化：求最优步长，即极小化： 05)( , 50102)()1(1)1(111)1(1XdXdF22)1(22)1(1)1(251005SXX以以X1(1)为新起点，沿为新起点，沿e2方向进展一维搜索：方向进展一维搜索： 5 . 45)( , 5 . 4092)()1(2)1(222)1(2XdXdF仍以最优步长原那么确定仍以最优步长原那么确定2： 继续进展第二轮迭代计算，等等。继续进展第二轮迭代计算，等等。从坐标轮换法的迭代过程可以看出其搜索道路较长，计算从坐标轮换法的迭代过程可以看出其搜索道路较长，计算效率低。效率低。因此，普通以为此法仅适宜因此，普通以为此法仅适宜n n1010的小型优化问题的求解。的小型优化问题的求解。另外，此法的效能在很大程度上取决于目的函数的性质。另外，此法的效能在很大程度上取决于目的函数的性质。7 . 65 . 4522)1 (0)1 (2XX按终止条件检验：按终止条件检验：1计