《最优化方法》课程教学资源（题解）第三次 梯度法和共轭梯度法

梯度法和共轭梯度法 无约束最优化问题 2.梯度法 3.共轭梯度法

梯度法和共轭梯度法 1. 无约束最优化问题 2. 梯度法 3. 共轭梯度法

无约束最优化问题 无约束最优化问题 min f(x) s,t.x∈Rn 其中f(x)有一阶连续偏导数。 解析方法:利用函数的解析性质构造迭代公式使之收敛到最优解

一. 无约束最优化问题 无约束最优化问题 n s t x R f x . .  min ( ) 其中f (x)有一阶连续偏导数。 解析方法：利用函数的解析性质构造迭代公式使之收敛到最优解

梯度法(最速下降法) 迭代公式:x4+1=xk+41dk 如何选择下降最快的方向? vf(xk)函数值增加最快的方向 函数值下降的方向 7(x)函数值下降最快的方向

二. 梯度法（最速下降法） 迭代公式： k k k k x = x +  d +1 如何选择下降最快的方向？ ( ) k f x ( ) k − f x 函数值下降最快的方向 函数值增加最快的方向 函数值下降的方向 k x

梯度法(最速下降法) 1搜索方向:d=-Vf(x),也称为最速下降方向; 2搜索步长:λ取最优步长即满足∫(x+λd)=minf(x+d) 梯度法算法步骤: 1给定初始点x1∈R",允许误差E>0,令k=1 2计算搜索方向d=-V∫(x); 3若dk‖≤,则停止计算,x为所求极值点否则,求最优步长2 使得∫(x+4d)=min∫(x4+adk) 4令xA=x4+d,令k:=k+1,转2

梯度法（最速下降法）： 1. 搜索方向：d k = − f (x k ) ,也称为最速下降方向； 2.搜索步长: k 取最优步长, 即满足 f (x k k d k ) min f (x k d k )。  + = + 梯度法算法步骤： 1. 给定初始点 x 1  R n ,允许误差  0, 令k = 1。 2. ( ); k k 计算搜索方向 d = − f x k k k 3.若|| d ||  ,则停止计算，x 为所求极值点；否则，求最优步长 使得 f (x k k d k ) min f (x k d k )。  + = + 4.令 x k+1 = x k + kd k ,令k := k + 1,转2

例用最速下降法求解:minf(x)=x2+3x2,设初始点为x2=(2,1), 求迭代一次后的迭代点x2。 解::Vf(x)=(2x1,6x2) d=-Vf(x2)=(-4,-6) .x+ad=(2-4,1-61) 令p(4)=∫(x2+Mn1)=(2-4x)2+3(1-6元)2 求解 mIn qp(1) 13 令q(孔)=-8(2-44)-36(1-6元)=0→M62 36-8 x2=x+1d=( 3131

. : min ( ) 3 , (2,1) , 2 1 2 2 1 T 例 用最速下降法求解 f x = x + x 设初始点为x = 求迭代一次后的迭代点 x 2 。 解： ( ) ( 2 ,6 ) , 1 2 T  f x = x x ( ) ( 4, 6) . 1 1 T  d = −f x = − − ( 2 4 ,1 6 ) . 1 1 T  x + d = −  −  令 () = f (x 1 + d 1 ) = (2 − 4) 2 + 3(1 − 6) 2 ， min ()  求解令() = −8( 2 − 4) − 36(1 − 6 ) = 0 62 13  1 = T x x d ) 31 8 , 31 36 ( 1 1 2 1 −  = +  =

收敛性 性质.设f(x)有一阶连续偏导数,若步长λ满足 f(x+n d )=min f(+nd) 则有Vf(xx+1d)d=0。 证明:令g(4)=f(xk+d),所以 o()=Vf(x+ad")d ∫(xx+A1d)=min∫(x+a) g(λ)=Vf(x+x2d)d=0 注:因为梯度法的搜索方向d+=-f(x4+1d),所以 (dk+)d4=0→d中1⊥dk

收敛性 ( ) min ( ) k k k k k f x  d f x d  + = + 则有 f (x k + kd k ) T d k = 0。 性质. 证明：令 () = f (x k + d k )，所以 ( ) ( ) . k k T k   = f x + d d ( ) min ( ) k k k k k f x  d f x d   + = +  ( ) =  ( + ) = 0 . k T k k k  k f x  d d 设 f (x) 有一阶连续偏导数，若步 长 k 满 足 注： (d k+1 ) T d k = 0  d k+1 ⊥ d k 。 因为梯度法的搜索方向 d k+1 = − f (x k + kd k )，所以

锯齿现象 在极小点附近,目标函数可以用二次函数近似其等值面近似 椭球面 注最速下降方向反映了目标函数的一种局部性质。它只是 局部目标函数值下降最快的方向 最速下降法是线性收敛的算法

锯齿现象 在极小点附近，目标函数可以用二次函数近似，其等值面近似 椭球面。1 x * x 2 x 3 x 最速下降方向反映了目标函数的一种局部性质。它只是 局部目标函数值下降最快的方向。 注  最速下降法是线性收敛的算法

共轭梯度法 1.共轭方向和共轭方向法 定义设A是nxn的对称正定矩阵,对于R中的两个非零向量d1和d2 若有d1Ad2=0,则称d和d2关于A共轭 设d2,d2,…,d是R"中一组非零向量,如果它们两两关于A 共轭,即dAd=0,i≠j,i,=1,2,…,k。 则称这组方向是关于A共轭的,也称它们是一组A共轭方向 注:如果A是单位矩阵,则 0→ d1⊥ 共轭是正交的推广

三. 共轭梯度法 1. 共轭方向和共轭方向法 定义 若有 d Ad ，则称d 和d 关于A共轭。 T1 2 1 2 = 0 d d d R A 设 1 , 2 ,  , k 是 n 中一组非零向量，如果它们两两关于 共轭，即 d Ad j i j i j k。 Ti = 0,  , , = 1,2,  , 则称这组方向是关于A共轭的，也称它们是一组A共轭方向。 注： 0 0 1 2 1 2 d  I  d =  d  d = T T 1 2  d ⊥ d 共轭是正交的推广。 设 A是 n n的对称正定矩阵，对于R n中的两个非零向量 d 1 和d 2 ， 如果A是单位矩阵，则

定理1.设A是n阶对称正定矩阵,1,d2,…,d是k个A共轭的非零 向量,则这个向量组线性无关。 证明设存在实数a1,a2,…,ak,使得 k ∑a;d2=0. 上式两边同时左乘dA,则有 ∑c;dAd=0, 因为dl,d2,…,d是k个A共轭的向量,所以上式可化简为 a: d/ ad=0 因为dJ≠0,而A是正定矩阵,所以Ad>0, 所以 =0,j=1,2,…,k 因此d1,d2,…,d线性无关

设 A是 n阶对称正定矩阵，d 1 ,d 2 ,  ,d k 是k个 A共轭的非零 向量，则这个向量组线性无关。 定理1. 证明 设存在实数1 , 2 ,  , k ，使得 0, 1  = = k i i  id 上式两边同时左乘d A，则有 Tj 0, 1  = = k i i Tj  id Ad 因 为d 1 ,d 2 ,  ,d k 是k个 A共轭的向量，所以上式可化简为 = 0 . j Tj  j d Ad 因为  0,而 是正定矩阵，所以 j  0， T j j d A d Ad 所以  j = 0, j = 1,2,  ,k。 因此 d 1 ,d 2 ,  ,d k 线性无关

几何意义 设有二次函数 ∫(x)=(x-x)A(x-x) 其中A是nxn对称正定矩阵,x是一个定点 则函数f(x)的等值面(x-x)A(x-x)=c 是以x为中心的椭球面。 由于Vf(x)=A(x-x)=0, 而V2f(x)=A, 因为4正定,所以v2f(x)=A>0, 因此x是f(x)的极小点

几何意义 设有二次函数 ( ) ( ) 2 1 f (x) x x A x x T = − − 其中 A是 n n 对称正定矩阵，x 是一个定点。 则函数 f (x)的等值面 x x A x x c T ( − ) ( − ) = 2 1 是以 x 为中心的椭球面。 由于 f (x) = A(x − x) = 0, ( ) 0, 2 因为A 正定，所以 f x = A  因此 x 是 f (x)的极小点。 x ( ) , 2 而  f x = A