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