无约束非线性规划

关于无约束非线性规划第1页，课件共139页，创作于2023年2月2.1非线性函数和非线性规划的概念线性函数:(1)f(kx)=kf(x)(2)f(x1+x2)=f(x1)+f(x2)则非线性函数就是不满足以上两个条件的函数．非线性规划：如果目标函数或约束条件中，有一个或多个是变量的非线性函数，就称为非线性规划．第2页，课件共139页，创作于2023年2月非线性规划问题例1

曲线的最优拟合问题第3页，课件共139页，创作于2023年2月例2构件容积问题第4页，课件共139页，创作于2023年2月非线性规划问题例3第5页，课件共139页，创作于2023年2月非线性规划问题例3第6页，课件共139页，创作于2023年2月非线性规划通常情况下，目标函数f(x)和约束条件hi(X)和gi(X)为自变量Ｘ的非线性函数第7页，课件共139页，创作于2023年2月非线性规划ULP的可行解或可行点约束集或可行域第8页，课件共139页，创作于2023年2月向量化表示当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。第9页，课件共139页，创作于2023年2月最优解和极小点第10页，课件共139页，创作于2023年2月最优解和极小点第11页，课件共139页，创作于2023年2月极值存在的条件１必要条件：设Ｒ是n维欧氏空间的某一区域，f(X)为定义在Ｒ上的实值函数，Ｘ＊是区域Ｒ的内点，若f(Ｘ）在Ｘ＊处可微，且在该点取得局部极小值，则必有或第12页，课件共139页，创作于2023年2月极值存在的条件其中，为函数f(x)在Ｘ＊处的梯度，梯度的方向为f(X)的等值面（等值线）的法线方向，沿这个方向函数值增加最快．满足上式的点称为驻点，在区域内部，极值点必为驻点；但驻点不一定是极值点．第13页，课件共139页，创作于2023年2月14二次型二次型是X=(x1,x2,…,xn)T的二次齐次函数：aij=aji,A为n*n对称矩阵。若A的所有元素均为实数，则为实二次型。一个二次型唯一对应一个对称矩阵，反之，一个对称矩阵也唯一确定一个二次型。二次型（对称矩阵）正定，负定，不定。半正定，半负定。第14页，课件共139页，创作于2023年2月15二次型二次型正定的充要条件，是它的矩阵的左上角各阶主子式都大于零。二次型负定的充要条件，是它的矩阵的左上角各阶主子式都负、正相间。例：判定正负性。第15页，课件共139页，创作于2023年2月极值存在的条件２充分条件：设Ｒ是n维欧氏空间的某一区域，f(X)为定义在Ｒ上的实值函数，Ｘ＊是区域Ｒ的内点，f(Ｘ）在Ｒ上二次连续可微，若f(Ｘ）在Ｘ＊且处满足（5．１）或（5．２）式，且对任何非零矢量均有则f(x)在Ｘ取严格局部极小值，此处Ｈ（x*)为f(x)在点Ｘ＊处的海赛（Hesse)矩阵．第16页，课件共139页，创作于2023年2月极值存在的条件此处Ｈ（x*)为f(x)在点Ｘ＊处的海赛（Hesse)矩阵．第17页，课件共139页，创作于2023年2月极值存在的条件例１求目标函数的梯度和Hesse矩阵解:因为,所以第18页，课件共139页，创作于2023年2月极值存在的条件又因为所以即为Hesse矩阵第19页，课件共139页，创作于2023年2月极值存在的条件例2试研究函数f(x1,x2)=x22-x1２的驻点．解：令得（０，０）点为驻点，x1=0是一无函数f(x1,0)=-x12的极大点，而x2=0却是一元函数f(0,x2)=x22的极小点，即：故驻点（０，０）不是极值点，而是一个鞍点第20页，课件共139页，创作于2023年2月极值存在的条件例3试求函数f(x1,x2)=2x12-8x1+2x2２-4x2+20的极值和极值点．解：令得（2,1）点为驻点第21页，课件共139页，创作于2023年2月极值存在的条件其海赛矩阵之行列式可知（2,1）点为极小点,其极小值为:第22页，课件共139页，创作于2023年2月凸函数和凸规划凸函数及其性质凸规划及其性质第23页，课件共139页，创作于2023年2月凸函数及其性质第24页，课件共139页，创作于2023年2月凸函数的性质第25页，课件共139页，创作于2023年2月凸函数的判定第26页，课件共139页，创作于2023年2月第27页，课件共139页，创作于2023年2月凸函数的判定例4判定下述函数是凸函数还是凹函数解:因为其海赛阵的行列式为：故其海赛阵处处正定，由定理2.2.4得f(X)为严格凸函数第28页，课件共139页，创作于2023年2月凸函数的判定例5试证明为凹函数证:(1)首先由定义来证明，任取两点a1,a2,看下式是否成立？或由于，故．显然，不管a1,a2取什么值，总有（３）式成立，故f(x1)=-x12为凹函数，同理可证f(x2)=-x22也是凹函数．或第29页，课件共139页，创作于2023年2月凸函数的判定证:(２)用定理2.2.4来证明，由于故海赛矩阵处处负定，故f(X)为严格凹函数．第30页，课件共139页，创作于2023年2月凸函数的判定证:(３)用定理5.2.3来证明，任意取第一点，第二点，这样现看下式是否成立或或证:(３)用定理2.2.3来证明，任意取第一点，第二点，这样第31页，课件共139页，创作于2023年2月凸函数的判定不管a1,a2和b1,b2取什么值，上式均成立从而证明f(Ｘ）是凹函数．或第32页，课件共139页，创作于2023年2月凸规划及其性质约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。第33页，课件共139页，创作于2023年2月定理2.2.6

凸规划的任一局部最优解都是它的整体最优解。第34页，课件共139页，创作于2023年2月凸规划及其性质由于线性函数也既是凸函数，又是凹函数，故线性规划也属于凸规划．第35页，课件共139页，创作于2023年2月凸规划及其性质例6试分析非线性规划解：f(X)和g2(X)的海赛矩阵的行列式是第36页，课件共139页，创作于2023年2月凸规划及其性质由上可知f(X)为严格凸函数,g2(x)为凹函数，由于为线性函数，故上述约束条件构成的可行域为凸集，这是一个凸规划，Ｃ点为最优点：Ｘ＊＝（0.58,1.34)T,目标函数的最优值为f(X*)=3.8.２g1(X)g2(X)=0C目标函数等值线第37页，课件共139页，创作于2023年2月算法及有关概念最优化问题的数值解法及理论根据：1在集合Ｘ上的迭代算法是指：开始：选定一个初始点,置k=0,然后再按某种规则Ａ把k次迭代的x(k)映射为新的一点x(k+1),记为．这称为第k+1次迭代．这个过程无限进行下去，就产生一个点列，其中规则Ａ称为算法．若收敛于问题的最优解，就称算法Ａ在Ｘ上是收敛的，否则是发散的．第38页，课件共139页，创作于2023年2月算法及有关概念一种算法除了满足计算终止准则的迭代点外,还应满足:下降算法:若对于每个k,都有,则称A为下降迭代算法,简称下降算法.许多最优化方法都采用将多维问题转化为一维问题的方法来求解.第39页，课件共139页，创作于2023年2月算法及有关概念如:设第k次迭代点xk已求得,若它不满足终止准则,在该点必存在下降方向.对于可微目标函数,即是满足的d.

按某种规则从中选取一个,例如dk,再沿这个方向适当迈进一步,即在直线上适当确定一个新点,

使那我们就说完成了第k+1次迭代,其中称为步长因子.第40页，课件共139页，创作于2023年2月算法及有关概念迭代过程中应满足两个准则:1是下降方向dk的选取;2是步长因子

的选取各种迭代法的区别就在于得出方向dk与步长的方式不同.对于非线性规划,总结出:第41页，课件共139页，创作于2023年2月非线性规划方法概述第42页，课件共139页，创作于2023年2月非线性规划基本迭代格式第43页，课件共139页，创作于2023年2月无约束优化:最优解的分类和条件给定一个函数f(x),寻找x*使得f(x*)最小，即其中局部最优解全局最优解必要条件x*f(x)xlxgo充分条件Hessian阵最优解在可行域边界上取得时不能用无约束优化方法求解第44页，课件共139页，创作于2023年2月2迭代法中直线搜索及其性质：在搜索方向已经确定的前提下,步长因子的选取有多种方法,如

i)取步长因子为某个常数,但不能保证使目标函数值下降;ii)可接受点算法，只要能使目标函数下降，可任意选取步长;

iii)基于沿搜索方向使目标函数值下降最多，沿射线求目标函数的极小值：第45页，课件共139页，创作于2023年2月2迭代法中直线搜索及其性质：

由于这项工作是求以为变量的一元函数的极小点，故称这一过程为一维搜索（线搜索），这样确定的步长为最佳步长,实际计算中常用此方法.

一维搜索有个性质：在搜索方向上所得最优点处的梯度和搜索方向正交．定理：设目标函数f(X)具有一阶连续偏导数，x(k+1)按下列规划产生：则有第46页，课件共139页，创作于2023年2月3收敛速度

一个算法不光能收敛于解,还必须以较快的速度收敛于解,这才是好的算法;

我们用以下收敛的阶来度量一个算法的收敛速度.第47页，课件共139页，创作于2023年2月3收敛速度

定义:设序列收敛于,而且若,则称为线性收敛的,为收敛比;

若,则称为超线性收敛.

定义:设序列收敛于,若对于某个实数,有

则称序列为阶收敛的第48页，课件共139页，创作于2023年2月3收敛速度

一般来说,线性收敛是比较慢的,而二阶收敛则是很快的,超线性收敛居中,如果一个算法具有超线性以上的收敛速度,我们就认为它是一个很好的算法了.第49页，课件共139页，创作于2023年2月50因真正的极值点事先并不知道，故在实用上只能根据相继两次迭代得到的计算结果来判断是否已达到要求，从而建立终止迭代计算的准则。常用的终止迭代准则有：（1）根据相继两次迭代结果的绝对误差。4.终止迭代准则（2）根据相继两次迭代结果的相对误差。（3）根据函数梯度的模足够小。迭代终止准则①点距准则②函数值下降准则③梯度准则第50页，课件共139页，创作于2023年2月2.2一维搜索方法精确一维搜索方法

0.618法

Newton法非精确一维搜索方法

Goldstein法

Armijo法第51页，课件共139页，创作于2023年2月一维搜索

上节提到,在大多数无约束极值的算法中,为了确定最优解,一般用解析的方法是很难得到的,即精确解通常是计算不出来的,故我们常采用的是数值的方法来得到其近似解,上节我们提到,数值解法最常用的一种方法是迭代法.

为了确定极小化点列,要沿逐次确定的系列射线求极小点,即所谓的一维搜索.

一维搜索可归结为单变量函数求极小的问题,设目标函数为,过点沿方向的直线可用点集表示为:

第52页，课件共139页，创作于2023年2月求在直线L上的极小点转化为求一元函数

的极小点.

如果的极小点为,通常称为沿方向的步长因子或简称步长.函数在直线上的极小点就是

一维搜索的方法一般有以下几类：

1.数学分析中所讲的方法，即解方程，此方法称为精确线性搜索.2.试探法:

按照某种方式试探点,通过一系列试探点的比较确定极小点.第53页，课件共139页，创作于2023年2月

3.函数逼近法:

用比较简单的曲线近似代替原来的曲线,用近似曲线的极小点来估计原来的极小点.

下面我们将分别具体介绍几种方法:

一.平分法根据以前我们所学习的知识,我们知道，在的极小点处有,并且当时,函数是递减的,即;而当时,函数递增,即.

注:因为为极小点,若:

此时为极大点.第54页，课件共139页，创作于2023年2月

我们找到了一个区间,具有性质则在间必然有的极小点,且.为了找到,

我们取.1.若,则在中有极小点,

2.若,则在中有极小点.y=f(x)00xy第55页，课件共139页，创作于2023年2月若情形1满足时,此时以作为新的区间;

若情形2满足时,此时以作为新的区间.

继续上述过程,逐步将区间换小,当区间充分小时,或者当充分小时,即可将区间中点取做极小点的近似,此时有:0xy0xy第56页，课件共139页，创作于2023年2月注:也可以用以下的收敛准则:1.成立,

2.成立.

但是我们如何来确定初始区间呢?下面我们将解决这个问题。

第57页，课件共139页，创作于2023年2月搜索区间的选取可采用如下的进—退算法：给定初始点，初始步长，求搜索区间：1）计算2）若,(此时称搜索成功，下一步搜索就大步前进)，则步长加倍，计算若，则；否则步长再加倍，并重复上面的运算；第58页，课件共139页，创作于2023年2月3）若,(此时称搜索失败，下一步就小步后退),则步长缩为原来的1/4，并改变符号，即新步长为，若

则；否则步长再加倍，继续后退。第59页，课件共139页，创作于2023年2月二、0.618法（近似黄金分割法）单谷函数退出前一页后一页第60页，课件共139页，创作于2023年2月搜索法求解：或基本过程：给出[a,b],使得t*在[a,b]中。[a,b]称为搜索区间。迭代缩短[a,b]的长度。当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。退出前一页后一页第61页，课件共139页，创作于2023年2月假定：已经确定了单谷区间[a,b]t1t2ababt1t2新搜索区间为[a,t2]新搜索区间为[t1,b]退出前一页后一页第62页，课件共139页，创作于2023年2月区间缩小比例的确定：区间缩短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a)缩短比例满足：每次插入搜索点使得两个区间[a,t2]和[t1,b]相等；每次迭代都以相等的比例缩小区间。0.618法t1t2ababt1t2退出前一页后一页第63页，课件共139页，创作于2023年2月确定[a,b],计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：是否是停止，输出t1否以[a,t2]为新的搜索区间是停止，输出t2否以[t1,b]为新的搜索区间退出前一页后一页第64页，课件共139页，创作于2023年2月例：解：t1t230t1、第一轮：t1=1.146,t2=1.854t2－0>0.5退出前一页后一页第65页，课件共139页，创作于2023年2月2、第二轮：t2=1.146,t1=0.708t2－0=1.146>0.53、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.4160tt2t1退出前一页后一页第66页，课件共139页，创作于2023年2月4、第四轮：t2=0.876,t1=0.708b-t1=1.146-0.708<0.5输出：t*=t2=0.876为最优解，最优值为-0.079801.416tt1t2退出前一页后一页第67页，课件共139页，创作于2023年2月68例求解f(x)=-18x2+72x+28的极大值点，≤0.1，起始搜索区间为[0,3]解：①用间接法：令f’(x)=-36x+72=0，得驻点x=2

又因为f’’(x)=-36＜0，故x=2为f(x)的极大值点，fmax=100②用直接法中的黄金分割法：令n-1=，得n=1+(lg)/(lg)≈5.78442

约6步即可，计算结果见下表：kakbkf(ak)f(bk)pk=

bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.0903第68页，课件共139页，创作于2023年2月第69页，课件共139页，创作于2023年2月第70页，课件共139页，创作于2023年2月第71页，课件共139页，创作于2023年2月第72页，课件共139页，创作于2023年2月三、Newton法Newton法基本思想：用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。退出前一页后一页第73页，课件共139页，创作于2023年2月解题步骤：给定初始点t1和精度是是停止，输出t1是否停止，解题失败否停止，输出t2否退出前一页后一页第74页，课件共139页，创作于2023年2月例：解：取t1=1,计算：迭代过程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退出前一页后一页第75页，课件共139页，创作于2023年2月第76页，课件共139页，创作于2023年2月3、非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。这样的搜索方法称之为非精确一维搜索方法退出前一页后一页第77页，课件共139页，创作于2023年2月Goldstein法原理：yt0bcdaY=(0)+´(0)tY=(0)+m2´(0)tY=(0)+m1´(0)t退出前一页后一页第78页，课件共139页，创作于2023年2月是Goldstein算法确定m1,m2,α,t0,a=0,b=+∞(t0)≤(0)+m1’(0)t0(t0)≥(0)+m2’(0)t0是停止,输出t0否a=a,b=t0,t1=(a+b)/2否a=t0,b=b,t1=(a+b)/2(若b=+∞,则t1=αa)退出前一页后一页第79页，课件共139页，创作于2023年2月Goldstein法步骤第80页，课件共139页，创作于2023年2月Armijo法第81页，课件共139页，创作于2023年2月82无约束条件下多变量函数寻优一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：①选定搜索方向；②在选定的方向上爬山搜索。二、变量轮换法(或降维法):选择与坐标轴平行的方向为搜索方向设S=f(X)=f(x1,x2,…,xn)，极值点存在的区间为

x1*[a1,b1]，x2*[a2,b2]，…

，xn*[an,bn]1、原理：①从起点X(0)出发，沿平行于x1

轴的方向P(1)进行一维搜索，求得f(X)在该方向P(1)上近似极值点X(1)；②从点X(1)出发，沿平行于x2

轴的方向P(2)进行一维搜索，求得f(X)在该方向P(2)上近似极值点X(2)；③从点X(2)出发，照此交替进行下去，直至满足给定的精度为止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

第82页，课件共139页，创作于2023年2月83

2、算法步骤：设S=f(X)=f(x1,x2)，极值点存在的区间为x1*[a1,b1]，x2*[a2,b2]

第一步：从X(0)=(x1(0),x2(0))T出发①先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得X(1)=(x1(0),x2(1))T

，S(1)=f(X(1))②再固定x2=x2(1):求以x1为单变量的目标函数的极值点，得X(2)=(x1(2),x2(1))T

，S(2)=f(X(2))

此时S(2)优于S(1)，且搜索区间缩短为x1*[x1(2),b1]，x2*[x2(1),b2]

第二步：如此交替搜索，直至满足给定精度为止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜ox1X(0)X(1)X(2)X(3)X(4)x2第83页，课件共139页，创作于2023年2月84例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.01解：设起始点X(0)=(0,0)T，用变量轮换法计算：①先固定x1=x1(0)=0:则f(0,x2)=x22-4x2+60，寻优得x2(1)=2

于是X(1)=(x1(0),x2(1))T=(0,2)T

，S(1)=f(X(1))=56②再固定x2=x2(1)=2:则f(x1,2)=x12-12x1+56，寻优得x1(2)=6

于是X(2)=(x1(2),x2(1))T=(6,2)T

，S(2)=f(X(2))=20

如此交替搜索，直至满足给定精度=0.01为止

|f(X(k))

-f(X(k-1))|＜0.01或

|S(k)-S(k-1)|＜0.01

最后得极小点X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2计算结果见下表：第84页，课件共139页，创作于2023年2月85k固定的xi单变量的目标函数f(xj)求得极点xj目标值S(k)|S(k)-S(k-1)|12345678x1=x1(0)=0x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10x2+36f(x1,5)=x12-15x1+65f(7.5,x2)=x22–11.5x2+41.25f(x1,5.75)=x12–15.75x1+70.06f(7.88,x2)=x22–11.88x2+43.27f(x1,5.94)=x12–15.94x1+71.50x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088ox1X(0)X(1)X(2)X(3)X(4)x2缺点：①很大程度上取决于目标函数性质。目标函数等高线的性质很重要。②道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。第85页，课件共139页，创作于2023年2月最速下降法第86页，课件共139页，创作于2023年2月是X(k)处函数值下降最快的方向。当时，p(k)是f(X)在X(k)处的下降方向。函数f(X)在X(k)处的负梯度方向梯度的性质：1、迭代原理证明：结论：一元函数泰勒公式：第87页，课件共139页，创作于2023年2月2.迭代原理最优步长第88页，课件共139页，创作于2023年2月最速下降法迭代原理：一维搜索找极小点：1)确定[0,1],精度0.12)用0.618法得到

040.53184第89页，课件共139页，创作于2023年2月最速下降法迭代原理：

第90页，课件共139页，创作于2023年2月线性规划3-42.迭代原理最优步长最优步长第91页，课件共139页，创作于2023年2月线性收敛2.迭代原理最优步长最优步长得到一个点列：可以证明：第92页，课件共139页，创作于2023年2月2.迭代原理证明：第93页，课件共139页，创作于2023年2月3.迭代步骤第94页，课件共139页，创作于2023年2月3.迭代步骤注释：(一阶必要条件)10停机准则：设连续(即f(X)连续可微)第95页，课件共139页，创作于2023年2月注释：3.迭代步骤一维搜索最优解的梯度与搜索方向正交20结论：证明：第96页，课件共139页，创作于2023年2月注释：最速下降法的任何两个相邻搜索方向正交(垂直)3.迭代步骤30结论：第97页，课件共139页，创作于2023年2月注释：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：第98页，课件共139页，创作于2023年2月线性规划3-4证明：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：注释：该公式具有普遍性第99页，课件共139页，创作于2023年2月注释：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：第100页，课件共139页，创作于2023年2月注释：3.迭代步骤50将最速下降法用于正定二次函数：则可以得到的表达式：第101页，课件共139页，创作于2023年2月注释：3.迭代步骤50最速下降法，Newton法，拟Newton法，共轭梯度法的区别就是搜索方向p(k)取得不同。第102页，课件共139页，创作于2023年2月4.举例例3-10解：用最速下降法求的极小点，迭代两次。第103页，课件共139页，创作于2023年2月例:试用最速下降法求的极小点,迭代两次,计算每个迭代点的函数值,梯度及模,并验证相邻两个搜索方向是正交的.

解:给初始点,,,,,

利用必要条件：第104页，课件共139页，创作于2023年2月于是：由解得

第105页，课件共139页，创作于2023年2月验证搜索方向的正交性:第106页，课件共139页，创作于2023年2月107例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.1解:①②从点X(1)出发，照此进行下去，直至满足给定的精度=0.1为止|f(X(k+1))

-f(X(k))|＜0.1或||G(k)||＜0.1

第107页，课件共139页，创作于2023年2月108计算结果见下表：缺点：①搜索效果比变量轮换法快，但愈接近极值点，步长愈小，目标值改进愈小。当遇到强交互作用时，不是有效的方法;当遇到山脊时，会慢慢爬行。②在远离极点时，收敛速度较快;在极点附近，收敛速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600.890.240.13-0.930.37-0.930.37-0.930.37-0.37-0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026ox1x(0)x(1)x(2)X(3)x2第108页，课件共139页，创作于2023年2月第109页，课件共139页，创作于2023年2月110四、共轭梯度法:选择共轭方向为搜索方向㈠问题的提出：在极值点附近，如何加快收敛速度，须对函数在极值点附近的性质进行研究。

设有n维目标函数S=f(X)=f(x1,x2,…,xn),在极值点X*附近展开成泰勒级数：

特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同心椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。

ox1X(0)P(0)X’(0)X(2)X(1)x2P’(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故：在极值点附近，沿搜索方向P(0)上巳得到一个切点X(1)，则只要得出通过极值点的连线方向P(1),在此方向上寻优,可一步直达极值点。而这个连线方向P(1)是上一次搜索方向P(0)的共轭方向。第110页，课件共139页，创作于2023年2月111㈡共轭方向的定义：1、定义：设X,Y是n维向量空间En中两个向量，A为n×n对称正定矩阵，若XTAY=0，则称向量X与Y对于矩阵A共轭。特例：若A=I，得XTY=0，则称向量X与Y正交。2、几何意义：共轭方向是通过极值点的方向。㈢寻优原理：设n元函数S=f(X)=f(x1,x2,…,xn),在极值点X*附近可用一个二次函数逼近其中H为n×n对称正定矩阵第111页，课件共139页，创作于2023年2月112特别：对二元二次函数S=f(X)=f(x1，x2)①从某点X(0)出发,以P(0)方向搜索,使f(X)达到极小值点X(1),则:X(1)必为该点处等高线的切点,P(0)为切线方向，且点X(1)的梯度方向f(X(1))为该等高线的法线方向，这两个方向正交。②从另一点X’(0)出发,仍以P(0)方向搜索,使f(X)达到另一个极小值点X(2),则:X(2)也必为该点处等高线的切点,P(0)为切线方向，且点X(2)的梯度方向f(X(2))为该等高线的法线方向，这两个方向正交。ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故:对二元二次函数,只须搜索两个方向P(0)和P(1)就可达到极值点X*。一般:对n元二次函数,可用不超过n次搜索就可达到极值点X*。而n元非二次函数在极值点附近可用二次函数逼近。第112页，课件共139页，创作于2023年2月113㈤适用于一般目标函数的共轭梯度法：1、共轭方向的计算问题：须用到目标函数的海赛矩阵H(二阶偏导数矩阵)，若目标函数为二次函数时，H容易求出；若目标函数为高次或高维函数时，H难以求出，此时共轭方向难以求出。2、共轭方向的计算方法：F-R法，由Fletcher和Reeves提出，可避免海赛矩阵H的计算，方便地确定共轭方向，简单有效。第113页，课件共139页，创作于2023年2月114

3、搜索过程：①从X(0)出发：②从X(1)出发：第114页，课件共139页，创作于2023年2月115③从X(2)出发：4、搜索方法:①若目标函数为n元二次函数，则理论上最多经n次迭代可达极小点，实际由于舍入误差，须n次以上的迭代。②若目标函数为n元非二次函数，但共轭方向只有n个，迭代n次以后应重新开始迭代，减少误差积累。一般，在开始阶段(二次型较弱)用一阶梯度法，接近极点(二次型较强)用共轭梯度法。一般有：第115页，课件共139页，创作于2023年2月第116页，课件共139页，创作于2023年2月117例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点。解:①②第117页，课件共139页，创作于2023年2月例2

用共轭梯度法求解,取解:用共轭梯度法的第一步和最速下降法是相同的,

故由前例知:

第118页，课件共139页，创作于2023年2月因为较大,还需要迭代,下一探索方向由共轭梯度并利用和组合而成.

其中

所以由

第119页，课件共139页，创作于2023年2月由：把分别代入的表达式中求得,因为,所以迭代终止,就是所求的极小点.第120页，课件共139页，创作于2023年2月共轭梯度法的特点:对于二次函数的情形,从理论上说,进行n次迭代即可达到极小点,但是,在实际计算中,由于数据的舍入以及计算误差积累,往往做不到这一点.由于n维问题的共轭方向最多只有个,在步之后继续如上进行就没有意义.因此,实际计算中如迭代n步还不收敛,就将X(n)作为新的始点,重新开始迭代,这样一般都可得到较好的效果.第121页，课件共139页，创作于2023年2月浙江理工大学经济管理学院1222.4牛顿法与拟牛顿法⑴牛顿方向四、牛顿法第122页，课件共139页，创作于2023年2月浙江理工大学经济管理学院123四、牛顿法（1）牛顿方向第123页，课件共139页，创作于2023年2月浙江理工大学经济管理学院1242.3无约束极值问题四、牛顿法（2）广义牛顿法步骤当一维搜索是精确的，牛顿法为二阶收敛。第124页，课件共139页，创作于2023年2月浙江理工大学经济管理学院1252.3无约束极值问题四、牛顿法（3）牛顿法优缺点优点：收敛速度快。缺点：有时进行不下去而需采取改进措施；当维数较高时，计算塞黑矩阵的逆工作量太大。可采用其他方法，如共轭梯度法，变尺度法等。第125页，课件共139页，创作于2023年2月

定理5.3：设,且正定,记是由修改的牛顿法所得到的迭代点列,若水平集有界,则必有聚点,且任一聚点必满足.

牛顿法的特征:1.牛顿法应用于具有正定阵的二次函数时,只要一次迭代就可以达到无约束优化问题的最优解,即算法具有二次收敛性.2.当初始点接近极小点时,牛顿法产生的序列以二阶收敛速度趋于问题的平稳点,但当初始点与极小点较远时,阵可能是奇异的，牛顿方向不存在,或者阵不正定,

不再是下降方向,此时需要使用改进的牛顿法,其收敛速度极大降低,因此,应该尽可能选取离极小点较远的初始点.3.牛顿法对目标函数要求高(二阶连续可微)且需要较多存储单元,

每次迭代要进行矩阵求逆运算.第126页，课件共139页，创作于2023年2月

二.拟牛顿法(变尺度法)

修改的牛顿法具有全局收敛性和收敛快的特点,但还存在一个

缺点,即在每步确定搜索方向时,要计算阵及其逆矩阵,这个计算工作最大.于是又有一种设想,将确定搜索方向公式中的用n阶矩阵代替,从而在第k次迭代时

由线性搜索得到，其中和初始矩阵是预先给定的,

在迭代中,利用一阶导数按某中规则得到.第127页，课件共139页，创作于2023年2月

确定的一种自然想法是将作为的近似来构造,注意到是对称的,且有关系即若记=,,,必须满足:1.对称正定

2.满足拟牛顿方程

(2.30)

另外,再设想是由经过简单修正而得到的,即校正矩阵自然应是对称矩阵,由(2.30)式应满足第128页，课件共139页，创作于2023年2月

(2.31)

满足(2.31)的对称矩阵有无穷多个,因此,拟牛顿算法是一族算法,

其最常见的算法所谓DFP是由提出,后经