单变量函数的优化方法

第四章

单变量函数的优化方法第一节优化方法的基本思想第二节搜索区间的确定第三节黄金分割法第四节抛物线插值法12024/4/3第四章单变量函数的优化方法第一节优化方法的基本思想第一节优化方法的基本思想

求目标函数

的极小点，从理论上说需要求解方程：

其中

那么如何来求的极小点呢？22024/4/3第一节优化方法的基本思想

求目标函数的极小基本思想:这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。32024/4/3基本思想:这种方法是逐次迭代的方法，在电子计算pk方向上的任何一点可以表示为

其中t为步长因子，为实系数，此时pk方向上任何一点的目标函数值为

，它是参数t的一元函数。那么在沿pk方向求

的极小点，这就是求一元函数

的极小问题，它可表示为：这个过程称为一维搜索过程。42024/4/3pk方向上的任何一点可以表示为这个过程称为一维搜索过程。42

故：

优化方法的基本思想是将优化问题转化为一系列的一维搜索问题，所以，一维搜索方法就成为优化设计中最基本的方法。

注意：采用一维搜索法求出极小点，必须考虑三个因素。初始点X0的选取，应尽量选择靠近极值点X*，这佯就能较快地找到极值点X*。

搜索方向pk的确定。从Xk出发沿什么方向可以很快找到F（X）的极小点X*？以不同的原则选取pk就构成了优化方法中各种不同的方法。在确定了搜索方向pk以后，关键的问题是如何进行沿pk方向的一维搜索。52024/4/3故：注意：采用一维搜索法求出极小点，必须考虑三个因素。初第二节搜索区间的确定欲求一元函数

的极小点

必须先确定极小点所在的区间〔a，b〕。图3-1具有单谷性的函数62024/4/3第二节搜索区间的确定欲求一元函数的极小点－、确定搜索区间〔a，b〕的外推法先假设

具有图示的单谷性。〔a，b〕区间形成“高—低—高”趋势。从a=0开始，以h0为步长向前试探：函数值上升→步长变号；函数值下降→步长加倍→区间的始点、中间点依次沿试探方向移动一步；重复步骤2直至函数值上升为止。最后得到的三点即为搜索区间的是始点、中间点和终点。图3-1具有单谷性的函数72024/4/3－、确定搜索区间〔a，b〕的外推法先假设图3-2图3-2表示a沿正向试探，每走一步区间的始点、中间点依次沿试探方向移动一步（进行换名），3步后确定搜索区间为

，且区间内：82024/4/3图3-2图3-2表示a沿正向试探，每走一步区图3-3图3-3表示a沿正向试探，确定搜索区间为

，且区间内

：92024/4/3图3-3图3-3表示a沿正向试探，确定搜索区间图3—4外推法的程序框图MATLAB程序实现OPT4t2waituifa.m102024/4/3图3—MATLAB102024/4/1二、区间消去方法搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内[a,b]任取两点a1，b1，对应函数值为，

；112024/4/3二、区间消去方法搜索区间确定之后，采用区间消存在三种可能情况：122024/4/3存在三种可能情况：122024/4/1综合为两种情况：1、若

则取

为缩短后的搜索区间。

2、若

则取

为缩短后的搜索区间。

思考：2、3两中情况为何写在一起？132024/4/3综合为两种情况：1、若第三节黄金分割法黄金分割法也是建立在区间消去法原理基础上的试探方法。基本思想是：

在搜索区间内[a,b]适当插入两点a1、a2

，将区间分成三段，然后利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点处函数值近似解。

它适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。142024/4/3第三节黄金分割法黄金分割法也是建立在黄金分割法对插入点的要求：1、插入点

、

的位置相对于区间

两端具有对称性，即：为待定常数；152024/4/3黄金分割法对插入点的要求：1、插入点、2、在保留下来的区间内再插入一点所形成的区间新三段，

与原来区间的三段具有相同的比例分布。设：

区间长度为1，保留下来区间为，其长度为

，区间缩短率为

。为了保持相同比例分布，新插入点应在

位置上，

在原区间的

位置相当于在保留区间的

位置。故:162024/4/32、在保留下来的区间内再插入一点所形成的区间新三段，设：区172024/4/3172024/4/1黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度

ε，将

λ赋以0.618；2）按坐标点计算公式计算

，

；并计算其对应的函数值

，

；182024/4/3黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度ε，将3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果：如果：记N0=0；记N0=1；192024/4/33）根据区间消去法原理缩短搜索区间。如果：如果：记N0=04）检查区间是否缩短到足够小和函数值收敛到足够精度：

如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）；5）产生新的插入点：如N0=0，则取如N0=1，则取转向3）进行新的区间缩小。202024/4/34）检查区间是否缩短到足够小和函数值收敛到足够精度：5）产生MATLAB程序实现