文档介绍：非线性规划
非线性规划
南京航空航天大学经济与管理学院
党耀国
教授、博士生导师
管理科学与工程系主任
无约束极值问题
现在我们来研究n元函数的无约束极值问题。
这种问题的表达式为:
Min f(X) X??E(n) (1)
为求此问题的最优解或近似最优解,常使用搜索法,并要进行若干次迭代。
当用迭代法求解问题(1)时,常从某一近似点X(k)出发,接着在这一点选定一搜索方向P(k),使目标函数值沿该方向下降,然后选择步长,沿P(k)方向移动一个步长,即可得下一个近似点X(k+1)
X(k+1)= X(k) + P(k)
且满足 f(X(k+1))< f(X(k))
这样即可逐步趋近极小点,当满足精度条件
||?? f(X(k+1)) ||2<??1, |f(X(k+1))- f(X(k)) |<??2时,停止迭代。
在求解无约束极值问题时常用迭代法,迭代法大致上可分为两大类。一类要用到函数的一阶导数或二阶导数,由于用到了函数的解析性质,故称为解析法。
另一类迭代过程中仅用到函数值,而不要求函数的解析性质,这种方法称为直接法。
一般来说,直接迭代法的收敛速度较慢,只是在变量个数较少时才适用。但直接法的迭代步骤简单,特别是目标函数的解析式十分复杂时,或写不出具体表达式时,这时求导就很困难,或导数不存在,这时只有利用直接法,下面介绍几种常用的基本方法。
该方法是1847年柯西提出的,它是求解无约束极值问题的解析法中最古老但又十分基本的一种方法,它的迭代过程简单,使用方便,对初始点的选取要求不严。
假设无约束极值问题中的目标函数f(x) 有一阶连续偏导数,且有极小点x*。我们取一初始近似点x(0)和一方向g(0),作射线
x=x(0)+ ?? 0 g(0) ?? 0 >0
这里的方向g(0)和步长?? 0都是待定的。
一、梯度法(最速下降法)
为了使f(x) 的函数值在x(0)沿方向g(0)移动步长?? 0后有所下降,我们将f(x)在x(0)上展开泰勒级数
f(x(0)+ ?? 0 g(0))= f(x(0))+ ?? 0 ?? f(x(0) )T g(0)+o(?? 0 )
只要?? 0 ?? f(x(0) )T g(0)<0,就可以保证f(x(0)+ ?? 0 g(0))< f(x(0))
若记x(1)= x(0)+ ?? 0 g(0),则 f(x(1) ) < f(x(0) )
现在的问题就是如何方向g(0)和步长?? 0,
使?? 0 ?? f(x(0) )T g(0)尽可能的小。
由于?? f(x(0) )T g(0)= || ?? f(x(0) )T ||3>. || g(0) ||cos??,
??是向量?? f(x(0) )T 与g(0)的夹角。
只有?? f(x(0) )T 与g(0)反向时, ?? f(x(0) )T g(0)最小
即: g(0)= -?? f(x(0) )
由此可以看出,函数在处沿梯度的反方向是函数值下降最快的方向。
由于优化设计是追求目标函数值最小,因此,自然可以设想从某点出发,其搜索方向取该点的负梯度方向,使函数值在该点附近下降最快。这种方法也称为最速下降法。
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))
=min f(x(k)-??(k)g(k))=min??(??)
因为
f(x(k)—???? f(x(k) )= f(x(k))- ???? f(x(k) )T ?? f(x(k) ) +
?? 2?? f(x(k) )T H(x(k) )?? f(x(k) )/2 +o(??2)
df(x(k)—?? ?? f(x(k) )/d ?? = - ?? f(x(k) )T ?? f(x(k) ) +
?? ?? f(x(k) )T H(x(k) )?? f(x(k) )=0
??= ?? f(x(k) )T ?? f(x(k) ) / ?? f(x(k) )T H(x(k) )?? f(x(k) )
??称为最优步长。它不但与梯度有关,而且与海赛矩阵 H(x(k) )有关。
根据一元函数极值条件和多元复合函数求导公式,得??’(??)= -(?? f(x(k)-??(k)g(k)))T g(k) =0 即(?? f(x(k+1)))T g(k) =0 或(g(k+1))Tg(k)=0
即(?? f(x(k+1)))T