5
$\begingroup$

I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$:

$$ \nabla^2f(x) \ d = -\nabla f(x) $$

So I need to solve a linear system, but the Hessian matrix $\nabla^2f(x)$ might not be positive definite which could give me an invalid descent direction. I want to run conjugate gradient to solve the linear system. In the conjugate gradient method, one of the steps involves this operation $v^T \nabla^2\ f(x)\ v$ (computing $\alpha$ according to Shewchuk's notes, page 50 https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf , I'm using $v$ rather than $d$ because in my convention $d$ is the descent direction to update $x$). I could recycle this operation to know if the Hessian is not positive definite (if such operation is negative).

I implemented my algorithm like that, so as soon as I detect that operation is negative, I stop the CG solver and return the solution iterated up to that point. I've actually seen it works pretty well in practice, but I have no rigorous justification for doing it. I remember hearing / reading people saying that each CG iteration takes care of different eigenvalues in order of "importance", so by stopping early you end up exploring the positive definite part of the Hessian. Can anybody point me to a more rigorous justification of this? Is this a valid way to enforce positive definiteness using CG for non-linear optimization?

$\endgroup$
  • 3
    $\begingroup$ There's no rigorous justification of your approach in the sense that you cannot tell how far you are from the solution of the linear system when negative curvature occurs. But if you combine this with a trust region globalization framework, you can in fact prove convergence -- this is known as truncated Newton-CG: Steihaug, Trond, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal. 20, 626-637 (1983). ZBL0518.65042. $\endgroup$ – Christian Clason Jul 17 '18 at 6:16
  • $\begingroup$ You can also prove convergence of a linesearch scheme very closely related to what the OP suggests: link.springer.com/article/10.1007/BF02592055 and fast local convergence: epubs.siam.org/doi/abs/10.1137/0719025. In the case of the trust-region method, an additional result due to Yuan shows that in the convex case, the solution identified by truncated CG is at least half as good as the global minimizer of the trust-region subproblem: link.springer.com/article/10.1007%2Fs101070050012 (Theorem 2). $\endgroup$ – Dominique Aug 7 '18 at 1:51
  • $\begingroup$ I should have mentioned that I'm also doing line search in my implementation. I just approximately solve the linear system with a few CG iterations, but I still have a safeguard with a backtracking line search to make sure I make progress using that descent direction. I'm not very familiar with trust region optimization, but I think line search and trust region are two valid ways to achieve similar results. Or is there any reason I should prefer trust region over line search in this case? $\endgroup$ – yewang Aug 19 '18 at 0:50

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.