An efficient algorithm for finding all solutions of nonlinear equations using parallelogram LP test
An efficient algorithm for finding all solutions of nonlinear equations using parallelogram LP test
复制标题
使用平行四边形 LP 检验求非线性方程所有解的有效算法
DOI：
10.1016/j.cam.2020.113080
复制
发表时间：
2021
影响因子：
2.4
通讯作者：
Kiyotaka Yamamura
中科院分区：
文献类型：
--
作者：
Satoshi Denno;Kazuma Yamamoto;and Yafei Hou;Kiyotaka Yamamura
This paper presents an efficient algorithm for finding all solutions of nonlinear equations using linear programming. This algorithm is based on a simple test (called the LP test) for nonexistence of a solution to a system of nonlinear equations in a given region. In the conventional LP test, a system of nonlinear equations is formulated as a linear programming problem by surrounding component nonlinear functions by rectangles. In the proposed algorithm, we first use rectangles, and when the nonlinearity of functions becomes weak, we switch to parallelograms. It is shown that we can use the dual simplex method throughout the algorithm by applying the variable transformation to the oblique coordinate system, by which the LP test becomes more efficient. Moreover, since polygons with proper sizes are used, the LP test becomes more powerful. By numerical examples, it is shown that the proposed algorithm is more efficient than the conventional algorithms using rectangles only or parallelograms only. We also consider the special case where component nonlinear functions are locally convex and monotone, and propose an efficient LP test algorithm using rectangles and triangles.
