004第四章 无约束优化计算方法.ppt

《004第四章 无约束优化计算方法.ppt》由会员分享，可在线阅读，更多相关《004第四章 无约束优化计算方法.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法）法）黄金分割法适用于 区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。一、一、区间压缩区间压缩原理原理 目标函数 ，所在搜索区间第一次搜索时定为 ，求给定方向 上的最优步长因子。首先在 区间内取两个 值 ,且满足 并按一个公比(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);e

5、ndif k=100000 disp(找不到最小值);x=NaN;minf=NaN;return;endx=(a+b)/2;minf=subs(f,findsym(f),x);format short;书本的87页，习题4-1一、基本思想：利用三点的函数值来构造一个二次插值多项式，以近似的表达原目标函数，并求这个的多项式的极值点作为原函数极小点的近似值。二、原理：在一维搜索中，与 均为已知，因此目标函数是 的一元函数 现在构造一个二次多项式 逼近目标函数4.2.2 二次插值法（近似抛物线法）二次插值法（近似抛物线法）二次插值法原理图思考：压缩搜索区间时，有几种情况，书上的程序框图中是怎样解决这

6、个问题的？二次插值程序框图课下作业课下作业用黄金分割法求函数 的极小点，给定要求：1.手工按黄金分割法计算 2.至少用一种计算机语言以黄金分割法编程计算4.3 多变量优化计算的非梯度方法多变量优化计算的非梯度方法4.34.3.1.1 坐标轮换法坐标轮换法将一个多维的无约束最优化问题转化为一系列沿将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化问题的求解，因此也称坐标轴方向的一维易优化问题的求解，因此也称降维法降维法。即，将一个。即，将一个n维优化问题转化为依次沿维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。每次一维搜个坐标方向反复进行一维搜索问题。每次一维搜索时，只允

7、许索时，只允许n个变量的一个改动，其余个变量的一个改动，其余(n-1)个个变量固定不变。变量固定不变。基本原理基本原理4.34.3.1.1 坐标轮换法坐标轮换法1）对于）对于n个变量的函数，若在第个变量的函数，若在第k轮沿着第轮沿着第i个坐标个坐标方向进行搜索，其迭代公式为：方向进行搜索，其迭代公式为：2）求最优搜索步长）求最优搜索步长计算步骤：计算步骤：3）本轮所有方向搜索完毕，判断迭代终止条件：）本轮所有方向搜索完毕，判断迭代终止条件：4）满足上式：）满足上式：否则，进行下一轮迭代。否则，进行下一轮迭代。搜索方向与步长的确定（1）搜索方向的确定对于第k轮第i次的计算第k轮第I次的迭代方向，

8、它轮流取n维坐标的单位向量。搜索步长的确定关于 值通常有以下几种取法（1）加速步长法（2）最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即此时可以采用0.618方法或二次插值方法来计算 的值。图4-12 加速步长法的搜索路线图4-14 最优步长法的搜索路线坐标轮换法存在的问题图4-14 坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效 例例 求目标函数求目标函数 的极小点。的极小点。取初始点取初始点解：第一轮迭代：解：第一轮迭代：求最优搜索步长求最优搜索步长 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：判断终止条件

9、，不满足，进行第二轮迭代：判断终止条件，不满足，进行第二轮迭代：求最优搜索步长求最优搜索步长 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：例例3:用坐标轮换法求下面问题的最优解，给定初用坐标轮换法求下面问题的最优解，给定初始点始点X0=0 0T,精度要求精度要求=0.1解解:第一轮迭代第一轮迭代求最优步长，即极小化：求最优步长，即极小化：以以X1(1)为新起点，沿为新起点，沿e2方向进行一维搜索：方向进行一维搜索：仍以最优步长原则确定仍以最优步长原则确定2：继续进行第二轮迭代计算，等等。继续进行第二轮迭代计算，等等。从坐标轮换法的迭代过程可以看出其搜索路线较长，

10、计算从坐标轮换法的迭代过程可以看出其搜索路线较长，计算效率低。效率低。因此，一般认为此法仅适宜因此，一般认为此法仅适宜n n1010的小型优化问题的求解。的小型优化问题的求解。另外，此法的效能在很大程度上取决于目标函数的性质。另外，此法的效能在很大程度上取决于目标函数的性质。按终止条件检验：按终止条件检验：（1）计算量少，程序简单，不需要求函数导数的直接）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。）探索路线较长，问题的维数愈多求解的效率愈低。当维数当维数n10时，则不应采用此法。仅适用于时，则不应采用此法。仅适用于n较少（较少（n 10）的目标函数求优；）的目标函数求优；（3）改变初始点重新迭代，可避免出现病态。）改变初始点重新迭代，可避免出现病态。方法特点方法特点