无约束优化计算方法.pptx

《无约束优化计算方法.pptx》由会员分享，可在线阅读，更多相关《无约束优化计算方法.pptx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1无约束优化计算方法无约束优化计算方法二、无约束优化问题的一般步骤:1 1.从某一初始点从某一初始点 开始迭代计算；开始迭代计算；2 2.各种方法在各种方法在 领域内产生新点领域内产生新点 ；3 3.检验点检验点 是否满足最优性条件。是否满足最优性条件。函数构造不同迭代终止准则第1页/共40页4.2 单变量优化计算方法单变量优化计算方法即，求优化步长因子 使 沿给定方向达到极小值。则称为一维搜索的最优步长因子。求 值的方法称为一一维搜索优化计算方法维搜索优化计算方法或单变量单变量优化计算方法优化计算方法。一、概念第2页/共40页一维搜索示意图一维搜索示意图一维搜索示意图一维搜索示意图第3

2、页/共40页 当目标函数可以精确求导时当目标函数可以精确求导时,其最优步长因子其最优步长因子可以用解析法求得：可以用解析法求得：一维搜索方法包括:分数法(Fibonacci法)、黄金分割法（0.618法）、牛顿法、二次插值法和三次插值法等。一维搜索最优化方法步骤：1、在 方向上确定函数值最小点所在区间2、求出该区间内的最优步长因子二、分类及一般步骤第4页/共40页4.2.14.2.1 搜索区间的确定搜索区间的确定搜索区间的确定搜索区间的确定 所谓搜索区间就是沿所谓搜索区间就是沿 方向找出一个单峰区间方向找出一个单峰区间 ,即在该区即在该区间内的函数变化只有一个峰值间内的函数变化只有一个峰值,如

3、图所示如图所示:性质：若在性质：若在 区间内另取一点区间内另取一点 ，即，即 或或 单峰函数单峰函数单峰函数单峰函数第5页/共40页 将初始迭代将初始迭代将初始迭代将初始迭代 和和和和 定为搜索区间的左端点定为搜索区间的左端点定为搜索区间的左端点定为搜索区间的左端点 ；用一试用一试用一试用一试探步长探步长探步长探步长 沿沿沿沿 方向移动一步方向移动一步方向移动一步方向移动一步 并计算其点的函数值并计算其点的函数值并计算其点的函数值并计算其点的函数值 ，若，若，若，若 则继续增大步长则继续增大步长则继续增大步长则继续增大步长 ，再计，再计，再计，再计算其函数值算其函数值算其函数值算其函数值 ，与

4、前一点的函数值进行比较，直到相临两点，与前一点的函数值进行比较，直到相临两点，与前一点的函数值进行比较，直到相临两点，与前一点的函数值进行比较，直到相临两点的函数值满足的函数值满足的函数值满足的函数值满足 时为止，即形成了时为止，即形成了时为止，即形成了时为止，即形成了高高高高-低低低低-高高高高的一维函的一维函的一维函的一维函数曲线数曲线数曲线数曲线；最后一点就定为搜索区间的右端点最后一点就定为搜索区间的右端点最后一点就定为搜索区间的右端点最后一点就定为搜索区间的右端点 。中间点中间点中间点中间点 。正向搜索前进极小点在右方第6页/共40页 若若若若 ，则步长值，则步长值，则步长值，则步长值

5、 改为改为改为改为 ，即取步长，即取步长，即取步长，即取步长 ，继，继，继，继续计算，直到续计算，直到续计算，直到续计算，直到 为止，也可得到为止，也可得到为止，也可得到为止，也可得到高高高高-低低低低-高高高高的一维函数的一维函数的一维函数的一维函数曲线。将左端点值定为终止点曲线。将左端点值定为终止点曲线。将左端点值定为终止点曲线。将左端点值定为终止点 ，而右端点定为起始，而右端点定为起始，而右端点定为起始，而右端点定为起始点点点点 ，中间点定为，中间点定为，中间点定为，中间点定为 。反向搜索后退进退法极小点在左方第7页/共40页外推法确定搜索区间向右移动求新点想想一一想想：该方法的程序框图

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

7、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;第16页/共40页书本的87页，习题4-1第17页/共40页第18页/共40页第19页/共40页一、基本思想：一、基本思想：利用三点的函数值来构造一个二次插值多项式，以近利用三点的函数值来构造一个二次插值多项式，以近似的表达原目标函数，并

8、求这个的多项式的极值点作为似的表达原目标函数，并求这个的多项式的极值点作为原函数极小点的近似值。原函数极小点的近似值。二、原理：二、原理：在一维搜索中，在一维搜索中，与与 均为已知，因此目标函数是均为已知，因此目标函数是 的一元函数的一元函数 现在构造一个二次多项式现在构造一个二次多项式 逼近目标函数逼近目标函数4.2.2 二次插值法（近似抛物线法）二次插值法（近似抛物线法）第20页/共40页二次插值法原理图二次插值法原理图二次插值法原理图二次插值法原理图思考：压缩搜索区间时，有几种情况，书上的程序框图中是怎样解决这个问题的？第21页/共40页二二二二次次次次插插插插值值值值程程程程序序序序框

9、框框框图图图图第22页/共40页课下作业课下作业n n用黄金分割法求函数 的极小点，给定n n要求：1.手工按黄金分割法计算 2.至少用一种计算机语言以黄金分割法编程计算第23页/共40页4.3 多变量优化计算的非梯度方法多变量优化计算的非梯度方法4.3.1 4.3.1 4.3.1 4.3.1 坐标轮换法坐标轮换法坐标轮换法坐标轮换法将一个多维的无约束最优化问题转化为一系列沿将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化问题的求解，因此也称坐标轴方向的一维易优化问题的求解，因此也称降维法降维法。即，将一个。即，将一个n维优化问题转化为依次沿维优化问题转化为依次沿n个坐标方向反

10、复进行一维搜索问题。每次一维个坐标方向反复进行一维搜索问题。每次一维搜索时，只允许搜索时，只允许n个变量的一个改动，其余个变量的一个改动，其余(n-1)个变量固定不变。个变量固定不变。基本原理基本原理第24页/共40页4.3.1 4.3.1 4.3.1 4.3.1 坐标轮换法坐标轮换法坐标轮换法坐标轮换法第25页/共40页1）对于）对于n个变量的函数，若在第个变量的函数，若在第k轮沿着第轮沿着第i个坐标个坐标方向进行搜索，其迭代公式为：方向进行搜索，其迭代公式为：2）求最优搜索步长）求最优搜索步长计算步骤：计算步骤：3）本轮所有方向搜索完毕，判断迭代终止条件：）本轮所有方向搜索完毕，判断迭代终

11、止条件：4）满足上式：）满足上式：否则，进行下一轮迭代。否则，进行下一轮迭代。第26页/共40页搜索方向与步长的确定搜索方向与步长的确定搜索方向与步长的确定搜索方向与步长的确定（1 1）搜索方向的确定）搜索方向的确定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。第27页/共40页搜索步长的确定搜索步长的确定搜索步长的确定搜索步长的确定关于关于 值通常有以下几种取法值通常有以下几种取法（1 1）加速步长法）加速步长法（2 2）最优步长法）最优步长法 最优步长法就是利用一维最优搜索方法来完最优步长法就是利用一维最优搜索方法来完成每一次迭代，即成每一次迭代，即此时可以采用

12、此时可以采用0.6180.618方法或二次插值方法来计算方法或二次插值方法来计算 的值。的值。第28页/共40页图4-12 加速步长法的搜索路线第29页/共40页图图4-14 4-14 最优步长法的搜索路线最优步长法的搜索路线第30页/共40页坐标轮换法存在的问题坐标轮换法存在的问题坐标轮换法存在的问题坐标轮换法存在的问题图图4-14 4-14 坐标轮换法在各种不同情况下的效能坐标轮换法在各种不同情况下的效能（a a）搜索有效；（）搜索有效；（b b）搜索低效；（）搜索低效；（c c）搜索无效）搜索无效第31页/共40页 例例 求目标函数求目标函数 的极小点。的极小点。取初始点取初始点解：第一

13、轮迭代：解：第一轮迭代：求最优搜索步长求最优搜索步长第32页/共40页 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：第33页/共40页判断终止条件，不满足，进行第二轮迭代：判断终止条件，不满足，进行第二轮迭代：求最优搜索步长求最优搜索步长第34页/共40页 求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：沿着第二个坐标方向搜索：第35页/共40页例例3:用坐标轮换法求下面问题的最优解，给定初用坐标轮换法求下面问题的最优解，给定初始点始点X0=0 0T,精度要求精度要求=0.1解解:第一轮迭代第一轮迭代求最优步长，即极小化：求最优步长，即极小化：第36页/共4

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