1
$\begingroup$

I have a large problem that I'm optimizing with Newton method. This involves a large sparse Hessian matrix. For better convergence and not to get stuck prematurely, I'd like to make the Hessian positive semidefinite. I leafed through some material:

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

https://ljk.imag.fr/membres/Jerome.Malick/Talks/11-SIOPT.pdf

https://hal.archives-ouvertes.fr/hal-00574437/file/henrion-malick-revision.pdf

and performed some experiments, but I didn't come up with a practical solution. I was wondering if anyone has tips on the matter.

EDIT: to clarify, it works fine when I'm projecting a dense matrix (using Matlab eig), but for large sparse matrices, this approach isn't practical.

--

My current problem is mesh-related, and I'm able to treat the terms in my energy separately, getting a local 6x6 Hessian, which I project to PSD using eigenvalue decomposition, a-la

https://www.math.ucla.edu/~jteran/papers/TSIF05.pdf

It works fine, but I was wondering about a solution to the general problem.

--

On the subject, I also have (sparse) linear constraints. Incorporating them with the Hessian (Lagrange-multipliers-style), the resulting KKT system (to extract a direction for the line search) becomes [H c; c' 0], which may not be PSD even if H is PSD. Any thoughts about that?

--

For code examples or libraries, my preference is matlab.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Since this is essentially a quasi-Newton method (modifying the Hessian to enforce positive-definiteness), why not use an existing quasi-Newton method like BFGS? $\endgroup$
    – whpowell96
    May 31, 2020 at 1:18
  • $\begingroup$ I disagree. It has a convergence rate at least like Newton, O(n^2), close to the optimum, while BFGS is significantly slower, O(n), and isn't comparable. $\endgroup$
    – Zohar Levi
    May 31, 2020 at 6:24
  • $\begingroup$ If I recall correctly, the thing that forces quasi-Newton methods to have linear convergence instead of quadratic is that the approximate Hessians only solve the secant equation but are not the true Hessian, which results in some errors not canceling like in vanilla Newton. Whatever you are doing to the Hessian will likely result in something similar unless the modifications the Hessian are tuned to go away as the iteration converges $\endgroup$
    – whpowell96
    May 31, 2020 at 6:34
  • $\begingroup$ I added a clarification that it works fine when I'm projecting a dense matrix. So, the question is how to project a sparse matrix to the PSD space. $\endgroup$
    – Zohar Levi
    May 31, 2020 at 23:03

1 Answer 1

Reset to default
2
$\begingroup$

You will want to look at the chapter on "Hessian modification" methods in the excellent book "Numerical Optimization" by Nocedal and Wright.

You will find that the Levenberg-Marquardt method is probably what you are looking for, given that you can't easily compute eigenvalues of large sparse matrices.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I wasn't aware of this section. It discusses the issue and suggests a few strategies such as the modified Cholesky factorization. $\endgroup$
    – Zohar Levi
    Jun 1, 2020 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.