分支定界算法

分支定界算法是已被提出的多种自适应分区策略，用于解决全局优化模型。 这些方法基于分区、抽样以及后续的下界和上界程序：这些操作被迭代地应用于可行集 内的活动（“候选”）子集集合中。 它们的穷举搜索特性以类似于整数线性规划方法的精神得到保证。 分支定界涵盖了许多具体的方法，并允许各种实现方式。 分支定界方法通常依赖于关于问题的一些先验结构知识。 例如，这些信息可能与每个函数的变化速度有关（例如，关于每个函数 和 的合适“整体”利普希茨常数的知识）；或者与所有函数的解析公式的可用性和保证的光滑性有关（例如，在基于区间算术的方法中）。 一般的分支定界方法适用于广泛的全局优化问题，例如，在组合优化、凹最小化、反向凸规划、DC 规划和利普希茨优化中（Neumaier 1990, Hansen 1992, Ratschek and Rokne 1995, Kearfott 1996, Horst and Tuy 1996, Pintér 1996）。