Transcription of Newton’s Method - CMU Statistics
{{id}} {{{paragraph}}}
Example: tourism industry
Newton’s Method - CMU Statistics
newton s MethodRyan TibshiraniConvex Optimization 10-725/36-7251 Last time: dual correspondencesGiven a functionf:Rn R, we define its conjugatef :Rn R,f (y) = maxxyTx f(x)Properties and examples: Conjugatef is always convex (regardless of convexity off) Whenfis a quadratic inQ 0,f is a quadratic inQ 1 Whenfis a norm,f is the indicator of the dual norm unitball Whenfis closed and convex,x f (y) y f(x)Relationship to duality:Primal:minxf(x) +g(x)Dual:maxu f (u) g ( u)2 newton s methodGiven unconstrained, smooth convex optimizationminf(x)wherefis convex, twice differentable, anddom(f) =Rn. Recallthat gradient descent chooses initialx(0) Rn, and repeatsx(k)=x(k 1) tk f(x(k 1)), k= 1,2,3,..In comparison, newton s Method repeatsx(k)=x(k 1) ( 2f(x(k 1))) 1 f(x(k 1)), k= 1,2,3,..Here 2f(x(k 1))is the Hessian matrix offatx(k 1)3 newton s Method interpretationRecall the motivation for gradient descent step atx: we minimizethe quadratic approximationf(y) f(x) + f(x)T(y x) +12t y x 22overy, and this yields the updatex+=x t f(x) newton s Method uses in a sense a better quadratic approximationf(y) f(x) + f(x)T(y x) +12(y x)T 2f(x)(y x)and minimizes overyto yieldx+=x ( 2f(x)) 1 f(x)4 Forf(x) = (10x21+x22)/2 + 5 log(1 +e x1 x2).
We have seenpure Newton’s method, which need not converge. In practice, we instead usedamped Newton’s method(i.e., Newton’s method), which repeats x+ = x t r2f(x) 1 rf(x) Note that the pure method uses t= 1 Step sizes here typically are chosen bybacktracking search, with parameters 0 < 1=2, 0 < <1. At each iteration, we start with t= 1 ...
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: