车辆优化设计理论与实践课件：一维搜索方法 -

车辆优化设计理论与实践一维搜索方法2.1概述2.2搜索区间的确定和区间消除法原理2.3黄金分割法2.4一维搜索的插值方法2.1

概述当采用数学规划法寻求多元函数的极值点时，一般要进行一系列迭代，产生迭代点列，使他们逐渐逼近最优点。迭代的一般格式可表示为：其中为第k+1次迭代的搜索方向，为沿搜索的最佳步长因子。当方向给定，求最佳步长就是求一元函数的极值问题，它称作一维搜索。而求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。2.1

概述求解一元函数的极小点，可采用解析解法，即利用一元函数的极值条件求。解析解法的缺点是需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况。所以在优化设计中，求解最佳步长因子主要采用数值解法，即利用计算机通过反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。2.2搜索区间的确定与区间消去法原理2.2.1确定搜索区间的进退法1．算法原理前进运算后退运算确定搜索区间的外推法的程序框图如图

2．算法的MATLAB实现在MATLAB中编程实现的进退法函数为：minJT。功用：用进退法求解一维函数的极值区间。调用格式：[minx,maxx]=minJT(f,x0,f0,eps0)

其中，f:目标函数;x0:初始点；

h0:初始步长；

eps0:精度；

minx:目标函数包含极值的区间左端点；

maxx:目标函数包含极值的区间右端点。3．算法举例例2-1用进退法求函数的极值区间。取初始点为0，初始步长为0.1。2.2.2区间消去法原理搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。2.2.2区间消去法原理为了避免多计算函数值，我们把第三种情形合并到前面两种情形中去。例如，可以把前面三种情形改为下列两种情形：1）若则取[a，b1]

为缩短后的搜索区间。2）若则取[a1，b]

为缩短后的搜索区间。2.2.3一维搜索方法的分类可将一维搜索方法分成两大类。一类称作试探法。这类方法是按某种给定的规律来确定区间内插入点的位置。此点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系。属于试探法一维搜索的有黄金分割法，斐波那契（Fibonacci）法等。另一类一维搜索方法称作插值法或函数逼近法。这类方法是根据某些点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函数来逼近原函数，用插值函数的极小点作为区间的插入点。属于插值法一维搜索的有二次插值法、三次插值法等。以下我们分别讨论这两类一维搜索方法。2.3黄金分割法黄金分割法适用于[a，b]

区间上的任何单峰函数求极小值问题。对函数除要求“单峰”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间[a，b]内适当插入两点，并计算其函数值,将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。2.3黄金分割法1．算法原理黄金分割法要求插入点的位置相对于区间[a，b]两端点具有对称性，即除对称要求外，黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。黄金分割法原理图为了保持相同的比例分布有:2．算法步骤黄金分割法的搜索过程是：1）给出初始搜索区间[a，b]

及收敛精度，将赋以0.618.2）按坐标点计算公式（2-3）计算两点，并计算其对应的函数值。3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及函数值。4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足则返回到步骤2。5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。例2-2试用黄金分割法求函数极小点，搜索区间为[-35]时。迭代序号aby1比较y20-30.0561.94450.115<7.6671-3-1.1110.564.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650.056-0.987<-0.8884-1.832-1.386-1.111-0.665-0.851>-0.9875-1.386-1.111-0.940-0.6653．算法的MATLAB实现在MATLAB中编程实现的黄金分割法的函数为：minHJ。功用：用黄金分割法求解一维函数的极值。调用格式：[x,minf]=minHJ(f,a,b,eps)

其中，f:目标函数;a:极值的区间左端点；

b:极值的区间右端点；

eps:精度；

minf:目标函数的极小值。2.4一维搜索的插值方法假定我们的问题是在某一确定区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值方法，又称作函数逼近法。2.4一维搜索的插值方法多项式是函数逼近的一种常用工具。在搜索区间内我们可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。因此，这里介绍两种用二次函数逼近原来函数的方法。一种是牛顿法（切线法）。它是利用一点的函数值、一阶导数值和二阶导数值来构造此二次函数的。另一种方法是抛物线法（二次插值法）。它是利用三个点的函数值形成一个抛物线来构造此二次函数的。2.4.1牛顿法1．算法原理对于一维搜索函数，假定已给出极小点的一个较好的近似点，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可在点附近用一个二次函数来逼近函数，2.4.1牛顿法1．算法原理然后以二次函数的极小点作为极小点的一个新近似点。根据极值必要条件2.4.1牛顿法1．算法原理依次继续下去，可得牛顿法迭代公式牛顿法的几何解释2.4.1牛顿法2．算法步骤给定初始点，控制误差，并令k=0；1）计算,；2）求3）若则求得近似解=，停止计算，否则作4；4）令k=k+1转1）。给定，试用牛顿法求其极小值点。0123435.166674.334744.039604.00066-52153.3518332.301993.382990.0055124184.33332109.4458686.8699284.047205.166674.334744.039604.000664.000593．算法的MATLAB实现在MATLAB中编程实现的牛顿法的函数为：minNewton。功用：用牛顿法求解一维函数的极值。调用格式：[x,minf]=minNewton(f,x0,eps)

其中，f:目标函数;x0:初始点；

eps:精度；

minf:目标函数的极小值。4．算法实例例2-5用牛顿法求函数的极小值，取初始点2。2.4.2二次插值法1．算法原理二次插值法又称抛物线法。它是利用在单股区间中的三点的相应函数值，作出如下的二次插值多项式

上面多项式的极值点可从极值的必要条件求得：2.4.2二次插值法利用：求得：=2.4.2二次插值法（a）第一次迭代（b）第二次迭代2．算法的MATLAB实现在MATLAB中编程实现的二次插值法的函数为：minPWX。功用：用二次插值法求解一维函数的极值。