单变量函数的优化方法.ppt

第四章单变量函数的优化方法,第一节优化方法的基本思想第二节搜索区间的确定第三节黄金分割法第四节抛物线插值法,1,2019/11/21,第一节优化方法的基本思想,求目标函数的极小点，从理论上说需要求解方程：其中那么如何来求的极小点呢？,2,2019/11/21,基本思想:,这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。,3,2019/11/21,pk方向上的任何一点可以表示为其中t为步长因子，为实系数，此时pk方向上任何一点的目标函数值为，它是参数t的一元函数。那么在沿pk方向求的极小点，这就是求一元函数的极小问题，它可表示为：,这个过程称为一维搜索过程。,4,2019/11/21,故：优化方法的基本思想是将优化问题转化为一系列的一维搜索问题，所以，一维搜索方法就成为优化设计中最基本的方法。,注意：采用一维搜索法求出极小点，必须考虑三个因素。,初始点X0的选取，应尽量选择靠近极值点X*，这佯就能较快地找到极值点X*。搜索方向pk的确定。从Xk出发沿什么方向可以很快找到F（X）的极小点X*？以不同的原则选取pk就构成了优化方法中各种不同的方法。在确定了搜索方向pk以后，关键的问题是如何进行沿pk方向的一维搜索。,5,2019/11/21,第二节搜索区间的确定,欲求一元函数的极小点必须先确定极小点所在的区间a，b。,图3-1具有单谷性的函数,6,2019/11/21,、确定搜索区间a，b的外推法,先假设具有图示的单谷性。a，b区间形成“高低高”趋势。,从a=0开始，以h0为步长向前试探：,函数值上升步长变号；函数值下降步长加倍区间的始点、中间点依次沿试探方向移动一步；重复步骤2直至函数值上升为止。,最后得到的三点即为搜索区间的是始点、中间点和终点。,图3-1具有单谷性的函数,7,2019/11/21,图3-2,图3-2表示a沿正向试探，每走一步区间的始点、中间点依次沿试探方向移动一步（进行换名），3步后确定搜索区间为，且区间内：,8,2019/11/21,图3-3,图3-3表示a沿正向试探，确定搜索区间为，且区间内：,9,2019/11/21,图34外推法的程序框图,MATLAB程序实现OPT4t2waituifa.m,10,2019/11/21,二、区间消去方法,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内a,b任取两点a1，b1，对应函数值为，；,11,2019/11/21,存在三种可能情况：,12,2019/11/21,综合为两种情况：,1、若则取为缩短后的搜索区间。2、若则取为缩短后的搜索区间。,思考：2、3两中情况为何写在一起？,13,2019/11/21,第三节黄金分割法,黄金分割法也是建立在区间消去法原理基础上的试探方法。基本思想是：在搜索区间内a,b适当插入两点a1、a2，将区间分成三段，然后利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点处函数值近似解。它适用于a,b区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。,14,2019/11/21,黄金分割法对插入点的要求：,1、插入点、的位置相对于区间两端具有对称性，即：,为待定常数；,15,2019/11/21,2、在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。,设：区间长度为1，保留下来区间为，其长度为，区间缩短率为。为了保持相同比例分布，新插入点应在位置上，在原区间的位置相当于在保留区间的位置。,故:,16,2019/11/21,17,2019/11/21,黄金分割法的搜索过程：,1）给出初始搜索区间及收敛精度，将赋以0.618；2）按坐标点计算公式计算，；并计算其对应的函数值，；,18,2019/11/21,3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。,如果：,如果：,记N0=0；,记N0=1；,19,2019/11/21,4）检查区间是否缩短到足够小和函数值收敛到足够精度：如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）；,5）产生新的插入点：,如N0=0，则取,如N0=1，则取,转向3）进行新的区间缩小。,20,2019/11/21,MATLAB程序实现QuZ