《第4章 一维优化方法.ppt》由会员分享，可在线阅读，更多相关《第4章 一维优化方法.ppt（85页珍藏版）》请在金锄头文库上搜索。
1、Lchming ,、借助最优化数值计算方法与计算机技术，求取工程问题的最优设计方案(最优设计参数)。包括：（1）建立数学模型；（2）运算求解。, 一、设计变量（参数）：可以进行调整和优选的独立参数 连续变量和离散变量,二、约束条件：对设计变量的取值加以某些限制的条件,三、目标函数：设计中所追求的目标，且可由设计变量表示的函数。,、设计变量的数目称为优化问题的维数 设计空间：由n个设计变量为坐标所组成的实空间。所有设计点的集合。 等值线或等值面：具有相等目标函数值的设计点构成的线或面。 可行域 :在设计空间中，由满足所有约束条件的设计点组成的区域。,、寻优思路,极值,极值,新点的可行性条件、适用
2、性条件。 收敛精度指相邻两次寻优的设计点或目标函数值的接近程度。寻优是逐渐逼近极值点的过程。,梯度方向是函数值增加最快的方向，方向导数,目标函数和不等式约束函数都是凸函数，则该约束优化问题为凸规划。,目标函数在极值点附近是二次函数,泰勒展开式,海森矩阵正定,无约束优化问题的极值条件,题 目,1、泰勒展开式，将高次函数简化 2、二次型 3、判断海森矩阵是否正定,第4章 一维优化方法,4-1 确定极值点所在区间的进退法 4-2 一维盲人探路优化方法 4-3 区间消去类优化方法 4-4 插值类优化方法 4-5 C语言调试的要点 4-6 小结,基本假设：单峰函数。方法适合于复杂区间，只要是连续变量的函
3、数，只一极小点。,在给定区间内仅有一个极小点的函数称单峰函数。下图为单峰函数的几种情况：,图中可以看出，单峰函数可以是不可微或甚至是不连续函数。,4-0 引言,优化问题的解法：解析法和数值近似法。 当采用数学规划法(有方向)寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:,当方向 给定，求最佳步长 就是求一元函数 :,的极值问题。这一过程也是一维搜索。,一维搜索方法分类： (a) 区间消去类方法； (b)函数逼近（插值）类方法,搜索方向是根据几何概念和数学原理，由目标函数和约束条件的局部信息状态形成的。,向左走，向右走Si prioche, Si loin,只研究单谷(峰）区间，因
4、为其它的可切割 在给定区间内仅有一个谷值的函数称为单谷函数，其区间称为单谷区间。,4-1 确定极值点所在区间的进退法,特点： 函数值：“大小大” 图形：“高低高”,单谷区间中一定存在极小点，其寻找步骤：,第一步：确定初始单谷区间； 第二步：使区间缩小。,（1）选定初始点a1, 初始步长hh0，a2=a1+h， 计算 y1f(a1)， y2f(a2)。 （2）比较y1和y2。 （a）如y1y2, 向右前进； 转（3）向前， （b）如y10时，a,b=a1,a3; hy3, a1=a2, a2=a3， 转（3）继续探测。,（1）选定初始点a1, 初始步长hh0，a2=a1+h， 计算 y1f(a1
5、)， y2f(a2)。 （2）比较y1和y2。 （a）如y1y2, 向右前进； 转（3）向前， （b）如y10时，a,b=a1,a3; hy3, a1=a2, a2=a3，加倍步长 h2 h， 转（3）继续探测。,进退法,每跨一步为前一次步长的2倍，直至函数值增加为止。,二、用进退法确定最小值所在区间的程序框图,int JT(double x3,double h) /*进退法确定区间子程序(返回计算目标函数值的次数)：x1 x2 x3,初始*/ double y3,dum; /*函数值，中间变量*/ int k=0; /*步数，保证适用性*/ y0=func(x0); /*初始点函数值*/ x
6、1=x0+h; y1=func(x1); if(y0y1) /*如果 ，则反向，调头*/ h=-h; dum=x0;x0=x1;x1=dum; dum=y0;y0=y1;y1=dum; ,for(;) /*计算循环*/ h=2*h; /*步长加速*/ x2=x1+h; y2=func(x2); /*第三点及其目标函数值*/ if(y1x2) /*如果是退的，则调整*/ dum=x0;x0=x2;x2=dum; return(K); /*返回计算目标函数值的次数*/ else /*否则，弃去第一点，重新找*/ x0=x1;x1=x2; y0=y1;y1=y2; /*end for(;)*/ /*
7、结束JT*/,三、关于用进退法求函数最小值所在区间的说明,该求最小值所在区间的方法思想简单、思路明确，但是，多数优化问题的目标函数并非单谷函数，如果初始步长太大，就有可能出现不收敛的情况。 为了保证收敛和所确定的区间较小，同时考虑到多维寻优时，给出的初值点一般靠近极值点，区间确定的初始步长值应给出较小的值，如取收敛精度值的 10 倍左右。,X0=1, h=1,1,h=1,4,8,21,2,12,9,10.5,h=2,h=4,x0 x1 x2,x0 x1,x2,x,4-2 一维盲人探路优化方法,基本思想 盲人走路时，往往拿根竹竿试探前面的路面，在确保安全之后再迈出或大或小的脚步。先探路再迈步的思
8、想用于多维优化方法即得出爬山类方法，用于一维优化问题极值点所在区间的确定即得出进退法。如果还将调整脚步大小的思想用于一维优化方法即得出“一维盲人探路优化设计方法”。 为提高寻优效率，以步长增倍提高接近极值点的速度，以步长减半提高收敛速度，以符合适用性条件作为更新当前点的前提。,算法步骤,（1）选定初始点x1为当前点，初始步长hh0，收敛精度值(=y2,，则y1=y2，x1=x2，h=h+h； （b）如y1=y2,，则y1=y2，x1=x2，h=h+h； （b）如y1=y2,，则y1=y2，x1=x2，h=h/2； （b）如y1，则转(7)继续。 （9）取x1、x2中目标函数值最小的点作为最优点
9、，返回；,算法的程序流程图,一阶导数法,适当增减步长。非首点换方向后每步减小步长。,平分法,设目标函数在极值点所在区间a,b上为下单峰函数且具有连续一阶导数，根据区间中点目标函数的导数值，确定去掉的一半区间。把保留下来的区间仍计为a，b，重复前面的过程，直到区间a，b的长度充分小，满足所要求的精度为止。该方法是线性收敛的，收敛比为1/2。,4-3 区间消去类优化方法,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区间内a,b 任取两点a1,b1,f1f（a1）， f2f（b1）,在极值点所在的区间中，取两点，将区间分为三段，根据目标函数的单峰特点，极
10、值点不在目标函数值较大的点外侧，因此搜索区间得以缩短。,f1f（a1）， f2f（b1） (1)如f1f2, 则缩小的新区间为a1,b; (3)如f1=f2, 则缩小的新区间为a1,b1,综合为两种情况： 若 则取 为缩短后的搜索区间。 若 则取 为缩短后的搜索区间。,一、黄金分割法Golden Section Method的基本思想,黄金分割法是建立在区间消去法原理基础上的试探方法。 在搜索区间内a,b适当取两点 ，将区间分成三段； 两个分割点相对于区间两端对称，在保留下来的区间内再找一分割点所形成的三段，与原区间的三段具有相同的比例分布。即每次区间削去只须计算一个分割点。,将区间分成三段,
11、黄金分割法还要求在保留下来的区间内再找一点所形成的三段区间，与原来的三段区间具有相同的比例分布 。,四个点三段。削去一段后，剩下三个点。 再找一个点组成的三段与原来的三段成比例,f(a1),f(a2),f(a1),f(a2),黄金分割法要求两个分割点：,黄金分割法区间消去示意：,区间缩短率,黄金分割法应该是计算量小 收敛准则 （1）区间绝对精度 ； （2）区间相对精度 ； （3）函数值绝对精度 ； （4）函数值相对精度 一）黄金分割法特点 （1）不必要求目标函数连续可微，只要利用函数值大小的比较，即可很快地找到最优点； （2）除了第一次缩小区间要计算两个点及其函数值以外，其余每次只要计算一个点
12、及其函数值； （3）可靠性好(掉进井里不会出来),二、黄金分割法的迭代过程和程序框图 1）给出初始搜索区间及收敛精度 ，将 赋以0.618。 2）按坐标点计算公式计算 , ；并计算其对应的函数值。 3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。 如果 ，则新区间 令 ,记N0=0; 如果 ，则新区间 ， 令 , 记N0=1; 4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。,5）产生新的分割点： 如N0=0，则
13、取 ； 如N0=1，则取 ， 转向3）进行新的区间缩小。,a x1 x2 b a x1 x2 b,例 3-1 用黄金分割法求函数 f ( x ) = 3 x 2 4 x + 2 的极小点，给定 x 0 = 0 , h = 1, = 0 . 2。,解： 1)确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x1+h=0+1=1, f2=f(x2)=1 由于f1f2, 应加大步长继续向前探测。h=2h,x3= x2+h=1+2=3, f3=f(x3)=17 由于f2f3,可知初始区间已经找到，即a,b=x1,x3=0,3,2)用黄金分割法缩小区间 第一次缩小区间(分割点)： x1=0+0
14、.382 (3-0)=1.146, f1=1.356 x2=0+0.618 (3-0)=1.854, f2=4.896 f10.2,第二次缩小区间：指出区间、分割点即可 令 x2=x1=1.146, f2=f1=1.356 x1=0+0.382(1.854-0)=0.708, f1=0.672 由于f1f2, 故新区间a,b=x1,b=0.708, 1.854 因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。,第三次缩小区间： 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.747
15、 由于f1 0 . 2 , 应继续缩小区间。,第四次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223 由于f10.2, 应继续缩小区间。,第五次缩小区间： 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382(0.764-0.472)=0.584, f1=0.262 由于f1f2, 故新区间a,b=x1,b=0.584, 0.764 因为 b-a=0.764-0.584=0.180.2, 停止迭代。,极小点与极小值： x*=0.5 (0.584+0.764)=0.674, f(x*)=0.222,int golden(a, b, e, x, y) double x1,x2,y1,y2; x1=a+0.382*(b-a); y1=func(x1); x2=a+0.618*(b-a); y2=func(x2); for(;) /*区间消去循环*/ if(y1y2) /*如果须消去右边*/ b=x2;x2=x1;y2=y1; x1=a+0.382*(b-a); y1=func(x1); ,else /*消去左边*/ a=x1;x1=x2;y1=y2; x2=a+0.618*
