欢迎来到天天文库
浏览记录
ID:1132188
大小:660.50 KB
页数:97页
时间:2017-11-07
《5无约束非线性规划2》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、非线性规划南京航空航天大学经济与管理学院党耀国教授、博士生导师管理科学与工程系主任iamdangyg@163.com无约束极值问题现在我们来研究n元函数的无约束极值问题。这种问题的表达式为:Minf(X)XE(n)(1)为求此问题的最优解或近似最优解,常使用搜索法,并要进行若干次迭代。当用迭代法求解问题(1)时,常从某一近似点X(k)出发,接着在这一点选定一搜索方向P(k),使目标函数值沿该方向下降,然后选择步长,沿P(k)方向移动一个步长,即可得下一个近似点X(k+1)X(k+1)=X(k)+P(k)且满足f(X(k+1))2、极小点,当满足精度条件3、4、f(X(k+1))5、6、2<1,7、f(X(k+1))-f(X(k))8、<2时,停止迭代。在求解无约束极值问题时常用迭代法,迭代法大致上可分为两大类。一类要用到函数的一阶导数或二阶导数,由于用到了函数的解析性质,故称为解析法。另一类迭代过程中仅用到函数值,而不要求函数的解析性质,这种方法称为直接法。一般来说,直接迭代法的收敛速度较慢,只是在变量个数较少时才适用。但直接法的迭代步骤简单,特别是目标函数的解析式十分复杂时,或写不出具体表达式时,这时求导就很困难,或导数不存在,这时只有利用直接法,下面介绍几种常用的基本方法。该方法是1849、7年柯西提出的,它是求解无约束极值问题的解析法中最古老但又十分基本的一种方法,它的迭代过程简单,使用方便,对初始点的选取要求不严。假设无约束极值问题中的目标函数f(x)有一阶连续偏导数,且有极小点x*。我们取一初始近似点x(0)和一方向g(0),作射线x=x(0)+0g(0)0>0这里的方向g(0)和步长0都是待定的。一、梯度法(最速下降法)为了使f(x)的函数值在x(0)沿方向g(0)移动步长0后有所下降,我们将f(x)在x(0)上展开泰勒级数f(x(0)+0g(0))=f(x(0))+0f(x(0))Tg(0)+o(0)只要0f(x(010、))Tg(0)<0,就可以保证f(x(0)+0g(0))11、12、f(x(0))T13、14、.15、16、g(0)17、18、cos,是向量f(x(0))T与g(0)的夹角。只有f(x(0))T与g(0)反向时,f(x(0))Tg(0)最小即:g(0)=-f(x(0))由此可以看出,函数在处沿梯度的反方向是函数值下降最快的方向。由于优化设计是追求目标函数值最小,因此,自然19、可以设想从某点出发,其搜索方向取该点的负梯度方向,使函数值在该点附近下降最快。这种方法也称为最速下降法。1、基本原理梯度法的迭代公式为:x(k+1)=x(k)-(k)g(k)其中g(k)是函数f(x)在迭代点x(k)处的梯度f(xk),(k)一般采用一维搜索的最优步长,即f(x(k+1))=f(x(k)-(k)g(k))=minf(x(k)-(k)g(k))=min()因为f(x(k)—f(x(k))=f(x(k))-f(x(k))Tf(x(k))+2f(x(k))TH(x(k))f(x(k))/2+o(2)df(x(k)—20、f(x(k))/d=-f(x(k))Tf(x(k))+f(x(k))TH(x(k))f(x(k))=0=f(x(k))Tf(x(k))/f(x(k))TH(x(k))f(x(k))称为最优步长。它不但与梯度有关,而且与海赛矩阵H(x(k))有关。根据一元函数极值条件和多元复合函数求导公式,得’()=-(f(x(k)-(k)g(k)))Tg(k)=0即(f(x(k+1)))Tg(k)=0或(g(k+1))Tg(k)=0即(f(x(k+1)))Tf(x(k))=0此式表明,相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过21、程中,相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线,越接近极小点,锯齿越细,前进速度越慢。这是因为,梯度是函数的局部性质,从局部上看,在该点附近函数的下降最快,但从总体上看则走了许多弯路,因此函数值的下降并不快。2、迭代终止条件采用梯度准则:22、23、g(k)24、25、3、迭代步骤(1)任选初始迭代点x(0),选收敛精度。(2)确定x(k)点的梯度(开始k=0)(3)判断是否满足终止条件26、27、g(k)28、29、?若满足输出最优解,结束计算。否则转下步。(4)从x(k)点出发,沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点x(30、k+1)=x(k)-(k)g(k),
2、极小点,当满足精度条件
3、
4、f(X(k+1))
5、
6、2<1,
7、f(X(k+1))-f(X(k))
8、<2时,停止迭代。在求解无约束极值问题时常用迭代法,迭代法大致上可分为两大类。一类要用到函数的一阶导数或二阶导数,由于用到了函数的解析性质,故称为解析法。另一类迭代过程中仅用到函数值,而不要求函数的解析性质,这种方法称为直接法。一般来说,直接迭代法的收敛速度较慢,只是在变量个数较少时才适用。但直接法的迭代步骤简单,特别是目标函数的解析式十分复杂时,或写不出具体表达式时,这时求导就很困难,或导数不存在,这时只有利用直接法,下面介绍几种常用的基本方法。该方法是184
9、7年柯西提出的,它是求解无约束极值问题的解析法中最古老但又十分基本的一种方法,它的迭代过程简单,使用方便,对初始点的选取要求不严。假设无约束极值问题中的目标函数f(x)有一阶连续偏导数,且有极小点x*。我们取一初始近似点x(0)和一方向g(0),作射线x=x(0)+0g(0)0>0这里的方向g(0)和步长0都是待定的。一、梯度法(最速下降法)为了使f(x)的函数值在x(0)沿方向g(0)移动步长0后有所下降,我们将f(x)在x(0)上展开泰勒级数f(x(0)+0g(0))=f(x(0))+0f(x(0))Tg(0)+o(0)只要0f(x(0
10、))Tg(0)<0,就可以保证f(x(0)+0g(0))11、12、f(x(0))T13、14、.15、16、g(0)17、18、cos,是向量f(x(0))T与g(0)的夹角。只有f(x(0))T与g(0)反向时,f(x(0))Tg(0)最小即:g(0)=-f(x(0))由此可以看出,函数在处沿梯度的反方向是函数值下降最快的方向。由于优化设计是追求目标函数值最小,因此,自然19、可以设想从某点出发,其搜索方向取该点的负梯度方向,使函数值在该点附近下降最快。这种方法也称为最速下降法。1、基本原理梯度法的迭代公式为:x(k+1)=x(k)-(k)g(k)其中g(k)是函数f(x)在迭代点x(k)处的梯度f(xk),(k)一般采用一维搜索的最优步长,即f(x(k+1))=f(x(k)-(k)g(k))=minf(x(k)-(k)g(k))=min()因为f(x(k)—f(x(k))=f(x(k))-f(x(k))Tf(x(k))+2f(x(k))TH(x(k))f(x(k))/2+o(2)df(x(k)—20、f(x(k))/d=-f(x(k))Tf(x(k))+f(x(k))TH(x(k))f(x(k))=0=f(x(k))Tf(x(k))/f(x(k))TH(x(k))f(x(k))称为最优步长。它不但与梯度有关,而且与海赛矩阵H(x(k))有关。根据一元函数极值条件和多元复合函数求导公式,得’()=-(f(x(k)-(k)g(k)))Tg(k)=0即(f(x(k+1)))Tg(k)=0或(g(k+1))Tg(k)=0即(f(x(k+1)))Tf(x(k))=0此式表明,相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过21、程中,相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线,越接近极小点,锯齿越细,前进速度越慢。这是因为,梯度是函数的局部性质,从局部上看,在该点附近函数的下降最快,但从总体上看则走了许多弯路,因此函数值的下降并不快。2、迭代终止条件采用梯度准则:22、23、g(k)24、25、3、迭代步骤(1)任选初始迭代点x(0),选收敛精度。(2)确定x(k)点的梯度(开始k=0)(3)判断是否满足终止条件26、27、g(k)28、29、?若满足输出最优解,结束计算。否则转下步。(4)从x(k)点出发,沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点x(30、k+1)=x(k)-(k)g(k),
11、
12、f(x(0))T
13、
14、.
15、
16、g(0)
17、
18、cos,是向量f(x(0))T与g(0)的夹角。只有f(x(0))T与g(0)反向时,f(x(0))Tg(0)最小即:g(0)=-f(x(0))由此可以看出,函数在处沿梯度的反方向是函数值下降最快的方向。由于优化设计是追求目标函数值最小,因此,自然
19、可以设想从某点出发,其搜索方向取该点的负梯度方向,使函数值在该点附近下降最快。这种方法也称为最速下降法。1、基本原理梯度法的迭代公式为:x(k+1)=x(k)-(k)g(k)其中g(k)是函数f(x)在迭代点x(k)处的梯度f(xk),(k)一般采用一维搜索的最优步长,即f(x(k+1))=f(x(k)-(k)g(k))=minf(x(k)-(k)g(k))=min()因为f(x(k)—f(x(k))=f(x(k))-f(x(k))Tf(x(k))+2f(x(k))TH(x(k))f(x(k))/2+o(2)df(x(k)—
20、f(x(k))/d=-f(x(k))Tf(x(k))+f(x(k))TH(x(k))f(x(k))=0=f(x(k))Tf(x(k))/f(x(k))TH(x(k))f(x(k))称为最优步长。它不但与梯度有关,而且与海赛矩阵H(x(k))有关。根据一元函数极值条件和多元复合函数求导公式,得’()=-(f(x(k)-(k)g(k)))Tg(k)=0即(f(x(k+1)))Tg(k)=0或(g(k+1))Tg(k)=0即(f(x(k+1)))Tf(x(k))=0此式表明,相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过
21、程中,相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线,越接近极小点,锯齿越细,前进速度越慢。这是因为,梯度是函数的局部性质,从局部上看,在该点附近函数的下降最快,但从总体上看则走了许多弯路,因此函数值的下降并不快。2、迭代终止条件采用梯度准则:
22、
23、g(k)
24、
25、3、迭代步骤(1)任选初始迭代点x(0),选收敛精度。(2)确定x(k)点的梯度(开始k=0)(3)判断是否满足终止条件
26、
27、g(k)
28、
29、?若满足输出最优解,结束计算。否则转下步。(4)从x(k)点出发,沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点x(
30、k+1)=x(k)-(k)g(k),
此文档下载收益归作者所有