非线性优化问题ppt课件.ppt

1、.第三专题 非线性优化问题n1、非线性优化模型的建立n2、非线性优化模型的寻优.非线性优化模型的建立n确定决策变量n确定目标（决策准则）n确定约束条件.实例分析（1）投资决策问题（P88)（2）曲线拟合问题 在实验数据处理或统计资料分析中，常常遇到这样的问题：如何利用有关变量的实验数据（资料）去确定这些变量间的函数关系。例如，已知某物体的温度 与时间 之间有如下形式的经验函数关系： 其中 是待定参数。通过测试获得n 组温度与时间之间的实验数据 ，试确定参数 使理论曲线尽可能地与 n个测试点拟合。 ( ,),1,2,iitinttcetcct321)(123, ,c c c123,c c c.非

2、线性规划问题的共同特征非线性规划问题的共同特征n 都是求一个目标函数在一组约束条件下 的极值问题。n在目标函数或约束条件中，至少有一个是变量的非线性函数。.非线性规划问题非线性规划问题n一般形式：n向量形式：121212min(,). .(,)0,1,2,(,)0,1,2,ninjnf x xxstg x xximh x xxjl11211min( ). .( )0,1,2,( )0,1,2,(,),:,:ijTnnnnnijf xstg ximh xjlxx xxRfRRgRRhRR其中且和。.非线性优化问题的寻优n相关概念及理论n一维最优化方法n多维无约束最优化方法n多维有约束最优化方法.

3、非线性规划的相关概念及理论n一阶导数、二阶导数和n元函数的Taylor公式112121 :,( )(,)(1,2, )( )( )( ) ( )(,)nnTniTnfRR xRfxf xxx xxinxfxf xf xf xf xxxxfx定义 设如果 在点 处关于自变量的各分量的偏导数都存在，则称函数 在点 处一阶可导(可微），并且称向量是 在点 处的一阶导数或梯度。. 1212222212112222221222212 :,( )(,)( ,1,2, ) nnTnijnnnfRR xRfxf xxx xxi jnx xfxf xf xf xx xx xxf xf xf xf xx xx x

4、xf xx x 定义 设如果 在点 处关于自变量的各分量的二阶偏导数都存在，则称函数 在点 处二阶可导，并且称矩阵（ ）（ ）（ ）（ ）（ ）（ ）（ ）222nnf xf xx xxfx（ ）（ ）是 在点 处的二阶导数或Hesse矩阵。.122123 :,Taylor1 ()( )( )()( )()2=(,) ( )( )( ) (nnTTTnTfRR xRfxfxf xxf xf xxxf xxoxxxxxxxxfxf xf xf xx 定义 设如果 在点 处的某邻域具有二阶连续偏导数，则 在点 处二阶展式：其中。若记，略去高阶小量后，得到 在点 处的线性逼近（函数）和二次逼近（函数

5、）：2)1 ( )( )( ) ()+()( )()2TTxf xf xf xxxxxf xxx.定义4设函数 xfnRD 定义在凸集上，若对任意的,Dyx及任意的1,0都有： yfxfyxf11则称函数 xf为凸集D上的凸函数定义5 严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义凸函数.例1： 设 ,12 xxf试证明 xf在,上是严格凸函数证明:设,Ryx且1,0,yx都有： yfxfyxf1122211111yxyx012yx因此 xf在,上是严格凸函数.例2： 试证线性函数是 nnTxcxcxcxcxf2211证明:设,1,0,RyxnR上的凸函数则yxcyxfT11 y

6、fxfycxcTT11所以xcT是凸函数类似可以证明xcT是凹函数.凸函数的几何性质对一元函数 ,xf在几何上 211xfxf10表示连接 2211,xfxxfx的线段211xxf表示在点211xx处的函数值所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.凸函数的性质（） 设（）设 xfxf21,函数， xf是凸集nRD上的凸函数，实数,0k则 xkf也是D上的凸函数是凸集nRD上的凸实数,0,则 xfxf21也是D上的凸函数（）设 xf是凸集nRD上的凸函数，是实数， 则水平集,fS xfDxx,是凸集.下面的图形给出了凸函数xyy 24243,yxxyxf的等值线的图形

7、，可以看出水平集是凸集.凸函数的判定定理1 设 xfnRD 上，,Dyx令 ,1,0,1tyttxft则:(1) xf是定义在凸集是凸集D上的凸函数的充要条件是对任意的,Dyx一元函数 t为1,0上的凸函数.(2)设,yxDyx若 t在1,0上为严格凸函数， 则 xf在D上为严格凸函数.该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧.一阶条件定理2.1设在凸集nRD 上 xf可微，则： xf在D上为凸函数的充要条件是对任意的,Dyx都有： xyxfxfyfT定理2.2严格凸函数(充要条件).二阶条件定理定理3 3设在开凸集nRD 内 xf二阶可微，则(1) xf是D内的凸函数的

8、充要条件为， 在D内任一点x处， xf的海色矩阵 xG半正定, 22221222222122122122122nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfxG其中：.二阶条件定理3设在开凸集nRD 内 xf(2)若在D内 xG正定, 则 xf在D内二阶可微，则是严格凸函数注: 反之不成立例： 4xxf显然是严格凸的，但在点0 x处 xG不是正定的.凸规划凸规划定义6 设nRD 为凸集， xf为D上的凸函数，则称规划问题 xfDxmin为凸规划问题定理4 (1)凸规划问题的任一局部极小点x是整体极小点，全体极小点组成凸集(2)若 xf是凸集nRD 上的严格凸函数，且凸规划问题

9、xfDxmin整体极小点存在，则整体极小点是唯一的.非线性规划的最优性条件非线性规划的最优性条件 最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。n无约束最优性条件无约束最优性条件 n约束最优性条件约束最优性条件 min( )f xmin( ). .( )0,1,2,( )0,1,2,ijf xstg xiph xjq.无约束最优性条件无约束最优性条件1 :, ( )0 0 ()( )( )0() ( )000,nnnTTTfRRxRPRf xPPfxfxfxTaylortf xtPf xt f xPtPf xPt 定理 设在处可微，若存在使，则称向量 是函数 在 处的下降方向

10、。证明 因为 在 处可微，故由 在 处的展式，对于任意的，有由于，从而存在对于 (0, ) ( )0()0 ()( ), (0, ) Ttt f xPtPf xtPf xtPfx 任意的，有从而有故 是函数 在 处的下降方向。.一（单）元函数的最优性条件（） 若（）*x为 fx的局部极小点， 则*0;fx若*0 ,0,fxfx则*x为 fx的严格局部极小点；若（）*x为 fx的局部极小点，则：*0 ,0.fxfx.多元函数的一阶必要条件（P106-107)定理1:若*x为 xf的局部极小点，且在 *xN内 xf一阶连续可导，则 .0*xfg注: (1)仅仅是必要条件，而非充分条件(2)满足 0

11、*xfg的点称为驻点驻点分为：极小点，极大点，鞍点.多元函数的二阶充分条件定理2: 若在 *xN内 xf二阶连续可导， 且 *,0 xGGg正定, 则 *x为严格局部 极小点 注: 如果 *G负定, 则 *x为严格局部极大点 .二阶必要条件和充要条件定理3:若*x为 xf的局部极小点，且在 *xN内 xf二阶连续可导， 则*,0 Gg 半正定定理4:设 xf在nR上是凸函数且有一阶连续偏导数， 则*x为 xf的整体极小点的充要条件是.0*g.例1：利用极值条件解下列问题： 12232313131minxxxxxf解：222221121xxxfxxf令 ,0 xf即：020122221xxx得到

12、驻点：(1)(2)(3)(4)1111,0202xxxx .函数 xf的海色阵： 22002212xxxf由此，在点(1)(2)(3)(4),xxxx处的海色阵依次为：2(1)2(2)20200202fxfx2(3)2(4)20200202fxfx.由于矩阵2(1)2(4),fxfx不定，则(1)(4),xx不是极小点2(3)fx负定， 则(3)x不是极小点，实际上它是极大点2(2)fx正定，则(2)x是局部极小点.约束最优性条件约束最优性条件(p133-p136)min( ). .( )0,1,2, ( )0,1,2,( )0,1,2, ;( )0,1,2,1,2,1,2, ijnijf x

13、stg xiph xjqDxRg xip h xjqJqIp一般约束问题的最优性（*)令可行域.定义1:有效约束： 若(*)中的一个可行点*x使得某个不等式约束 0igx 变成等式， 即则称为关于 的有效(积极）约束非有效约束： 若对*0,kgx则 0kgx 称为关于的非有效(无效）约束有效集：*0iII xi gx定义2:锥：nR的子集， 如果它关于正的数乘运算是封闭的 如果锥也是凸集，则称为凸锥凸锥关于加法和正的数乘运算是封闭的*0igx 0igx *x*x.一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件)(1951)设 *,()ifxgxiI在可微，*x*iijjjJi I

14、fxgxhx*( )()()(),()0()(),jijijxhxjJxgxiIhxjJxiIjJ点处连续。在点处连续可微,且线性无关。若是问题（*)的局部最优解，则存在和使得 *()igxiI I在（K-T条件）条件）.一阶必要条件定理1:(Kuhn-Tucker一阶必要条件)*0iigxIi *,( )()()(),()0()(),ijijijfxgxiIxhxjJxgxiIhxjJxiIjJ设在点处可微,在点处连续可微,且线性无关。若是问题（*)的局部最优解，则存在和使得*iijji IjJfxgxhx（互补松弛条件）（互补松弛条件）.* min( ) . .( )0,1,2, 0()

15、min( ) . .( )0,1,2, ()iiiii Ijjf xstg xipxiIf xgxf xst h xjqxjJ不等式约束问题若 是不等式约束问题的局部最优解，则存在使得等式约束问题若 是等式约束问题的局部最优解，则存在使* jjj Jf xhx得.例2：验证 是否满足Kuhn-Tucker条件： 22212312123222123min32. .00003fxxxxstxxxxxxxx 试验证最优点Tx1, 1, 1*为KT点x.解： *1I Txf4,2,6*12,2,2Thx*11,1,0Tgx 令*11612212402所以*112 ,2 即：*1122fxgxhx *1

16、10gx*10所以：*x是KT点.Lagrange函数及K-T条件11112121212:,:(),:() ( )( ),( ),( ) ( )( ( ),( ),( ) =(,) , =(,)( , , )nnnijTpTqTTpqfRR gRR iI hRRjJg xg x gxgxh xh x h xh xL xf 定义：设。记则称 *( )( )( ) = ( )( )( )(,)0()0,0,iijji Ij JTTxiiixg xh xf xg xh xLagrangeLagrangeL xKTg xiIiI 是非线性规划问题的函数，其中 和 叫乘子。条件： .在一定凸性下的最优性

17、的充分条件在一定凸性下的最优性的充分条件 *,( )()-,( )()ijijf xgxiIxh xjJxxK Tf xgxiIh xjJx定理3.6：对一般非线性规划问题（*)，若在点 处可微,在点 处连续可微,若 满足上述条件，并且是凸函数，是线性函数，则 是该问题的全局（整体）最优解。2212121212123 - (,)(1)(2) . . 20 -0 -0 10K Tf x xxxst xxxxxx 例 ： 用条件求下列问题min .一维最优化方法（线性搜索方法）一维最优化方法（线性搜索方法）已知,kx并且求出了kx处的可行下降方向,kp从kx出发， 沿方向kp求目标函数的最优解，或

18、者选取 00minminkkpxf0k使得：0Tkkkkf xpp问题描述()0k 即即.设其最优解为k（叫精确步长因子），kkkkpxx1所以线性搜索是求解一元函数 的最优化问题（也叫一维最优化问题）。我们来求解：于是得到一个新点： xfbxamin.一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。搜索区间：搜索区间：*0:,0,),)min ( )RR 设并且 (* , 0,), , , a ba ba b若存在使，则称0min 是（ ）的搜索区间。.搜索区间求取方法搜索区间求取方法 n进退法：进退

19、法：一种简单的确定初始搜索区间方法.n基本思想：基本思想：是从一点出发，按一定步长，试图确定出函数值呈现“高-低-高”的三点，即 这里 。 具体地说，就是给出初始点 ，初始步长 ，若 ，则下一步从新点 出发，加大步长，再向前搜索，直到目标函数上升为止。 ( )( )( )acbacb0000h 000()()h 100h. 若 ，则下一步仍以 为出发点，沿反方向同样搜索，直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。 n计算步骤：见计算步骤：见P96n计算框图计算框图:见见P970000()()h .黄金分割法（黄金分割法（0.6180.618法）法）n基本思想： 它通过对

20、试探点的函数值进行比较，使得包含极小点的区间不断缩短，当区间长度小到精度范围之内时，可以粗略地认为区间上各点的函数值均接近于极小值。.设 xf在ba,上为下单峰函数， 即有唯一的极小点,*x在*x左边 xf严格下降，在*x右边 xf严格上升。在ba,内任取,21xx 若 ,21xfxf则2*,xax 若 ,21xfxf则bxx,1*单峰函数：黄金分割法黄金分割法.黄金分割法若第一次选取的试点为,21xx 则下一步保留的区间为2,xa或,1bx两者的机会是均等的因此我们选取试点时希望.12xbax设,1abpax则.12abpax另外，我们希望如果缩小的区间包含原来的试点，则该试点在下一步被利用

21、若保留的区.我们希望原来的间为,2xa前一次的试点1x在这个区间内1x在缩小的区间内成为新的.2x我们根据这条件 来计算. p计算2x的公式为：abpax12因此我们希望：221,xapbaaa bx即：aabpapaabpa1121xx .化简得：618.01382.02530132pppp若保留区间为,1bx我们得到的结果是一致的 该方法称为黄金分割法，实际计算取：abaxabax618. 0382. 021所以黄金分割法又称为0.618法黄金分割法每次缩小区间的比例是一致的，每次将区间长度缩小到原来的0.618倍. 黄金分割法的算法步骤Step1给定baba,以及0令 1110.382,

22、xabaff xStep2Step3转Step.令2220.618,xabaff x转Step.若,ab则,2*bax停； 否则转Step.Step4 若,21ff 则,12122ffxxxb 1110.382,xabaff x转Step3.黄金分割法的算法步骤Step5 若,21ff 则,21xbxa 1110.382,xabaff x2220.618,xabaff x转Step3.若,21ff 则,21211ffxxxa2220.618,xabaff x转Step3.例1（黄金分割法）用黄金分割法求函数 22xxxf在区间3 , 1上的极小点。 要求最终区间长度不大于原始区间长度的0.08

23、倍解：函数 xf在区间3 , 1上为下单峰函数，32. 008. 013.第一次迭代：3, 1ba10.3820.528xaba751. 11f20.6181.472xaba695. 22f,21ff 缩短后区间为472. 1, 1第二次迭代：472. 1, 1ba528. 012 xx751. 112 ff059. 21f,21ff 缩短后区间为472. 1,056. 010.3820.056xaba .迭代次数0.5281.4721.7512.695否-0.0560.5282.0591.751否0.5280.8881.7511.901否0.3050.5281.7881.751否0.5280

24、.6651.7511.777否0.4430.5281.7531.751否0.5280.5801.7511.757是ba,1x2x1f2fab3,1472.1 , 1472. 1 ,056. 0888. 0 ,056. 0888. 0 ,305. 0665. 0 ,305. 0665. 0 ,443. 0554.02/665.0443.0*x.Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。 如果在区间只有一个试点，我们无法将区间缩小。如果知道两个试点,21xx 根据 21,xfxf的大 小关系，可以得到缩小的区间2,xa或者.,1bx 它与0.618法的主要区别之一在于：搜索区间长

25、度的缩短率不是采用0.618，而是采用Fibonacci数。 .下面我们考虑任给一个另外一种思维方式为， xf的单峰区间, a b如果给定试点的个数,n如何使最后确定最优值的区间尽量的小。按什么方式取点，求n次函数值之后， 可最多将多长的原始区间长度缩小为. 1设nL为试点个数为、n最终区间长度为1时、 原始区间ba,的最大可能长度。的包含.设最初两个试点为1x和,2x若极小点在1,xa内，至多还有2n个试点，则,21nLax若极小点在bx ,1内， 包括2x在内可以有1n个试点，则,11nLxb因此，,21nnnLLL如果我们采取合适的技巧，可以使得：,21nnnLLL另外，显然，. 110

26、 LL.从而nL满足差分方程：121021LLnLLLnnn此为Fibonacci数列，一般写为：121021FFnFFFnnn.若原始区间为,ba要求最终区间长度,则,abFn由此可确定,n区间缩短之后与之前的比依次为：21,32,53,121nnnnFFFFn确定之后，最初两个试点分别为：abFFaxabFFaxnnnn122121,xx关于ba,对称1112()nnnnFbabaF1121123()nnFFFbaFFF111()nbaF由于 .上述过程完成了依次迭代，新区间仍记为1iba,若已经进行了次迭代，第i次迭代时，还有1in个试点（包括已经计算过的函数值的一个）abFFaxabF

27、Faxinininin12111注意注意：（）若在一定的误差范围内， ,21xfxf则认为*x在21,xx内。（）最后的两个试点的选取方式：abxxabx1 . 0, 2/121.例3.1（Fibonacci法）用Fibonacci法求函数 22xxxf在区间3 , 1上的极小点。要求最终区间长度不大于原始区间长度的0.08倍解： 函数 xf在区间3 , 1上为下单峰函数，32. 008. 013由, 5 .1208. 0/ 1nF可知n应取.136FFibonacci算法与算法与0.618法几乎完全相同法几乎完全相同 。.第一次迭代：3, 1baabFFax64141351538. 0462

28、. 141381652abFFax675. 2,751. 121ff,21ff 缩短后区间为462. 1, 1.第二次迭代：462. 1, 1ba538. 02x751. 12f077. 01462. 11531FFx083. 21f,21ff 缩短后区间为462. 1,077. 0.第三次迭代：462. 1,077. 0ba538. 01x751. 11f846. 0077. 0462. 1077. 0432FFx870. 12f,21ff 缩短后区间为846. 0,077. 0第四次迭代：846. 0,077. 0ba538. 02x751. 12f231. 0077. 0846. 007

29、7. 0311FFx822. 11f,21ff 缩短后区间为846. 0,231. 0.第五次迭代：846. 0,231. 0ba538. 02x751. 12f477. 0231. 0846. 01 . 021 xx751. 11f,21ff 取最优解508. 0221*xxx.Fibonacci方法评价Fibonacci法的优点（）如果缩小的区间包含原来的试点，则该试点在下一步被利用；（）效率最高，有限个试点的情况下，可将最优点所在的区间缩小到最小.Fibonacci法的缺点（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致1、黄金分割法（、黄金分割法（0.618法）与法）与F

30、ibonacci法法的区别与联系是什么？的区别与联系是什么？2、请读者自己写出算法和程序、请读者自己写出算法和程序 .二分法二分法若 xf的导数存在且容易计算，则线性搜索的速度可以得到提高 下面的二分法每次将区间缩小至原来的二分之一设 xf为下单峰函数， 若 xf在ba,内具有连续的一阶导数，且 0,0bfaf.取, 2/bac若 , 0 cf则c为极小点；若 , 0 cf则以ca,代替, a b ；若 , 0 cf则以cb,代替, a b 。 二分法每次迭代都将区间缩短一半，故二分法的收敛速度也是线性的，收敛比为1/2。 n 计算步骤：见计算步骤：见P105n 计算框图计算框图:见见P106

31、.多维无约束最优化方法多维无约束最优化方法n最速下降法最速下降法n( (阻尼阻尼) )牛顿法牛顿法n共轭梯度法共轭梯度法.最速下降法最速下降法.问题提出问题：在点( )kx处， 沿什么方向,kd xf下降最快?分析：( )( )0kkTkkkkf xdf xg dod考查：coskkkTkdgdg显然当1cos时，kTkdg取极小值因此：kkgd结论： 负梯度方向使 xf下降最快， 亦即最速下降方向.最速下降法算法Step1: 给出(0),01,:0nxRkStep2:计算(),kfx如果(),kfx停Step3:计算下降方向.kkgdStep4:计算步长因子()()0()min()kkkkk

32、f xdf xdStep5: 令(1)(),kkkkxxd转步.,k使得.问题：设 cxbGxxxfTT21是正定二次函数,由精确的线搜索确定的?k特别当： TkkkTkkg dd Gd 则kkgdkTkkTkkGgggg( )( )()0kkTTkkkkdf xdd G xdb dd( ) g,kkGxb又.例1： 用最速下降法求解： 22(0)1219min9,122Tfxxxx解： TxxGxxxg0,090019*21(0)009,19,9TTxgfx (1)(0)000007.20.8TTg gxxgg Gg2.72.71g(2)(1)2111221190.810.8TTg gxxg

33、g Gg .()90.8,1,2,1kkkxk分析： (1)(1)(1)()()*limlim0.8kkkkkkxxxxxx因此： 最速下降法是整体收敛的，且是线性收敛的(2) 两个相邻的搜索方向是正交的02.7,2.79,91010ddddTTT.收敛性分析定理1: 设 xf在 0 xfxfRxLn上存在且一致连续，则最速下降法产生的序列满足或者对某个k有,0kg或者,kxf. 0kg证明： 对于最速下降法，,0k由以上定理立得.收敛性分析定理2: 设 xf二次连续可微， 且 ,2Mxf其中M是个正常数， 对任何给定的初始点(0),x最速下降算法或有限终止， 或者,limkkxf或者.0li

34、mkkg证明：用以上的结论：()(1)212kkkfxfxgM.最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求(2) 有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛.最速下降法缺点最速下降法是线性收敛的，并且有时是很慢的线性收敛原因： kkgd仅反映 xf在kx处的局部性质,01kTkdg相继两次迭代中搜索方向是正交的.小结最速下降法是基本算法之一，而非有效的实用算法最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近.牛顿法牛顿法.基本思想利用目标函数 xf在点( )kx处的二阶Taylor展开式去近似目标函数， 用

35、二次函数的极小点去逼近目标函数的极小点.算法构造问题：设 xf二阶连续可微，( ),knxR( ),kkgf x海色阵( )2kkGf x正定如何从( )(1)?kkxx ( )( )( )kkkTkkkf xf xxxqxfgxx( )( )12kkTkxxGxx因为kG正定， 则 xqk有唯一极小点， 用这个极小点作为(1).kx.所以要求：(1)0kkqx即：(1)( )0kkkkGxxg(1)( )1kkkkxxG g因此：这就是牛顿法迭代公式注：这里., 11kkkkgGd.牛顿法算法Step1: 给出(0),01,:0nxRkStep2: 计算(),kfx如果(),kfx停Step

36、3: 否则计算,kGStep4: 令(1)(),kkkxxd转步.并且求解方程,kkkgdG得出.kd.例1： 用牛顿法求解： (0)221219min9,122Tfxxxx解： TxxGxxxg0,090019*21(1)(0)11*009109010990 xxG gx .牛顿法收敛定理定理定理1: 设 xf二次连续可微，*x是 xf的局部极小点，2*fx正定 假定 xf的海色阵()2kkGfx 满足Lipschitz条件，即存在,0使得对于所有nji ,1有： 1,nijijRyxyxyGxG其中 xGij是海色阵kG的ji,元素 则当(0)x充分靠近*x时， 对于一切,k牛顿迭代有意义

37、，迭代序列()kx收敛到,*x并且具有二阶收敛速度.牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点如果*G正定且初始点选取合适， 算法二阶收敛.牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需要计算,kG计算量大(3)每次都需要解;kkgdG方程组有时奇异或病态的， 无法确定,kd或kd不是下降方向(4) 收敛到鞍点或极大点的可能性并不小.阻尼牛顿法算法Step1: 给出(0),01,:0nxRkStep2: 计算(),kfx如果(),kfx停Step3: 否则计算,kGStep4: 沿并且求解方程,kkgdG得出.kdkd进行线搜索， 得出.kStep5: 令(1)

38、(),kkkkxxd转Step2.阻尼牛顿法收敛定理定理定理2: 设 xf二阶连续可微， 又设对任意的(0),nxR存在常数,0m使得 xf在 0 xfxfxL上满足： (0)22,TnfxmRxL x则在精确线搜索条件下， 阻尼牛顿法产生的点列( )kx满足：(1)当( )kx是有限点列时， 其最后一个点为 xf的唯一极小点(2)当( )kx是无限点列时， 收敛到 xf的唯一极小点.阻尼牛顿法收敛定理定理定理3: 设 xf二阶连续可微， 又设对任意的(0),nxR存在常数,0m使得 xf在 (0)Lx fxfx上满足： (0)22,TnfxmRxL x则在Wolfe不精确线搜索条件下，阻尼牛

39、顿法产生的点列( )kx满足：( )lim0kkfx且( )kx收敛到 xf的唯一极小点.例2：用阻尼牛顿法求解： (0)241122min10, 0Tfxxx xxx解：21102000Gg显然0G不是正定的， 但：011210G于是，020100gGd沿方向0d进行线搜索，(0)40161,fxd得其极小点. 00从而迭代不能继续下去.带保护的牛顿法算法给出(0)12,:0nxRk Step1:kG若为奇异的，转Step8，否则，Step2: 令,1kkkgGdStep3: 若,1kkkTkdgdg为奇异的，转Step8，否则，则转Step8，否则，Step4: 若,1kkkTkdgdg则

40、转Step9，否则，Step5: 沿方向kd进行线搜索， 求出,k并令(1)().kkkkxxd.Step6:若,21kg停；Step7: 令, 1 kk转Step1；Step8:令,kkgd转Step5；Step9: 令,kkdd转Step5.例3： 用带保护的牛顿法求解： (0)241122min10, 0Tfxxx xxx解：21102000Gg显然0G不是正定的， 但：011210G于是，020100gGd因为，,000dgT故令，,2000gd沿0d进行线搜索得：,210.(1)(1)0,01xfx第二次迭代：2110,0111Gg而：121111gGd使,0211dgT故令1212

41、1d沿1d进行线搜索， 得出,3479422.01于是:(2)(2)0.69588440.58244511.3479422xfx 此时:01073.072g.共轭梯度法共轭梯度法.问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性(经过有限次迭代必达到极小点的性质）.算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法.共轭方向及其性质定义1: 设mddd,21是nR中任一组非零向量， 如果：jiGddjTi,0则

42、称mddd,21是关于G共轭的注： 若, IG 则是正交的，因此共轭是正交的推广.定理1:设G为n阶正定阵， 非零向量组mddd,21关于G共轭，则必线性无关推论1:设G为n阶正定阵， 非零向量组nddd,21关于G共轭， 则向量构成nR的一组基推论2:设G为n阶正定阵，非零向量组nddd,21关于G共轭， 若向量v与nddd,21关于G共轭，则.0v.求 的极小点的方法共轭方向法算法( )( )0min,kkkkkf xdf xdStep1: 给出(0),01,:0nxRk计算(0)0gg x和初始下降方向.0dStep2: 如果,kg停止迭代Step3: 计算(1),kkx使得(1)().

43、kkkkxxdStep4: 采用某种共轭方向法计算1kd使得：., 1 ,0,01kjGddjTkStep5: 令, 1: kk转Step2.共轭方向法基本定理定义2: 设n维向量组kddd,21线性无关，(1),nxR向量集合(1)11kkiiiiHxdR为(1)x与kddd,21生成的k维超平面.引理1: 设 xf是连续可微的严格凸函数，n维向量组kddd,21线性无关，(1),nxR则：(1)(1)1kkiiixxd 是 xf在kH上唯一极小点的充要条件是：kidgiTk,2, 1,01.定理2: 设G为n阶正定阵， 向量组kddd,21关于G共轭， 对正定二次函数 ,21cxbGxxx

44、fTT由任意开始，依次进行k次精确线搜索：(1)( ),1,2,iiiixxd ik则：（）kidgiTk,2, 1,01（）(1)kx是 xf在kH上的极小点推论:当nk 时，为正定二次函数在nR上的极小点(1)x(1)nx.共轭梯度法记：11kkkkdgd左乘,1GdTk并使1111kTkkTkkGddGdg,01kTkdGd得：（Hestenes-Stiefel公式）取：00gd是一种特殊的共轭方向法是一种特殊的共轭方向法.共轭梯度法基本性质定理3: 对于正定二次函数，采用精确线搜索的共轭梯度法在nm 步后终止，且对ni 1成立下列关系式：, 1, 1 ,0,0ijGddjTi, 1,

45、1 ,0,0ijggjTi,iTiiTigggd,1, 1 ,00ijdgjTi（共轭性）（正交性）（下降条件）.系数的其他形式（）FR公式111kTkkTkkgggg（1964）（2）PRP公式1111kTkkkTkkggggg（1969）.FR共轭梯度法算法( +1)+1,kkgf x (0)00()dgf x 令Step1: 给出(0),01,:0nxRkStep2:如果,kg停Step5:转Step2.计算计算Step4:11,kkkkdgd 11TkkkTkkggg g，Step3:由精确线搜索求,k计算 1,kk令(1)( ) ,kkkkxxd并令.例4： 用FR共轭梯度法求解：

46、22(0)1212131min22, 422Tfxxxx xxx 解：化成 cxbGxxxfTT21形式 2121210,21113,21xxxxxxxf(0)24x(0)0126gGxb(1)0126d.17500000GdddgTT(1)(0)0026173817xxd116171217gGxb789.01g(2)289100110ggggTT289210289900011dgd171011111GdddgTT(2)(1)1111xxd 02g*(2)11xx .例5： 用FR共轭梯度法求解： 22(0)12011min1,11,022TTfxxxxd 解：化成 cxbGxxxfTT21形

47、式 21211001,21xxxxxf(0)11x (0)011gGxb (1)010d.100000GdddgTT(1)(0)0001xxd (1)101gGxb 11g(2)2100110ggggTT1210011dgd5411111GdddgTT(2)(1)112515xxd.(2)22515gGxb21/5g(3)2211115TTg gg g221131025dgd 2222225TTg dd Gd (3)(2)22125125xxd(3)3125125gGxb32,25g注意：注意：FR方法中初始搜索方向必须取最速下降方方法中初始搜索方向必须取最速下降方向，才满足二次终止性。向，才

48、满足二次终止性。.FR共轭梯度法收敛定理kx（ ）定理定理4:假定 xf在有界水平集 0nLxRf xf x（ ）上连续可微， 且有下界， 那么采用精确线搜索下的FR共轭梯度法产生的点列kx（ ）至少有一个聚点是驻点，即：(1) 当是有穷点列时， 其最后一个点是 xf的驻点(2)当是无穷点列时， 它必有聚点， 且任一聚点都是 xf的驻点kx（ ）.再开始FR共轭梯度法算法Step1: 给出0,01,:0nxRk（ ）Step2: 计算00,gfx （ ）如果,0g停，Step4:否则.00gdStep3: 由精确线搜索求,k并令：1,1.kkkkxxdkk（）（ ）计算,kkgfx （ ）若,

49、 1.021kkTkggg令0:,kxx（ ）（ ）转Step2;如果,kg停.Step5: 若,nk 令转step2.Step6: 计算11111,kkkkkTkkTkkdgdggggStep7: 如果,0kTkgd令转step2,否则 转step3.0:,kxx（ ）（ ）0:,kxx（ ）（ ）.作业用FR共轭梯度法求解： 022125min25f xxxx （ ）.多维约束最优化方法多维约束最优化方法n惩罚函数法惩罚函数法 SUMT:SUMT:序列无约束极小化方法序列无约束极小化方法 (Sequential Unconstrained Minimization Technique) n

50、乘子法乘子法外点法（二次罚函数方法） 内点法（内点障碍罚函数法） .罚函数法罚函数法.基本思想设法将约束问题求解转化为无约束问题求解具体说： 根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解惩罚策略： 企图违反约束的迭代点给予很大的目标函数值 迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点.外罚函数法（外点法）引例： 求解等式约束问题:222121,minxxxxf02.21 xxt s解:图解法求出最优解.1 , 1*Tx 构造：22,2121222121xxxxxxxxF但是21,xxF性