1
$\begingroup$

I have a vector valued function $F: \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$, which consists of quadratic taylor approximations. So one could say that function F consists of stacked approximations like: $F_i = f(\pmb a) + \nabla f(\pmb a)^T (\pmb x - \pmb a) + 0.5 (\pmb x - \pmb a)^T \nabla^2 f( \pmb a ) (\pmb x - \pmb a) \quad \forall i=1,...,m$ $F = [F_1, F_2, ..., F_m]^T$

currently I am solving the sum of squares problem of this with Gauss-Newton:

$\min \left\Vert F \right\Vert_2^2$

but Gauss-Newton uses only an approximation of the Hessian matrix: $H \approx 2( \nabla f(\pmb a) )^T ( \nabla f(\pmb a) )$.

Since I can explicitly express the Hessian, and the approximation for the Hessian is quite bad, I would like to use exact Hessian when possible.

Do you know any method to solve this problem?

Thank you!

EDIT: What about solving the sum-of-squares problem with Newon's method (true Hessian) ? I.e:

$g=\sum_{i=1}^{m} f_i^2 = \left\Vert F \right\Vert_2^2$ and then:

$x_{k+1} = x_k - ( \nabla^2 g )^{-1} \nabla g$

is this a good idea? Why does one normally use Gauss-Newton over Newton's method for this? Only for computational complexity reduction?

$\endgroup$
  • $\begingroup$ Some stabilized version of Newton's method? $\endgroup$ – copper.hat Jul 1 '13 at 7:44
  • $\begingroup$ @copper.hat thanks for your reply. Could you reference some information about this? Thanks $\endgroup$ – bonanza Jul 1 '13 at 8:37
  • $\begingroup$ Your cost function may not be convex, right? So we won't be guaranteed to find a global minimum. But probably that's ok. I think Newton's method sounds like a good idea if $\nabla^2 g$ is not too large. (Otherwise forming $\nabla^2 g$ and solving $\nabla^2 g \, \Delta x = \nabla g$ at each iteration may be very expensive.) But you should use Newton's method with a line search. You can't just use a step size of $1$ at each iteration of Newton's method. $\endgroup$ – littleO Jul 1 '13 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.