In Convergence-order analysis of branch-and-bound algorithms for constrained problems (click here), Rohit Kannan and Paul I. Barton investigate the convergence order of bounding schemes for deterministic global optimization algorithms. Specifically, this article proposes a definition of convergence order for lower bounding schemes for constrained problems, defines the convergence order of full-space relaxation-based and Lagrangian dual-based lower bounding schemes, and analyzes the convergence order of some widely-applicable reduced-space lower bounding schemes.

In The cluster problem in constrained global optimization (click here), the authors use this recently-developed notion of convergence order for lower bounding schemes to extend previous analyses of the cluster problem in unconstrained global optimization to the constrained setting. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer, and that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions, unlike the case of unconstrained optimization. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided.