第五章无约束优化的间接搜索法.ppt

机械优化设计,太原科技大学 张学良,第五章 无约束优化的间接搜索法,间搜索法是指搜索方向S(k)的构建利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法。,X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , ),基本思想,§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) + (k) f (X(k) ),举例： 用梯度法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T ， X2(0)= 2 2 T。,基本思想和基本算法,§5.2 牛顿法,在点X(k)的邻域内，用一个二次函数(X) 来近似代替原目标函数，并以 (X ) 的极小点作为原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。,f (X) f (X (k) + T f (X (k) (X - X (k) + 0.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) =0,2 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),牛顿法的迭代公式为 X (k+1) = X (k) - 2 f (X (k) -1 f (X (k),X (k+1)=X (k) + (k) S(k),牛顿方向：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),计算步骤及算法框图,1） 任选初始点 X (0) ，给定收敛精度0， k=0；,2） 计算X (k)点的梯度f (X (k)及其模；,3） 检验终止条件： | f (X (k) | ？ 若满足，则输出最优解：X * = X (k)， f * = f (X *) ，并终止迭代计算 ； 否则，继续下一步迭代计算；,4）计算X (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），重复上述迭代计算过程。,举例： 用牛顿法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X1(0)= 0 0 T ， X2(0)= 2 2 T。,解： f (X) = 2x1 8x2 T,X1(1)= X1(0) - 2f (X1(0)-1 f (X1(0) ),X2(1)= X2(0) - 2f (X2(0)-1 f (X2(0) ),可见，X2(1)= X1(0) = 0 0 T 就是目标函数的理论极小点，仅仅迭代了一次，与初始点的选择无关。,由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在每次迭代计算时都要计算目标函数的海赛,矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法所需要的存储量是很大的。,若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。,基本思想,§5.3 共轭梯度法,共轭梯度法属于共轭方向法中的一种方法。它是利用目标函数在迭代点X(k)的梯度来构造共轭搜索方向的，具有二次收敛性。,共轭梯度法搜索的第一步沿负梯度方向，以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向,共轭梯度法共轭搜索方向的生成,考虑二次函数 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）,（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) 的共轭,方向S(j)与正交。共轭梯度法就是利用这个性质做到不必计算矩阵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)构成平面正交系。,2）在S(0)与g(1)构成的平面正交系中求S(0)的共轭方向S(1)，以此作为下一步迭代计算的搜索方向。取S(1)为S(0)与g(1)的线性组合，即 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,所以 - 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)|2,S(1) = -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,故有 -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(2)构成一个空间正交系。,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,即 -g(2) + (1) g(1) + (0) g(0) T g(1) g(0) = 0 -g(2) + (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),因此 S(2) = -g(2) + (1) g(1) + (0) g(0) = -g(2) - (1) g(1) - (1) (0) g(0) = -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),沿着这些共轭搜索方向一直搜索下去，直到最后迭代点处梯度的模小于给定的允许值为止。若目标函数为非二次函数，经n次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。,共轭梯度法的计算步骤及算法框图,1）给定初始点X(0)及收敛精度0，k=0；,2）取 S(0) = f (X(0) )；,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) = | f (X(k+1) ) |2 / | f (X(k) ) |2,S(k+1) = - f (X(k+1) ) + (k) S(k) 并令 k k+1，转3）。,1）尽管理论上可以证明目标函数为n维正定二次函数时，共轭梯度法只需要n次迭代就可以达到最优点，但由于计算机的舍入误差，实际计算往往要多进行若干次才能得到满足精度要求的结果；而对于一般的目标函数，迭代次数将更多。,关于共轭梯度法的说明,2）由于n维设计空间中最多只能有n个线性无关的向量，所以n维优化问题的共轭方向最多只有n个。因此，共轭梯度法进行n步搜索后，若仍不满足精度要求，继续产生共轭方向S(n+1)进行迭代搜索是没有意义的（效果很差），而应令X(0) = X(n) ，重新开始新一轮的共轭梯度法迭代搜索。实践证明，这样处理一般都可以取得较好的效果。,举例： 用共轭梯度法求目标函数 f (X) = x12 + 4x22 的无约束最优解。初始点X(0)= 2 2 T， =0.01 。,解： f (X) = 2x1 8x2 T,S(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,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.034082837 -4 -16 T = -3.09017751 0.193136016 T,X(2)= X(1) +(1) S(1) = 1.476923077 -0.09230768 T + (1) -3.09017751 0.193136016 T,据 df (X(2)/d(1) = 0 得 (1)=0.477941179,X(2)=6×10-9 -2.4×10-8 T 0 0T,| f (X(2) ) | 0 =0.01,故最优解为 X *= X(2) = 0 0T f (X *) = 0,DFP变尺度法的基本思想,§5.4 变尺度法,它是基于牛顿法的思想，并对其做了重要的改进后的一类方法。它不需要计算二阶导数矩阵及其逆阵，又比共轭梯度法有更好的收敛性，对较高维数的无约束优化问题有明显的优越性。,梯度法远离最优点时，对突破函数的非二次性极为有利（即收敛速度快），但迭代点接近最优点时收敛速度慢；而牛顿法则正好相反，它具有二次收敛性，接近最优点时,收敛极快，但它需要计算海赛矩阵及其逆阵，计算工作量比梯度法大为增加。若能构造一种算法，它兼有梯度法和牛顿法各自的优点，那么这种算法一定比梯度法和牛顿法更有效，于是便产生了变尺度法。,梯度法： X (k+1) =X (k) - (k) f (X (k) 牛顿法：X (k+1) =X (k) - (k)2 f (X (k) -1 f (X (k),变尺度法的迭代公式 : X (k+1) =X (k) - (k) A(k) f (X (k),A(k) 为人为构造的对称方阵，称为构造矩阵， 它迭代点位置的变化而变化。,变尺度法的迭代公式 : X (k+1) =X (k) - (k) A(k) f (X (k),若在迭代初始时，A(k) = I，则上式与梯度法的迭代公式相同，可使迭代点远离最优点时收敛速度加快。以后随着迭代过程的进行，不断地修正构造矩阵，使它逐步逼近函数在迭代点X(k)处的海赛矩阵的逆阵 2f(X (k)-1，这样当迭代点逼近最优点时，迭代搜索方向就趋于牛顿方向，因此收敛速度极快。,变尺度法的搜索方向为: S (k) = - A(k) f (X (k) 称为逆牛顿方向。,构造矩阵可看成是搜索过程中的一种尺度变换矩阵，它从一次迭代到另一次迭代是变化的，所以又称为变尺度矩阵。要实现上述变尺度法的基本思想，关键在于如何产生变尺度矩阵。,DFP变尺度法中变尺度矩阵系列的产生, 变尺度矩阵A(k)是随迭代点X(k)变化而变化，,初始变尺度矩阵A(0)需预先选定，且必须是正定对称矩阵，一般取 A(0)=I。, A(k)是一个序列，记为 A(k) （k = 0, 1, 2, ）,假定在迭代过程中已构造得到矩阵A(k)，则第(k+1)次迭代所需的变尺度矩阵A(k+1)可用如下简单形式的迭代公式产生。,1）变尺度阵A(k+1)应满足拟牛顿条件,A(k+1) = A(k) +A(k) A(k)为校正矩阵,对于一般二次函数 f (X) = 0.5 XT H X + BT X + C 其梯度记为,g(k) = f (X(k) ) = H X(k) + B （2） g(k+1) = f (X(k+1) ) = H X(k+1） + B （3）,g(k+1) - g(k) = g(k) = H ( X(k+1) - X(k) )=H X(k),若H 可逆，则由上式可得 H -1 g(k) = X(k),为使A(k)序列最终逼近H -1，则A(k+1)矩阵应满足拟牛顿条件 A(k+1) g(k) = X(k),2） 校正矩阵A(k)的构建,校正矩阵A(k)只依赖于本次迭代的矢量差 X(k) = X(k+1) - X(k) 和 相应的梯度差 g(k) 。,将 A(k+1) = A(k) +A(k) 代入拟牛顿条件，得,（A(k) +A(k)）g(k) = X(k),展开，得 A(k)g(k) + A(k)g(k) = X(k),在DFP算法中，令 A(k) = akukukT + bkvkvkT ak、bk 待定常数， uk、vk n维待定矢量,所以，有 akukukT g(k) + bkvkvkT g(k) = X(k) - A(k)g(k),uk、vk 的取法有多种，这里令,akukukT g(k) = X(k) bkvkvkT g(k) = - A(k)g(k),akukukT g(k) = X(k) bkvkvkT g(k) = - A(k)g(k), ukT g(k) 、vkT g(k)是数量， 令,akukTg(k) = 1 bkvkTg(k) = 1,则 uk= X(k) ak = 1/( X(k)Tg(k) ) vk= - A(k)g(k) bk = -1/( g(k)T A(k)T g(k) ), A(k) 是正定对称矩阵多种，这里令, A(k)T = A(k),故 bk = -1/( g(k)T A(k) g(k) ),于是校正矩阵A(k)为 A(k) =( X(k) X(k)T)/ ( X(k)T g(k) ) - (A(k) g(k) g(k) T A(k) )/ (g(k)T A(k) g(k) ),DFP变尺度法计算步骤及算法框图,1）给定初始点X(0)及收敛精度0，k=0；,2）置 k = 0， A(0)=I ；,3）沿搜索方向 S (k) = - A(k) f (X (k)作一维搜索，得 X (k+1) =X (k) + (k) S (k) ；,4）计算 g(k+1) = f (X(k+1) ) 若 |g(k+1)| ，则输出最优解： X * = X (k+1) f * = f (X *) X (k) 否则，转 5）；,5）若 k = n，则 X (0) = X (k+1) ，转 2）； 若 k n，转 6）；,6）计算 X(k) = X(k+1) - X(k) g(k) = g(k+1) - g(k) A(k) =( X(k) X(k)T)/ ( X(k)T g(k) ) - (A(k) g(k) g(k) T A(k) )/ (g(k)T A(k) g(k) ) A(k+1) = A(k) +A(k) 令 k k+1，转3）。,