983 无约束极值问题 王页下页返
无约束极值问题
无约束极值问题 983 无约束极值问题可简单表述为: minf(X),X∈Rn(n维欧氏空间) xkh=x+且满足 fx网 这样逐步迭代直至满足精度条件 VfX+e1(梯度绝对值<E1) 王页下页返
无约束极值问题 无约束极值问题可简单表述为： min f(X)，XRn （n维欧氏空间） X(k+1)=X(k)+p (k) 且满足 f [X(k+1) ]< f [X(k) ] 这样逐步迭代直至满足精度条件 ‖▽f [X(k+1) ]‖< 1 (梯度绝对值< 1 )
无约束最优化方法 983 无约束极值问题的求解方法通常称为无约束最优化方法 et(unconstrained optimization method) >如何选择搜索方向是无约束最优化方法的核心,且不同的 ·搜索方向形成不同的最优化方法。 >无约束极值的求解方法包括: 最速下降法 ·牛顿法 共轭梯度法 变尺度法 王页下页返
无约束最优化方法 ➢ 无约束极值问题的求解方法通常称为无约束最优化方法 (unconstrained optimization method) ➢ 如何选择搜索方向是无约束最优化方法的核心，且不同的 搜索方向形成不同的最优化方法。 ➢ 无约束极值的求解方法包括： • 最速下降法 • 牛顿法 • 共轭梯度法 • 变尺度法
王最速下降法回顾 983 对于无约束最优化问题: minf(x), X=(x,x2,.,x)T 假设已经选代了k次,第k次迭代点为x 且v(X)≠0 午 令X=X+D为了(x)/(x 需要进行以下步骤: 王页下页返
最速下降法回顾 对于无约束最优化问题： min{ f (X)}, X = (x1 , x2 , …, xn ) T 假设已经迭代了k次，第k次迭代点为 且 ( ) k X ( ) k f (X ) k f X ( ) 1 1 ( ) ( 1 ) 0. , k k k k k k k f X X X p f X f X + + + 令 为了让 ， = + 需要进行以下步骤：
最速下降法回顾 983 1、确定搜索方向,选取最快的下降方向 Pk=-Vf(XR) 2、确定步长 取步长λ为最优步长,使得 f(Xk+apk)=minf(X+ap,) ≥0 求出λ,得到第k+1个迭代点 X=X+npk 直到Vf(X)<s(给定的误差值),迭代终止 王页下页返
最速下降法回顾 1、确定搜索方向，选取最快的下降方向 2、确定步长 ( ) ( ) k p f X k = − 1 0 ( ) ( ) min ( ) 1 ( ) ( k k k k k k k k k k k k f X p f X p k X X p f X + + = + + = + 取步长 为最优步长，使得 求出 ，得到第 个迭代点 直到 给定的误差值），迭代终止
生最速下降法回顾 983 3、例子 用最速下降法求解问题 min f(x)=4x,+x c共中X(,xy取初始点x=(1y允许误差=01 解:∫在点X=(x1x2)处的梯度Vf(X)=(8x,2x2) 第一次迭代: 令搜索方向p0=-Vf(X0)=(-8,-2) lpnl=√64+4=2vh7>E Vf(Xn) Vf(XK c故从点X出发沿P作一维搜索,由公式x(x)V(x) 有 1=0.130769 X1=(1)+0.13.769(8.,-2)=(-00461520.738462) 王页下页返
最速下降法回顾 3、例子 2 2 1 2 2 min ( ) 4 , , ) . (1,1) , 0.1. T T f X x x x = + 1 0 = = 用最速下降法求解问题 其中X=(x 取初始点X 允许误差 2 1 2 0 0 0 0 1 , ) ( ) (8 , 2 ) . ( ) ( 8, 2) , 64 4 2 17 ( ) ( ) ( ) ( ) 0.130769 1 1 T T T T k k T k k T f X x f X x x p f X p f X f X p f X Q f X X = = = − = − − = + = = = = + 1 0 k 0 解： 在点 （x 处的梯度 第一次迭代： 令搜索方向 故从点X 出发沿 作一维搜索，由公式 有 （，） 0.13.769( 8, 2) ( 0.046152,0.738462) T T − − = −
最速下降法回顾 第二次迭代: c令搜索方向P=(x)=(036926.-1476924) 983 pn‖=√2.18305=1522375>E 从点X出发沿作一维搜索, X2=(0.101537,0.147682) 第三次迭代: 中令搜索方向P2=-V(X2)=(0369216-1476924), p2=√0.747056=0.864329>E 从点X2出发沿p2作一维搜索, 工工 X3=(-0.009747,0.107217) 第四次迭代: 令搜索方向一 Vf(X3)=(0.077976,0.214434) lp3‖|=√0052062=0228171>E 从点X3出发沿P2作一维搜索, X4=(0.019126,0.027816) 王页下页返
最速下降法回顾 1 1 1 1 2 2 2 ( ) (0.369216, 1.476924) , 2.18305 1.522375 (0.101537,0.147682) ( ) (0.369216, 1.476924) , T T T p f X p p X p f X = − = − = = = = − = − 1 第二次迭代： 令搜索方向 从点X 出发沿 作一维搜索， 第三次迭代： 令搜索方向 2 2 3 3 3 3 3 0.747056 0.864329 ( 0.009747,0.107217) ( ) (0.077976, 0.214434) , 0.052062 0.228171 T T p p X p f X p p = = = − = − = − = = 2 3 从点X 出发沿 作一维搜索， 第四次迭代： 令搜索方向 从点X 出发沿 作一维搜索 4 (0.019126,0.027816)T X =
王最速下降法回顾 983 第五次迭代: 令搜索方向p4=-Vf(X4)=(-0.153008-0055632), lp1|=√026506=0.162807> 从点X出发沿P2作一维搜索, X5=(-00018350.020195 此时,V(X3)‖=√000847<满足精度要求,故得问题的最优解为 X5=(-00018350020195) 实际上,原问题的最优解为X=(0,0)7 王页下页返
4 4 4 3 5 5 ( ) ( 0.153008, 0.055632) , 0.026506 0.162807 ( 0.001835,0.020195) ( ) 0.001847 , T T p f X p p X f X = − = − − = = = − = 3 第五次迭代： 令搜索方向 从点X 出发沿 作一维搜索， 此时， 满足精度要求，故得问题的最优解为 5 ( 0.001835,0.020195) (0,0) T T X = − = 实际上，原问题的最优解为X 最速下降法回顾
王最速下降法回顾 983 ·最速下降法存在的间题:回m 所谓最速下降方向V(x)仅仅反映了在点X处的局部性质, 对局部来说是最速的下降方向,但对整体求解过程并不一定 斗使目标值下降得最快。最速下降法逼近极小点X的路线是锯齿 形的,当迭代点越靠近X,其搜索长就越小,因而收敛速度 工工 越慢。 上园回
• 最速下降法存在的问题： 最速下降法回顾 ( ) k k f X f X X X 所谓最速下降方向 仅仅反映了 在点 处的局部性质， − 对局部来说是最速的下降方向，但对整体求解过程并不一定 使目标值下降得最快。最速下降法逼近极小点 的路线是锯齿 形的，当迭代点越靠近 ，其搜索步长就越小，因而收敛速度 越慢
牛顿法 983 ·牛顿法的基本思想 为了寻找收敛速度快的无约束最优化方法,我们考虑在 每次迭代时,用适当的二次函数去近似目标函数f,并用 迭代点指向近似二次函数极小点的方向来构造搜索方向, 然后精确地求出近似二次函数的极小点,以该极小点作 为f极小点近似值 王页下页返
• 牛顿法的基本思想 为了寻找收敛速度快的无约束最优化方法，我们考虑在 每次迭代时，用适当的二次函数去近似目标函数f，并用 迭代点指向近似二次函数极小点的方向来构造搜索方向， 然后精确地求出近似二次函数的极小点，以该极小点作 为f的极小点近似值。 牛顿法