非线性规划课件.pptx

1、非线性规划非线性规划（优选）非线性规划2 2 2、多元函数、多元函数 y=f(X)=f(xy=f(X)=f(x1 1,x,x2 2,x,xn n)：在：在 X X0 0 附近作泰勒展开，得附近作泰勒展开，得 )xxx(),X(xxxx)X(f21xx)X(f)X(f)X(f0ii3jin1j,iji02in1ii00 )XXX(,XHX21X)X(f)X(f)X(f0TT00 ,x)X(fx)X(f)X(f:n0100 其中其中.X)X(f0梯度梯度处的一阶导数向量处的一阶导数向量在在为为 nn1nn1112n021n02n1022102hhhhx)X(fxx)X(fxx)X(fx)X(fH.

2、HessienX)X(f0矩阵矩阵处的二阶导数矩阵处的二阶导数矩阵在在为为 极值点存在的必要条件：极值点存在的必要条件：f(x)=0f(x)=0，此时求出的，此时求出的 x x0 0 为驻点。为驻点。极值点存在的充分条件：极值点存在的充分条件：XHXXfXfT 21)()(0为为极极小小值值点点。则则正正定定若若0X,H.a)0hhhh,0hhhh,0hH(nn1nn1112221121111 正正定定为为极极大大值值点点。则则负负定定若若0X,H.b)0hhhh)1(,0hhhh,0hH(nn1nn111n2221121111 负负定定只只为为驻驻点点。则则不不定定若若0X,H.c的的极极值

3、值和和极极值值点点。求求例例20 x4x2x8x2)x,x(f:22212121 ,04484)()()(:2121 xxxXfxXfXf令令解解,12X0 得得驻驻点点 4004x)X(fxx)X(fxx)X(fx)X(fH222122212212,H正正定定显显然然,X0为为极极小小值值点点故故10)1,2(f*四、四、凸函数与凹函数凸函数与凹函数：1 1、定义：、定义：y=f(x)y=f(x)是是E En n中某凸集中某凸集R R上的函数上的函数 对对0,10,1及及 X X1 1、X X2 2 R R，且，且 X X1 1XX2 2 若若ff X X1 1+(1-+(1-)X)X2 2

4、 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2)，则，则f(x)f(x)为为R R上的凸函数。上的凸函数。若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2)，则，则f(x)f(x)为为R R上的严格凸函数。上的严格凸函数。对对0,10,1及及 X X1 1、X X2 2 R R，且，且 X X1 1XX2 2 若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2)，则，则f(x)f(x)为为R R上的上的凹凹函数。函数。若若ff X X1 1+(1-+

5、(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2)，则，则f(x)f(x)为为R R上的严格上的严格凹凹函数。函数。y yx xo oX X1 1X X2 2 X X1 1+(1-+(1-)X)X2 2y=f(x)y=f(x)凸函数凸函数y yx xo oX X1 1X X2 2 X X1 1+(1-+(1-)X)X2 2y=f(x)y=f(x)凹凹函数函数y yx xo oX X1 1X X2 2y=f(x)y=f(x)非凸、非非凸、非凹凹函数函数 2 2、性质：、性质：f fi i(X)(X)为凸集为凸集R R上的凸函数，则对上的凸函数，则对 k ki i

6、00，i=1,2,i=1,2,m,m，有，有 k k1 1f f1 1(X)+k(X)+k2 2f f2 2(X)+(X)+k+km mf fm m(X)(X)仍为仍为凸函数。凸函数。3 3、凸函数的判定：、凸函数的判定：f(X)f(X)定义在凸集定义在凸集R R上，若上，若f(X)f(X)有连续的二阶导数，有连续的二阶导数，则则f(X)f(X)为凸函数为凸函数 H H为半正定。为半正定。f(X)f(X)为严格凸函数为严格凸函数 H H为正定。为正定。4 4、凸函数的局部极值与全局极值的关系凸函数的局部极值与全局极值的关系 若目标函数在可行域中为若目标函数在可行域中为凸函数，则其极值点为最优值

7、点；凸函数，则其极值点为最优值点；若目标函数在可行域中为若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。严格凸函数，则其极值点为唯一最优值点。10 xx2x2x3)X(f:212221 判判断断函函数数凹凹凸凸性性例例正定解4006)()()()(222122212212xXfxxXfxxXfxXfH为为严严格格凸凸函函数数。)X(f五、五、凸规划凸规划：1 1、定义：非线性规划、定义：非线性规划(p)(p)Min f(X)Min f(X)g gi i(X)0(X)0 ，i=1,2,i=1,2,m,m 若若 f(X)f(X)，-g-gi i(X)(X)为凸函数，则为凸函数，则(p)

8、(p)称为凸规划。称为凸规划。2 2、性质：、性质：(p)(p)的可行解集的可行解集 R R 是凸集；最优解集是凸集；最优解集 R R*也是凸集。也是凸集。(p)(p)的任何局部最优解均是全局最优解。的任何局部最优解均是全局最优解。若若f(X)f(X)为严格凸函数时，其最优解必唯一。为严格凸函数时，其最优解必唯一。特例特例:线性函数既是凸函数又是凹函数，故线性函数既是凸函数又是凹函数，故 L.P.L.P.为凸规划。为凸规划。六、六、寻优方法概述寻优方法概述：1 1、N.L.P.N.L.P.问题分类问题分类 无约束条件的无约束条件的NLPNLP问题。问题。有约束条件的有约束条件的NLPNLP问题

9、。问题。2 2、寻优方法寻优方法 间接法间接法(解析法解析法)：适应于目标函数有简单明确的数学表达式。：适应于目标函数有简单明确的数学表达式。直接法直接法(搜索法搜索法)：目标函数复杂或无明确的数学表达式。：目标函数复杂或无明确的数学表达式。a.a.消去法消去法(对单变量函数有效对单变量函数有效)：不断消去部分搜索区间，逐步缩小极值点存在的范围。不断消去部分搜索区间，逐步缩小极值点存在的范围。b.b.爬山法爬山法(对多变量函数有效对多变量函数有效)：根据已求得的目标值，判断前进方向，逐步改善目标值。根据已求得的目标值，判断前进方向，逐步改善目标值。9.2 9.2 无约束条件下单变量函数寻优无约

10、束条件下单变量函数寻优一、消去法原理：一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求设要寻求f(X)f(X)的极小值点为的极小值点为 X X*，起始搜索区间为，起始搜索区间为aa0 0,b,b0 0。x x1 1、x x2 2 aa0 0,b,b0 0，且，且x x2 2x x1 1，计算，计算 f(xf(x1 1)和和f(xf(x2 2)，并且比较结果：，并且比较结果：f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的右侧的右侧x x1 1

11、x x2 2f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的左侧的左侧x x1 1x x2 2f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的两侧的两侧x x1 1x x2 2 x x1 1,x,x2 2 均在均在x x*的右侧，的右侧，f(xf(x2 2)f(xf(x1 1)，去掉，去掉xx1 1,b,b0 0，此时，此时x x*aa0 0,x,x1 1 x x1 1,x,x2 2 均在均在x x*的左侧，的左侧，f(xf(x2 2)f(xf(x1 1)，去掉，去掉aa0 0,x,x2

12、 2，此时，此时x x*xx2 2,b,b0 0 x x1 1,x,x2 2 均在均在x x*的两侧，的两侧，f(xf(x2 2)f(xf(x1 1)：a.a.去掉去掉xx1 1,b,b0 0，此时，此时x x*aa0 0,x,x1 1 b.b.去掉去掉aa0 0,x,x2 2，此时，此时x x*xx2 2,b,b0 0 二、黄金分割法二、黄金分割法(0.618(0.618法法)：是一种常用的消去法：是一种常用的消去法 与对分法、与对分法、FibonacciFibonacci法比较，具有计算次数少，过程简单的特点。法比较，具有计算次数少，过程简单的特点。1 1、原理：、原理：LxL-x,xxL

13、Lx 满满足足0LLxx22 解解得得,012 即即有有618.0618034.0251 处处。的的为为黄黄金金分分割割点点，位位于于618.0L,L618.0Lx1 的的对对称称点点。为为112x,L382.0L)1(LLxLx Lx1x2 2 2、取点法则：、取点法则：Lx1x2a0b0L)ab(aLx:0001 取取点点)ab(bxLx00012 f(x f(x2 2)f(x)f(x1 1)，取，取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1 1-(b b1 1-a-a1 1)a1b1x1x2 f(x f(x2 2)f(xf(x

14、1 1)，取，取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a-a1 1)x x2 2=x=x1 1 a1b1x1x2计算计算n n个点后，总缩短率为个点后，总缩短率为 E En n=n-1n-1，可得试点数可得试点数n n。3 3、计算步骤：求函数、计算步骤：求函数f(x)f(x)的极值点的极值点 第一步：取初始区间第一步：取初始区间aa0 0,b,b0 0 x1x2a0b0)ab(ax:0001 取取点点)ab(bx0002 )x(f)x(f21和和计计算算 若求若求f(x)f(x)的极小值点，则的极小值点，则 f(xf(x2 2)f(

15、x)f(x1 1)，取，取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1 1-(b b1 1-a-a1 1)f(x f(x2 2)f(xf(x1 1)，取，取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a-a1 1)x x2 2=x=x1 1 a1b1x1x2a1b1x1x2 若求若求f(x)f(x)的极大值点，则的极大值点，则 f(xf(x2 2)f(x)f(x1 1)，取，取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1

16、1-(b b1 1-a-a1 1)f(x f(x2 2)f(xf(x1 1)，取，取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a-a1 1)x x2 2=x=x1 1 第二步：求区间的缩短率第二步：求区间的缩短率|abab|00kk若若.则则停停止止，得得近近似似极极值值点点否否则则，继继续续缩缩短短区区间间，止止。直直至至满满足足给给定定的的精精度度为为例例 求解求解 f(x)=-18xf(x)=-18x2 2+72x+28+72x+28 的极大值点，的极大值点，0.10.1，起始搜索区间为，起始搜索区间为0,30,3解：用间接法：令解

17、：用间接法：令 f f(x)=-36x+72=0(x)=-36x+72=0，得驻点，得驻点 x=2x=2 又因为又因为f f(x)=-36(x)=-360 0，故，故 x=2 x=2 为为f(x)f(x)的极大值点，的极大值点，f fmaxmax=100=100 用直接法中的黄金分割法：令用直接法中的黄金分割法：令 n-1n-1=，得，得n=1+(lgn=1+(lg)/)/(lg(lg)5.78442)5.78442 约约6 6步即可，计算结果见下表：步即可，计算结果见下表：ka ak kb bk kf(ak)f(bk)pk=bk-akpk/p0 x x1 1k k=ak+pkx x2 2k

18、k=bk-pkf(x x2 2k k)f(x x1 1k k)0032882311.8541.14686.999.62f(x)f(x)x xo o3 3x x1 1x x2 2100f,2x*max*11.146386.9821.8540.6182.2921.85499.62 98.4621.1462.29286.998.461.1460.3821.8541.58496.8999.6231.5842.29296.8998.460.7080.2362.0221.85499.62 99.9941.8542.29299.6298.460.4380.1462.1252.02299.99 98.7251

19、.8542.12599.6299.720.2710.09039.3 9.3 无约束条件下多变量函数寻优无约束条件下多变量函数寻优一、爬山法原理：一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：由以下二部分组成：选定搜索方向；选定搜索方向；在选定的方向上爬山搜索。在选定的方向上爬山搜索。二、变量轮换法二、变量轮换法(或降维法或降维法):):选择与坐标轴平行的方向为搜索方向选择与坐标轴平行的方向为搜索方向 设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)，极值

20、点存在的区间为，极值点存在的区间为 x x1 1*aa1 1,b,b1 1，x x2 2*aa2 2,b,b2 2，x xn n*aan n,b,bn n 1 1、原理：从起点、原理：从起点 X X(0)(0)出发，沿平行于出发，沿平行于 x x1 1 轴的方向轴的方向P P(1)(1)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在该方向在该方向P(1)P(1)上近似极值点上近似极值点 X X(1)(1)；从点从点 X X(1)(1)出发，沿平行于出发，沿平行于 x x2 2 轴的方向轴的方向P P(2)(2)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在该方向在该方向P(

21、2)P(2)上近似极值点上近似极值点 X X(2)(2)；从点从点 X X(2)(2)出发，照此交替进行下去，直至满足给定的精度出发，照此交替进行下去，直至满足给定的精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|2 2、算法步骤：、算法步骤：设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2)，极值点存在的区间为，极值点存在的区间为x x1 1*aa1 1,b,b1 1，x x2 2*aa2 2,b,b2 2 第一步：从第一步：从 X X(0)(0)=(x=(x1 1(0)(0),x,x

22、2 2(0)(0)T T出发出发 先固定先固定x x1 1=x=x1 1(0)(0):求以求以x x2 2为单变量的目标函数的极值点，为单变量的目标函数的极值点，得得 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1)T T ，S S(1)(1)=f(X=f(X(1)(1)再固定再固定x x2 2=x=x2 2(1)(1):求以求以x x1 1为单变量的目标函数的极值点，为单变量的目标函数的极值点，得得 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T ，S S(2)(2)=f(X=f(X(2)(2)此时此时S S(2)(2)优于优于S

23、S(1)(1)，且搜索区间缩短为，且搜索区间缩短为x x1 1*x x1 1(2)(2),b,b1 1，x x2 2*x x2 2(1)(1),b,b2 2 第二步：如此交替搜索，直至满足给定精度第二步：如此交替搜索，直至满足给定精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x

24、-10 x1 1-4x-4x2 2+60+60 的极小值点，的极小值点，=0.01=0.01解：设起始点解：设起始点 X X(0)(0)=(0,0)=(0,0)T T，用变量轮换法，用变量轮换法计算：计算：先固定先固定x x1 1=x=x1 1(0)(0)=0:=0:则则 f(0,x2)=x22-4x2+60，寻优得寻优得 x x2 2(1)(1)=2=2 于是于是 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1)T T=(0,2)=(0,2)T T ，S S(1)(1)=f(X=f(X(1)(1)=56)=56 再固定再固定x x2 2=x=x2 2(1)(1)=2

25、:=2:则则 f(x1,2)=x12-12x1+56，寻优得寻优得 x x1 1(2)(2)=6=6 于是于是 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T=(6,2)=(6,2)T T ，S S(2)(2)=f(X=f(X(2)(2)=20)=20 如此交替搜索，直至满足给定精度如此交替搜索，直至满足给定精度 =0.01=0.01 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|0.01 0.01 或或|S|S(k)(k)-S-S(k-1)(k-1)|0.010.01 最后得极小点最后得极小点 X X*=(8,6)=(8,6)

26、T T，f(Xf(X*)=8)=8o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2计算结果见下表：计算结果见下表：8)X(f,)6,8(X*T*k固定的固定的x xi i单变量的目标函数单变量的目标函数f(xj)求得极点求得极点xj目标值目标值S S(k)(k)|S|S(k)(k)-S S(k-1)(k-1)|12345678x x1 1=x=x1 1(0)(0)=0=0 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=

27、x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1 1=x=x1 1(6)(6)=7.88=7.88x x2 2=x=x2 2(7)(7)=5.94=5.94f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10 x2+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.50 x x2 2

28、=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1 1=x=x1 1(6)(6)=7.875=7.875x x2 2=x=x2 2(7)(7)=5.94=5.94x x1 1=x=x1 1(8)(8)=7.97=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088o ox x1 1X X(0)(0)X X(1)(1)

29、X X(2)(2)X X(3)(3)X X(4)(4)x x2 2缺点缺点：很大程度上取决于目标函数性质。：很大程度上取决于目标函数性质。目标函数等高线的性质很重要。目标函数等高线的性质很重要。道路迂回曲折，多次变换方向，道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。收敛速度慢。故不是一个有利方向。三、一阶梯度法三、一阶梯度法(最速下降或上升法最速下降或上升法):):选择负梯度方向为搜索方向选择负梯度方向为搜索方向 设求设求 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)的极值点。的极值点。1

30、1、原理：从起点、原理：从起点 X X(0)(0)出发，沿某个有利方向出发，沿某个有利方向 P P(0)(0)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在在 P P(0)(0)方向近似极小点方向近似极小点 X X(1)(1)；从点从点 X X(1)(1)出发，沿某个新有利方向出发，沿某个新有利方向 P P(1)(1)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在在 P P(1)(1)方向近似极小点方向近似极小点 X X(2)(2)；从点从点 X X(2)(2)出发，照此进行下去，直至满足给定的精度出发，照此进行下去，直至满足给定的精度 为止为止|f(X|f(X(k)(k)

31、-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|2 2、算法步骤：设求、算法步骤：设求 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2)的极值点。的极值点。第一步：从给定起点第一步：从给定起点 X X(0)(0)出发出发 )0(2)0(1)0()0(gg)X(fG:.a 计计算算该该点点梯梯度度|G|GE:.b)0()0()0(计计算算该该梯梯度度的的单单位位方方向向为为一一维维搜搜索索方方向向，的的反反方方向向以以)0()0()0(EPE.c :h)0(使使得得长长在在此此方方向向上上寻寻找找最最优优步步)0h(),PhX(fMi

32、n)PhX(f)h(J)0()0(h)0()0()0()0()0()0()0()1(PhXX.d 求求得得新新点点 第二步：从点第二步：从点 X X(1)(1)出发，照此进行下去，直至满足给定的精度出发，照此进行下去，直至满足给定的精度 为止为止|f(X|f(X(k+1)(k+1)-f(X-f(X(k)(k)|)|或或|G|G(k)(k)|例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 的极小值点，的极小值点，=0.1=0.18)X(f,)6,8(X:*T*最最后后得得极极小小值值点

33、点为为:00 x)0(出出发发从从起起点点 解解:4104xx210 xx2gg)X(fG:.a)0(X1221)0(2)0(1)0()0(计计算算该该点点梯梯度度 37.093.0|G|g|G|g|G|GeeE:.b)0()0(2)0()0(1)0()0()0(2)0(1)0(计计算算该该梯梯度度的的单单位位方方向向为为一一维维搜搜索索方方向向的的反反方方向向以以 37.093.0EPE.c)0()0()0(:h)0(使使得得长长在在此此方方向向上上寻寻找找最最优优步步)h37.0,h93.0(fMin)PhX(fMin)PhX(f)h(Jh)0()0(h)0()0()0()0(21946.

34、8h,0dh)h(dJ)0(得得令令 05.363.7PhXX.d)0()0()0()1(求求得得新新点点 从点从点 X X(1)(1)出发，照此进行下去，直至满足给定的精度出发，照此进行下去，直至满足给定的精度 =0.1=0.1 为止为止|f(X|f(X(k+1)(k+1)-f(X-f(X(k)(k)|)|0.1 0.1 或或|G|G(k)(k)|0.10.1 6078.106577.02 hh计算结果见下表：计算结果见下表：8f,)6,8(x*maxT*缺点缺点：搜索效果比变量轮换法快，但愈接近极值：搜索效果比变量轮换法快，但愈接近极值 点，步长愈小，目标值改进愈小。点，步长愈小，目标值改

35、进愈小。当遇到强交互作用时，不是有效的方法当遇到强交互作用时，不是有效的方法;当遇到山脊时，会慢慢爬行。当遇到山脊时，会慢慢爬行。在远离极点时，收敛速度较快在远离极点时，收敛速度较快;在极点附近，收敛速度不快。在极点附近，收敛速度不快。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.9

36、288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026)k(1x)k(2x)k(1g10 xx221 )k(2g4xx212|G|)k(|G|ge)k()k(11|G|ge)k()k(22)k(h)X(f)k()X(f|)1k(|)X(f)k(o ox x1 1x x(0)(0)x x(1)(1)x x(2)(2)X X(3)(3)x x2 2四、共轭梯度法四、共轭梯度法:选择共轭方向为搜索方向选择共轭方向为搜索方向 问题的提出：在极值点附近，如何加快收敛速度，问题的提出：在极值点附近，如何加快收敛速度

37、，须对函数在极值点附近的性质进行研究。须对函数在极值点附近的性质进行研究。设有设有n n维目标函数维目标函数 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n),),在极值点在极值点X X*附近展开成泰勒级数：附近展开成泰勒级数：XHX21X)X(f)X(f)X(fTT*XHX21)X(fT*XXXX)X(fH 处处的的海海赛赛矩矩阵阵，在在点点为为其其中中近近似似于于一一个个二二次次函函数数。附附近近在在极极值值点点说说明明,X)X(f*特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同心特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同

38、心 椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。o ox x1 1X X(0)(0)P P(0)(0)X X(0)(0)X X(2)(2)X X(1)(1)x x2 2P P(0)(0)P P(1)(1)=X=X(2)(2)-X-X(1)(1)P P(1)(1)与与P P(0)(0)共轭共轭0PHP)0(T)1(故：在极值点附近，沿搜索方向故：在极值点附近，沿搜索方向P P(0)(0)上巳得到一个上巳得到一个 切点切点X X(1)(1)，则只要得出通过极值点的连线方向，则只要得出通过极值点的连线方向 P P(1

39、)(1),在此方向上寻优在此方向上寻优,可一步直达极值点。可一步直达极值点。而这个连线方向而这个连线方向P P(1)(1)是上一次搜索方向是上一次搜索方向P P(0)(0)的的 共轭方向。共轭方向。共轭方向的定义：共轭方向的定义：1 1、定义：设、定义：设 X,Y X,Y 是是n n维向量空间维向量空间E En n中两个向量，中两个向量，A A 为为n nn n对称正定矩阵，对称正定矩阵，若若 X XT TAY=0 AY=0，则称向量，则称向量X X与与Y Y对于矩阵对于矩阵A A共轭。共轭。特例：若特例：若 A=IA=I，得，得 X XT TY=0Y=0，则称向量，则称向量X X与与Y Y正

40、交。正交。2 2、几何意义：共轭方向是通过极值点的方向。、几何意义：共轭方向是通过极值点的方向。寻优原理：寻优原理：设设n n元函数元函数 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n),),在极值点在极值点X X*附近可用一个二次函数逼近附近可用一个二次函数逼近XHX21X)X(f)X(f)X(fTT*,XHX21XbaTT 其中其中 H H 为为n nn n对称正定矩阵对称正定矩阵TTXHb)X(fX)X(f 特别：对二元二次函数特别：对二元二次函数 S=f(X)=f(xS=f(X)=f(x1 1，x x2 2)从某点从某点X X(0)(0)出发出发,以以P

41、P(0)(0)方向搜索方向搜索,使使f(X)f(X)达到极小值点达到极小值点X X(1)(1),则则:X:X(1)(1)必为该点处等高线的切点必为该点处等高线的切点,P,P(0)(0)为切线方向，为切线方向，且点且点X X(1)(1)的梯度方向的梯度方向 f(Xf(X(1)(1)为该等高线的法线方向，这两个方向正交。为该等高线的法线方向，这两个方向正交。,0P)X(f:)0(T)1(故故0PXHb:)0(T)1(即即 从另一点从另一点X X(0)(0)出发出发,仍以仍以P P(0)(0)方向搜索方向搜索,使使f(X)f(X)达到另一个极小值点达到另一个极小值点X X(2)(2),则则:X:X(

42、2)(2)也必为该点处等高线的切点也必为该点处等高线的切点,P,P(0)(0)为切线方向，为切线方向，且点且点X X(2)(2)的梯度方向的梯度方向 f(Xf(X(2)(2)为该等高线的法线方向，这两个方向正交。为该等高线的法线方向，这两个方向正交。,0P)X(f:)0(T)2(故故0PXHb:)0(T)2(即即0)(:)0()1()2(PHXXT两两式式相相减减得得,XX,XXP)2()1()1()2()1(的的连连线线方方向向和和为为两两切切点点令令 ,0PHP:)0(T)1(则则共共轭轭与与由由定定义义知知)0()1(PP:,P)1(上上的的极极小小点点沿沿方方向向o ox x1 1X

43、X(0)(0)P P(0)(0)X X(0)(0)X X(2)(2)X X(1)(1)x x2 2P P(0)(0)P P(1)(1)=X=X(2)(2)-X-X(1)(1)P P(1)(1)与与P P(0)(0)共轭共轭0PHP)0(T)1(.)X(f的的极极小小点点即即为为故故:对二元二次函数对二元二次函数,只须搜索两个方向只须搜索两个方向P P(0)(0)和和P P(1)(1)就就 可达到极值点可达到极值点 X X*。一般一般:对对n n元二次函数元二次函数,可用不超过可用不超过n n次搜索就可达到次搜索就可达到 极值点极值点 X X*。而而n n元非二次函数在极值点附近可用二次函数逼近

44、。元非二次函数在极值点附近可用二次函数逼近。寻优步骤：寻优步骤：例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 的极小值点。的极小值点。解解为为正正定定对对称称矩矩阵阵，海海赛赛矩矩阵阵 2112x)X(fxx)X(fxx)X(fx)X(fH222122212212有有极极小小点点)X(f ,00 x)0(出出发发从从起起点点 01eeEP)0(2)0(1)0()0(搜搜索索方方向向为为)()()0()0(PhXfhJ 5h,010h2dh)h(dJ)0(得得最最优优步步长长令令,0

45、5PhXX)0()0()0()1(求求得得新新点点35S)1(6010)0,(2 hhhf),()0(2)0(2)0(1)0(1ehxehxf o ox x1 1X X(0)(0)P P(0)(0)X X(1)(1)x x2 2 ,05x)1(出出发发从从新新点点 共共轭轭。与与搜搜索索方方向向为为)0()1(2)1(1)1()1(PeeEP 0ee2112)0,1(PHP:)1(2)1(1)1(T)0(则则有有即即0ee2)1(2)1(1 1e e 2)1(22)1(1 51e)1(1 52e)1(2 5/25/1EP)1()1()520,55(),()()()1(2)1(2)1(1)1(1

46、)1()1(hhfehxehxfPhXfhJ 35518532 hh53h,0518h56dh)h(dJ)1(得得最最优优步步长长令令,68PhXX)1()1()1()2(求求得得新新点点8S)2(,68XX)2(*极极小小点点8SS)2(*o ox x1 1X X(0)(0)P P(0)(0)X X(1)(1)x x2 2P P(1)(1)与与P P(0)(0)共轭共轭0PHP)0(T)1(X X(2)(2)对二元二次函数对二元二次函数,只须两次搜索就可达到极值点只须两次搜索就可达到极值点 X X*,一般一般:对对n n元二次函数元二次函数,可用不超过可用不超过n n次搜索就可达到极值点次搜

47、索就可达到极值点 X X*。而而n n元非二次函数在极值点附近可用二次函数逼近。元非二次函数在极值点附近可用二次函数逼近。适用于一般目标函数的共轭梯度法：适用于一般目标函数的共轭梯度法：1 1、共轭方向的计算问题：须用到目标函数的海赛矩阵、共轭方向的计算问题：须用到目标函数的海赛矩阵H(H(二阶偏导数矩阵二阶偏导数矩阵)，若目标函数为二次函数时，若目标函数为二次函数时，H H 容易求出；容易求出；若目标函数为高次或高维函数时，若目标函数为高次或高维函数时，H H 难以求出，此时共轭方向难以求出。难以求出，此时共轭方向难以求出。2 2、共轭方向的计算方法：、共轭方向的计算方法：F-R F-R 法

48、，由法，由FletcherFletcher和和ReevesReeves提出，提出，可避免海赛矩阵可避免海赛矩阵 H H 的计算，方便地确定共轭方向，简单有效。的计算，方便地确定共轭方向，简单有效。,XHX21Xba)X(f:nTT 元元二二次次函函数数设设目目标标函函数数为为)0(X起起点点为为的的共共轭轭方方向向，次次迭迭代代中中要要寻寻求求的的关关于于为为HiP,P,P)i()1()0(ji,0PHP:)i(T)j(则则有有.X,X,X)1i()2()1(似似极极小小点点为为沿沿这这些些方方向向求求得得的的近近,XHb)X(fG:)i()i()i(则则有有)1i()1i()1i(XHb)X

49、(fG X)PhX(H)XX(HGG:)i()i()i()i()i()1i()i()1i(于于是是)i()i(PHh 0)()(:)()()()()()()()1()(）（从从而而iTjiiiTjiiTjPHPhPHhPGGP,0)GG(P:)i()1i(T)j(即即,2,1,0,;jiji 3 3、搜索过程：、搜索过程：从从X X(0)(0)出发：出发：)X(,0)X(G)X(fP)0()0()0()0(巳巳为为极极值值点点否否则则搜搜索索方方向向为为 )PhX(fMin)h(J:h)0()0(h)0()0(使使求求步步长长)0()0()0()1(PhXX 求求得得新新点点 从从X X(1)

50、(1)出发：出发：,PGP)0()0()1()1(搜搜索索方方向向为为共共轭轭应应与与)0(P为为上上次次搜搜索索方方向向，其其中中)(:)0()0()0(XfGP 处处的的梯梯度度方方向向，为为本本次次点点)1()1()1()(XXfG ;X)1(处处的的法法线线方方向向即即点点:)0(正正交交它它与与 P:PP)0()1()0(共共轭轭与与使使得得下下面面确确定定系系数数 ,0)GG(P)0()1(T)1(0)(:)0()1()0()0()1(GGGGT 即即,0GGGG:)0(T)0()0()1(T)1(得得)0(T)0()1(T)1()0(GGGG:即即)0()0(T)0()1(T)1