Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.