Download Contents
Transcript
3.23 A PSD-Problem 159 a private note saying: 1) Our suggestions are only good for matrices that are nicely positive definite. It is both slow and unrealiable for matrices with small diagonal elements (and an example showed how poorly it worked - se below). 2) Methods from numerical analysis, e.g. incomplete Cholesky factorization, works much better and faster. I agree with Michael on both points. However, as I understood the original question about a week ago, the SPD approximation was just one small part of a larger model. I have worked with a model where the objective was to estimate a production function given some observations, with the constraint that a derivative matrix for the production function had to be positive definite. The model components shown by Tom and I can be used as building blocks in larger models to represent constraints like these. The example given by Tom has one little misprint relative to my original suggestion, namely in the initialization. You should use a diagonal matrix, W(i,i) = 1, and not W(i,j)$L(i,j) = 1. The diagonal puts equal emphasis on the variables. Results with Tom’s start and Michaels data (shown below) on my Pentium/133 are: MINOS CONOPT Iterations 3579 902 Seconds 237 61.8 Objective 1.5729 1.5729 and with the diagonal start: MINOS CONOPT Iterations 1163 191 Seconds 75.9 9.9 Objective 0.0065 0.0000 If you remove the lower bound on the diagonal of the factor, thereby changing the requirement from strictly positive definite to positive semi definite (we do not have a good measure for how close we can accept it anyway and the model becomes unconstrained without bounds -- the easiest class we have) then the results become: MINOS CONOPT Iterations 133 212 Seconds 8.9 10.8 Objective 0.0000 0.0000 As a comparions to these results I have also written a small GAMS program to do an incomplete Cholesky factorization. In model 1 I simply ignored small pivots, and in model 2 I perform pivoting. The GAMS executing times were around 0.150 seconds. The models with Michael Ferris "bad" data follows. *------------------Start of model 1--------------------$Title Incomplete Cholesky factorization of a symmetric matrix