《无约束优化计算方法ppt课件》由会员分享，可在线阅读，更多相关《无约束优化计算方法ppt课件（41页珍藏版）》请在金锄头文库上搜索。
1、本次课的主要内容：本次课的主要内容：1.一维寻优最优化的概念2.极值存在区间确实定3.紧缩区间计算原理4.黄金分割法的由来及其计算步骤5.0.618法的程序框图第四章第四章 无约束优化计算方法无约束优化计算方法4.1 引言引言一、无约束优化问题的普通方式: 求其最优解 和 的方法,称为无约束优化计算方法分 类非梯度算法随机搜索法、坐标轮换法、Powell法、单纯形法等梯度法、共轭梯度法、牛顿法、修正牛顿法、变尺度法等梯度算法二、无约束优化问题的普通步骤:1.从某一初始点 开场迭代计算；2.各种方法在 领域内产生新点 ；3.检验点 能否满足最优性条件。函数构造不同迭代终止准那么4.2 单变量优化
2、计算方法单变量优化计算方法即，求优化步长因子 使 沿给定方向到达极小值。 那么称为一维搜索的最优步长因子。求 值的方法称为一维搜索优化计算方法或单变量优化计算方法。一、概念一维搜索表示图 当目的函数可以准确求导时,其最优步长因子可以用解析法求得：一维搜索方法包括: 分数法(Fibonacci法)、黄金分割法0.618法、 牛顿法、二次插值法和三次插值法等。一维搜索最优化方法步骤：1、在 方向上确定函数值最小点所在区间2、求出该区间内的最优步长因子二、分类及普通步骤4.2.1 搜索区间确实定搜索区间确实定 所谓搜索区间就是沿所谓搜索区间就是沿 方向找出一个单峰区间方向找出一个单峰区间 ,即在该区
3、间内的函数变化只需一个峰值即在该区间内的函数变化只需一个峰值,如下图如下图: 性质：假设在性质：假设在 区间内另取一点区间内另取一点 ，即，即 或或 单峰函数 将初始迭代 和 定为搜索区间的左端点 ；用一试探步长 沿 方向挪动一步 并计算其点的函数值 ，假设 那么继续增大步长 ，再计算其函数值 ，与前一点的函数值进展比较，直到相临两点的函数值满足 时为止，即构成了高-低-高的一维函数曲线；最后一点就定为搜索区间的右端点 。 中间点 。 正向搜索前进极小点在右方 假设 ，那么步长值 改为 ，即取步长 ，继续计算，直到 为止，也可得到高-低-高的一维函数曲线。将左端点值定为终止点 ，而右端点定为起
4、始点 ，中间点定为 。 反向搜索后退进退法极小点在左方外推法确定搜索区间向右挪动求新点想想一一想想： 该该方方法法的的程程序序框框图图高-低-高4.2.2 黄金分割法黄金分割法0.618法法 黄金分割法适用于黄金分割法适用于 区间上的任何单峰函数求区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至极小值问题。对函数除要求单峰外不作其它要求，甚至可以不延续。因此，这种方法的顺应面相当广。可以不延续。因此，这种方法的顺应面相当广。一、区间紧缩原理一、区间紧缩原理 目的函数目的函数 ， 所在搜索区所在搜索区间第一次搜索时定为间第一次搜索时定为 ，求给定方向，求给定方向 上上的最优
5、步长因子。的最优步长因子。 首先在首先在 区间内取两个区间内取两个 值值 , , 且且满足满足 并按一个公比并按一个公比 (0 eps & kfu a=l; %改动区间左端点 l=u; u=a+0.382*(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一、根本思想：
6、利用三点的函数值来构造一个二次插值多项式，以近似的表达原目的函数，并求这个的多项式的极值点作为原函数极小点的近似值。二、原理： 在一维搜索中， 与 均为知，因此目的函数是 的一元函数 如今构造一个二次多项式 逼近目的函数4.2.2 二次插值法近似抛物线法二次插值法近似抛物线法二次插值法原理图思索： 紧缩搜索区间时，有几种情况，书上的程序框图中是怎样处理这个问题的？二次插值程序框图课下作业课下作业用黄金分割法求函数 的极小点，给定要求： 1. 手工按黄金分割法计算 2. 至少用一种计算机言语以黄金分割法编程计算4.3 多多变量量优化化计算的非梯度方法算的非梯度方法4.3.1 4.3.1 坐坐标轮
7、换法法将一个多维的无约束最优化问题转化为一系列沿将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化问题的求解，因此也称坐标轴方向的一维易优化问题的求解，因此也称降维法。即，将一个降维法。即，将一个n维优化问题转化为依次沿维优化问题转化为依次沿n个坐标方向反复进展一维搜索问题。每次一维搜个坐标方向反复进展一维搜索问题。每次一维搜索时，只允许索时，只允许n个变量的一个改动，其他个变量的一个改动，其他(n-1)个个变量固定不变。变量固定不变。根本原理根本原理4.3.1 4.3.1 坐坐标轮换法法1对于对于n个变量的函数，假设在第个变量的函数，假设在第k轮沿着第轮沿着第i个坐个坐标方向进
8、展搜索，其迭代公式为：标方向进展搜索，其迭代公式为：2求最优搜索步长求最优搜索步长计算步骤：计算步骤：3本轮一切方向搜索终了，判别迭代终止条件：本轮一切方向搜索终了，判别迭代终止条件：4满足上式：满足上式：否那么，进展下一轮迭代。否那么，进展下一轮迭代。搜索方向与步长确实定1搜索方向确实定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮番取n维坐标的单位向量。搜索步长确实定关于 值通常有以下几种取法1加速步长法2最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即此时可以采用0.618方法或二次插值方法来计算 的值。图4-12 加速步长法的搜索道路图4-14 最优步长法的搜索道
9、路坐标轮换法存在的问题图4-14 坐标轮换法在各种不同情况下的效能a搜索有效；b搜索低效；c搜索无效 例例 求目的函数求目的函数 的极小点。的极小点。 取初始点取初始点解：第一轮迭代：解：第一轮迭代： 求最优搜索步长求最优搜索步长 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：判别终止条件，不满足，进展第二轮迭代：判别终止条件，不满足，进展第二轮迭代： 求最优搜索步长求最优搜索步长 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：例例3: 用坐用坐标轮换法求下面法求下面问题的最的最优解，解，给定初定初始点始点X0=0 0T,精度要求精度
10、要求=0.1解解: 第一轮迭代第一轮迭代求最优步长，即极小化：求最优步长，即极小化： 以以X1(1)为新起点，沿为新起点，沿e2方向进展一维搜索：方向进展一维搜索： 仍以最仍以最优步步长原那么确定原那么确定2： 继续进展第二轮迭代计算，等等。继续进展第二轮迭代计算，等等。从坐标轮换法的迭代过程可以看出其搜索道路较长，计算从坐标轮换法的迭代过程可以看出其搜索道路较长，计算效率低。效率低。因此，普通以为此法仅适宜因此，普通以为此法仅适宜n n1010的小型优化问题的求解。的小型优化问题的求解。另外，此法的效能在很大程度上取决于目的函数的性质。另外，此法的效能在很大程度上取决于目的函数的性质。按终止条件检验：按终止条件检验：1计算量少，程序简单，不需求求函数导数的直接计算量少，程序简单，不需求求函数导数的直接探求目的函数最优解的方法；探求目的函数最优解的方法；2探求道路较长，问题的维数愈多求解的效率愈低。探求道路较长，问题的维数愈多求解的效率愈低。当维数当维数n10时，那么不应采用此法。仅适用于时，那么不应采用此法。仅适用于n较少较少n 10的目的函数求优；的目的函数求优； 3改动初始点重新迭代，可防止出现病态。改动初始点重新迭代，可防止出现病态。 方法特点方法特点
