第四章 无约束优化方法

第四章

无约束优化方法坐标轮换法鲍威尔法梯度法牛顿法DFP变尺度法BFGS变尺度法无约束优化方法的评价准则及选用

无约束优化方法是优化技术中基本的也是非常重要的内容。无约束优化问题的数学模型求上述问题最优解（x*,F*）的方法，称为无约束优化方法

无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的研究给约束优

化方法建立明确的概念、提供良好的基础·某些优化设计方法就是先把约束优化设计问题转化为无约束问题后，

再直接用无约束优化方法求解。无约束优化理论研究开展得较早，构成的优化方法巳很多，也比较成熟，新的方法仍在陆续出现。本章的内容与目的是讨论几个常用无约束优化方法的基本思想、方法构成、迭代步骤以及终止准则等方面问题。无约束优化方法总体分成两大类型:解析法或称间接法、直接搜索法或简称直接法；在n维无约束优化方法的算法中，用函数的一阶、二价导数进行求解的算法，称为解析法;对于n维优化问题，如果只利用函数值求最优值的解法，称为直接搜索法；解析法的收敛速率较高，直接法的可靠性较高。

本章介绍的坐标轮换法和鲍威尔法属于直接法；梯度法、共轭梯度法、牛顿法和变尺度法属于解析法无约束优化方法算法的基本过程是:从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k),取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步逼近最优点x*。可以把初始点x(k)、搜索方向S(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定着一个算法的成败、收敛速率的快慢等。所以，一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一。坐标轮换法坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经过适当处理用于约束优化问题求解。坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。一、坐标轮换法的迭代过程二次函数为例。任取一初始点x(0)作为第一轮的始点x0

(1),先沿第一坐标轴的方向e1作一维搜索，用一维优化方法确定最优步1长

(1)

，得第一轮的第一个迭代点x1

=x0

+(1)

(1)(1)

e

，1

1然后以x1

(1)为新起点，沿第二坐标轴的方向e2作一维2搜索，确定步长

(1)

，得第一轮的第二个迭代点2

1x

(1)

=x

(1)

+(1)

e1

2第二轮迭代，需要x

(2)x0

2(1)1

0x

(2)

=

x

(2)

+1(2)

e1x

(2)

=x

(2)

+(2)

e2

1

2

2依次类推，不断迭代，目标函数值不断下降，最后逼近该目标函数的最优点。二、终止准则可以采用点距准则注意：若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。坐标轮换法的计算步骤⑴任选初始点，置n个坐标轴方向矢量为单位作为第一轮的起点坐标矢量：⑵按照下面迭代公式进行迭代计算k为迭代轮数的序号，取k=1，2，……；i为该轮中一维搜索的序号，取i=1，2，……n步长α一般通过一维优化方法求出其最优步长。⑶按下式判断是否中止迭代如满足，迭代中止，并输出最优解最优解否则，令k←k+1返回步骤（2）例题4.1

用坐标轮换法求目标函数的无约束最优解。给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，为第一轮的起始点，取按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1。这里，我们暂且用微分学求导解出，令其一阶导数为零以

为新起点，沿e2方向一维搜索以最优步长原则确定α2，即为极小化对于第一轮按终止条件检验继续进行第2轮迭代计算，各轮计算结果见课本表4.1。计算5轮后，有故近似优化解为标轮换法的流程图-+-+小结坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于10的低维优化问题。对于目标函数存在“脊线”的情况，在脊线的尖点处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。x2x1脊线鲍威尔方法鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法。一、鲍威尔基本算法如图所示，以三维二次目标函数的无约束优化问题为例。鲍威尔基本算法的搜索过程鲍威尔基本算法的步骤：第一环基本方向组取单位坐标矢量系e1、e2、e3

、…、

en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向，n

0Sk=x

k-x

k再沿新生方向作一维搜索，完成第一环的迭代。以后每环的基本方向组是将上环的第一个方向淘汰，上环的新生方向补入本环的最后而构成。……

S2

3

nS

k

S

k

Skn维目标函数完成n环的迭代过程称为一轮。从这一轮的终点出发沿新生方向搜索所得到的极小点，作为下一轮迭代的始点。这样就形成了算法的循环。鲍威尔基本算法的缺陷：可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第k环中，产生新的方向：Sk=xnk-x0k=1(k)S1(k)+

2(k)S2(k)

+

•

•

•

+

n(k)Sn(k)式中，S1(k)、S2(k)、•••、Sn(k)为第k环基本方向组矢量，1(k)、2(k)、•••、n(k)为个方向的最优步长。若在第k环的优化搜索过程中出现1(k)=0，则方向Sk表示为S2(k)、S3(k)、•••、Sn(k)的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。如图所示为一个三维优化问题的示例，设第一环中1=0

，则新生方向与e2

、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。鲍威尔基本算法的退化x1x31=02e23e3S1x2二、鲍威尔修正算法在某环已经取得的n+1各方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组鲍威尔修正算法的搜索方向的构造：在第k环的搜索中，x0k

为初始点，搜索方向为S1(k)、S2(k)、•••、Sn(k)，产生的新方向为Sk

，此方向的极小点为x(k)。点xn+1(k)=2xn(k)-x0(k)，为x0(k)对xn(k)的映射点。计算x0(k)、x1(k)、•••、xn(k)、x(k)、x

n+1(k)各点的函数值，记作：0

2nF1=F(x

(k))

F

=F(x

(k))F3=F(x(k))=

F(x

(k))

-F(xn+1

m

m-1(k))是第k环方向组中，依次沿各方向搜索函数值下降最大值，即Sm(k)方向函数下降最大。(F2)(F1)影射点(F3)函数下降量△尔算法的方向淘汰为了构造第k+1环基本方向组，采用如下判别式：按照以下两种情况处理：1、上式中至少一个不等式成立，则第k+1环的基本方1

2

n向仍用老方向组S

(k)、S

(k)、•••、S

(k)。k+1环的初始点取0

nx

(k+1)=x

(k)F

<F2

30n+1x

(k+1)=x

(k)F2

F32、两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为S

(k)、S

(k)、•••、S1

2

m-1m+1

n(k)、S

(k)

•

•

•

、

S

(k)

、Sn+1(k)。k+1环的初始点取0x

(k+1)=x(k)n+1x(K)是第k环沿S

(K)方向搜索的极小点。鲍威尔算法的终止条件：0||

x(K)-x

(k)

||三修正算法的迭代步骤及流程图Powell算法的步骤如下：⑴任选初始迭代点，选定迭代精度ε，取初始基本方向组为单位坐标矢量系其中，i=1，2……n（下同）。然后令k=1（环数）开始下面的迭代⑵沿

诸方向依次进行n次一微搜索，确定各步长使i=1，2……n得到点阵构成新生方向沿

方向进行一维搜索求得优化步长

，得⑶判断是否满足迭代终止条件。如满足则可结束迭代，最优解为停止计算。否则，继续进行下步。⑷计算各迭代点的函数值最大者，并找出相邻点函数值差（1≤m≤n）及与之相对应的两个点的连线方向。和，并以

表示两点⑸确定映射点并计算函数值检验鲍威尔条件若至少其中之一成立转下步，否则转步骤⑺⑹置k+1环的基本方向组和起始点为（即取老方向组）当F2＜F3当F2≥F3令k←k+1，返回步骤⑵⑺置k+1环的方向组和起始点为令k←k+1，返回步骤⑵例题4.2试用鲍威尔修正算法求目标函数的最优解。已知初始点，迭代精度ε=0.001解：第一环迭代计算沿第一坐标方向e1进行一维搜索α1=2以

为起点，改沿第二坐标轴方向e2进行一维搜索α2=0.5构成新方向沿S1方向进行以为搜索得极小点与极小值计算点距需进行第二环迭代计算第二环迭代计算首先确定上环中的最大函数下降量及其相应方向映射点及其函数值检查鲍威尔条件于是可知鲍威尔条件两式均不成立。第二环取基本方向组和起始点为沿e2方向作一维搜索得以

为起点沿S1方向一维搜索得构成新生方向沿S2方向一维搜索得检查迭代终止条件需再作第三环迭代计算。根据具体情况来分析，S1，S2实际上为共轭方向，见下图。本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三环迭代，则一定各一维搜索的步长为零，必有故得最优解梯度法优化设计是追求目标函数值最小，因此，自然可以设想从某点出发，其搜索方向取该点的负梯度方向，使函数值在该点附近下降最快。这种方法也称为最速下降法。一、基本原理梯度法的迭代公式为：x(k+1)=x(k)-

(k)g(k)f(x(k))

，(k)其中g(k)是函数F(x)在迭代点x(k)处的梯度一般采用一维搜索的最优步长，即f(x(k+1))=f(x(k)-

(k)g(k))=min

f(x(k)-(k)g(k))=min(

)据一元函数极值条件和多元复合函数求导公式，得’(

)=

-(

f(x(k)-(k)g(k)))T

g(k)

=0即(f(x(k+1)))T

g(k)

=0➢或(g(k+1))Tg(k)=0此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。这是因为梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。二、迭代终止条件？若满足输出最优解采用梯度准则：||

g(k)

||三、迭代步骤任选初始迭代点x(0)，选收敛精度

。确定x(k)点的梯度（开始k=0)判断是否满足终止条件||

g(k)||结束计算。否则转下步。（4）从x(k)点出发，沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点

x(k+1)=x(k)-

(k)g(k)

,令k=k+1

返回步骤(2)。四、梯度法流程图出口入口给定：x(0)，k=0x(k)=

x(0)计算：g(k)k=k+1沿g(k)方向一维搜索，求最优步长(k)。x(k+1)=

x(k)-

(k)

g(k)/

||g(k)||N？||g(k)||Yx*=x(k)f*=f(x(k))的最优解。例题4.3用梯度法求目标函数已知初始点迭代精度ε=0.005解：函数的梯度第一次迭代：以为起点沿一方向作一维搜索得第一个迭代点继续第二次迭代到第五次迭代结束时，有故迭代可终止，最优解为迭代数据表见课本表4.2共轭梯度法共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。一、共轭梯度法的搜索方向共轭梯度法的搜索方向采用梯度法基础上的共轭方向，如图所示，目标函数F(x)在迭代点xk+1处的负梯度为-f(xk+1)，该方向与前一搜索方向Sk互为正交，在此基础上构造一种具有较高收敛速度的算法，该算法的搜索方向要满足以下两个条件：（1）以xk+1点出发的搜索方向

Sk+1是-

f(xk+1)与Sk的线性组合。即xkx*xk+1-

f(xk+1)Sk+1Skf(xk+1)

+Sk+1

=

-

kSk（2）以与为基底的子空间中，矢量与相共轭，即满足[Sk+1]T

G

Sk

=0二、

k的确定确定方法自学，不作要求。记住三、共轭梯度法的算法（1）选初始点x0和收敛精度

。（2）令k=0，计算S0

=

-

f(x0)

。(k)，得（3）沿Sk方向进行一维搜索求x(k+1)=x(k)+

(k)S(k)（4）计算

f(xk+1)

，若||

f(xk+1)||，则终止迭代，取x*=xk+1；否则进行下一步。（5）检查搜索次数，若k=n，则令x0=xk+1，转（2），否则，进行下一步。（6）构造新的共轭方向f(xk+1)

+Sk+1

=

-

kSk令k=k+1，转（3）四、共轭梯度法流程图||

f(xk+1)

||？出口求(k)S(k)(k)

，x(k+1)=

x(k)

+计算：

f(xk+1)x*=xk+1f(x*)=f(xk+1)YN入口给定：x(0)，k=0，计算：-

f(x0)x0=xk+1Nk

n

？YSk+1

=

-f(xk+1)

+kSkK=K+1五、共轭梯度法的特点共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。六、例题牛顿法牛顿法是求无约束最优解的一种古典解析算法。牛顿法可以分为原始牛顿法和阻尼牛顿法两种。实际中应用较多的是阻尼牛顿法。原始牛顿法一、原始牛顿法的基本思想在第k次迭代的迭代点x(k)邻域内，用一个二次函数去近似代替原目标函数F(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过多次重复迭代，使迭代点逐步逼近原目标函数的极小点。如图所示。0(x)1(x)F(x)x0x2

x1x*二、原始牛顿法的迭代公式设目标函数F(x)具有连续的一、二阶导数，在x(k)点邻域内取F(x)的二次泰勒多项式作近似式，即取逼近函数

(x)为设x(k+1)为(x)极小点，根据极值的必要条件，应有(x(k+1))=0，即(x)=

gk+

Hk

x=0又x=

x

(k+1)

-

x

(k)得x

(k+1)=x

(k)-H

-1gk

kk

k即牛顿法迭代公式，方向-H

-1g

称为牛顿方向三、原始牛顿法的特点若用原始牛顿法求某二次目标函数的最优解，则构造的逼近函数与原目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。牛顿法是具有二次收敛性的算法。其优点是：对于二次正定函数，迭代一次即可以得到最优解，对于非二次函数，若函数二次性较强或迭代点已经进入最优点的较小邻域，则收敛速度也很快。原始牛顿法的缺点是：由于迭代点的位置是按照极值条件确定的，并未沿函数值下降方向搜索，因此，对于非二次函数，有时会使函数值上升，即f(xk+1)>

f(xk)，而使计算失败。阻尼牛顿法(k)对原始牛顿法的改进为解决原始牛顿法的不足，加入搜索步长因此，迭代公式变为：x

(k+1)

=

x

(k)

-

(k)

H

-1gk

k这就是阻尼牛顿法的迭代公式，最优步长(k)也称为阻尼因子，是沿牛顿方向一维搜索得到的最优步长。ε牛顿法算法步骤⑴任选初始点，给定精度ε，置k←0⑵计算

点的梯度矢量及其模⑶检验迭代终止条件如满足，则输出最优解否则，转下步⑷计算

点处的海塞矩阵i，j=1，2……n并求其逆矩阵⑸确定牛顿方向方向上的最优步并沿牛顿方向作一维搜索，求出在长⑹计算第k+1个迭代点置k←k+1，返回步骤⑵顿法的算法流程图+-例题4.5

用牛顿法求函数的最优解。初始点，解：函数的梯度和海赛矩阵及其逆在

点处沿

方向移位搜索求得最优步长故新迭代点为该点的梯度迭代即可结束由于目标函数是二次正定函数，故迭代一次即达到最优点三、阻尼牛顿法的特点优点：由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有苛刻的要求。缺点：1、对目标函数要求苛刻，要求函数具有连续的一、二阶导数；为保证函数的稳定下降，海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇异。2、计算复杂且计算量大，存储量大DFP变尺度法变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经

Fletcher和Powell加以发展和完善的一种变尺度法，故称为DFP变尺度法。一、变尺度法的基本思想变尺度法的基本思想与牛顿法和梯度法有密切联系。观察梯度法和牛顿法的迭代公式和kx(k+1)=x(k)-

(k)g(k)x(k+1)=x(k)-

(k)H

-1

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

-1

g(k)，不仅需要计算一k阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。若迭代过程先用梯度法，后用牛顿法并避开牛顿法的

海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的基本构想为此，综合梯度法和牛顿法的优点，提出变尺度法的基本思想。式中的Ak为构造的n

n阶对称矩阵，它是随迭代点的位置的变化而变化的。若Ak

=I，上式为梯度法的迭代公式k若Ak

=H

-1

，上式为阻尼牛顿法的迭代公式。变尺度法的搜索方向S(k)=-Ak

gk

，称为拟牛顿方向。变尺度法的基本迭代公式写为下面的形式：➢x(k+1)

=

x(k)

-

(k)Ak

gkDFP法构造矩阵序列的产生构造矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列{Ak}，k=1，2，……选取初始矩阵A0，并以梯度方向快速收敛，通常取单位矩阵E作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令A

=A

+△A1

0

0推广到一般的k+1次构造矩阵Ak+1=Ak+△Ak矩阵序列的基本迭代式△Ak称为校正矩阵拟牛顿条件设F（x）为一般形式n阶的目标函数，并具有连续的一、二阶偏导。在点

处的二次泰勒近似展开该近似二次函数的梯度是式中，，若令，则有上式中

是第k次迭代中前后迭代点的矢量差，称他为位移矢量，并为简化书写而是前后迭代点的梯度矢量差由以上三式得海赛矩阵与梯度间的关系式由上式，用第k+1次构造矩阵近似代替，则上式通常称为拟牛顿条件或拟牛顿方程DFP法构造矩阵的递推公式（推导过程略）Ak+1=Ak+△Ak的确定取决于第k次迭代由上式可以看出，构造矩阵中的下列信息：上次的构造矩阵Ak，迭代点位移矢量迭代点的梯度增量

，因此，不必作二阶导数矩阵及其求逆的计算对DFP法几个问题的说明与讨论⑴DFP公式总有确切的解⑵构造矩阵的正定性⑶DFP法搜索方向的共轭性⑷关于算法的稳定性DFP算法的迭代步骤步骤⑴任取初始点给出迭代精度ε.计算初始点精度若

转步骤⑺，及其模否则进行下一步。⑵置k←0，取Ak←E⑶计算迭代方向沿

方向做一维搜索求优化步长

，使确定下一个迭代点，若⑷计算

的梯度

及其模则转步骤⑺，否则转下一步⑸计算位移矢量

和梯度矢量按DFP公式计算构造矩阵⑹置k←k+1。若k<n(n为优化问题