# Making Hessian positive semidefinite

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.

• 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? May 31, 2020 at 1:18
• 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. May 31, 2020 at 6:24
• 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 May 31, 2020 at 6:34
• 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. May 31, 2020 at 23:03