无约束优化的间接搜索法课件

1、机械优化设计太原科技大学张学良第1页，共40页。第五章 无约束优化的间接搜索法 间搜索法是指搜索方向S(k)的构建利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法。 X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , )第2页，共40页。 基本思想 5.1 梯度法（最速下降法、负梯度法） 利用负梯度方向作为迭代计算的搜索方向，即S(k) = f (X(k) ) 或 S(k) = f (X(k) )/| f (X(k) ) | 迭代计算公式 X (k+1)=X (k) + (k) f (X(k) )或 X (k+1)=X (k

2、) + (k) f (X(k) )第3页，共40页。 举例： 用梯度法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T ， X2(0)= 2 2 T。第4页，共40页。 基本思想和基本算法 5.2 牛顿法 在点X(k)的邻域内，用一个二次函数(X) 来近似代替原目标函数，并以 (X ) 的极小点作为原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。第5页，共40页。 f (X) f (X (k) + T f (X (k) (X - X (k) + 0.

3、5 (X - X (k) T 2 f (X (k) (X - X (k)= (X) (X)的极小点应满足： (X)=0 即 f (X (k)+ 2 f (X (k) (X - X (k) =02 f (X (k) (X - X (k) = - f (X (k) 当 2 f (X (k) 正定且有逆阵时，上式两边同时左乘 2 f (X (k) -1， 得X = X (k) - 2 f (X (k) -1 f (X (k)第6页，共40页。 牛顿法的迭代公式为X (k+1) = X (k) - 2 f (X (k) -1 f (X (k) X (k+1)=X (k) + (k) S(k)牛顿方向：

4、S(k) = - 2 f (X (k) -1 f (X (k) 迭代步长：(k) =1 修正牛顿法（又称阻尼牛顿法）的迭代公式为X (k+1) = X (k) - (k) 2 f (X (k) -1 f (X (k) 阻尼因子： (k) 第7页，共40页。 计算步骤及算法框图 1） 任选初始点 X (0) ，给定收敛精度0， k=0； 2） 计算X (k)点的梯度f (X (k)及其模； 3） 检验终止条件： | f (X (k) | ？ 若满足，则输出最优解：X * = X (k)， f * = f (X *) ，并终止迭代计算 ； 否则，继续下一步迭代计算；第8页，共40页。 4）计算X

5、(k)点的海赛矩阵2 f (X (k)及其逆矩阵2 f (X (k) -1 5）沿牛顿方向S(k) = - 2 f (X (k) -1 f (X (k)进行一维搜索，求最佳步长(k)； 6）令X (k+1)=X (k) + (k) S(k) ，并令k k+1，转2），重复上述迭代计算过程。第9页，共40页。举例： 用牛顿法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T ， X2(0)= 2 2 T。 解： f (X) = 2x1 8x2 T2 f (X)= 00 82 f (X) -1 =0.5 00 0.125f (X1(0) ) = 0 0

6、 Tf (X2(0) ) = 4 16 TX1(1)= X1(0) - 2f (X1(0)-1 f (X1(0) ) = 0 0 T - 0.5 00 0.125 0 0 = 0 0 T 第10页，共40页。X2(1)= X2(0) - 2f (X2(0)-1 f (X2(0) ) = 2 2 T - 0.5 00 0.125 4 16 = 0 0 T 可见，X2(1)= X1(0) = 0 0 T 就是目标函数的理论极小点，仅仅迭代了一次，与初始点的选择无关。 由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在每次迭代计算时都要计算

7、目标函数的海赛第11页，共40页。矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法所需要的存储量是很大的。 若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。第12页，共40页。 基本思想5.3 共轭梯度法 共轭梯度法属于共轭方向法中的一种方法。它是利用目标函数在迭代点X(k)的梯度来构造共轭搜索方向的，具有二次收敛性。 共轭梯度法搜索的第

8、一步沿负梯度方向，以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向第13页，共40页。 共轭梯度法共轭搜索方向的生成 考虑二次函数 f (X) = 0.5 XT H X + BT X + C 从 X(k) 出发，沿H的某一共轭方向S(k)作一维搜索得到 X(k+1)，即 X(k+1) X(k) = (k) S(k) （1）将f (X)在 X(k) 和 X(k+1)两点处的梯度表示并记作 g(k) = f (X(k) ) = H X(k) + B （2） g(k+1) = f (X(k+1) ) = H X(k+1） + B （3）第14页，共

9、40页。（3）-（2）得 g(k+1) g(k) = H ( X(k+1) X(k) )= (k) H S(k) （4）（4）式两边同时左乘S(j) T，有S(j) Tg(k+1) g(k) = (k) S(j) TH S(k) = 0 若S(j)和S(k)关于H共轭，则有S(j) T H S(k) = 0即 S(j) T g(k+1) g(k) = 0 （5） 式（5）就是共轭方向与梯度之间的关系。它表明沿方向S(k) 进行一维搜索，其终点X(k+1)与始点X(k)梯度之差(g(k+1)g(k)与 S(k) 的共轭第15页，共40页。方向S(j)与正交。共轭梯度法就是利用这个性质做到不必计算

10、矩阵H就能求得共轭方向的。 1）设初始点X(0) ，第一个搜索方向S(0)取X(0)点的负梯度方向 -g(0)。即 S(0) = -g(0) 沿S(0)进行一维搜索，得 X(1) = X(0) + (0) S(0)，并计算X(1)点的梯度 g(1) 。 那么， g(1)与S(0) 有什么关系呢？X(0)g(1)-g(0)X(1) 二者正交，即 g(1)TS(0)=0 或 S(0)Tg(1) =0 因此，S(0)与g(1)构成平面正交系。第16页，共40页。 2）在S(0)与g(1)构成的平面正交系中求S(0)的共轭方向S(1)，以此作为下一步迭代计算的搜索方向。取S(1)为S(0)与g(1)的

11、线性组合，即 S(1) = -g(1) + (0)S(0) 其中，(0)为待定常数，可以利用共轭方向与梯度之间的关系求得。 由 S(1) T g(1) g(0) = 0 有 -g(1) + (0)S(0) T g(1) g(0) = 0 展开，得- g(1)Tg(1) +g(1)Tg(0)+(0)S(0)Tg(1) - (0)S(0)Tg(0) = 0 第17页，共40页。所以 - g(1)Tg(1) - (0)S(0)Tg(0) = 0所以 (0) = - g(1)Tg(1) / S(0)Tg(0) = g(1)Tg(1) / g(0)Tg(0) = |g(1)|2 / |g(0)|2S(1

12、) = -g(1) + |g(1)|2 / |g(0)|2 S(0) 沿S(1)进行一维搜索，得 X(2) = X(1) + (1) S(1)，并计算X(2)点的梯度 g(2) ，则有S(1)Tg(2) =0第18页，共40页。 故有 -g(1) + (0)S(0) T g(2) = 0 （6） 因为S(0)和S(1)共轭，所以有S(0) T g(2) g(1) = 0 因为 S(0) T g(1) = 0 所以 S(0) T g(2) = 0 即 g(2) 与g(0)正交。 所以 S(0) T g(2) = 0 由式（6）得 g(1) T g(2) = 0 可见， g(0)、g(1) 、g(

13、2)构成一个空间正交系。第19页，共40页。 3）在g(0)、g(1)、g(2)构成的空间正交系中求与S(0)及S(1)均共轭的方向S(2)，以此作为下一步迭代计算的搜索方向。仍取S(2)为g(0)、g(1)、g(2) 的线性组合，即 S(2) = -g(2) + (1) g(1) + (0) g(0) 其中， (1) 、 (0) 为待定常数，可以利用共轭方向与梯度之间的关系求得。 S(2) T g(1) g(0) = 0 S(2) T g(2) g(1) = 0第20页，共40页。 即 -g(2) + (1) g(1) + (0) g(0) T g(1) g(0) = 0 -g(2) + (

14、1) g(1) + (0) g(0) T g(2) g(1) = 0 所以 (1)g(1)Tg(1) - (0) g(0)T g(0) = 0 -g(2)T g(2) - (1)g(1)Tg(1) = 0 令 (1) = - (1) 得 (1) = - (1) = g(2)T g(2)/ g(1)Tg(1) = |g(2)|2 / |g(1)|2 (0) = (1) g(1)T g(1)/ g(0)Tg(0) = - (1) (0)第21页，共40页。 因此 S(2) = -g(2) + (1) g(1) + (0) g(0) = -g(2) - (1) g(1) - (1) (0) g(0)

15、 = -g(2) + (1) - g(1) - (0) g(0) = -g(2) + (1) S(1) 故 S(2) = -g(2) + |g(2)|2 / |g(1)|2 S(1) 再沿S(2) 进行一维搜索，得 X(3) = X(2) + (2) S(2)，如此继续下去，可以求得共轭方向的递推公式为 S(k+1) = -g(k+1) + |g(k+1)|2 / |g(k)|2 S(k)(k = 0, 1, 2, , n-1)第22页，共40页。 沿着这些共轭搜索方向一直搜索下去，直到最后迭代点处梯度的模小于给定的允许值为止。若目标函数为非二次函数，经n次搜索还未达到最优点时，则以最后得到的

16、点作为初始点，重新计算共轭方向，一直到满足精度要求为止。 共轭梯度法的计算步骤及算法框图 1）给定初始点X(0)及收敛精度0，k=0； 2）取 S(0) = f (X(0) )；第23页，共40页。 3） X(k+1) = X(k) + (k) S(k) ( k = 0, 1, 2, , n) (k) 为一维搜索所得的最佳步长。 4） 判断 | f (X(k+1) ) | ? 若满足，则输出 X * = X(k+1) 和 f * = f (X * ) 否则，转下一步； 5） 判断 k+1=n ? 若 k+1=n ，令X(0) = X(k+1) ，转 2）； 若 k+1n ，则计算 (k) =

17、| f (X(k+1) ) |2 / | f (X(k) ) |2第24页，共40页。 S(k+1) = - f (X(k+1) ) + (k) S(k) 并令 k k+1，转3）。 1）尽管理论上可以证明目标函数为n维正定二次函数时，共轭梯度法只需要n次迭代就可以达到最优点，但由于计算机的舍入误差，实际计算往往要多进行若干次才能得到满足精度要求的结果；而对于一般的目标函数，迭代次数将更多。 关于共轭梯度法的说明第25页，共40页。 2）由于n维设计空间中最多只能有n个线性无关的向量，所以n维优化问题的共轭方向最多只有n个。因此，共轭梯度法进行n步搜索后，若仍不满足精度要求，继续产生共轭方向S

18、(n+1)进行迭代搜索是没有意义的（效果很差），而应令X(0) = X(n) ，重新开始新一轮的共轭梯度法迭代搜索。实践证明，这样处理一般都可以取得较好的效果。第26页，共40页。举例： 用共轭梯度法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X(0)= 2 2 T， =0.01 。 解： f (X) = 2x1 8x2 TS(0) = -f (X(0) ) = -4 -16 T X(1)= X(0) - (0)f (X(0) )=2 2 T - (0) 4 16T = 2 - 4(0) 2 - 16(0) T f (X(1) = (2 - 4(0)2 +4 (2 - 16(0)2据 df (X(1)/d(0) = 0 得 (0)=0.13076923 X(1)=1.476923077 -0.09230768 T 第27页，共40页。f (X(1) ) = 2.953846154 -0.73846144 T(0) = | f (X(1) ) |2 / | f (X(0) ) |2 =0.034082837 S(1) = - f (X(1) ) + (0) S(0) = - 2.953846154 -0.73846144 T + 0.034