求解无约束优化的基本思路 搜索方向的选择 1最速下降法 暂不考虑搜索步 基本思想在中某一点,确定一个搜索方向 梯度法) 长,可设a=1 及沿该方向的移动步长,得到使目标函数下降的新的点 将∫(x-)在x*点作泰勒展开,只保留一阶项, 选代 Step 1初始化:初始点,终止准则等 步辈 f(x)=f(x+d)=f(x)+Vf(r)d Step2选代改进:方向dk,步长ak 下降方向 vf(x)d<o dk f(x)<f(r) 最速下降方向 f(x2)(负梯度方向) Step3终止检验:得到近优解或k+1=k转2 选代改进格式 x-vf(x) 选择daxk使∫下降更快→不同算法 算法特点初始阶投改进较快,最优解附近改进较慢 2 Newton方法 3拟 Newton方法 将八x+)在x点作泰勒展开至二阶项,用d替代d 目的不计算 Hessian阵,克服病态、不正定、计 f(x )=f(x+d)=f(x)+Vf(x )d+od'V f(x )d 算复杂等缺陷,同时保持收做较快的优点 求d使(+)极小右端对导数为0=4)+= 思路回顾解方程组F(x)=0的拟牛顿法 牛顿方程Vf(x2)d=-Vf(x2) x+=x2F(xF(2)口x+1=x4-()-F(x 牛顿方向d=-(Vf(x2)vf(x2) 使满足4(xk-x4-)=F(xk)-F(x4- 迭代格式x=x2-(Vf(x2))Vf(x) 用迭代方法A4=Ak-1+△4-1计算A 特点局部2阶收斂;需计算 Hessian阵它可能病态或不正定 比较解F(x)=0x+=x2-{F(x)Fx 优化问题Mmf(x)v(x)相当F(x) F(x)o Vf(x) V2f(x)相当F(xV2不一定正定,构造正定阵G代替ⅴf (学学奖 3拟 Newton方法(续) 3拟 Newton方法(续) 设在第k步,G已得到,=()y1,可计算 31 Davidon- Fletcher-Powell(DFP)公式 k+lk uk HA(NH 记△xk AG=+ (Ar)GAr A"( )-(Ar)G+GAr(4") (△x2) △x2)4y Ax)'A 按照拟牛顿条件 3.2 Broyden- Fletcher- Goldfarb-Shanno(BFGS公式 构造迭代公式Gk+1=Gk+AGk或Hk+1=Hk+MH Mk(4)aAxk(△x)Gk 于是有x+2=x2-H*"vf(x+) THA Ar( M=0+ (Ar)A7△rys3 求解无约束优化的基本思路 基本思想 在 n ℜ 中某一点，确定一个搜索方向 及沿该方向的移动步长，得到使目标函数下降的新的点 迭代 步骤 Step 1 初始化：初始点x0，终止准则等 Step 2 迭代改进：方向d k，步长α k ( ) ( ) k 1 k f x < f x k k k k + x = x + α d +1 Step 3 终止检验：得到近优解或k+1⇒k转2 选择d k ,α k 使 f 下降更快 ⇒ 不同算法 搜索方向的选择 1 最速下降法 （梯度法） 下 降方向 最速下降方向 迭代改进格式 算法特点 初始阶段改进较快，最优解附近改进较慢 k k k k T k k f (x ) f (x d ) f (x ) f (x )d 1 = + = + ∇ + ∇ ( ) < 0 T k k f x d ( ) k k d = −∇f x ( ) k 1 k k x = x − ∇f x + 将 ( ) k +1 f x 在 k x 点作泰勒展开，只保留一阶项，有 暂不考虑搜索步 长，可设αk=1 (负梯度方向) 2 Newton方法 特点 局部2阶收敛;需计算Hessian阵,它可能病态或不正定 将f(xk+1)在xk点作泰勒展开至二阶项，用d替代dk 牛顿方程 牛顿方向 迭代格式 ( ) ( ) 2 k k ∇ f x d = −∇f x f x f x d f x f x d d f x d k k k T k T k ( ) 2 1 ( ) ( ) ( ) ( ) 1 2 = + = + ∇ + ∇ + ( ( )) ( ) k 2 k 1 k d = − ∇ f x ∇f x − ( ( )) ( ) k 1 k 2 k 1 k x = x − ∇ f x ∇f x + − [ ( )] ( ) k 1 k k 1 k x x F x F x + − 比较 = − ′ 的牛顿法 解F ( x) = 0 F ( x) ⇔ ∇f ( x) 求d使f(xk+1)极小⇒右端对d导数为0 ( ) ( ) 0 2 ⇒∇f x +∇ f x d = k k 3 拟Newton方法 目的 不计算Hessian阵，克服病态、不正定、计 算复杂等缺陷，同时保持收敛较快的优点 回顾解方程组 F(x)=0的拟牛顿法 ( ) ( ) ( ) −1 −1 − = − k k k k k k 使A 满足 A x x F x F x k k k k 用迭代方法A A A 计算A −1 −1 = + ∆ 思路 [ ( )] ( ) k 1 k k 1 k x x F x F x + − = − ′ ( ) ( ) k 1 k k 1 k x x A F x + − = − Min f (x) 优化问题 x ∇f ( x)相当 F ( x) f x F x f G f 2 2 2 ∇ ( )相当 ′( ), ∇ 不一定正定，构造正定阵 代替∇ 3 拟Newton方法(续) k k k k k k G = G + ∆G H = H + ∆H 构造 迭代公式 +1 或 +1 按照拟牛顿条件： k k k k k k G ∆x = ∆f ∆x = H ∆f +1 或 +1 , ( ) ( ) k k 1 k k k 1 k ∆x = x − x ∆f = ∇f x − ∇f x 记 + + ( ) k 1 k k k x = x − H ∇f x + 设在第k步, Gk已得到, Hk=(Gk)-1,可计算 ( ) +2 +1 +1 +1 = − ∇ k k k k 于是有 x x H f x 3.1 Davidon-Fletcher-Powell(DFP)公式 k T k k k k k T k k T k k k T k f H f H f f H x f x x H ∆ ∆ ∆ ∆ − ∆ ∆ ∆ ∆ ∆ = ( ) ( ) ( ) ( ) 3 拟Newton方法(续) k T k k k T k k k k T k T k k k T k T k k T k k k x f f x G G x f x f f f x f x G x G ∆ ∆ ∆ ∆ + ∆ ∆ − ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ = + ( ) ( ) ( ) ( ) ( ) ) ( ) ( ) (1 3.2 Broyden-Fletcher-Goldfarb-Shanno(BFGS)公式 k T k k k k k T k k T k k k T k x G x G x x G f x f f G ∆ ∆ ∆ ∆ − ∆ ∆ ∆ ∆ ∆ = ( ) ( ) ( ) ( ) k T k k k T k k k k T k T k k k T k T k k T k k k x f x f H H f x x f x x x f f H f H ∆ ∆ ∆ ∆ + ∆ ∆ − ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ = + ( ) ( ) ( ) ( ) ( ) ) ( ) ( ) (1