Lecture11:数值优化方法 张伟平 Monday 23d November,2009
Lecture 11: Íä`zê{ ‹ï² Monday 23rd November, 2009
Contents 1 Numerical optimization methods in R y 1.1 Root-finding in one dimension............ 1.1.1 Bisection method............... 2 1.1.2 Brent's method .... 6 1.1.3 Newton's method..················ 11.4 Fisher scoring..·······.·······.·17 l.2 multivariate optimization··········.········ 18 1.2.1 Newton's method and Fisher scoring.........19 l.3 Numerical Integration.·........·.···.·.···20 1.4 Maximum Likelihood Problems . 27 1.5 Optimization Problems........ 29 1.5.1One-dimension Optimization...。。.....·.· 29 1.5.2 multi-dimensional Optimization.....·.·..·· 34 1.6 Linear Programming..·.···..·.·····.·..··38 Previous Next First Last Back Forward 1
Contents 1 Numerical optimization methods in R 1 1.1 Root-finding in one dimension . . . . . . . . . . . . . . . . . 1 1.1.1 Bisection method . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Brent’s method . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Newton’s method . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Fisher scoring . . . . . . . . . . . . . . . . . . . . . . 17 1.2 multivariate optimization . . . . . . . . . . . . . . . . . . . 18 1.2.1 Newton’s method and Fisher scoring . . . . . . . . . 19 1.3 Numerical Integration . . . . . . . . . . . . . . . . . . . . . 20 1.4 Maximum Likelihood Problems . . . . . . . . . . . . . . . . 27 1.5 Optimization Problems . . . . . . . . . . . . . . . . . . . . . 29 1.5.1 One-dimension Optimization . . . . . . . . . . . . . 29 1.5.2 multi-dimensional Optimization . . . . . . . . . . . . 34 1.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . 38 Previous Next First Last Back Forward 1
Chapter 1 Numerical optimization methods in R 1.1 Root-finding in one dimension 假设f:R→R为一连续函数，则方程f(x)=c的根x,满足g(x)=f(x)一c= 0.因此我们只考虑f(x)=0形式的方程求根问题.使用数值方法求此 方程的根，可以选择是使用f的一阶导数还是不使用导数的方法.Nw- ton方法或者Newton-Raphson方法是使用一阶导数的方法，而Brent的最 小化算法l是不使用导数的一种求根方法.在R中，函数uniroot就是基 于Brent的求根算法.该算法的Fortran程序源代码可以在下面网址上找 到http://www.gnu.org/software/gsl/月 IR.Brent.Algorithms for minimization without derivatives.Prentice-Hall,New Jersey,1973 Previous Next First Last Back Forward 1
Chapter 1 Numerical optimization methods in R 1.1 Root-finding in one dimension bf : R → RèòÎYºÍ, Kêßf(x) = cäx, ˜vg(x) = f(x) − c = 0. œd·Ç êƒf(x) = 0/™ê߶äØK. ¶^Íäê{¶d êßä, 屿J¥¶^fò ÍÑ¥ ÿ¶^Íê{. Newtonê{½ˆNewton-Raphsonê{¥¶^ò Íê{, BrentÅ z é{1¥ÿ¶^Íò´¶äê{. 3R•, ºÍuniroot“¥ƒ uBrent¶äé{. Té{Fortran ßS ìËå±3e° å˛È http://www.gnu.org/software/gsl/. 1R. Brent. Algorithms for minimization without derivatives. Prentice-Hall, New Jersey, 1973 Previous Next First Last Back Forward 1
1.1.1 Bisection method 如果f(x)在区间[a,b上连续，以及f(a)和f(b)有相反的符号，则由中值定理知 道存在a<c<b,使得f(c)=0.二分法通过在每次迭代中简单的判断f(x)在 中点x=(a+b)/2处的符号来寻求方程的根.如果f(a)和f(x)有相反的符号， 则区间就被[a,替代，否则就被[x,b)替代.在每次迭代中，包含根的区间长度 减少一半.即 1.记a0=a.b0=b,以及x(0)=(a+b)/2. 2.更新区间为 [at+1,b+i]= at,x(t)]. f(au)f(xt)≤0 z(t),btl. f(at)f(x())>0 以及x+1)=(at+1+b+1)/2 3.狮环2直至达到收敛准则。 常用的收敛准则有 Previous Next First Last Back Forward 2
1.1.1 Bisection method XJf(x)3´m[a, b]˛ÎY, ±9f(a)⁄f(b)kÉጓ, Kd•ä½n 3a < c < b, ¶f(c) = 0. ©{œL3zgSì•{¸‰f(x)3 •:x = (a + b)/2?Œ“5œ¶ êßä. XJf(a)⁄f(x)kÉጓ, K´m“[a, x]Oì, ƒK“[x, b]Oì. 3zgSì•, ù¹ä´m› ~òå. = 1. Pa0 = a, b0 = b, ±9x (0) = (a + b)/2. 2. ç#´mè [at+1, bt+1] = [at, x(t) ], f(at)f(x (t) ) ≤ 0 [x (t) , bt], f(at)f(x (t) ) > 0 ±9 x (t+1) = (at+1 + bt+1)/2. 3. ÃÇ2Üñà¬ÒOK. ~^¬ÒOKk Previous Next First Last Back Forward 2
绝对收敛 |x(t+1)-x(1<e 其中是选定的可容忍的精度.对于二分法，可以验证 b-at=2-'(bo-ao） 因此，当2-(+1)(b0-ao)<时，即t>lo92{(b0-a0)/6}-1,将达到容忍 精度x()-x<6. 可以看出，二分法不会失效，达到指定精度所需要的迭代次数也是事先可以 得到的.如果在区间[α，里方程有多个根，则二分法会找到一个根.二分法的 收敛速度是线性的， 相对收敛 相对收敛准则要求 z(t+1)-z(t) <E 2() Previous Next First Last Back Forward 3
˝È¬Ò |x (t+1) − x (t) | < Ÿ•¥¿½åN=°›. Èu©{, å±y bt − at = 2−t (b0 − a0) œd, 2−(t+1)(b0 − a0) < δû, =t > log2{(b0 − a0)/δ} − 1, ÚàN= °›|x (t) − x ∗| < δ. å±w—, ©{ÿ¨î, àç½°›§IáSìgÍè¥Økå± . XJ3´m[a, b]p êßkıáä, K©{¨Èòáä. ©{ ¬ÒÑ›¥Ç5. ÉÈ¬Ò ÉȬÒOKᶠ|x (t+1) − x (t) | |x(t) | < Previous Next First Last Back Forward 3