教学材料《CAD概述》-第17 章

17.1无约束优化的一维搜索方法

在上一章中已经提出数学规划法的迭代公式：这个过程就称为一维搜索。下一页返回17.1无约束优化的一维搜索方法

上一页下一页返回17.1无约束优化的一维搜索方法

a

(k)为一维搜索最佳步长因子，应满足：上一页下一页返回17.1无约束优化的一维搜索方法

对于函数关系复杂、求导困难或得不到

显式表达式的情况，用解析法求解将非常困难，因此一维搜索主要还是采用数值解法。数值解法的主要思路是：先确定极小点所在的搜索区间，该区间应为单峰区间，即在该区间内目标函数只有一个极小值；然后求出该区间内的，求解的方法可采用区间消去原理不断缩小搜索区间，从而获得*的数值近似解。1.搜索区间的确定与区间消去原理（1）确定搜索区间的外推法一维搜索时，为了确定极小点所在的单峰区间[a,b]，应使函数f(

)在[a,b]区间里形成“高—低—高”的趋势，如图17

1所示，即区间始点、中间点和终点123＜，所对应的函数值123f(

)＞f(

)＜。确定搜索区间可以采用外推法，其程序框图如图17

2所示。上一页下一页返回17.1无约束优化的一维搜索方法

上一页下一页返回17.1无约束优化的一维搜索方法

此时y3＞y2，故即所求初始单峰区间：上一页下一页返回17.1无约束优化的一维搜索方法

（2）区间消去法原理在搜索区间[a,b]内任取两点计算函数值于是将有下列三种可能情形：上一页下一页返回17.1无约束优化的一维搜索方法

2.黄金分割法确定了单峰区间[a,b]后，一维搜索的任务就是求函数在该区间上的极小值。黄金分割法适用于[a,b]区间上任何单谷函数求极小值的问题，又称0.618法。它通过对黄金分割点函数值的计算和比较，将初始区间逐次进行缩短，当区间缩短到规定的足够小的程度时，就得到区间上极小点的近似黄金分割法要求插入点1的位置相对于区间[a,b]两端点具有对称性，即解。上一页下一页返回17.1无约束优化的一维搜索方法

式中，λ为待定常数。黄金分割法还要求每次区间缩短都有相同的缩短率，即在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布，如图17

3所示。故有所谓黄金分割，就是指将一条线段分成两段后，整段与较长段的长度比值等于较长段与较短段的长度比值，即上一页下一页返回17.1无约束优化的一维搜索方法

按照这样的取点规则，黄金分割法的缩短率也为0.618。为了使最终区间收缩到预定的迭代精度ε以内，区间缩短的次数N必须满足：黄金分割法的搜索过程是：①给出初始搜索区间[a,b]及收敛精度ε，将λ赋以0.618。②按坐标点计算公式（17

2）中的1和2，并计算其对应的函数值1f(

)、2f(

)。③根据区间消去法原理缩短搜索区间。④检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足，则返回到步骤②。⑤如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。上一页下一页返回17.1无约束优化的一维搜索方法

【例17

3】对于函数，给定初始搜索区间为[1,7]，迭代精度试用黄金分割法求其极小点解：①计算插入点。条件不满足，需进一步缩短区间。依次迭代下去，计算过程见表17

1。上一页下一页返回17.1无约束优化的一维搜索方法

迭代到第6次，区间长度：迭代终止。3.二次插值法在某一确定区间内寻求函数的极小点，可以根据已有的若干点处的函数信息（包括函数值、导数值等），利用插值方法建立与目标函数近似的插值多项式，然后用多项式函数的极小点作为原函数极小点的近似值。经过一系列的迭代，多项式函数的极小点与原来函数极小点之间的距离逐渐缩小，直到满足一定的精度要求时迭代终止。这种方法就称作插值方法，又称作函数逼近法。上一页下一页返回17.1无约束优化的一维搜索方法

上一页下一页返回17.1无约束优化的一维搜索方法

图17

4上一页下一页返回17.1无约束优化的一维搜索方法

【例17

4】试用二次插值法求函数f(

)

(的极小点，给定初始区间为[1,7]，迭代精度ε=0.01。上一页下一页返回17.1无约束优化的一维搜索方法

解：①计算初始插值点及其函数值。②计算二次插值函数的极小点及极小值。上一页下一页返回17.1无约束优化的一维搜索方法

③缩短区间。上一页返回17.2多维无约束优化方法多维无约束优化问题是：求n维设计变量使目标函数f(x)→min，而对x没有任何限制条件。尽管实际中几乎所有的设计问题都是有约束的，但无约束优化方法仍然是优化技术中最重要和最基本的内容之一。原因是它不仅可以直接用来求解无约束优化问题，而且约束优化问题也常常可以通过某种途径转化为无约束优化问题来求解。此外，有些约束优化方法，还可以借助无约束优化方法的思想来进行构造。下一页返回17.2多维无约束优化方法1.最速下降法优化设计是追求目标函数f(x)最小，因此，一个很自然的想法是从某点x(k)出发，沿着该点的负梯度方向f(x搜索，使目标函数在该点附近下降最快，因此称这种方法为最速下降法，又称为梯度法。其迭代的算法是：上一页下一页返回17.2多维无约束优化方法根据一元函数极值的必要条件和多元复合函数求导公式，得由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直，也就是相邻两个搜索方向是互相垂直的，如图17

5所示。从图中可以直观地看出，在远离极小点的地方，每次迭代可使函数值有较多的下降；在接近极小点的位置，迭代行进的距离缩短，收敛速度也就减慢，因而最速下降法的收敛速度并不快。这是因为梯度是函数的局部性质，函数在迭代点x(k)的负梯度方向仅仅是在x(k)点处为最速下降方向，一旦离开了该点，原先的方向就不再是最速下降方向了。上一页下一页返回17.2多维无约束优化方法【例17

5】求目标函数解：函数的梯度为上一页下一页返回17.2多维无约束优化方法沿负梯度方向进行一维搜索，有上一页下一页返回17.2多维无约束优化方法根据极值存在的必要条件：继续搜索下去，计算过程见表17

2。上一页下一页返回17.2多维无约束优化方法搜索到第8次：2.共轭梯度法（1）共轭方向的概念上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法（2）共轭方向的性质上一页下一页返回17.2多维无约束优化方法共轭方向法就是建立在性质3基础上的。如果一种迭代方法能使二次函数在有限次迭代内达到极小点，则称这种迭代方法是二次收敛的，因此共轭方向法具有二次收敛性。提供共轭向量系的方法有许多种，比如共轭梯度法就是每个共轭向量都是依赖于迭代点处的负梯度构造出来的，而鲍威尔法则是直接利用函数值来构造共轭方向的。（3）共轭梯度法考虑二次函数：上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法再沿d(2)方向继续进行一维搜索，如此继续下去，可得共轭方向的递推公式。沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。若目标函数为非二次函数，经n次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法3.牛顿型方法在最速下降法中，只用到了目标函数的一阶导数信息来确定搜索方向，如果能用函数的二阶导数信息，就可以对函数进行更精确的表达，也就可能找到更好的搜索路径，获得更快的收敛速度。牛顿型方法就用到了海赛矩阵来构造搜索方向。上一页下一页返回17.2多维无约束优化方法称为牛顿方向，其步长为恒定值(k对于正定的二次函数，f(x)的上述泰勒展开式不是近似的，而是精确的。因此，无论从任何点出发，只需一步就可找到极值点，因此牛顿法也是二次收敛的。上一页下一页返回17.2多维无约束优化方法代入牛顿法迭代公式，得从而经过一次迭代即求得极小点x*=[00]及函数极小值f(x*)=0。由此可见，当初始点选得合适且f(x)为二次函数时，牛顿法收敛很快。但是如果初始点选择不当，离极小点远而离极大点近时，就可能收敛于极大点，有时还会收敛到鞍点或不收敛。这是由于迭代时没有优化步长，不能保证每次迭代目标函数值都是下降的，即因此，需要对上述牛顿法做些修改。修改的方法可以是每次从x(k)点沿牛顿方向进行一维搜索时，将该方向上的最优点作为x(k+1)，其迭代公式为：上一页下一页返回17.2多维无约束优化方法式中，为沿牛顿方向进行一维搜索的最佳步长，称为阻尼因子。上述方法也称为阻尼牛顿法，或称修正牛顿法。阻尼牛顿法的计算步骤如下：上一页下一页返回17.2多维无约束优化方法4.变尺度法牛顿型方法对于目标函数性态较好或初始点取在极小点附近时，有收敛速度较快的优点，但它存在构造牛顿方向比较困难（需要求海赛矩阵的逆矩阵）甚至无法构造的缺点。变尺度法就是人们基于牛顿法的思想做了一些重要改进的一类方法，它通过采用变尺度矩阵来近似海赛矩阵的逆矩阵，简化了牛顿型方法的计算，又保持了牛顿型方法收敛快的优点，这类方法又称为拟牛顿法。（1）变尺度矩阵的建立对于一般函数f(x)，其牛顿迭代公式为：上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法（2）DFP变尺度法在变尺度法中，校正矩阵E(k)取不同的形式，就形成不同的变尺度法。DFP变尺度法是由W.C.Davidon于1959年首先提出，后又于1963年经R.Fletcher和N.H.D.Powell加以发展完善的一种变尺度法，其校正矩阵E(k)取下列形式：上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法上一页下一页返回17.2多维无约束优化方法代入校正公式：上一页下一页返回17.2多维无约束优化方法则第二次搜寻方向为上一页返回17.3约束优化方法大多数优化设计问题属于约束优化设计问题，其数学模型为：求解上式的方法称为约束优化方法。约束优化方法可分为直接法和间接法两类。直接法通常用于仅含不等式约束的优化问题，其基本思想是在可行域内按照一定的原则直接探索出最优点。当可行域为非凸集或目标函数是非凸函数时，往往还需要更换几次初始点，进行多路线探索。属于直接法的约束优化方法有随机方向法、复合形法、可行方向法、简约梯度法等。下一页返回17.3约束优化方法间接法对于等式约束和不等式约束优化问题均有效，它有不同的求解策略，其中一种解法的基本思路是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数，将约束优化问题转化为一个或一系列的无约束优化问题进行求解。属于间接解法的方法有惩罚函数法和增广拉格朗日乘子法等。1.复合形法复合形法是求解约束优化问题的一种重要的直接方法，其基本方法是：首先在设计空间内选择位于可行域内的k个初始点，构造一个初始复合形；接着利用复合形各顶点处目标函数值的大小关系，判断目标函数的下降方向，找到目标函数值最大的最坏点，代之以既使目标函数值有所下降又能满足约束条件的新点，从而构成新的复合形（如图17

7所示）。如此重复进行下去，使新的复合形不断地向最优点移动和收缩，直至满足收敛条件为止。上一页下一页返回17.3约束优化方法（1）初始复合形的产生方法初始复合形是在可行域内选择k（n

1≤k≤2n）个可行点作为顶点构造而成的，而这k个顶点可以采用以下的方法产生。①由设计者试选全部k个顶点；②由设计者先选定一个顶点，其余k

1个顶点用随机方法计算产生，计算的方法是：式中，xj为复合形中的第j个顶点；a、b为设计变量的下限和上限；rj为在（0，1）区间内的伪随机数。这样得到的随机点不一定在可行域内，需设法将非可行点移到可行域内。通常采用的方法是，求出已经在可行域内的L个顶点的中心点xC。上一页下一页返回17.3约束优化方法然后将非可行点向中心点移动，即若L

还不满足约束条件，则重复利用上式使其继续向中心点移动。只要中心点是可行点，总可以将这些非可行点移到可行域内。如果中心点是非可行点，就应该缩小随机选点的边界，重新产生各个顶点。③全部顶点均用随机方法产生。（2）复合形法的搜索方法生成初始复合形后，就要通过一定的搜索方法不断改变其形状，使复合形逐步向最优点逼近。下面介绍复合形法中最常用的反射搜索方法。反射是改变复合形形状的一种主要策略，其步骤为：上一页下一页返回17.3约束优化方法①计算复合形各顶点的目标函数值，并比较其大小，求出最好点xL、最坏点xH及次坏点xG；②计算除去最坏点xH外的其他（k

1）个顶点的形心xC；上一页下一页返回17.3约束优化方法③通常由xH

指向xC的方向是目标函数值下降的方向，因此沿（xC

xH）方向求反射点，如图17

8所示。此外，还有扩张、收缩、使复合形各顶点向最好点压缩及绕最好点旋转一个角度等搜索方法。上一页下一页返回17.3约束优化方法【例17

9】已知约束优化问题：上一页下一页返回17.3约束优化方法上一页下一页返回17.3约束优化方法上一页下一页返回17.3约束优化方法2.惩罚函数法惩罚函数法是一种使用广泛的重要的间接解法，其基本原理是将约束优化问题：通过引入几个可调整的惩罚参数（因子）构造一个新的目标函数——惩罚函数。式中，r1、r2

为惩罚因子。通过不断调整惩罚因子的值，求解一系列新目标函数的无约束极小值，使其不断逼近原约束问题的最优解。这是一个序列求优过程，因此该方法又称序列无约束极小化方法（SequentialUnconstrainedMinimizationTechnique，简称SUMT法）上一页下一页返回17.3约束优化方法根据迭代过程是否在可行域内进行，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法三种方法。（1）内点惩罚函数法内点惩罚函数法简称内点法，它将新的目标函数——惩罚函数定义于可行域内，搜索过程也在可行域内进行，因此初始点及迭代点序列都在可行域内。内点惩罚函数法是求解不等式约束优化问题的有效方法。对于不等式约束优化问题：上一页下一页返回17.3约束优化方法【例17

10】用内点法求上一页下一页返回17.3约束优化方法由此可知，当逐步减小r(k)值直至趋于0时，x*(r(k))逼近原问题的约束最优点，如图17

9所示。下面是几个使用内点法时需要注意的问题：①初始点x(0)的选取。初始点x(0)应严格满足所有约束条件，避免位于边界上。②惩罚因子初值r(0)的选取。r(0)的选取是否恰当，对收敛的速度和求解是否成功影响较大。若r(0)取得太小，惩罚函数的性态会变差，甚至难以收敛到极小点；若r(0)取得太大，则开始几次构造的惩罚函数的无约束极值点就会离边界较远，计算效率较低。一般可以先选一个r(0)（比如r(0)=1）进行试算，根据试算的结果再进行调整。上一页下一页返回17.3约束优化方法③惩罚因子的缩减。相邻两次迭代的惩罚因子的关系为：式中，c称为惩罚因子的缩减系数，通常的取值范围为0.1～0.7。（2）外点惩罚函数法外点惩罚函数法简称为外点法，它将惩罚函数定义于可行域之外，求解过程中迭代点是从可行域外侧逐步逼近原约束优化问题最优解的。对于约束优化问题：上一页下一页返回17.3约束优化方法【例17

11】用外点法求的约束最优解。解：构造外点惩罚函数：上一页下一页返回17.3约束优化方法由此可知，当逐步增大s(k)值直至趋于∞时，x*(s(k))逼近原问题的约束最优点，如图17

10所示。上一页下一页返回17.3约束优化方法外点法的初始点可任意选择，应用比较方便。其惩罚因子按公式s(k)递增，式中t为递增系数，通常取t=5～10。（3）混合惩罚函数法混合惩罚函数法简称混合法，对于约束优化问题：上一页返回17.4现代优化算法现代优化算法是20世纪80年代初兴起的启发式算法，主要包括遗传算法、禁忌搜索、模拟退火和人工神经网络算法等。主要应用于解决大量实际问题，并在理论和实际应用方面得到了较大的发展。下面简介现代优化算法中比较常用的遗传算法，这种优化方法算法思想比较简单，程序实现方便。遗传算法（GeneticAlgorithm，GA）是美国Michigan大学的J.H.Holland教授于1975年提出的一种模拟生物进化过程、自然选择和遗传的随机搜索方法。遗传算法的术语借鉴于生物遗传学，一个解称为一个个体（Individual），解的编码称为染色体（Chromosome），染色体由决定其特性的基因（Gene）组成。目标函数被转换为对应各个个体的适应性（Fitness），而一组染色体组成一个群体（Population），根据适应函数值选取的一组染色体称为种群（Reproduction）。下一页返回17.4现代优化算法典型的遗传算法步骤有：①随机生成一个群体；②计算每个染