TAILIEUCHUNG - 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 .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.