Numerical solution for bounding feasible point sets

摘要

Finding feasible points is important in optimization. There are currently two major classes of algorithms to deal with the problem of feasible points. The first class of algorithms (of local nature) is to find an approximate feasible point. Given a neighbourhood of an approximate feasible point, the second class of algorithms is to prove whether a feasible point exists inside this neighbourhood. To the best of our knowledge, no methods have been practically implemented to efficiently find the smallest boxes for bounding the feasible points defined by a system of nonlinear and nonconvex inequalities, unless the feasible set is convex. In this paper, we will present a numerical method to find the smallest boxes for bounding the feasible point sets defined by a nonlinear and nonconvex inequality and/or a system of nonlinear and nonconvex inequalities. Two examples have been synthetically constructed and used to show that the proposed numerical method can indeed correctly find all the smallest bounding boxes at any given accuracy efficiently. A brief comparison with relevant techniques will be discussed. Our method may also be thought of as the first solid theoretical basis for multisection and multisplitting in global optimization, when compared with those empirical ones in the literature.