For a quadratic convex function Classical Newton method for unconstrained optimization reaches the minimum point in one iteration. It this true?
If so, what is the proof ?
Asked
Active
Viewed 408 times
2
user107723
- 548
-
The minimum of a quadratic convex function, even in multiple variables, amounts to the root of a linear system, which the Newton iteration finds (using the inverse Jacobian in the multivariable case). – hardmath Jan 25 '14 at 06:07
-
In how many iteration does it find ? – user107723 Jan 25 '14 at 06:08
-
1In one iteration. – hardmath Jan 25 '14 at 06:08
-
Can you suggest the proof of getting it in one iteration for multivariate case – user107723 Jan 25 '14 at 06:09
1 Answers
1
Recall that a quadratic convex function, $f(\overline{u}) = \overline{u}A\overline{u}^T + \overline{u}b^T$, has a unique global minimum characterized by the vanishing of first partial derivatives.
Thus if $\nabla_f$ is the gradient of $f$, the minimizing point $\overline{u}$ is also the solution of the system $\nabla_f = 0$. Minimizing $f(\overline{u})$ by Newton's method means to solve the system $\nabla_f = 0$ by Newton iterations.
However one such iteration suffices because the gradient of $f$ is a linear function of $\overline{u}$, and the Newton iteration step is simply to solve the corresponding system.
hardmath
- 37,015
-
I got the idea clearly. Can you suggest me some good material about this to read ? – user107723 Jan 25 '14 at 07:12
-
1The Hessian of $f$ is the matrix of second partial derivatives, and when we apply Newton's method to solve $\nabla_f = 0$, the "correction" to our initial value $\overline{u}$ is computed using the Hessian inverse. For some background see these class notes by Prof. Tom Angell at Univ. of Delaware, but your case is the simple one where the Hessian is a constant matrix (the same for every $\overline{u}$). – hardmath Jan 25 '14 at 07:23