第三章无约束优化方法

第三章无约束优化方法第1页，课件共101页，创作于2023年2月§3.1引言一.

目的：求一组n维设计变量X=[x1,x2,…,xn]T,使目标函数达到

min.f(x)X∈Rn即求目标函数的最优解：最优点x*和最优值f(x*)。二.意义：

为约束优化方法的研究提供了策略思想、概念基础和基本方法；为约束优化问题的间接解法提供了有效而方便的方法；对于某些工程问题，进行分析后，便于提供解决的有效方法；约束优化问题的求解往往可以通过一系列无约束优化方法实现；无约束优化问题的解法是优化设计方法的基本组成部分。第2页，课件共101页，创作于2023年2月§3.1引言三.内容：一维搜索：求最优步长因子α(k)多维（变量）优化：确定搜索方向S(k)黄金分割切线法平分法插值法格点法坐标轮换法最速下降法共轭方向法鲍威尔法梯度法共轭梯度法牛顿法单形替换法变尺度法第3页，课件共101页，创作于2023年2月§3.1引言四.无约束优化方法计算步骤：1、选择一个初始点x(0)，这一点越靠近极小点x*越好。2、若已经取得某设计点x(k)，并且该点不是近似极小点，则在x(k)点根据函数f(x)的性质，选择一个方向S(k)，并且沿此方向搜索函数值是下降的，称下降方向。3、当搜索方向S(k)确定后，由x(k)点出发，沿S(k)方向进行搜索，定出步长因子

(k)，得到新的设计点：

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

(k)S(k)，并满足f(x(k+1))<f(x(k))4、若x(k+1)满足迭代计算终止条件，x(k+1)点作为x*；否则从该点出发，返回第二步继续搜索迭代。第4页，课件共101页，创作于2023年2月开始给定x和S的初始值计算

使f（x+S）极小x＝x+S

满足收敛条件？结束形成新的S无约束优化算法粗框图第5页，课件共101页，创作于2023年2月

无约束优化数值计算方法采用的是搜索方法，其基本思想是从给定的初始点出发，沿某一个搜索方向进行不断的搜索，确定最佳步长使函数值沿搜索方向下降最大，其迭代公式为x(k+1)=x(k)+

(k)S(k)各种无约束优化方法的区别在于确定其搜索方向的S(k)的方法不同。所以，搜索方向的构成问题是无约束优化问题的关键。五.无约束优化方法的关键问题：§3.1引言第6页，课件共101页，创作于2023年2月六.无约束优化方法的分类：§3.1引言

无约束优化方法的分类依据就是根据

(k)和S(k)的确定方法而定的。若根据构成搜索方向所使用的信息性质的不同，可以分为两类。

1、间接法又称解析法，是利用目标函数导数的无约束优化方法，如最速下降法、共轭梯度法、牛顿法及变尺度法等。

2、直接法

只利用目标函数值的无约束优化方法，如坐标轮换法、鲍威尔法及单形替换法等。第7页，课件共101页，创作于2023年2月§3.2一维搜索方法一.一维搜索：定义:

在第K次迭代时，从已知点X(k)出发，沿给定方向求最优步长因子α(k)，使f(X(k)+α

S(k))达到最小值的过程，称为一维搜索。方法：1.解析法：

f(x(k+1)

)=min.f(x(k)+α

S(k))=f(x(k)+α(k)S(k))

步骤:①f(X(k)+αS(k))沿S(k)

方向x(k)

台劳展开；②取二次近似：第8页，课件共101页，创作于2023年2月对α求导，令其为零。

2.数值迭代法：直接法——应用序列消去原理：分数法、黄金分割法近似法——利用多项式函数逼近（曲线拟合）原理：

二次插值法、三次插值法④求得最优步长因子：§3.2一维搜索方法第9页，课件共101页，创作于2023年2月二.迭代法求解一维搜索问题的基本思想：

先选定一个初始点x0，从x0出发沿某一选定方向p0求f(x)的极小点，设其为x1；然后再从x1出发沿某一选定方向p1求f(x)的极小点，设其为x2；如此下去，从xk出发沿某一选定方向pk求的极小点xk+1，…

，直到求得的xk满足要求为止。求得的值是逐渐下降的：

称pk为第k次的搜索方向，因此，在过xk的pk方向上，任意一点可以表示为x=xk+t*pk，目标函数值为f(xk+t*pk)，目标函数实际上成了一元函数。所以沿pk方向求f(x)的极小点，就是求一元函数f(xk+t*pk)的极小问题，表示为：总结：将优化问题转化为一系列的一维搜索问题§3.2一维搜索方法第10页，课件共101页，创作于2023年2月沿方向S的一维搜索第11页，课件共101页，创作于2023年2月§3.2一维搜索方法单峰区间解析概念：

在区间[α1，α3]内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点α*，当任意一点α2＞α*时，f(α2)＞f(α*)，说明：单峰区间内，函数可以有不可微点，也可以是不连续函数；三.搜索区间的确定：f(x)0α1α3α0αf(x)α3α1f(α)αα3α2α*α10当α2＜α*时，仍有f(α2)＞f(α*)，则α*是最优点，也即为最优步长因子α(k)。α2确定的搜索区间必定是一个含有最优点α*的单峰区间。第12页，课件共101页，创作于2023年2月§3.2一维搜索方法2。单峰区间几何概念：

指函数在区间内只有一个极小点。在极小点左边的函数值应是严格下降，在极小点右边的函数值应是严格上升，即单峰区间内的函数值具有的特征是：“高—低—高”。进退法确定的单峰区间三.搜索区间的确定：第13页，课件共101页，创作于2023年2月§3.2一维搜索方法3.定步长搜索法:4.加速步长搜索法：f2=f(α1+t0)α1f1第14页，课件共101页，创作于2023年2月解：计算试点例3-1

用进退法求单变量函数的搜索区间。初始点，步长比较两试点函数值，由于作前进搜索比较两试点函数值，由于作前进搜索比较两试点函数值，由于作前进搜索此时，三个试点函数值已经出现“高－低－高”特征，得搜索区间为第15页，课件共101页，创作于2023年2月§3.2一维搜索方法四.黄金分割法(0.618)：1.序列消去原理：f(α)αα3(1)α12α*α1(1)0α3(2)α11α21α22α1(2)α1(3)α3(3)第16页，课件共101页，创作于2023年2月§3.2一维搜索方法黄金分割法消去示例：第17页，课件共101页，创作于2023年2月§3.2一维搜索方法2.黄金分割与0.618：bd

古希腊建筑师认为：边长为b，d的矩形建筑物，若边长能符合以下条件，则最美观：欧几里德几何称这种边长分割为黄金分割。

序列消去法中，为提高效率，减少计算量和存储量，希望第18页，课件共101页，创作于2023年2月黄金分割法的算法框图第19页，课件共101页，创作于2023年2月解：在搜索区间内取两试点并且计算它们函数值

比较两试点函数值，缩短搜索区间，由于，消去右区间，令：例3-2用黄金分割法求单变量函数的极小点。初始搜索区间，迭代精度第20页，课件共101页，创作于2023年2月判断迭代终止条件：

不满足迭代终止条件。再取两试点并且比较它们的函数值，继续缩短搜索区间。搜索区间经过6次缩短（中间迭代过程略）后，区间长度为：可以终止迭代，得到近似极小点和最优解

第21页，课件共101页，创作于2023年2月§3.2一维搜索方法五.二次插值法（抛物线法）：1.基本原理：步骤：第22页，课件共101页，创作于2023年2月§3.2一维搜索方法2.步骤(续)：3.结果分析：问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析）？

②令：第23页，课件共101页，创作于2023年2月单谷搜索区间缩短情况x1x2x3xP*f2fP*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd第24页，课件共101页，创作于2023年2月入口xp*>x2?f2*>fP*?f2<fP*?x3

x2f3

f2x2

xp*f2

fP*x1

x2f1

f2x2

xp*f2

fP*出口YYYNNNabcdx3

xp*f3

fP*x1

xp*f1

fP*二次插值法区间缩短流程图第25页，课件共101页，创作于2023年2月§3.2一维搜索方法

与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。4.方法评价:5.迭代终止条件:当满足如下两个条件，可终止迭代：

如果和两点的距离很小，即：

如果和充分接近，即：第26页，课件共101页，创作于2023年2月二次插值法的算法框图第27页，课件共101页，创作于2023年2月解：1）确定初始插值结点与函数值

2）计算插值函数极小点

例3-3用二次插值法求一维函数的最优解。初始单谷搜索区间，迭代精度第28页，课件共101页，创作于2023年2月

由于判别式成立，表明落在单谷搜索区间之内

3）缩短单谷搜索区间

由于和，则舍弃左边的区间，构成缩短后的新搜索区间。即：第29页，课件共101页，创作于2023年2月4）检验迭代终止条件

满足迭代终止条件，输出最优解

第30页，课件共101页，创作于2023年2月六.切线法：

一维搜索函数，假定已给出较好的近似点，连续可微的函数在极小点附近与一个二次函数很接近，所以可以在附近用一个二次函数来逼近函数：

以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件：§3.2一维搜索方法第31页，课件共101页，创作于2023年2月解：

1)求函数的一阶、二阶导函数：例3-4

给定函数，初始值为，控制误差，试用切线法求其极小点。

2)求

3)求第32页，课件共101页，创作于2023年2月4.000594.000664.039604.334745.1666784.0472086.86992109.44586184.3332240.005513.3829932.30199153.3518-524.000664.039604.334745.16667343210k值

4)迭代值如下：第33页，课件共101页，创作于2023年2月切线法流程图NY开始结束k=k+1给定

k=0第34页，课件共101页，创作于2023年2月１.收敛速度快；２.需要计算函数的一阶和二阶导数，增加迭代工作量；３.要求初始点选得比较好，离极小点不远，否则有可能使极小化序列发散或收敛到非极小点。切线法优缺点:§3.2一维搜索方法第35页，课件共101页，创作于2023年2月§3.2一维搜索方法取具有极小点的单峰函数的探索区间[a,b]的坐标中点作为计算点，计算目标函数在该点处的导数为，并利用函数在极小点处的导数为零而在其左侧为负、右侧为正的原理，来判断极小点所在的那一半探索区间，以消掉另一半区间。这样逐次迭代下去，总能将探索区间收敛到一个局部极小点附近，求得极小点的近似解。收敛速度虽然较慢，但缩短率也达到0.5，特别是每次迭代计算量较少，可靠性较好，所以仍然是一个受欢迎的方法。七.平分法：第36页，课件共101页，创作于2023年2月§3.2一维搜索方法平分法的迭代计算步骤:给定计算，若，则停止迭代并取否则进行下一步。计算，若或，则停止迭代并取若则取为缩短后的搜索区间转第二步若则取为缩短后的搜索区间转第二步当求解困难时:

可直接计算并比较两者大小，用序列消去法原理消去掉近一半的区域，再重新迭代，直到将探索区间缩短至精度要求为止。第37页，课件共101页，创作于2023年2月例3-5

试用平分法求的极小点和极小值，设解：

1)取

2)计算

3)缩短搜索区间为取

4)计算

5)所以函数的极小点为,极小值为:第38页，课件共101页，创作于2023年2月§3.2一维搜索方法设一维函数为f(x)，搜索区间为[a,b]，一维收敛精度为

。在区间[a,b]的内部取n个等分点：x1,x2,…,xn。区间被分为n+1等分，各分点坐标为对应各点的函数值为y1,y2,…,yn+2。比较其大小，取最小者ym=min{yk,k=1,2,…,n＋2}，则在区间[xm-1,xm+1]内必包含极小点，取[xm-1,xm+1]为缩短后新区间，若新区间满足收敛条件:xm+1-xm+1

，则最优解为x*=xm，y*=ym

若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止。八.格点法：第39页，课件共101页，创作于2023年2月

新区间y1ym-1ymym+1Yn＋2x1axm-1xmxm+1Xn＋2b格点法区间搜索原理第40页，课件共101页，创作于2023年2月格点法流程图YN开始p=y,m=ky<p给定

m=0,k=1，p=足够大的数k=nk=k+1|b-a|<εNYYN第41页，课件共101页，创作于2023年2月相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。不同点：试验点位置的确定方法不同。直接法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。黄金分割法是按照等比例0.618缩短率确定的，仅仅利用了试验点函数值进行大小的比较；间接法中，试验点的位置是按函数值近似分布的极小点确定的，利用了函数值本身或其导数信息。当函数具有较好的解析性质时，间接方法比直接方法效果更好。§3.2一维搜索方法九.间接法与直接法的异同点：第42页，课件共101页，创作于2023年2月§3.2一维搜索方法1.掌握进退法确定单谷搜索区间；2.掌握黄金分割法的原理和程序设计；3.掌握二次插值法的原理和程序设计；4.掌握切线法的原理和流程；5.了解平分法和格点法。十.学习要求：试用二次插值法求的近似极小点和极小值，已知十一.习题：第43页，课件共101页，创作于2023年2月一.坐标轮换法：1.基本思想：2.搜索方向与步长：

每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi(k)…n次搜索后获得极值点序列x1(k),x2(k,…,xn(k)，若未收敛，则开始第k+1次迭代，直至收敛到最优点x*。§3.3

坐标轮换法、共轭方向法和Poweel法第44页，课件共101页，创作于2023年2月一.坐标轮换法：3.方法评价：

方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。

受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），在脊线的尖点A处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。§3.3

坐标轮换法、共轭方向法和Poweel法第45页，课件共101页，创作于2023年2月i=n坐标轮换法的流程图

开始给定：x0,

k=1i=1,x0k=x0xik=x0k-1沿ei方向一维搜索求

ixik=xi-1k+

ikeix=xkf=f(x)||xnk-x0k||

x*=x

f*=f(x*)结束i=i+1x0k+1=xnkk=k+1NYNY第46页，课件共101页，创作于2023年2月此问题可用一维优化方法求解，这里用微分学求解：解：1.作第一轮迭代计算得：1)沿e1方向进行一维搜索例4-1

用坐标轮换法求目标函数的无约束最优解，给定初始点，精度要求其中为第一轮的起始点。取：按最优步长原则确定2)以为新起点，沿e2方向一维搜索：按最优步长原则确定得：3)按迭代终止条件检验

2.作第二轮迭代计算，如此共进行9轮得到结果第47页，课件共101页，创作于2023年2月二.共轭方向法：1.共轭方向的由来：2.共轭方向的定义：

共轭方向概念是在研究具有正定矩阵G的二次函数

的极小化问题时形成的。其基本思想是在不用导数的前提下，在迭代中逐次构造G的共轭方向。§3.3

坐标轮换法、共轭方向法和Poweel法第48页，课件共101页，创作于2023年2月3.共轭方向法的二次收敛性：

正定的二元二次函数的等值线为一组椭圆，任选初始点x0，沿某个下降方向S0作一维搜索，得x1

此时，x1点的梯度必然与方向S0垂直，即有：x0x*x1

1S1-f(x1)S1

0S0

S0与某一等值线相切于x1点。下一次的迭代，若选择负梯度方向为搜索方向，将产生锯齿现象。为避免锯齿的产生，我们取迭代方向S0直指极小点x*，如图所示。若选定这样的方向，则对于二元二次函数只需进行S0

和S1两次搜索就可以求得极小点x*，即§3.3

坐标轮换法、共轭方向法和Poweel法第49页，课件共101页，创作于2023年2月3.共轭方向法的二次收敛性（续）：

由于，当时，由是的极小点，应满足极值必要条件，故即：

等式两端同乘以,得，故两个向量，是G的共轭向量。

因此，若要使第二个迭代点成为正定二元二次函数的极小点，只要使两次一维搜索的方向，关于函数的二阶导数矩阵G共轭就可以了。

对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。§3.3

坐标轮换法、共轭方向法和Poweel法第50页，课件共101页，创作于2023年2月4.二维函数的共轭方向：

二维函数，任意给定某个方向，按这个方向上的两条平行线进行一维搜索求得的极小点为和，它们应该是方向为的两条平行线与目标函数等值线的切点。

连接两个切点和构成向量：

可以证明，如果二维函数的海塞矩阵H是正定的，则S1向量与向量S2满足条件：

具有这种性质的方向为关于正定矩阵H的共轭方向。§3.3

坐标轮换法、共轭方向法和Poweel法第51页，课件共101页，创作于2023年2月

所以有：4.二维函数的共轭方向（续）：证明：

设二维函数在极值点X*附近的二次泰勒展开式为：

由此得函数的一阶导数：

由于S1为等值线的切线，故方向S1应垂直于X(1)

,X(2)

的梯度方向：§3.3

坐标轮换法、共轭方向法和Poweel法第52页，课件共101页，创作于2023年2月

所以有：4.二维函数的共轭方向（续2）：

两式相减得：

由，上式可简化为：§3.3

坐标轮换法、共轭方向法和Poweel法第53页，课件共101页，创作于2023年2月5.二维函数共轭方向法的迭代过程：

1.令循环次数k＝1，取初始点，初始搜索方向为坐标方向

4.取下次循环的初始点，替换掉原来的第一方向，构成新的搜索方向：

5.k=k+1，转步骤2。

2.从出发，依次沿和进行一维搜索，分别得到相应的极小点和。

3.构建新方向，沿方向进行搜索，得到第k次的极小点§3.3

坐标轮换法、共轭方向法和Poweel法第54页，课件共101页，创作于2023年2月6.多维二次函数共轭方向的构建：

如果n维函数的海赛矩阵是正定的，一组非零向量满足：

则向量系：是关于海赛矩阵H共轭，即他们是n个互为共轭的方向。

§3.3

坐标轮换法、共轭方向法和Poweel法第55页，课件共101页，创作于2023年2月8.方法评价：

计算步骤复杂;

是二次收敛方法，收敛快。对非正定函数，也很有效;

是比较稳定的方法。7.说明：

若是正定二次函数，n轮迭代后收敛于最优点x*。若是非正定二次函数，则迭代次数增加。

若是n维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(1)(i=1,2,…,n)的n个方向和共轭方向S(1)，搜索n+1次得极值点xn+1(1)

；第二轮迭代，沿方向组Si(2)(i=1,2,…,n；i≠m)的n-1个方向和共轭方向S(1)，构筑共轭方向S(2)搜索n+1次得极值点xn+1(2)

。其中，为保证搜索方向的线性无关，去除了Sm(2)方向。

在第k轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向Sm(k)。——去除的原则请自学。§3.3

坐标轮换法、共轭方向法和Poweel法第56页，课件共101页，创作于2023年2月共轭方向法的程序框图第57页，课件共101页，创作于2023年2月9.共轭方向法的缺陷：

共轭方向法的迭代过程可能会产生不理想的情况，在以后某环的迭代中可能出现基本方向组为线性相关向量系。以后的搜索将在维数下降后的设计空间中进行，无法收敛到n维设计空间中目标函数的极小点。

以三维问题为例，设从初始点出发，沿着坐标轴方向，进行第一环搜索，在各个方向获得极小点为：

由该环搜索的初始点与终点产生的新生方向：§3.3

坐标轮换法、共轭方向法和Poweel法第58页，课件共101页，创作于2023年2月9.共轭方向法的缺陷（续）：

如果其中第三维优化步长等于或非常接近0，即表示沿着则坐标轴方向的搜索没有前进或前进很少，则共轭方向：

表明向量与向量是线性相关的。

第2环搜索的基本方向组中，是与线性相关或接近线性相关，即向量在和组成的平面内。以后的搜索将在维数下降（不包含方向）的平面中进行，无法收敛到空间中目标函数的极小点。§3.3

坐标轮换法、共轭方向法和Poweel法第59页，课件共101页，创作于2023年2月三.Poweel法：1.基本步骤：1.给定初始点，选取由n个线性无关的向量组成的初始方向组，置。2.从出发，顺次沿作一维搜索得。接着以为起点，沿方向：移动一个的距离，得到：

分别称为一轮迭代的始点、终点和反射点。它们所对应的函数值分别为：

同时计算各中间点处的函数值，并记为：§3.3

坐标轮换法、共轭方向法和Poweel法第60页，课件共101页，创作于2023年2月§3.3

坐标轮换法、共轭方向法和Poweel法1.基本步骤（续）：

计算n个函数值之差：3.为了构造第k＋1环基本方向组，采用如下判别式：

按以下两种情况处理：

其中最大者记作：鲍威尔判别式

a.上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组.,k+1的环初始点取:

第61页，课件共101页，创作于2023年2月1.基本步骤（续2）：b.两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为：

k+1环的初始点取，是第k环沿方向搜索的极小点。§3.3

坐标轮换法、共轭方向法和Poweel法第62页，课件共101页，创作于2023年2月鲍威尔法的流程图第63页，课件共101页，创作于2023年2月一.梯度法（最速下降法）：1.基本思想：2.负梯度方向为最速下降方向的证明：

目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向为搜索方向，期望很快找到最优点。S由方向导数概念可得：设：取最小值－1时，S为梯度的负方向。§3.4梯度法和共轭梯度法第64页，课件共101页，创作于2023年2月4.迭代格式：3.搜索方向：a.任意给定一个初始步长，使其满足：根据一元函数的极值必要条件和多元复合函数的求导公式，得：或负梯度方向或单位负梯度向量5.最佳步长的选取：b.沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得到最佳步长：即：§3.4梯度法和共轭梯度法第65页，课件共101页，创作于2023年2月

最速下降法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。

这是因为，梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。5.最佳步长的选取（续）：

此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。6.搜索路径：§3.4梯度法和共轭梯度法第66页，课件共101页，创作于2023年2月（1）任选初始迭代点x(0)，选收敛精度

。（2）确定x(k)点的梯度(开始k=0)。（3）判断是否满足终止条件，若满足输出最优解，结束计算。否则转下步。（4）从x(k)点出发，沿

方向作一维搜索求最优步长

(k)。得下一迭代点。令k=k+1返回步骤（2）。7.迭代终止条件：

采用梯度准则：8.迭代步骤：§3.4梯度法和共轭梯度法第67页，课件共101页，创作于2023年2月梯度法流程图NY开始给定：x(0)，

k=0x*=x(k)f*=f(x(k))结束x(k)=

x(0)k=k+1第68页，课件共101页，创作于2023年2月§3.4梯度法和共轭梯度法9.方法评价：

迭代过程简单，对初始点的选择，要求不高。梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。第69页，课件共101页，创作于2023年2月例4-1

二维无约束目标函数试用梯度法求其极小值，初始点，精度

解：

1）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向第70页，课件共101页，创作于2023年2月2）计算最佳搜索步长3）计算第一次迭代更新值和目标函数值4）当迭代7次时，满足终止条件，得到最有值第71页，课件共101页，创作于2023年2月§3.4梯度法和共轭梯度法二.共轭梯度法（旋转梯度法）：1.基本思想：2.共轭方向：

对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。3.共轭系数：推导过程请自学。β(k)S(k)第72页，课件共101页，创作于2023年2月步骤：

5.方法评价：

迭代程序简单，容易实现，存储量较小。开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛快。§3.4梯度法和共轭梯度法第73页，课件共101页，创作于2023年2月开始k=0，计算：-f(x0)

||f(xk+1)

||

？结束求

(k)

，x(k+1)=

x(k)+

(k)S(k)计算：

f(xk+1)

x*=xk+1f(x*)=f(xk+1)YN给定：x(0)，

kn？x0=xk+1YNSk+1=-f(xk+1)

+

kSkK=K+1共轭梯度法流程图第74页，课件共101页，创作于2023年2月例4-2

二维无约束目标函数试用共轭梯度法求其极小值，初始点，精度

解：

1）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向第75页，课件共101页，创作于2023年2月2）计算新迭代点的梯度和搜索方向的修正量，进行第2次搜索

第76页，课件共101页，创作于2023年2月可见，共轭梯度法具有两次收敛性，对于二维函数只要经过两次迭代就可以达到极值点。

第77页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法一.牛顿法（二阶梯度法）：

1.基本思想：

将f(x)在x(k)

点作台劳展开，取二次函数式Φ(x)作为近似函数,以Φ(x)的极小值点作为f(x)的近似极小值点。说明：

f(x)若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。第78页，课件共101页，创作于2023年2月2.修正牛顿法（阻尼牛顿法）：一.牛顿法（二阶梯度法）：

可通过如下极小化过程求得：

避免了迭代后函数上升的现象，保持了牛顿法二次收敛的特性，对初始点的选取并没有苛刻的要求。阻尼牛顿法的计算步骤：1）给定初始点，收敛精度，置§3.5

牛顿法和变尺度法第79页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法3.方法评价：

使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。若初始点选得合适，牛顿法的收敛速度相当快。牛顿法求逆矩阵的工作量大，计算量与存储量均随n2上升。3）求，其中为沿进行一维搜索的最佳步长4）检查收敛精度。若，则，否则，令，返回2）继续进行搜索。2）计算：第80页，课件共101页，创作于2023年2月阻尼牛顿法流程图第81页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法

变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。

梯度法只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。DFP变尺度法是由Davidon于1959年提出的一种变尺度法；BFGS变尺度法是由Broydon等提出的改进算法，提高了算法的稳定性。

牛顿法不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。

若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的构想。一.变尺度法:第82页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法二.DFP变尺度法:1.变尺度的定义：每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。2.基本思想：

发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。第83页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法3.变尺度矩阵的构造：原则：

使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）；使算法有二次收敛性，则S(k)(k=1,2,…)应关于H(k)

是共轭的；构造变尺度矩阵的递推公式：4.修正矩阵:

第84页，课件共101页，创作于2023年2月§3.5

牛顿法和变尺度法步骤：1、选定初始点和收敛精度；2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0；3、计算搜索方向Sk=

-Akgk

；4、沿Sk方向一维搜索，计算gk+1、sk=xk+1-xk、yk=gk+1-gk。5、判断是否满足终止准则，若满足输出最优解，否则转6。6、当迭代n次还未找到极小点，重置Ak为单位矩阵，并以当前点为初始点返回2，否则转7。7、计算Ak+1=Ak+ΔAk，置k=k+1返回3。第85页，课件共101页，创作于2023年2月6.方法评价：

DFP变尺度法以逐次逼近的方法实现H-1

的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。算法的第一步是梯度法，最速下降；接近x*时，又采用二次收敛的共轭方向，总的收敛速度较快。

H(k)

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

H(k)

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

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

§3.5

牛顿法和变尺度法第86页，课件共101页，创作于2023年2月DFP变尺度法流程图第87页，课件共101页，创作于2023年2月例4-3

二维无约束目标函数试用DFP算法求其极小值。解：

1）取初始点，为了按DFP法构造第一次搜索方向，需要计算初始点处的梯度：并取初始变尺度矩阵为单位矩阵A0=I，则第一次搜索方向为：沿方向进行一维搜索，得：其中，为一维搜索最佳步长，应满足：第88页，课件共101页，创作于2023年2月2）再按DFP法构造点处的搜索方向，需要计算：得：代入DFP校正公式，得：第89页，课件共101页，创作于2023年2月

得：则第二次搜索方向为：其中，为一维搜索最佳步长，应满足：沿d1进行一维搜索：第90页，课件共101页，创作于2023年2月3)为了判断x2点是否为极值点，需计算x2点处的梯度及其海赛矩阵：

梯度为零向量，海赛矩阵为正定矩阵，可见x2点满足极值充分必要条件，因此x2为极小点。函数的极值解为：第91页，课件共101页，创作于2023年2月DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，其校正公式为：

因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度法的算法，1970年黄（huang）从共轭条件出发对变尺度法做了统一处理，写出了统一公式：一.BFGS变尺度法:

可以看出，当取，就是DFP法的公式。当取，就是BFGS法的公式§3.5

牛顿法和变尺度法第92页，课件共101页，创作于2023年2月§3.6

单形替换法一.单形替换法基本思想:单纯形：在一定的空间中的最简单的图形，如三角形，四面体等。

先算出n维空间n+1个