Tuesday, September 16, 2008

On solving a large system of nonlinear equation

When trying to solve a very large system of nonlinear F(x)=0 I encountered a number of problems. Large meant here about 224k variables and equations. Solving as CNS gave "pivot too small". An NLP formulation:

min dummy
F(x)=0

caused lack of progress and stopped with an infeasible solution. In the end I could solve the model reliably using a min absolute deviations formulation where explicit slacks are omitted for linear equations, i.e.:

min ∑ si
Ax−b=0
G(x)+s = 0

A standard variable splitting technique is used to model the absolute value:

min ∑ vi+wi
Ax−b=0
G(x)+v−w=0
v,w≥0