Numerical solution for bounding feasible point sets
Numerical solution for bounding feasible point sets
复制标题
DOI：
10.1016/s0377-0427(02)00912-3
复制
发表时间：
2003-07
影响因子：
2.4
通讯作者：
Peiliang Xu
中科院分区：
文献类型：
--
作者：
Peiliang Xu
寻找可行点是优化问题中的一个重要问题。目前有两大类算法来处理可行点的问题。第一类算法（局部性质的）是找到一个近似可行点。给定一个近似可行点的邻域，第二类算法是证明该邻域内是否存在可行点。据我们所知，没有任何方法已经实际实施，有效地找到最小的框界定的可行点定义的非线性和非凸不等式系统，除非可行集是凸的。在本文中，我们将提出一个数值方法来找到最小的框界定的可行点集定义的非线性和非凸不等式和/或系统的非线性和非凸不等式。两个例子已经综合构造和使用表明，所提出的数值方法确实可以正确地找到所有的最小包围盒在任何给定的精度有效。将讨论与相关技术的简要比较。我们的方法也可以被认为是第一个坚实的理论基础，多节和多分裂的全局优化，当与文献中的经验相比。
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.