Subdivision Strategies for Boxes in Branch-and-Bound Nonlinear Solvers and Verification
Tóm tắt
Most verified solvers for nonlinear interval systems of equations comprise two strategies: a branch-and-bound-type “location” phase for excluding regions that cannot contain a solution, and a “verification” phase for proving that the remaining regions do indeed contain solutions. In the first phase, subdivision is crucial for the efficiency of the solvers. We discuss several ways for subdivision and present robust strategies that are suited for a variety of nonlinear systems. Particular focus is on the choice of subdivision directions, subdivision points and the handling of unbounded intervals. Furthermore we discuss a method to discard parts of a box within subdivision. Numerical evaluations are given based on the nonlinear interval solver SONIC. In the verification phase, further subdivision can increase the strength of the verification tests. In this paper, we address methods for the rigorous implementation of symmetrical subdivision which is needed, e.g., in existence tests based on Borsuk’s theorem.
Tài liệu tham khảo
Beelitz, T.: Effiziente Methoden zum verifizierten Lösen von Optimierungsaufgaben und nichtlinearen Gleichungssystemen. Ph.D. thesis, Bergische Universität Wuppertal, (2006)
Beelitz, T., Bischof, C.H., Lang, B., Willems, P.: SONIC—a framework for the rigorous solution of nonlinear problems. Tech. Rep. BUW-SC 2004/7, University of Wuppertal, (2004)
Beelitz T., Frommer A., Lang B., Willems P.: Symbolic–numeric techniques for solving nonlinear systems. PAMM 5(1), 705–708 (2005)
Beelitz, T., Lang B., Bischof, C.H.: Intervals and OpenMP : towards an efficient parallel result-verifying nonlinear solver. In Proceedings of the 5th European Workshop on OpenMP, Aachen, Germany, September 22-26, 2003, pp. 119–125, Aachen, Germany, (2003)
Beelitz T., Lang B., Bischof C.H.:: Efficient task scheduling in the parallel result-verifying solution of nonlinear systems. Reliab. Comput. 12(2), 141–151 (2006)
Du K., Kearfott R.B.: The cluster problem in multivariate global optimization. J. Global Optim. 5(3), 253–265 (1994)
Hanson, E.: Global Optimization Using Interval Analysis. Marcel Dekker, (1992)
Hickey, T.J., Ju, Q., van Emden, M.H.: Interval arithmetic: from principles to implementation. Technical report, Brandeis University CS, April (1999)
Just, E.: Adaptive use of extended systems for the efficient verified solution of nonlinear systems. PhD thesis, Bergische Universität Wuppertal (2014)
Just E., Lang B.: Success-guided selection of expanded systems for result-verifying nonlinear solvers. Reliab. Comput. 16, 73–83 (2012)
Kearfott, R.B., Nakao, M.T., Neumaier, A., Rump, S.M., Shary, S.P., van Hentenryck, P.: Standardized notation in interval analysis. In In Proc. XIII Baikal International School-seminar Optimization methods and their applications. Vol. 4 Interval analysis. Irkutsk: Institute of Energy Systems SB RAS, pp. 106–113 (2002)
Kearfott R.B., Novoa M. III: Algorithm 681: INTBIS, a portable interval Newton/bisection package. ACM Trans. Math. Software 16(2), 152–157 (1990)
Schulte Althoff, K.: Algorithmen zum verifizierten Lösen nichtlinearer Gleichungssysteme. Diploma thesis, RWTH Aachen University (2002)
Ueberholz, P.: An efficient parallel result-verifying nonlinear solver for large systems. Science and Supercomputing in Europe, pp. 441–446 (2007)
Willems, P.: Symbolisch-numerische Techniken zur verifizierten Lösung nichtlinearer Gleichungssysteme. Diploma thesis, RWTH Aachen University, (2004)