Nonsmooth exclusion test for finding all solutions of nonlinear equations
Nonsmooth exclusion test for finding all solutions of nonlinear equations
复制标题
DOI：
10.1007/s10543-010-0280-6
复制
发表时间：
2010-09
影响因子：
1.5
通讯作者：
M. D. Stuber;V. Kumar;Paul I. Barton
中科院分区：
文献类型：
--
作者：
M. D. Stuber;V. Kumar;Paul I. Barton
提出了一种寻找具有边界约束的非线性方程组的所有实数解的新方法。零查找问题被转换为全局优化问题，其目标值为零的全局最小值（如果有）对应于原始问题的所有解。分支定界算法与 McCormick 的非光滑凸松弛一起使用来生成下界。建立了松弛问题的解集与原始非凸问题的解集之间的包含关系，这激发了一种方法自动生成局部牛顿型方法的起点。采用具有自然水平函数的阻尼牛顿法，采用限制性单调性测试来稳健且快速地找到解决方案。由于目标函数的特殊结构，凸下界问题的解决方案产生非光滑根排除测试，该测试被发现比早期基于区间分析的排除测试表现更好。组件式 Krawczyk 算子和区间牛顿算子以及基于 Gauss-Seidel 的根包含和排除测试也都嵌入到所提出的算法中，以细化变量范围，从而有效地理解搜索空间。给出了该算法在文献中的各种测试问题上的性能，对于大多数问题，由于良好的起点生成，在算法的第一次迭代时找到了第一个解决方案。
A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method withnatural level functionsemploying therestrictive monotonicity testis employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.