第4章 无约束优化方法

第四章无约束优化方法§4-1最速下降法（梯度法）§4-2牛顿类方法§4-3共轭方向法§4-4共轭梯度法§4-5变尺度法§4-6坐标轮换法§4-7鲍威尔方法§4-8单形替换法第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。

为什么要研究无约束优化问题?

（1）有些实际问题，其数学模型本身就是一个无约束优化问题。

（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。

（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。无约束优化问题是：求n维设计变量使目标函数

目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。（1）间接法——要使用目标函数的一阶或二阶导数构造搜索方向，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，只利用目标函数值构造搜索方向，如坐标轮换法、鲍威尔法、单纯形法等。4-1梯度法

基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。

搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。

为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有

根据一元函数极值的必要条件和多元复合函数求导公式，得图4-2最速下降法的搜索路径

在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。梯度法计算步骤例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

算出一维搜索最佳步长

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

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

这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图4-3。图4-3等值线为椭圆的迭代过程将上例中目标函数引入变换y1=x1,y2=5x2则函数f(X)变为：其等值线由椭圆变成一簇同心圆。

仍从

即

出发进行最速下降法寻优。此时：沿负梯度方向进行一维搜索：β为一维搜索最佳步长，可由极值条件：由从而算得一步计算后设计点的位置及其目标函数：经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。等值线为圆的迭代过程比较以上两种函数形式二次型函数的对角形矩阵刻画了椭圆的长短轴，它们是表示度量的矩阵或者是表示尺度的矩阵。最速下降法的收敛速度和变量的尺度关系很大，在适当条件下，最速下降法的收敛速度估计式为M——f（x）海塞矩阵最大特征值上界m——f（x）海塞矩阵最小特征值下界梯度法的特点（1）理论明确，程序简单，对初始点要求不严格。每迭代一次除需进行一维搜索外，只需计算函数的一阶导数，计算量小。（2）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（3）按负梯度方向搜索并不等同于以最短时间到达最优点，对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指迭代点的一个局部性质，从局部上看，在一点附近函数下降是最快的，但从整体看则走了许多弯路，下降的并不算快。（4）梯度法的收敛速度与目标函数的性质和初始点的位置选择密切有关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。最速下降法采用了函数的负梯度方向作为下一步的搜索方向，整个搜索过程收敛速度较慢，这是它的主要缺点。但是，应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用，特别是一些更有效的方法都是在对它进行改进后，或在它的启发下获得的，因此最速下降法仍是有约速和无约束优化方法的基础。4-2牛顿类方法基本思想：在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。设为的极小点

一维情况的牛顿迭代公式k+1=kf

(k)/f(k)k=0,1,2,对于多元函数f(x),设xk为f(x)极小点x*的一个近似点，在xk处将f(x)进行泰勒展开，保留到二次项，得到海塞矩阵这就是多元函数求极值的牛顿法迭代公式。

对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。

例4－2求目标函数的极小点。解取初始点则初始点处的函数梯度、海赛矩阵及其逆阵分别为牛顿方向经过一次迭代即求得极小点函数极小值

从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。阻尼牛顿法

阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：

阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有要求。阻尼牛顿法的迭代步骤：例用牛顿法求解下列方法：给定初始点解目标函数f(x)的梯度和海塞矩阵是在x(1)处，目标函数f(x)的梯度和海塞矩阵是牛顿方向从x(1)出发，沿d(1)作一维搜索，令步长变量为λ，最优步长为λ1，则有令故上述想x（2）即极小点。牛顿法方法特点

（1）初始点应选在极小值X*附近，有一定难度；（2）尽管每次迭代都不会使函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；

（4）

不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。梯度法与牛顿法：一般迭代式：梯度法：牛顿法：阻尼牛顿法：4-3

共轭方向及共轭方向法为了克服最速下降法的锯齿现象以提高其收敛速度，发展了一类共轭方向法。一、共轭方向的基本概念首先以二元二次函数为例予以说明共轭方向概念，设函数2*2阶对称正定矩阵式中二元二次函数的等值线为一组椭圆，任选初始点x0沿某个下降方向d0作一维搜索，得x1=x0+0d0。0是沿d0方向搜索的最佳步长，即在x1点处函数f(x)沿d0方向的方向导数为零。故有d0与某一等值线相切于x1点。为了避免按最速下降法出现的锯齿现象，可取下一次的迭代搜索方向d1直指极小点x*，如图所示。既有x*=x1+1d11为d1方向上的最佳步长。二次函数f(x)在x1点的梯度为f(x1)=Gx1+b当x1x*时10，由于x*是函数f(x)的极小点，应有f(x*)=Gx*+b=0f(x*)=G(x1+1d1)+b=f(x1)+1Gd1=0等式两边同时左乘(d0)T,整理，得(d0)TGd1=0这就是为使d1直指极小点x*,d1所必须满足的条件。满足上式得两个向量d0,d1称为G的共轭向量，或者说d0,d1对G是共轭的。d1方向应该满足什么条件？二、共轭方向的性质定义设G是nn阶对称正定矩阵，若维空间中有m个非零向量d0，d1，dm-1满足(di)TGdj=0(i,j=0,1,2,,m-1)(ij)则称d0，d1，dm-1对G共轭，或称它们是G的共轭方向。

当G=I(单位矩阵）时，上式变成(di)Tdj

=0(ij)即向量d0，d1，dm-1互相正交。由此知，共轭概念是正交概念的推广，正交是共轭的特例。性质1

若非零向量d0，d1，dm-1对G共轭，则这m个向量线性无关。性质2

在n维空间中相互共轭的非零向量的个数不超过n。性质3

从任意初始点x0出发，顺此沿n个G的共轭方向d0，d1，dm-1进行一维搜索，最多经过n次迭代就可以找到二次函数的极小点。此性质表明本迭代方法具有二次收敛性。一个算法能经有限步的搜寻后求出二次目标函数的极小点三、共轭方向法建立在性质3的基础上，提供了求二次函数极小点的原则方法。步骤是：1）选定初始点x0,下降方向d0和收敛精度，置k0。共轭方向法的程序框图2）沿dk

方向进行一维搜索，得xk+1=xk

+kd

k.3)判断||f(xk+1)||<是否满足，满足则打印xk+1，停机，否则转4。4）提供新的共轭方向dk+1,使(dj)TGdk+1=0,j=0,1,2,,k.5)置kk+1,转2。格拉姆-斯密特向量系共轭化方法设已选定线性无关向量系（例如，它们是n个坐标轴上的单位向量），首先取令其中是待定系数，它根据与共轭条件来确定，即与共轭的设已求得共轭向量，现求。令为使与共轭，应有由此解得于是

例4-3求的一组共轭向量d0,d1,d2。解：选三个坐标轴上的单位向量e0、e1、e2作为一组线性无关向量系取设得设得计算表明说明d0,d1,d2对G共轭。

上述算法是针对二次函数的，对于非二次函数，在极小点可以用二次函数来近似上式中的海赛矩阵相当于二次函数中的矩阵G，但x*未知。当迭代点x0充分靠近x*时，可用G(x0)构造共轭向量系。更有效的共轭方法是构造共轭向量系时避开海塞矩阵，下一节将讨论构造共轭向量系时如何避开海赛矩阵。

共轭方向法是建立在共轭方向性质3的基础上的。它提供了求二次函数极小点的原则方法。在无约束方法中许多算法都是以共轭方向作为搜索方向，根据构造共轭方向的原理不同，可以形成不同的共轭方向法，如共轭梯度法，鲍威尔法等。4-4

共轭梯度法

共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。本节介绍的共轭梯度法是一种著名的共轭方向法，它的基本思想是把共轭性与最速下降法相结合，利用已知点的梯度构造一组共轭方向，并沿此组方向进行搜索，求出目标函数的极小点。该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来，根据共轭方向的基本性质，这种方法具有二次收敛性。考虑二次函数从点出发，沿G的某一共轭方向做一维搜索，到达点，即或海塞矩阵而在点处的梯度分别为若与对G是共轭的，则据共轭条件有所以有（4-1）对式4-1两端左乘，即得式中不再包含海塞矩阵此式表明沿方向进行一维搜索，其终点与始点的梯度之差与的共轭方向正交。共轭梯度法的计算过程1、设初始点为，第一个搜索方向取，得并算出点处的梯度。和组成平面正交系2、在和组成的平面正交系中求的共轭方向。令——待定常数，根据共轭方向与梯度关系求得。由X0点负梯度方向线性无关有求得构成一个正交系。沿方向进行一维搜索与共轭为最佳步长即X1点梯度方向3、在所构成的正交系中，求与及均共轭的方向。因为与均共轭，有考虑到g0,g1,g2相互正交，有设1=1，得因此从而得出沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。若目标函数为非二次函数，经n次搜索还未达到最优点时，则以最后得到的点为初始点，重新计算共轭方向，一直到满足收敛精度要求为止。再沿点d2方向继续进行一维搜索，可得递推公式为共轭梯度法的迭代步骤共轭梯度法的程序框图例题4-3求下列问题的极值，已知初始点[1,1]T解：1）第一次沿负梯度方向搜寻计算初始点处的梯度为一维搜索最佳步长，应满足得:2）第二次迭代：代入目标函数由得从而有：即x2点满足极值必要条件，再根据x2点的海赛矩阵正定，可知x2满足极值充分必要条件。故x2是极小点，即函数的极小值为f(x*)=8

共轭梯度法的计算过程可以看出，第一个搜索方向是负梯度方向，这就是最速下降法。其余各步的搜索方向是将负梯度偏转一个角度，也就是对负梯度进行修正，称为旋转梯度法。共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。4-5变尺度法变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法，故称为DFP变尺度法。一、变尺度法的基本思想

变尺度法的基本思想与牛顿法和梯度法有密切联系。观察梯度法和牛顿法的迭代公式

x(k+1)

=x(k)

-(k)

g(k)

和 x(k+1)

=x(k)

-(k)

Gk-1

g(k)

分析比较这两种方法可知：梯度法的搜索方向为-g(k)，只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。

牛顿法的搜索方向为-Gk-1g(k)

，不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的基本构想。

为此，综合梯度法和牛顿法的优点，提出变尺度法的基本思想。变尺度法的基本迭代公式写为下面的形式：

xk+1=xk-kH(k)

g(k)式中的H(k)为构造的nn阶对称矩阵，它是随迭代点的位置的变化而变化的。变尺度法的搜索方向-H(k)

g(k)

，称为拟牛顿方向。若H(k)=I，上式为梯度法的迭代公式，若H(k)=[G(xk)]-1

，上式为阻尼牛顿法的迭代公式。当矩阵Ak不断地迭代而能很好地逼近H(k)=[G(xk)]-1

时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵Hk的产生。二、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。尺度变换能显著地改进几乎所有极小化方法的收敛性质。例如在用最速下降法求的极小值时需要进行10次迭代才能达到极小点如作变换

y1=x1,y2=5x2把的尺度放大5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。x2消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。对于一般二次函数为减低函数二次项的偏心程度，进行尺度变换

xQx则在新的坐标系中，函数的二次项变为若矩阵是正定的，则总存在矩阵Q使QTGQ=I将函数的偏心变为零。用Q-1右乘等式两边，得QTG=Q-1再用Q左乘等式两边，得QQTG=I所以QQT=G-1这说明二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q求得。

QQT实际上是在空间内测量距离大小的一种度量，称为尺度矩阵，记作H，即

H=

QQT根据变尺度法的基本原理，需要构造一个变尺度矩阵序列{Hk}来逼近海赛逆矩阵序列{Gk-1}，每迭代一次，尺度改变一次。从初始矩阵A0=I(单位矩阵)开始，通过对公式中修正矩阵ΔHk的不断修正，在迭代中逐步逼近于Gk-1.因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。变尺度法的迭代公式：牛顿法法的迭代公式：搜索方向三、变尺度矩阵的建立根据变尺度法的基本思想，需要构造一个矩阵Hk，使其得到的搜索方向必须具有下降性、收敛性和计算简便性。1、下降性即只要构造的矩阵H（k）为对称正定矩阵，就是下降方向。对于求目标函数的极小化问题，当沿某个可行方向向量s作出微小移动时，其目标函数的变化为对于充分小的，若成立，则s为目标函数下降可行方向。即2、为了使构造的矩阵H(k)逐渐逼近，所以还要满足拟牛顿条件。取其梯度，令设，若为极值点附近的第k+1次的迭代，则即即若用一矩阵Hk+1来逼近，就必须满足令则为拟牛顿条件3、为适应迭代需要，希望变尺度矩阵有如下递推形式，即——称为第k次的校正矩阵（1）选定初始点和收敛精度（4）沿方向进行一维搜索，计算（5）收敛判断，停机，否则6若满足则（6）若令转2，若转7.四、变尺度法的一般步骤及程序框图（7）计算矩阵，置，返回到3。（2）计算，选取初始对称正定矩阵置（3）计算搜索方向变尺度法程序框图五、DFP算法

在变尺度法中，校正矩阵Ek取不同的形式，就形成不同的变尺度法。用递推方法构造拟牛顿条件(1)再令(2)可保证AK的对称性待定常数代入(1):两边对比得:回代到(2)得:(3)例4-3：

用DFP算法求下列问题的极值：解：1）取初始点，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度取初始变尺度矩阵为单位矩阵H0=I，则第一次搜寻方向为

沿d0方向进行一维搜索，得为一维搜索最佳步长，应满足得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算代入校正公式==第二次搜寻方向为再沿d1进行一维搜索，得为一维搜索最佳步长，应满足,得3）判断x2是否为极值点梯度:

海赛矩阵:梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。

算法评价：

DEF变尺度法以逐次逼近的方法实现G-1

的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。算法的第一步是梯度法，最速下降；接近x*

时，又采用二次收敛的共轭方向，总的收敛速度较快。

H(k)

近似代表x(k)点的二阶导数，当其为零时，可判断x(k)为鞍点。

H(k)

的计算较复杂，存储量较大。算法稳定性较差，由于计算机有舍入误差，容易使H(k)

的正定性破坏，趋于奇异。

六、BFGS算法式中4-6坐标轮换法坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经过适当处理用于约束优化问题求解。坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。基本思想：是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程。每次一维搜索时，只允许n个变量的一次改动，其余(n-1)个变量固定不变。故坐标轮换法也常称单变量法或变量交错法。坐标轮换法的迭代过程以二元函数为例，如右图所示。从初始点x00出发，沿第一个坐标方向搜索，即d10=e1得x10=x00+10d10按照一维搜索方法确定最佳步长因子10满足：；然后从x10出发沿d20=e2方向搜索得x20=x10+20d20，

其中步长因子20满足：x20为一轮(k=0)的终点。检验始、终点间距离是否满足精度要求，即判断||x20

x00||<的条件是否满足。若满足则x*x20，否则令x01x20,重新依次沿坐标方向进行下一轮(k=1)的搜索。根据上述原理，对于第k轮计算，其迭代公式为其中搜索方向是轮流取n维空间个坐标轴的单位向量此法的收敛效果与目标函数等值线的形状有很大关系二次就收敛到极值点多次迭代后逼近极值点目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴，以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。方法特点

（1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。当维数n＞10时，则不应采用此法。仅适用于n较少（n<10）的目标函数求优；（3）受目标函数性态影响很大。改变初始点重新迭代，可避免出现病态。4-7鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。因此本质上是一种共轭方向法。这种方法不用对目标函数求导计算。当目标函数不易求导或导数不连续时，可以采用这种方法。共轭方向的定义共轭方向的性质：鲍威尔方法是在研究具有正定矩阵G的二次函数的极小化问题时形成的。对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。

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

根据梯度和等值面相垂直的性质,

dj和

xk,xk+1两点处的梯度gk,gk+1之间存在关系:另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:取两式相减，得因而有则dk和dj对G共轭。这说明只要沿dj方向分别对函数作两次一维搜索，得到两个极小点xk和xk+1，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。对于二维问题，的等值线为一族椭圆，A,B为沿轴方向上的两个极小点，分别处于等值线的切点上。则AB就是与轴一起对G共轭的方向。沿此共轭方向进行一维搜索就可找到函数的极小点x*。2.鲍威尔的基本算法针对二维情况描述鲍威尔的基本算法:

x1x2x0oe1e2d1d2x*11）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。2）从x0出发，顺次沿e1，e2作一维搜索，得点，两点连线得一新方向d1用d1代替e1形成两个线性无关向量e2,d1，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。3）从出发，顺次沿e2,d1

作一维搜索，得到点，两点连线得一新方向:从x21出发，沿d2作一维搜索得点x2即是二维问题的极小点x*。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。

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

鲍威尔基本算法的缺陷

可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第k环中，产生新的方向：

Sk=xnk-x0k=1kS1k+2kS2k+•••+nkSnk

式中，S1k、S2k、

•••、Snk为第k环基本方向组矢量，1k

、2k、•••、nk为对应方向的最优步长。

若在第k环的优化搜索过程中出现1k=0，则方向Sk表示为S2k、

S3k、•••、Snk的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。

如图所示为一个三维优化问题的示例，设第一环中1=0，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。鲍威尔基本算法的退化x1x2x31=01e23e3S1

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

3.改进的算法

在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。

在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。为此，要解决两个关键问题：（1）dk＋1是否较好？是否应该进入新的方向组？即方向组是否进行更新？（2）如果应该更新方向组，dk＋1不一定替换方向，而是有选择地替换某一方向。改进算法步骤：（1）给点初始点x0（记做），选取初始方向组它由n个线性无关的向量所组成，置k0。令在k次循环中分别称为一轮迭代的始点、终点和反射点。（2）从出发，顺次沿做一维搜索得。接着以为起点，沿方向移动一个的距离，得同时计算各中间点处的函数值记：因此则在第k次循环中函数下降最多的第m次迭代是相应的方向为。为了构成共轭性好的方向组，须遵循下列准则：在k次循环中，若不满足条件：和则下轮迭代仍用原方向组，并以中函数值小者作为下一轮迭代的始点。

这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函数，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。

若满足条件，则去掉方向，将补充到原方向组中的最后位置。即新方向组为作为下轮迭代的搜索方向。下轮迭代的始点取为沿方向进行一维搜索的极小点。例4-5用改进的鲍威尔法求目标函数。的最优解。已知初始点[1,1]T，迭代精度解：（1）第1轮迭代计算沿e1方向进行一维搜索得以为起点，沿第二坐标轴方向e2进行一维搜索得确定此轮中的最大下降量及其相应方向反射点及其函数值检验Powell条件由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。构成新的方向

沿方向一维搜索得极小点和极小值此点为下轮迭代初始点。

按点距准则检验终止条件

需进行第二轮迭代机算。（2）第2轮迭代计算此轮基本方向组为e2，，分别相当于，，起始点为＝。沿e2方向进行一维搜索得

以为起点沿方向一维搜索得确定此轮中函数值最大下降量及其相应方向反射点及其函数值检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为，。

构成新的方向沿方向进行一维搜索得检验终止条件

（3）第3轮迭代计算此轮基本方向组为，，起始点为＝，先后沿，方向，进行一维搜索，得，检验终止条件故最优解实际上，前两轮迭代的，为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。如果做第三次迭代，则一定各一维搜索的步长为零。4-8单形替换法一、基本思想

单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。单纯形法迭代的基本要点是保证单纯形不断向最优点移动并使单纯形缩小直至趋于一点。定义：单纯形n维空间中的恰好有n+1个顶点的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主