I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully negative definite for a local minimum)

But since I have a system of 1000 variables, I am stuck with a 1000*1000 matrix to determine whether it is positive definite or negative definite.(this is all real numbers)

Is there any way to do it other than calculates all the eigenvalue ? Someone suggests a cholesky decomposition, but I failed to understand why.

  • $\begingroup$ since the number in first row and first column in Bordered Hessian is 0,Sylvester's criterion could not apply. $\endgroup$ – user56134 Aug 3 '15 at 22:29
  • 1
    $\begingroup$ a symmetric matrix is positive definite if and only if it has a cholesky decomposition $\endgroup$ – user251257 Aug 3 '15 at 22:37

@ user56134 , a bordered Hessian cannot be $>0$ or $<0$ (cf. your comment)!). If there are $n$ unknowns and $m<n$ constraints, then you must consider the signum(s) of $n-m$ minors of the bordered Hessian. A priori, (if $m<<n$) the complexity of the calculation is in $O(n^4)$, that is here in $10^{12}$ ; yet, eventually there is a faster algorithm.


Your Answer

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

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