第四章 无约束最优化方法
第四章 无约束最优化方法
§4.1最速下降法
§ 4.1 最速下降法
问题提出 问题在点x处沿什么方向d2(x)下降最快? 分析:/(x2+ad)=(x)+gd+0(a4a>0) 考查:gdk= ged cos 显然当cos9=-1时,g4d4取极小值 因此 gk 结论负梯度方向使f(x)下降最快亦即最速 下降方向
问题提出 问题：在点 k x 处，沿什么方向 , k d f (x) 下降最快? 分析： ( + ) = ( )+ + ( )( 0) k k T k k k k f x d f x g d o d 考查： k k k cos T k g d = g d 显然当 cos = −1 时， k T k g d 取极小值． 因此： k k d = −g 结论：负梯度方向使 f (x) 下降最快，亦即最速 下降方向．
最速下降法算法 Step1:给出x∈R",O≤E<<1,k:=0 step2:计算v(x),如果V(xk)川≤e,停 Step3:计算下降方向dk=-gk Sep4:计算步长因子ak step5:令xk1=xk+adk,转步2
最速下降法算法 Step1: 给出 x0 R ,0 1, k := 0 n Step2: 计算 ( ), k f x 如果 ( ) , k f x 停． Step3: 计算下降方向 . dk = −gk Step4: 计算步长因子 . k Step5: 令 , k 1 k k dk x + = x + 转步２
分析设f(x)=xGx+b7x+c是正定二次函数, 由精确的线搜索确定的∝=? dk Gd 特别当:dk=-gA sk6k
分析：设 f (x) x Gx b x c T T = + + 2 1 是正定二次函数, 由精确的线搜索确定的 = ? k k T k k T k k d Gd g d = − 特别当： dk = −gk k T k k T k k g Gg g g =
例1:用最速下降法求解 m/(x)=1x2+9x2 (9,1) 解 G(x)= x=(00) 9 09 =(9,1)go=Vf(x0)=(9,9) 7.2 080 0 0.8 7.2 0 0 2 9×0.8 g1(-1)2×0
例1：用最速下降法求解： ( ) ( ) T f x x x x 9,1 2 9 2 1 min 0 2 2 2 = 1 + = 解： ( ) ( ) ( ) T G x x x x g x 0,0 0 9 1 0 9 * 2 1 = = = ( ) ( ) ( ) T T x0 = 9,1 g0 = f x0 = 9,9 − = − = 0.8 7.2 0 0 0 0 0 1 0 g g Gg g g x x T T − = 7.2 7.2 g1 ( ) − = − = 2 2 2 1 1 1 1 1 2 1 1 0.8 9 0.8 g g Gg g g x x T T
((-1)y O.8),k 分析(1)lm lim k+1 0.8 k 因此:最速下降法是整体收敛的, 且是线性收敛的 (2)两个相邻的搜索方向是正交的 (9,9)d1=-(7.2,-7.2)dba1=0
( ) (0.8) , 1,2, 1 9 = − x = k k k k 分析：(1) lim lim 0.8 1 * * 1 = = − − + → + → k k k k k k x x x x x x 因此：最速下降法是整体收敛的， 且是线性收敛的． (2) 两个相邻的搜索方向是正交的． d0 = −(9,9) d1 = −(7.2,−7.2) d0 d1 = 0 T T T
0 十大 0000 86420246 5
收敛性分析 定理1:设v(x)在L={x∈R(x)≤f(xo) 上存在且一致连续,则最速下降法产生的序列 满足或者对某个k有gk=0,或者f(x)→>-∞, Sk->0. 证明:对于最速下降法=0由以上定理立得
收敛性分析 定理1: 设 f (x) 在 L x R f (x) f (x0 ) n = 上存在且一致连续，则最速下降法产生的序列 满足或者对某个 k 有 = 0, gk 或者 ( )→ −, xk f → 0. gk 证明：对于最速下降法， = 0, k 由以上定理立得．
收敛性分析 定理2:设/(x)二次连续可微且|y2(x米≤M, 其中M是个正常数,对任何给定的初始点x0, 最速下降算法或有限终止,或者lmnf(xk)=-∞, 或者ingk=0. 证明:用以上的结论 f(xk)-f(xk+)≥‖ 2M
收敛性分析 定理2: 设 f (x) 二次连续可微，且 ( ) , 2 f x M 其中 M 是个正常数，对任何给定的初始点 , x0 最速下降算法或有限终止，或者 lim ( ) = −, → k k f x 或者 lim = 0. → k k g 证明：用以上的结论： ( ) ( ) 2 1 2 1 k k gk M f x − f x +