LP Examples

There are 4 "pars" structures that contain sample data for running your LP codes. The first 3 (pars1,pars2,pars3) are all generated in the manner that I suggested to you so the initial points are exactly feasible and are in the "-infinity neighborhood" of the central path with gamma = 0.4. Therefore, run your LSPF algorithm with gamma=0.4. The first example has a dense A and the second and third have a sparse A. Make sure you are solving only sparse linear systems when A is sparse.

The fourth example is generated differently and the initial points are not feasible within machine precision; however, they are close to being feasible. Since your codes do not correct for infeasibilty, they may not solve this example very accurately. Also, you will have to use a smaller gamma for the LSPF method.

I am particularly interested to know how the condition numbers of the three linear systems behave as convergence takes place for the four examples. You should see different behavior on different examples. You can speculate as to why this might be, but I am not expecting you to figure it out. I'll explain it in the last class if you remind me.

Notice that even though A is very sparse in the second and third examples, it has full row rank. This is important. If you try your codes when A does not have rank m, they will fail to work as the linear systems are all obviously singular in this case. I generated each sparse matrix in a loop that generated random matrices with a certain level of sparsity, starting with sparsity 2/n and doubling this until A had full rank (which I checked by making sure min(svd(full(A))) was not very small).

Matlab 7 data file: save (in Netscape, right click this link) and type "load filename" in Matlab 7
Version for Matlab 6

Sorry about the delay in posting this. The deadline is extended to Monday Apr 25 at noon. I won't be here Monday so please turn the homework in to Celeste Williams, Room 524.