Solving Sparse Systems of Equations with an optimizer: a basis trick

Sparse Systems of Linear Equations

Solving a sparse system of linear equations\[Ax=b\] is a task an LP solver should be quite well-equipped to do. A typical Simplex method will contain a rather sophisticated sparse LU factorization routine. Formulating this as a standard LP with a dummy objective leads to somewhat disappointing performance (see the table below). Here we try a very sparse system of \(n=9,801\) variables and equations.

One reason a simplex method is slow here it that the initial basis is chosen rather poorly. We can help the solver with this. We know that the basis status of the final solution is as follows:

• All rows are nonbasic
• All columns are basic

This suggests we can construct an advanced basis that reflects this prediction, and tell the LP solver to use this. In GAMS it is very easy to setup such a basis. A non-zero marginal indicates the corresponding row or column is non-basic. We can just use an assignment statement:

   equation e(i,j);
   e.m(i,j) = 1;

The variables just have their default marginal value of zero. The results are not something to sneeze at:

Solver	Model	Iterations	Seconds
cplex	LP	4358	27
cplex	LP+basis	0	6.5

When we pass on an advanced basis the solver needs no simplex iterations (i.e. basis changes): it just factorizes the basis matrix and it is done.

Sparse Systems of Nonlinear Equations

When dealing with a large system of nonlinear equations \[F(x)=0\] we can do a similar thing. It helps only for algorithms that are simplex based such as MINOS. Here we solve a standard benchmark problem due to Broyden:

Broyden's tridiagonal problem

This is a quadratic problem with \(n=10,000\) equations and variables. Solvers like Cplex or Gurobi are not able to solve it. The model type CNS stands for Constrained Nonlinear System: a square system of non-linear equations (with some possible bounds) without an objective. With MINOS we see:

Solver	Model	Iterations	Seconds
minos	CNS	The problem is unbounded (or badly scaled)
minos	CNS+basis	0	0.2

We see again that a good starting basis can help: in this case it makes the difference between being able to solve the problem or not. Using an advanced basis, the solver does not need to do any simplex-type iterations and just can use some Newton algorithm which will converges extremely fast.

References

1. Erwin Kalvelagen, Solving Systems of Linear Equations with GAMS, http://amsterdamoptimization.com/pdf/lineq.pdf
2. C. G. Broyden, A Class of Methods for Solving Nonlinear Simultaneous Equations,  Mathematics of Computation, Vol. 19, No. 92 (Oct., 1965), pp. 577-593