14. Newton's Method

이 장에서는 Newton’s Method에 대해 살펴본다.

Newton’s method는 두 번 미분가능한 함수에 대하여 second-order Taylor expansion으로 함수를 근사한 뒤, 근사 함수의 최솟값을 찾으며 해에 접근하는 방법이다. 해의 근처에서는 quadratic convergence를 만족하며, gradient descent에 비하여 무척 빠른 수렴속도를 보인다.

References and further readings

• S. Boyd and L. Vandenberghe (2004), “Convex optimization”, Chapter 9 and 10
• Y. Nesterov (1998), “Introductory lectures on convex optimization: a basic course”, Chapter 2
• Y. Nesterov and A. Nemirovskii (1994), “Interior-point polynomial methods in convex programming”, Chapter 2
• J. Nocedal and S. Wright (2006), “Numerical optimization”, Chapters 6 and 7
• L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring 2011-2012

• 14-01 Newton's method
• 14-01-01 Newton's method interpretation
• 14-02 Interpretation & Properties
• 14-02-01 Root finding
• 14-02-02 Affine invariance of Newton's method
• 14-02-03 Local convergence analyisis
• 14-03 Newton decrement
• 14-04 Backtracking line search
• 14-05 Convergence analysis
• 14-06 Self concordance
• 14-06-01 Definition of self-concordant functions
• 14-06-02 Convergence analysis for self-concordant functions
• 14-07 Comparison to first-order method
• 14-08 Special cases
• 14-09 Quasi-Newton methods