第四章+无约束优化计算方法(new)

第四章无约束优化计算方法4.1引言4.2单变量优化计算方法4.3多变量优化计算的非梯度方法4.4多变量优化计算的梯度方法

求解优化问题的基本解法有：

解析法数值解法解析法：即利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。在目标函数比较简单时，求解还可以。

局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。4.1引言

数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：

1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到X（1）点；

2）得到新点X（1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从X（1）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。数值解法求解步骤在中间过程中每一步的迭代形式为：

上式中：X（k）——第k步迭代计算所得到的点，称第k步迭代点，亦为第k步设计方案；

a（k）——第k步迭代计算的步长；

S（k）——第k步迭代计算的探索方向。迭代计算机逐步逼近最优点过程示意图用迭代法逐步逼近最优点的探索过程如图所示。

运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求：（1）选择搜索方向（2）确定步长因子（3）给定收敛准则迭代法要解决的问题：终止准则准则1-点距准则准则2-下降准则：

准则3-梯度准则

往往采用两个准则来判别（1）f(x)在x*附近比较平坦

往往采用两个准则来判别（2）

f(x)在X*附近比较陡峭

结论：由于不知道函数的具体形态，有时用两个准则判断更可靠！！

当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:当方向给定，求最佳步长就是求一元函数

:的极值问题，这一过程被称为一维搜索.

一维搜索的最优化方法-分析法例

已知极小值在区间内，若从点出发，根据迭代公式：取将代入得：令

得：

将（3-3）代入（3-2）得：

因为满足准则3所以=0（3-3）（3-2）由举例可知，一维搜索方法解析法利用一维函数的极值条件：一维搜索方法数值解法分类

一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。4.2.1进退法（确定搜索区间）

进退法也称外推法，是一种通过比较函数值大小来确定单峰区间的方法。任意给定初始点X1和步长h，算出f(x1)和

x2=x1+h点的f(x2)函数值。

图(a)．f(x1)>f(x2)，说明x*>x1，将步长增加一倍，取x3=x2+2h；

图(b)．f(x1)>f(x2)，说明x*<x1，需改变步长符号，得点x3=x2-h。

以此类推，即每跨一步为前一次步长的2倍，直至函数值增加为止。4.2单变量优化计算方法在搜索区间内[a,b]适当插入两点，将区间分成三段；4.2.2黄金分割法黄金分割法适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法也是建立在区间消去法原理基础上的试探方法。

利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解。黄金分割法要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。将区间分成三段

黄金分割法也称0.618法，是通过对黄金分割点函数值的计算和比较，将初始区间逐次进行缩小，直到满足给定的精度要求，即求得一维极小点的近似解x*。1）

区间缩小的基本思路

已知f(x)的单峰区间[a,b]。为了缩小区间，在[a,b]内按一定规则对称地取2个内部点x1

和x2

，并计算f(x1)和f(x2)。可能有三种情况：

图(a)．经过一次函数比较，区间缩小一次。在新的区间内，保留一个好点x1和f(x1)，下一次只需再按一定规则，在新区间内找另一个与x1

对称的点x2

，计算f(x2)，与f(x1)比较。如此反复。

图(b)．淘汰[a,x1],得新区间[a,b],此时：a=x1，x1=x2,x2为x1对称点，b=b。

图(c)．可归纳入上面任一种情况处理。2）取点规则黄金分割法的均匀缩短率为0.618，即每经过一次函数值比较，都是淘汰本次区间的0.382倍。根据上式，黄金分割法的取点规则是3）收敛准则

由于实际问题的需要和函数形态的不同，常常需要不同的收敛准则确定最优点。对于直接法，有以下几种收敛准则：

（1）．区间绝对精度

（2）．区间相对精度

（3）．函数值绝对精度；

（4）．函数值相对精度4）

黄金分割法特点（1）不必要求f(x)可微，只要利用函数值大小的比较，即可很快地找到x*；（2）除了第一次缩小区间要计算两个点及其函数值以外，其余每次只要计算一个点及其函数值；（3）可靠性好。

5）

黄金分割法前提条件x1、x2在区间中的位置相对于边界来说是对称的在舍去一段后,留在新区间的那个点仍处于新区间内两个计算点之一的位置；在缩小区间时,λ的值为一不变的常数。演示过程1演示过程2黄金分割法计算框图黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度，将赋以0.618。2）按坐标点计算公式计算,；并计算其对应的函数值。3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果，则新区间＝ 令记N0=0；如果，则新区间＝，令，记N0=1；4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。如N0=0，则取如N0=1，则取5）产生新的插入点：转向3）进行新的区间缩小。例:用黄金分割法求函数f(x)=3x3-4x+2的极小点

给定x0=0,h=1,ε=0.2。解：1）确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1>f2,应在原方向继续向前探测。x3=x2+h=1+1=2,f3=f(x3)=18由于f2<f3,可知初始区间已经找到，即[a,b]=[x1,x2]=[0,2]2）用黄金分割法缩小区间第一次缩小区间：

x1=0+0.382X(2-0)=0.764,f1=0.282x2=0+0.618X(2-0)=1.236,f2=2.72f1<f2,新区间[a,b]=[a,x2]=[0,1.236],b-a>0.2第二次缩小区间：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新区间[a,b]=[x1,b]=[0.472,1.236]因为b-a=1.236-0.472=0.764>0.2,应继续缩小区间。第三次缩小区间：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新区间[a,b]=[a,x2]=[0.472,0.944]因为b-a=0.944-0.472=0.472>0.2,应继续缩小区间。

第四次缩小区间：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新区间[a,b]=[a,x2]=[0.472,0.764]因为b-a=0.764-0.472=0.292>0.2,应继续缩小区间。第五次缩小区间：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新区间[a,b]=[x1,b]=[0.584,0.764]因为b-a=0.764-0.584=0.18<0.2,停止迭代。极小点与极小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222思考题：

试用黄金分割法求

近似极小点及极小值。已知[a,b]=[0,2]，ε=0.01（只要求进行2轮迭代，判断是否收敛）。一维搜索的插值方法假定我们的问题是在某一确定区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值方法，又称作函数迫近法。二次插值法（抛物线法）二次插值的基本思想是利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点(即p’(x*p)=0的根)作为目标函数f(x)的近似极值点。

x23p2p1f3x*1xf(x)p(x)xx1p3f2fp例1用二次插值法求函数f(x)=3x3-4x+2的极小点，给定x0=0,ε=0.2。

解

1）确定初始区间初始区间[a,b]=[0,2],中间点x2=1。2）用二次插值法逼近极小点相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292在新区间，相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.xp*＝0.607,fp=0.243

由于fp<f2,xp>x2,新区间[a,b]=[x2,b]=[0.555,1]|x2-xp*|=|0.555-0.607|=0.052<0.2,迭代终止。

xp*＝0.607,f*=0.243由于fp<f2,xp*

<x2,新区间[a,b]=[a,x2]=[0,1]|x2-xp*

|=1-0.555=0.445>0.2,应继续迭代。

坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻忧方法。它把多变量的优化问题轮流地转化成单变量(其余变量视为常量)的优化问题，因此又称这种方法为变量轮换法。在搜索过程中可以不需要目标函数的导数，只需目标函数值信息。这比前面所讨论的利用目标函数导数信息建立搜索方向的方法要简单得多。4.3.1坐标轮换法4.3多变量优化计算的非梯度方法（1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。当维数n＞10时，则不应采用此法。仅适用于n较少（n<10）的目标函数求优；

（3）改变初始点重新迭代，可避免出现病态。方法特点

鲍威尔方法

鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。

对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。

1.共轭方向的生成jjkkkdddjggk+1xxk+1设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。

梯度和等值面相垂直的性质,dj和xk,xk+1两点处的梯度gk,gk+1之间存在关系:另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:因而有取这说明只要沿dj方向分别对函数作两次一维搜索，得到两个极小点xk和xk+1

，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。2.基本算法二维情况描述鲍威尔的基本算法:

1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。2）从x0出发，顺次沿e1，e1作一维搜索，得点，两点连线得一新方向d1沿d2作一维搜索得点x2

。即是二维问题的极小点x*

。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。用

d1代替e1形成两个线性无关向量d1,e2

，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。

3）从出发，顺次沿e2,d1

作一维搜索，得到点，两点连线得一新方向:

把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。

因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点，所以上述基本算法有待改进。

鲍威尔方法是鲍威尔于1964年提出的，以后又经过他本人的改进。该法是一种有效的共轭方向法，它可以在有限步内找到二次函数的极小点。对于非二次函数只要具有连续二阶导数，用这种方法也是有效的。单纯形方法一、基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。定义：单纯形

n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。（1）反射——设除了最劣点X1以外的基余顶点的中心为X4，作X1关于点X4的对称点X5，称X5为X1的反射点。求反射点的过程称之为反射。（2）扩张——在得到反射点X5之后，如果X5优于原单纯形的最劣点（即有），表明反射方向（X5—X1）是有利方向，反射成功。若进一步有，可沿反射方向前进适当的距离到点X6。X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代X1，得新单纯形{X6,X2,X3}；否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形{X5,X2,X3}。设当前的单纯形的顶点为X1，X2，X3，且有如果出现。表示反射完全失败，应退回到介于X4与X1之间的某个点X8。（3）收缩——在得到反射点X5之后，如果有表示反射部分成功，方向（X5—X1）虽然是有利方向，但X5前进过远，应收缩到介于X4与X5之间的某个点X7。上述两种从反射点向X1方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形{X7,X2,X3}或{X8,X2,X3}；否则，称之为收缩失败，舍弃收缩点。（4）缩边——若收缩失败，则应压缩当前单纯形的边长：令最优点X3不动，而其余顶点向X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点X1压缩到点X9，点X2压缩到点X10，得新单纯形{X9,X10,X3}，这一过程称之为缩边。二、单纯形替换算法设初始点为X0，初始边长h，ei为坐标轴方向的单位向量，预定正数（2）比较各项点Xi的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为Xw；（3）求反射中心其中，a>0，通常取a=1；

（1）令；输出XL，为原问题近似极小点；否则，转（2）。构造新单纯形；（4）根据不同情况，分别进行扩张，收缩或缩边，其中收缩因子（5）如果满足1、坐标轮换法计算效率较低适合维数较低，目标函数无导数或导数较难求得2、Powell法具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一3、单纯形法思路清楚，收敛慢无约束优化方法——直接法总结4.4梯度法

基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有

根据一元函数极值的必要条件和多元复合函数求导公式，得

在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。

最速下降法的搜索路径方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为算出一维搜索最佳步长

第一次迭代设计点位置和函数值

继续作下去，经10次迭代后，得到最优解

这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图。将上例中目标函数引入变换其等值线由椭圆变成一簇同心圆。

仍从

即

出发进行最速下降法寻优。此时：沿负梯度方向进行一维搜索：则函数f(X)变为：y1=x1,y2=5x2β为一维搜索最佳步长，可由极值条件：由从而算得一步计算后设计点的位置及其目标函数：经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。共轭梯度法共轭梯度法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从x(k)出发，沿负梯度方向作一维搜索:设与sk共轭的下一个方向sk+1由sk和点xk+1的负梯度的线形组合构成，即：共轭条件：则：解得：令为函数的泰勒二次展开式则上两式相减，并代入将式与式转置两边相乘，应用共轭条件得：因此，已知初始点[1,1]T例题4-4求下列问题的极值解：1）第一次沿负梯度方向搜寻计算初始点处的梯度为一维搜索最佳步长，应满足迭代精度。得:2）第二次迭代：代入目标函数得因收敛。由从而有：梯度法的特点（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等