tailieunhanh - Bài giảng Tối ưu hóa nâng cao: Chương 10 - Hoàng Nam Dũng

Bài giảng "Tối ưu hóa nâng cao - Chương 10: Newton's method" cung cấp cho người học các kiến thức: Newton-Raphson method, linearized optimality condition, affine invariance of Newton's method, backtracking line search,. . | Bài giảng Tối ưu hóa nâng cao: Chương 10 - Hoàng Nam Dũng Newton’s Method Hoàng Nam Dũng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Newton-Raphson method scribes/ Newton’ Annimation: Animations/RootFinding/NewtonMethod/ 1 Newton’s method Given unconstrained, smooth convex optimization min f (x), x where f is convex, twice differentable, and dom(f ) = Rn . Recall that gradient descent chooses initial x (0) ∈ Rn , and repeats x (k) = x (k−1) − tk · ∇f (x (k−1) ), k = 1, 2, 3, . . . In comparison, Newton’s method repeats −1 x (k) = x (k−1) − ∇2 f (x (k−1) ) ∇f (x (k−1) ), k = 1, 2, 3, . . . Here ∇2 f (x (k−1) ) is the Hessian matrix of f at x (k−1) . 2 Newton’s method interpretation Recall the motivation for gradient descent step at x: we minimize the quadratic approximation 1 f (y ) ≈ f (x) + ∇f (x)T (y − x) + ky − xk22 , 2t over y , and this yields the update x + = x − t∇f (x). Newton’s method uses in a sense a better quadratic approximation 1 f (y ) ≈ f (x) + ∇f (x)T (y − x) + (y − x)T ∇2 f (x)(y − x), 2 and minimizes over y to yield x + = x − (∇2 f (x))−1 ∇f (x). 3 Newton’s method f (x) ==(10x 2 + 5 log(1 + e −x1−x 2 2 x 2 )/2 −x12−x Consider Considerminimizing minimizing f (x) 1 + (10x 1 +2 x2 )/2 + 5 log(1 + e ) 2) (this must be a nonquadratic . why?) 20 ● ● ● ● ● ●● ● ● ● ● ● ● ● ● We compare gradient de- ● ● ● ● ● ● 10 ● ● ● ● ● ● ● ● ● scent We(black) compareto Newton’s gradient de- ● ● ● ●●● ● ● ● ●● method (blue), where scent (black) to Newton’s 0 method both (blue), take steps of where roughlyboth take .