On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination

Kirst, Peter; Füllner, Christian Article — Published Version On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination Computational Optimization and Applications Provided in Cooperation with: Springer Nature Suggested Citation: Kirst, Peter; Füllner, Christian (2025) : On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination, Computational Optimization and Applications, ISSN 1573-2894, Springer US, New York, NY, Vol. 90, Iss. 3, pp. 691-720, https://doi.org/10.1007/s10589-025-00652-5 This Version is available at: https://hdl.handle.net/10419/323335 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Computational Optimization and Applications (2025) 90:691–720 https://doi.org/10.1007/s10589-025-00652-5 On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination Peter Kirst1 ·Christian Füllner2 Received: 12 October 2023 / Accepted: 16 January 2025 / Published online: 8 February 2025 © The Author(s) 2025 Abstract Spatial branch-and-bound algorithms for global minimization of non-convex problems require both lower and upper bounding procedures that finally converge to a globally optimal value in order to ensure termination of these methods. Whereas convergence of lower bounds is commonly guaranteed for standard approaches in the literature, this does not always hold for upper bounds. For this reason, different so-called convergent upper bounding procedures are proposed. These methods are not always used in practice, possibly due to their additional complexity or possibly due to increasing runtimes on average problems. For that reason, in this article we propose a refinement of classical branch-and-bound methods that is simple to implement and comes with marginal overhead. We prove that this small improvement already leads to convergent upper bounds, and thus show that termination of spatial branch-and-bound methods is ensured under mild assumptions. Keywords global optimization ·branch-and-bound ·upper bounding procedure · feasible points ·feasibility verification ·restriction of the right-hand side Mathematics Subject Classification 90C26 1 Introduction In this article, we address the computation of upper bounds in spatial branch-and-bound algorithms in global optimization, as well as the termination of these algorithms. In BPeter Kirst [email protected] Christian Füllner [email protected] 1Operations Research and Logistics (ORL), Wageningen University & Research (WUR), Wageningen, The Netherlands 2Institute for Operations Research, Stochastic Optimization, Karlsruhe Institute of Technology, Karlsruhe, Germany 123 692 P. Kirst, C. Füllner this context, we consider problems of the form P(B):min x∈Rnf(x) s.t.gi(x)≤0,i∈I, x∈B with a finite set I. The box Bis defined by B=x∈Rn|b≤x≤bwith b,b∈Rn,b<b, where inequalities are understood component-wise. We assume the functions fand gito be continuous, but we do not require fand gito be convex. For that reason, the feasible set M(B):= {x∈B|gi(x)≤0,i∈I} does not need to be convex either. In total, problem P(B)is a non-convex problem. Throughout this article the definition M(X):= X∩M(B)will be convenient for some box X⊂B. For a problem of type P(B)and some predefined optimality tolerance εv>0a typical aim in global optimization is to determine a so-called εv-optimal feasible point x∗∈M(B), i.e. a feasible point x∗with f(x∗)≤f(x)+εv for all x∈M(B). Clearly, this immediately implies v∗≤f(x∗)≤v∗+εvwhere v∗denotes the globally minimal value of P(B). Note that we impose hard constraints here, which means that approximately feasible points satisfying the εv-optimality criterion are not accepted. The most common approach to globally solve problems of type P(B)in this sense is to apply spatial branch-and-bound algorithms. In such methods, the problem is iteratively branched into subproblems P(X)of the form P(X):min x∈Rnf(x)s.t.x∈M(X) with sub-boxes X⊂B. Then, for those subproblems lower bounds are constructed and, furthermore, overall lower bounds at the globally minimal value v∗of the original problem P(B)are computed as a minimum of all these lower bounds. Wherever possible, boxes that cannot contain globally optimal points are excluded from the search space. In addition, upper bounds at globally minimal values are computed and the algorithm terminates if lower and upper bounds are sufficiently close to each other. Whereas convergence is typically ensured for lower bounds, this is not guaranteed for commonly used upper bounding procedures. Upper bounds for v∗can be constructed by explicitly evaluating the objective function at feasible points of P(B)or by applying local solvers, which implicitly make use of such evaluation. However, as the problem P(B)is non-convex, finding a feasible point is already NP-hard, which makes it challenging to generate a sequence of feasible points that lead to improved 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 693 upper bounds. Therefore, most research on upper bounding procedures focuses on heuristics which perform sufficiently well for many practical applications, but are not guaranteed to ensure convergence of upper bounds in spatial branch-and-bound methods in general [10,11]. A popular strategy is the aforementioned approach to solve the non-convex problem P(B), or some subproblem P(X), locally [7]. Although this often works well in practice, in general this does not guarantee sufficiently good upper bounds for termination of branch-and-bound algorithms. Since exact feasibility is hard to ensure, another common concept is to accept so-called εf-feasible points, i.e. points x∈B with gi(x)≤εf,i∈I,for some tolerance εf>0. However, this concept is not sufficient to compute valid upper bounds for v∗either. This even holds for εfclose to zero, as discussed in detail by Tuy [56] and Kirst et al. [30]. Hence, whereas for most lower bounding procedures in the literature certain convergence results are available, unfortunately, this does not hold for classical upper bounding procedures. Since spatial branch-and-bound algorithms rely on convergent valid upper bounds in the termination criterion, however, such convergence guarantees for the upper bounds are crucial to ensure termination after a finite number of iterations. Research in this direction has been limited so far. As discussed above, computing upper bounds for v∗and identifying feasible points are closely related. Therefore, the work that does exist is mostly focused on feasibility verification. Once verification is successful for some box X, valid upper bounds are obtained by computing an upper bound for the objective function over X.In[13,28,29] several different feasibility verification methods are presented. They are based on computing approximately feasible points, e.g., by using conventional nonlinear solvers, and then verifying the existence of feasible points in specifically constructed boxes around such points using interval Newton methods. While these methods are rigorous in the sense that they rule out false positive feasibility verification, and thus do yield valid upper bounds for v∗, there exist no proven convergence guarantees. In our emphasis on the convergence of the upper bounding procedure, our work clearly differs from these methods. For the case of purely inequality-constrained and box-constrained problems, a convergent upper bounding procedure is presented in [30] based on perturbing infeasible iterates along Mangasarian-Fromovitz directions. It is not straightforward to extend this approach to equality-constrained problems, though. In reverse, for the case of purely equality-constrained and box-constrained problems, a convergent upper bounding procedure is presented in [19] based on a generalization of Miranda’s Theorem [37]. This method, however, does not allow for inequality constraints in problems P(B)and requires the box constraints to be strictly satisfied. An extension to problems that also include inequality constraints is presented in [18] based on utilizing approximations of active index sets of inequalities. Another common drawback of the existing upper bounding procedures with proven convergence in the literature is that they are rather technical and often tedious to implement. On the contrary, some very simple upper bounding procedures, such as starting non-linear solvers at different points during the solution process, are not guaranteed to ensure convergence of spatial branch-and-bound algorithms in general, but provide sufficiently good upper bounds to achieve termination for many problems in practice. 123 694 P. Kirst, C. Füllner In this article, we propose a new upper bounding procedure that exploits the strengths and overcomes the weaknesses of both types of approaches. That is, our proposed procedure •is simple to implement, •is computationally efficient in the sense that there is at most little overhead, •can be combined easily with other common methods such as the local solution of the problem at hand, •but is still proven to provide sufficiently good upper bounds in order to terminate the algorithm after a finite number of iterations under mild assumptions. Note that, although some illustrative computational examples are provided using a simple implementation as a proof-of-concept, it is not our aim to develop an entire new solver. Instead, we focus on a new upper bounding procedure that can be incorporated in a wide variety of solvers. The main idea in this article is based on the concept of restriction of the righthand side, which has recently been proposed in [40,41] in the context of semi-infinite programming to compute feasible points. Whereas this technique is used for (standard as well as generalized) semi-infinite programs in [40,41], to our best knowledge it has never been examined for standard non-convex problems in global optimization. This article is structured as follows. In Sect. 2we briefly review some basic concepts from global optimization and further discuss difficulties of non-convergent upper bounding procedures. In Sect.3we explain how the concept of restriction of the righthand side from the literature can be applied within a spatial branch-and-bound method for continuous non-linear global optimization. Based on this, in Sect.4we prove that this leads to a convergent algorithm given some assumptions, which are discussed in Sect.5. In Sect.6we provide computational results for some illustrative test problems, which highlight that, while providing proven convergence guarantees, the proposed method has little computational overhead. Finally, Sect.7concludes the paper with some final remarks. The notation in this article is standard. In particular, Df denotes the row vector of partial derivatives of a function fand by diag(X)we denote the diagonal length of a box X. 2 Preliminaries and assumptions In this section we briefly review some important concepts from the literature that are needed for our approach. We start with a small overview on spatial branch-andbound methods in global optimization where we focus in particular on lower bounding procedures. A general definition of a convergent lower bound taken from [30]is described in Sect.2.2. The concept of restriction of the right-hand side, which is the basis for our new upper bounding procedure, is briefly explained in Sect.2.3. 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 695 2.1 Lower bounding procedures for spatial branch-and-bound methods Spatial branch-and-bound algorithms for global optimization were first proposed by Falk and Soland in [16]. Since then, various enhancements have been developed, for instance, branch-and-reduce [47,48], symbolic branch-and-bound [51,52], branchand-contract [59] or branch-and-cut [55]. In addition to these purely scientific works, many state-of-the-art global optimization solvers are based on implementations of spatial branch-and-bound algorithms, for example Baron [49], Couenne [9], Antigone [39], LindoGlobal [33]orScip [1,57]. For monographs covering the theory on global optimization and, in particular, spatial branch-and-bound algorithms we refer to [17,23,34]. Typically, in spatial branch-and-bound algorithms, lower bounds for v∗are obtained by special bounding procedures. A well-known approach is to compute lower bounds by solving convex relaxations of problems P(X)to optimality. Determining these relaxations, in turn, is based on computing as tight as possible convex underestimators of the functions fand gi,i∈I, contained in P(B). Many different underestimators have been proposed for specific classes of functions, among them underestimators and envelopes for bilinear terms [35], polynomials [32], non-convex piecewise linear functions [24] and general lower-semicontinuous functions [53,54]. Additionally, generic convex underestimators can be constructed for arbitrary non-convex functions, as described in [2,21,36] and applied in the αBB algorithm [3,4,7]. Since tight underestimators can only be determined explicitly for functions in low dimensions, these techniques are usually combined with factorization and symbolic reformulation approaches [35,52]. However, recently there has also been some progress on obtaining tight relaxations for composite functions directly [22]. Moreover, convex underestimators can often be considerably strengthened by bounds tightening techniques [9,44]. Different lower bounding procedures are based on exploiting duality [14, 15], using piecewise linear approximations [20,38,45,46], using Lipschitz constants [43] or applying interval arithmetic [42] and related concepts, such as centered forms [8,31]. For several of those lower bounding procedures it is proven that the determined lower bounds converge to v∗for decreasing box sizes, as they naturally occur in spatial branch-and-bound algorithms. 2.2 Convergence of lower bounding procedures In this article we assume that convergent lower bounding procedures are available, which is commonly fulfilled for the aforementioned approaches. However, in order to keep the exposition as general as possible we briefly review some definitions from [30], which will be convenient throughout this article. Furthermore, this enables us to prove convergence in a rather general manner without restricting our consideration to a particular lower bounding procedure. We start with some special classes of bounding procedures. 123 696 P. Kirst, C. Füllner Definition 1 (Bounding procedures, from [30]) •A function from the set of all sub-boxes Xof Bto Ris called M-dependent lower bounding procedure for the objective function of P(B),if(X)≤infx∈M(X)f(x) holds for all sub-boxes X⊆Band any choice of the functions f,gi,i∈I. •A function from the set of all sub-boxes Xof Bto Ris called M-independent lower bounding procedure for a function, if it satisfies (X)≤minx∈Xφ(x)for all sub-boxes X⊆Band any choice of the function φ:B→R. •A lower bounding procedure is called monotone, if (X1)≥(X2)holds for all boxes X1⊆X2⊆B. In the following, by φwe denote an M-independent lower bounding procedure applied to a specific function φ,e.g. for gi,i∈I. To make sure that our spatial branch-and-bound algorithm converges, it is crucial that all applied lower bounding procedures are convergent. To define the concept of convergent lower bounding procedures, we consider so-called exhaustive sequences of boxes and apply the bounding procedures to these sequences. A sequence of boxes (Xk)k∈Nis called exhaustive, if it is nested (Xk⊂Xk−1for all k∈N), contains no empty boxes (Xk=∅for all k∈N) and satisfies limk→∞ diag(Xk)=0. We refer to [23] for more information. For commonly applied box division strategies in global optimization, e.g., dividing a box along the midpoint of a longest edge, any exhaustive sequence of boxes (Xk)k∈N converges to a single point ˜x, i.e. we have k∈NXk={˜x}. Note that under continuity of f, this implies lim k→∞ min x∈Xk f(x)=f(˜x), and in particular the limit exists [30]. We can now introduce the notion of convergent bounding procedures. Definition 2 (Convergent bounding procedures, from [30]) •An M-independent lower bounding procedure φis called convergent if it satisfies lim k→∞φ(Xk)=lim k→∞ min x∈Xk φ(x) for any exhaustive sequence of boxes (Xk)k∈Nand any function φ:B→R. •An M-dependent lower bounding procedure is called convergent if it satisfies lim k→∞(Xk)=lim k→∞ min x∈M(Xk)f(x), where limk→∞ minx∈M(Xk)f(x)=+∞if ˜x/∈M(B), for any exhaustive sequence of boxes (Xk)k∈N. 2.3 Restriction of the right-hand side Convergence of lower bounds of many spatial branch-and-bound algorithms in global optimization is ensured. Similarly, it is straightforward to compute a sequence of points 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 697 (xk)k∈Nthat possesses a convergent subsequence (xkν)ν∈Nsuch that limν→∞ xkν= x∗, where x∗denotes a globally minimal point of the problem P(B). This follows immediately from the theory on global optimization (see, e.g., [23]) and is ensured under mild assumptions. Depending on the exact type of algorithm, for instance, the midpoints of the boxes that are currently examined in the branch-and-bound framework possess a subsequence that fulfills this requirement, as we shall see in Sect. 4.In contrast, similar convergence results for upper bounds have not been established in general, as discussed in Sect.1. In this article, we are concerned with the computation of convergent upper bounds. As already discussed before, computing valid upper bounds is closely related to finding feasible points because evaluation of the objective function fat a feasible point immediately yields an upper bound for v∗. Therefore, our new upper bounding procedure is based on an efficient method to generate feasible points of problem P(B). As a key idea, our approach draws on a technique called restriction of the righthand side, which is introduced in [40,41] for (generalized) semi-infinite problems. Using this technique, we introduce some tolerance in the constraints. Importantly, in contrast to the concept of εf-feasibility, here it is used to further restrict them. Hence, we require gi(x)≤−εffor all constraints gi. Clearly, a point satisfying these conditions is also feasible for P(B). However, if εfis chosen too large, the feasible set can become empty. Moreover, using a fixed value of εfin general does not lead to a convergent upper bounding procedure. For that reason, in order to combine restriction of the right-hand side with a standard branch-and-bound algorithm in global optimization, a crucial component of our procedure is to drive εfto zero in an appropriate way. As we shall see throughout this article, this can be achieved such that convergence of upper bounds is ensured, and thus branch-and-bound algorithms are proven to terminate. We remark that in [40,41] in presence of semi-infinite constraints several nonlinear problems have to be solved from scratch using different parameter settings to obtain the desired upper bounds. However, in standard global optimization, i.e. in the absence of semi-infinite constraints, it is not possible to solve several optimization problems from scratch in order to compute the solution of a single optimization problem, since this is by far too expensive from a computational point of view. Therefore, in this article we propose to carefully incorporate the concept of restriction of the right-hand side into a spatial branch-and-bound algorithm, such that we get along without this requirement. Essentially, as we shall see, this incorporation results in a different box selection rule in the branch-and-bound algorithm. 3 Incorporation of restriction of the right-hand side into spatial branch-and-bound methods In this section, we propose a new upper bounding procedure which is convergent. It is based on finding feasible points of P(B)with guarantee and then evaluating the objective function fin such points. To achieve this, the main idea is to exploit convergence of subsequences (xki)i∈Nfor a slightly altered problem. 123 698 P. Kirst, C. Füllner More precisely, given a parameter δ>0, we consider a problem of the form P(B,δ):min x∈Rnf(x) s.t.gi(x)≤−δ, i∈I, x∈B. Werefertothisastherestricted problem. The feasible set of P(B,δ)is denoted by M(B,δ)and, moreover, let xdenote a globally optimal point of P(B,δ). According to the explanation at the beginning of this section, given that δis chosen carefully such that M(B,δ)still contains a feasible point, by applying a branch-andbound algorithm a subsequence (xkν)ν∈Nis generated that satisfies limν→∞ xkν=x. This implies gi(x)≤−δand due to continuity of the functions githere exists someν such that for all ν≥νwe have gi(xkν)<0. Thus, as the box constraints are fulfilled as well, xkνis feasible for the original problem P(B), and we obtain an upper bound for v∗by evaluating the objective function fin xkν. Note that the main difference to applying the same reasoning to the original problem P(B)is that by restriction of the right-hand side we ensure that a feasible point satisfying gi(x)≤0 is found after a finite number of steps and not only in limit. Simply applying a spatial branch-and-bound algorithm to the problem P(B,δ) instead of the original problem P(B)is still not sufficient for our purpose. In particular, in that case the obtained lower bounds converge to the optimal value of the restricted problem which may differ from the value of interest v∗. This is clearly not desired. Moreover, simply using some fixed δ>0 is not sufficient to obtain a sequence of upper bounds that converges to v∗as upper bounds may remain too large in such a setting. For that reason, our main idea is to combine the solution of the original problem P(B)and the use of restriction of the right-hand side in a reasonable way. To this end, we consider a standard spatial branch-and-bound algorithm for solving P(B)and, in addition, incorporate the solution of more restricted problems for different values of δ. This is explained in the following and stated formally in Algorithm 1. As is common for spatial branch-and-bound algorithms in global optimization, each iteration kis started by choosing a tuple (Xk,v k)from a list Lof boxes still to explore, with vka lower bound for the optimal value v∗(Xk)on Xk(Step 1). In every second iteration, we follow the selection rule of classical spatial branch-and-bound algorithms in global optimization, which typically means that a box with the smallest lower bound is chosen, as it appears most promising to contain a globally minimal point x∗. We refer to this as a normal selection step. In the remaining iterations, we only choose boxes Xkthat may contain feasible points for the restricted problems P(Xk,δ), thus aiming at the solution of problems P(B,δ). This is checked by computing lower bounds gi(Xk)for all gi,i∈I,onXk using lower bounding procedures, such as interval arithmetic [42]. In case that no such box can be selected, we reduce the value δ>0 in order to refine the approximation obtained by restriction of the right-hand side. The same refinement is applied if a feasible point for P(B)is found (see Step 4) in order to ensure convergence of the upper bounds to v∗. We refer to this as a restricted selection step. 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 705 Proof We consider an exhaustive subsequence of boxes (Xkν)ν∈Nchosen in Step 1 with max i∈Igi(Xkν)≤−δfor all ν∈N. First, we point out that given the box selection rule in Step 1 such an exhaustive sequence of boxes exists, provided the possibly infinite branch-and-bound procedure corresponding to εv=0 does not terminate. This follows immediately using standard arguments from global optimization. In order to see this, it is important to note that there are at most a finite number of such boxes in the list Lin every iteration and at least in every second iteration one must choose such an element. For a more formal explanation we refer to the proof of Theorem IV.1. as well as to Corollary IV.1. in [23]. We now consider a point xthat is contained in all boxes Xkνfor all ν∈N.Fromthe definition of M-independent lower bounding procedures as well as continuity of the defining functions it follows limν→∞ gi(Xkν)=gi(x)for all i∈I, and hence we have maxi∈Igi(x)≤−δ. Again, using continuity of the functions gi,forνsufficiently large we conclude that all points in Xkνare feasible for P(B). Therefore, every point xkνthat is chosen from this box is feasible as well, which concludes the proof.  Revisiting our discussion on feasibility verification from Sect.3, we observe that the proof of Lemma 2allows to check feasibility for sets M(Xj k,¯ δ) with 0 <¯ δ<δ in Step 4 of Algorithm 1without compromising the result. Importantly, it can be shown that the assumptions of Lemma 2are always satisfied after a finite number of steps. Lemma 3 Assume that Assumption 1and Assumption 2are satisfied, and that the possibly infinite branch-and-bound procedure corresponding to εv=0in Algorithm 1 does not terminate. Let (δk)k∈Ndenote the sequence of δobtained in Algorithm 1. Then, there exists some ¯ k∈Nsuch that the first condition from Lemma 2is satisfied for all k≥¯ k. Proof First, we note that due to the existence of a Slater point ˜x∈M(B)satisfying gi(˜x)<0 for all i∈I(Assumption 2), for some sufficiently small ¯ δ>0, the first condition from Lemma 2is guaranteed to be satisfied. By construction, it is also satisfied for all δ<¯ δthen. We now prove that such a ¯ δis reached in Algorithm 1after a finite number of steps. We assume that this does not hold and derive a contradiction. Hence, we assume that for all k∈N,wehavegi(x)>−δkfor all x∈M(B)and at least one i∈I. We now consider an exhaustive subsequence of boxes (Xkν)ν∈Nobtained in Algorithm 1, with ¯x∈Xkνfor all ν∈N.Wehave ¯x∈M(B),asbyLemma4.1in[30], otherwise the boxes (Xkν)ν∈Nwould no longer be selected and refined in Algorithm 1 after a finite number of steps. As the M-independent lower bounding procedure gi,i∈I,is convergent according to Assumption 1, for at least one i∈Iwe obtain limν→∞ gi(Xkν)=gi(¯x)> −δkν. From continuity it follows that there exists some ¯ν∈Nsuch that also maxi∈Igi(Xkν)>−δkνfor all ν≥¯ν. 123 706 P. Kirst, C. Füllner However, this means that for all ν≥¯νthe list ¯ Lis empty and the parameter δkis decreased in Step 1 of Algorithm 1. The same argument can be repeated, so we obtain limν→∞ δkν=0, and thus also limk→∞ δk=0. This is a contradiction to ¯ δnot being reached after a finite number of steps.  Remark 1 Lemma 3in combination with Lemma 2implies that after finitely many steps in Algorithm 1a feasible point is identified, and thus the global upper bound ukis updated. In particular, there exists a non-empty subsequence (ukν)ν∈Nof upper bounds related to iterations kν,ν ∈N,where the upper bound is updated. Remark 2 From Lemma 3it also follows that there exists some ˜ k∈Nsuch that for all k≥˜ kwe have M(B,δ˜ k)=∅. Therefore, by restricting to a subsequence (δkν)ν∈N with kν≥˜ kfor all ν∈N, all conditions of Lemma 1are satisfied. With these results, we are now able to prove convergence of the sequence of upper bounds generated by Algorithm 1. Theorem 4 Consider problem P(B)with non-empty feasible set M(B). Let Assumptions 1and 2hold. Then, if the possibly infinite branch-and-bound procedure corresponding to εv=0in Algorithm 1does not terminate, the sequence of upper bounds (uk)k∈Nconverges to the globally optimal value v∗. Proof The sequence (uk)k∈Nof upper bounds generated by Alorithm 1is monotonically decreasing and bounded from below by the optimal value v∗of the original problem P(B). Thus, the sequence (uk)k∈Nis convergent. However, it remains to be shown that this sequence really converges to the globally optimal value v∗of P(B). To this end, we consider the non-empty subsequence (ukν)ν∈Nwhere there is an update of the upper bound in iteration kν. According to Lemma 3and Remark 2such a sequence exists. The values ukνare computed by evaluating the objective function at feasible points (xkν)ν∈N. Since all these points are feasible and since the feasible set is compact, there must be a cluster point xof this sequence of points with x∈M(B). Next, we show that xis, in fact, a globally optimal point of problem P(B).To achieve this, we assume that this is not the case and derive a contradiction. Hence, if xis feasible and not optimal, then we have f(x)>v ∗. Moreover, in view of the box selection rule of Algorithm 1there must be an exhaustive sequence of boxes (Xμ)μ∈N created by the algorithm such that x∈Xμfor all μ∈N. By Assumption 1our lower bounding procedures are convergent, so we have lim μ→∞(Xμ)=f(x)>v ∗. In particular, there is some μsuch that (Xμ)>1 2f(x)+v∗for all μ≥μ. (1) We now continue to show that this is actually not possible. To this end, we consider an arbitrary iteration ktogether with the corresponding δk. After a finite number of 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 707 iterations we either have that the list Lis empty or otherwise, as shown in Lemma 3, that a feasible point is found. In both cases, in these iterations kthe value δkis decreased by letting δk+1=γδ k(either in Step 1 or in Step 4). Inductively, for that reason, we have limk→∞ δk=0. Additionally, by Lemma 3and Remark 1, for sufficiently large k, all conditions of Lemma 1are satisfied. Hence, we conclude that the sequence of optimal values v∗ kof the problems P(B,δ k)converges to v∗. In particular, there is some k∈Nsuch that v∗ k≤1 2f(x)+v∗for all k≥k. Then, however, for k≥k, neither in iterations with an even iteration number knor in iterations with an odd iteration number kwe select a box in Step 1 of Algorithm 1with a lower bound larger than v∗ k≤1 2(f(x)+v∗), because there are always boxes with a smaller lower bound contained in the list Land L, respectively. In particular, that means that inequality (1) is violated for μsufficiently large, such that the sequence (Xμ)μ∈Nis not created by the algorithm at all. This contradicts our assumption and, hence, the point xmust be a globally optimal point of the problem P(B). Since our upper bounds are created by evaluating the objective function at the points (xkν)ν∈Nand since this sequence possesses the feasible point xas a cluster point, the assertion now follows from continuity of the objective function f. 4.2 Convergence of lower bounds and optimal points In this section we establish convergence of the sequence of the overall lower boundsvk of Algorithm 1. Together with the convergent upper bounding procedure this ensures finite termination of the branch-and-bound algorithm. Similarly, one can establish a convergence result for optimal points. Proposition 5 Let M(B)=∅and let Assumption 1hold. Then, if the possibly infinite branch-and-bound procedure of Algorithm 1corresponding to εv=0does not terminate, for the overall lower bounds vkin every iteration k the limit satisfies limk→∞vk=v∗where v∗denotes the optimal value of P(B). Proof We apply Theorem IV.3. from [23]. To this end, two main properties need to be ensured, i.e. the bounding operation needs to be bound improving and consistent.The former means that after a finite number of iterations a tesselation element needs to be selected where the lowest bound is attained. Clearly, in Algorithm 1in every second iteration such a box is chosen. The latter, i.e. consistency of the bounding operation, is a bit more involved. In view of the box division rule in Algorithm 1for our setting this means that for every exhaustive sequence of boxes (Xkν)ν∈Ncreated by the algorithm we have lim ν→∞ukν−(Xkν)=0. 123 708 P. Kirst, C. Füllner Clearly, this expression cannot be negative, since boxes Xwhere the lower bound (X) is strictly larger than the current upper bound ukare fathomed in Step 6 of the algorithm. Moreover, for any threshold τ>0 the difference ukν−(Xkν)cannot remain larger than τ, as we show now. From Theorem 4we know that for the subsequence of upper bounds (ukν)ν∈Nwe have lim ν→∞ukν=v∗. Furthermore, by monotonicity of the lower bounding procedure the sequence of lower bounds ((Xkν))ν∈Nis monotonically increasing. As it is also bounded from above by v∗, it is convergent. Let us now assume for a moment that lim ν→∞(Xkν)=v<v ∗. Then, there exists a feasible point x∈Xkνfor all νwith f(x)=v, see Lemma 4.1 in [30]. However, that means that v∗could not be the optimal value of the problem, which contradicts our assumption. Hence, we have 0≤ukν−(Xkν)=ukν−v∗+v∗−(Xkν) and the assertion follows by sandwiching the expression in the middle.  In classical branch-and-bound algorithms in global optimization one can easily consider convergent subsequences of points in boxes and usually these subsequences converge to globally optimal points of the original problem. Due to the fact that not always boxes with the most promising lower bounds are selected in Step 1, in Algorithm 1one could think that this might not necessarily be the case. However, in the next result we show that this result still holds under this modification. Proposition 6 Let M(B)=∅, let Assumption 1and Assumption 2hold and let us assume that the possibly infinite branch-and-bound procedure of Algorithm 1corresponding to εv=0does not terminate. Moreover, we consider a subsequence of boxes (Xk)k∈Nchosen in Step 1, and let xk∈Xkfor all k ∈N. Then, (xk)k∈Npossesses a cluster point and any such cluster point is a globally optimal point of P(B). Proof Due to xk∈Bfor all k∈Nand due to the fact that Bis bounded, the sequence (xk)k∈Npossesses a cluster point. We now consider a convergent subsequence (xkν)ν∈N of (xk)k∈Nand put x:= limν→∞ xkν. Next, we assume that xis not a globally optimal point and derive a contradiction by distinguishing two different cases. Case 1: x∈M(B)and f(x)>v ∗.Then, there exists an exhaustive sequence of boxes (Xkμ)μ∈Ngenerated by the algorithm with x∈Xkμfor all μ∈N. According to Assumption 1in Step 3 an M-dependent lower bounding procedure is used, so we have limμ→∞ (Xkμ)=f(x). Using arguments from the proof of Theorem 4we can show that after a finite number of iterations no box with (Xkμ)> 1 2(f(x)+v∗)is selected and, hence, the exhaustive sequence of boxes (Xkμ)μ∈Nis not created at all, contradicting the assumption. 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 709 Case 2: x/∈M(B). Then, by Assumption 1we have limμ→∞ (Xkμ)=+∞. Again, this can be ruled out by using the same line of arguments as in the proof of Theorem 4. According to Theorem 4, the overall upper bounds generated by Algorithm 1converge to the globally optimal value if the assumptions of Theorem 4hold. Moreover, in view of Proposition 5lower bounds are ensured to converge to the globally optimal value as well. Therefore, the branch-and-bound method terminates after a finite number of iterations for εv>0. This immediate consequence is stated formally in the following result. Corollary 7 Consider problem P(B)with non-empty feasible set M(B)and let a positive termination tolerance εv>0be given. Further assume that Assumption 1 and Assumption 2hold. Then, if a convergent lower bounding procedure is used, Algorithm 1terminates after a finite number of iterations. Proof Since the lower bounding procedure is assumed to be convergent we have from Proposition 5the limit limk→∞vk=v∗. Moreover, according to Theorem 4we have limk→∞ uk=v∗. Thus, we obtain lim k→∞(uk−vk)=lim k→∞(uk−v∗)+(v∗−vk)=0. Therefore, after a finite number of iterations we have uk−vk≤εv, and the assertion must hold.  Let us remark that we have not addressed the case of an empty feasible set yet. Typically, spatial branch-and-bound algorithms in global optimization are able to recognize this by stopping with a certificate of infeasibility. In this case, no box can be selected in Step 1 anymore, since the list Lbecomes empty. In principle, this also holds for Algorithm 1. In order to show this formally, it is required that the lower bounding procedure is not only convergent, but also recognizes empty boxes Xby evaluating to the extended real value (X)=+∞, provided that the box Xis sufficiently small. This is also fulfilled for common lower bounding procedures (see, e.g., [3,4,7]). 5 Discussion of the assumptions In the following we briefly discuss our main requirements that need to be fulfilled so that the concept of restriction of the right-hand side in Algorithm 1is sufficient to ensure termination of spatial branch-and-bound algorithms. We start with Assumption 1that is straightforward in this regard, as it comprises a common requirement regarding the lower bounding procedure in global optimization. In fact, lower bounding procedures that fulfill this are widely used and typically required for basically all algorithms in that domain (see, e.g., [23,30]). In contrast, Assumption 2is rarely used in global optimization, although very common in local optimization. Moreover, under the additional assumption that all defining functions are differentiable, it can even be shown to be a straightforward 123 710 P. Kirst, C. Füllner consequence of other (weak) constraint qualifications that are also common in nonlinear local optimization. This holds, for instance, for the Mangasarian-Fromovitz constraint qualification (MFCQ). In order to formulate this for problem P(B)we explicitly rewrite the box constraints as additional constraints, see [30]: hi(x)=bi−xi≤0i=1,...,n hj(x)=xi−bi≤0j=n+1,...,2n. Then, MFCQ is said to hold at a feasible point x∈M(B), if there is a direction d∈Rnsuch that Dgi(x)d<0 for all active indices, i.e. indices iwith gi(x)=0 Dhj(x)d<0 for all active indices, i.e. indices jwith hj(x)=0. Hence, if MFCQ holds at every globally optimal point x∗, then standard arguments show that for λ>0 sufficiently close to zero we have gi(x∗+λd)<0 for all i∈I and hj(x∗+λd)<0 for all j=1,...,2n, and thus a Slater point exists in every neighbourhood N(x∗)around a point x∗.In particular, that means that Assumption 2holds. Hence, Assumption 2is mild in the sense that it is a direct consequence of MFCQ, which, in turn, is implied by the Linear Independence Constraint Qualification (LICQ). This, however, is already mild in the sense that it is proven to generically hold everywhere in the feasible set M(B)(see [27]). The latter means, in particular, that in case of its violation it may be expected to hold at least under small perturbations of the problem data. We briefly state the aforementioned consideration in the next remark. Remark 3 Let MFCQ or LICQ hold in every globally optimal point of problem P(B). Then, Assumption 2is fulfilled. Furthermore, we point out that in nonlinear local optimization the assumption of LICQ even in all locally minimal points is standard for convergence proofs. This means, in particular, that common upper bounding procedures in spatial branch-andbound methods which rely on the local solution of NLP subproblems implicitly use this or related assumptions as well and, hence, Assumption 2is not restrictive in this regard. Finally, let us stress that even in case that Assumption 2is violated, our upper bounding procedure may still provide valid upper bounds, although it may happen that these upper bounds do not converge to the globally optimal value v∗. As becomes clear from the proof of Lemma 1it is not possible, though, that a value is computed that is strictly smaller than v∗, in contrast to many other approaches such as acceptance of εf-feasible points. 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 711 Table 1 Test problems and dimensions name np booth 2 1 hs011 2 1 simpllpa 2 2 zecevic4 2 2 hs030 3 1 congigmz 3 5 hs044 4 6 hs268 5 5 ex3_1_2 5 6 hs098 6 4 hs113 10 8 6 Illustrative computational results In this section, we provide illustrative computational results for 11 small test problems from the COCONUT benchmark library [50], which are summarized in Table 1with their name, variable dimension and number of inequality constraints. We should emphasize that we do not present results for extensive computational tests and large problem instances, and this is for the following reason: The merit of restriction of the right-hand side is that it is a very simple, but powerful concept that allows to ensure deterministic and finite convergence of spatial branch-and-bound methods with marginal additional computational effort. For most of the implementations of such algorithms, this is not guaranteed. However, solvers like ANTIGONE, BARON, LINDOGlobal, Octeract or SCIP are highly-tuned and perform extremely well for many test problems. Therefore, we do not expect a simple implementation using restriction of the right-hand side to be computationally competitive with these solvers. We rather advocate to incorporate our proposed approach into existing methods as an additional way to obtain upper bounds and as a convergence guarantee. The results in this section are included for illustrative reasons and as a proof-of-concept. 6.1 Implementation and test details Our implementation is based on Algorithm 1with only slight modifications. The algorithm is implemented in Python 3.7. For numeric operations Numpy and Scipy are used, and for interval arithmetic operations we apply the IntvalPy package [6]. The lower bounds are computed using centered forms [31]. Moreover, as indicated in Sect.3, for each k,thevalueδ(Xk)=maxi∈Igi(Xk)is computed once when the box Xkis constructed. We do not use bounds tightening or similar acceleration techniques. In Step 4 of Algorithm 1, we use three different strategies to choose candidate points xj k: (a) Mid: Here, we choose xj k:= mid(Xj k), and then check for feasibility. 123 712 P. Kirst, C. Füllner (b) Mid + Loc: Here, in addition to (a), if mid(Xj k)/∈M(Xj k),werunIPOPT [58] to obtain a local solution of P(Xj k)as an alternative candidate for xj k.This candidate is then checked for feasibility. (c) Mid + Loc-Res: Same approach as (b), but for kbeing even, we solve the restricted problem P(Xj k,δ k)locally; see also our discussion at the end of Sect. 3. In each case, we do not allow for εf-feasibility when checking whether xj k∈ M(Xj k). To access IPOPT as a local solver, we use the default function minimize_ipopt from the Python package cyipopt [5]. We use the default feasibility tolerance of 10−4,but do not provide information on gradients or Hessians manually. For restriction of the right-hand side, we choose δ0=1,γ =0.95 and perform a restricted selection step in every κ-th iteration with κ∈{2,10,100}. We compare this to a branch-and-bound method with only normal selection steps (no restriction). Note that for case Mid + Loc-Res we only consider κ∈{2,10}, since solving the restricted problems locally only seems worthwhile if restricted problems occur sufficiently often. For the termination criterion we set εv=10−3and additionally introduce a time limit of 7,200s and an iteration limit of 10,000 iterations. The experiments are executed on a Windows machine with 2.5GHz Intel Core i5-6300U CPU and 12GB of RAM. 6.2 Discussion of results The results are summarized in Tables 2. The columns compare the results for different values of κ(with “-” indicating that no restriction is applied) and with different selection strategies for xj k. In each column, the total number of iterations until termination (itterm), the first iteration in which a feasible point is found and an upper bound is computed (it feas), the total time in seconds (time) and the solution status (status) are reported. If the problem is not solved to optimality, we report the remaining relative optimality gap UB−LB |UB|as the status. The results show that the computational performance of using restriction of the right-hand side and of using only normal selection steps do not differ by much (for all strategies, Mid,Mid + Loc and Mid + Loc-Res). On first sight, this seems detrimental, as we do not see a clear performance advantage for our proposed method. However, the results highlight that restriction of the right-hand side provides a convergence guarantee at low computational overhead, i.e. without compromising the performance of the spatial branch-and-bound method by much. For several problems, the number of iterations and total time required until termination are a bit lower if only normal selection steps are applied, but this is not always the case. In fact, we see that in one case, for problem congigmz, restriction of the right-hand side with a sufficiently small κand xj k=mid(Xj k)leads to an early identification of a feasible point, and thus computation of a valid upper bound for v∗. In contrast, without restriction of the right-hand side no finite upper bound can be computed within the given time and iteration limit. 123 On the Use of Restriction of the Right-hand Side in Spatial Branch… 713 Table 2 Computational results for Algorithm 1 (part 1) Mid Mid +Loc Mid +Loc-Res κ2 10 100 - 2 10 100 - 2 10 booth itt527 527 2 527 2 2 2 2 2 2 it f526 526 1 526 1 1 1 1 1 1 time1821417322222 status* opt opt opt opt opt opt opt opt opt opt hs011 itt1683 1673 1672 1672 1672 1672 1672 1672 1671 1672 it f1111111111 time 57 56 52 56 673 613 627 599 1004 710 status* opt opt opt opt opt opt opt opt opt opt simpllpa itt106 92 89 89 106 92 89 89 100 92 it f1111111111 time3 3 6 4 201918182720 status* opt opt opt opt opt opt opt opt opt opt zecevic4 itt609 579 572 570 603 579 572 572 570 579 it f4444444424 time 27 29 29 47 532 506 542 509 521 667 status* opt opt opt opt opt opt opt opt opt opt hs030 ittmax max max max 400 400 400 400 414 400 it f- - - - 111111 time 334 292 386 345 354 349 356 338 494 413 status* - - - - opt opt opt opt opt opt congigmz ittmax max max max 852 839 728 920 594 511 it f964 1580 - ------- time 1042 1017 1345 1049 max max max max max max status* 0.02 0.21 - ------- hs044 itt398 283 268 268 398 283 269 269 384 283 it f47 47 47 47 47 47 47 47 47 47 time 46 43 36 40 2194 1870 1614 1577 2195 1746 status* opt opt opt opt opt opt opt opt opt opt 123 714 P. Kirst, C. Füllner Table 2 continued Mid Mid +Loc Mid +Loc-Res κ2 10 100 - 2 10 100 - 2 10 hs268 ittmax max max max 902 839 738 912 862 780 it f----- - - - - - time 1536 1926 1914 1466 max max max max max max status* ----- - - - - - ex3_1_2 ittmax max max max 613 710 652 714 732 221 it f22222 2 2 2 4 2 time 2793 2871 2619 2384 max max max max max max status* 0.01 0.01 0.01 0.01 5.65 1.97 2.01 1.90 5.65 6.59 hs098 ittmax max max max 525 529 493 529 522 350 it f----299223210210420 time 2102 2418 2323 2518 max max max max max max status* - - - - 71.83 68.02 68.05 67.15 71.88 72.70 hs113 ittmax max 6725 max 79 73 62 82 69 74 it f----- - - - - - time 3456 4360 max 6995 max max max max max max status* ----- - - - - - *opt:anε-optimal solution has been determined; otherwise the remaining relative gap UB−LB |UB|is reported (“-” if no UB has been found) Whereas the additional usage of basic IPOPT does not lead to significantly more instances being solved (only hs030), and also slows down the solution process, the results illustrate that local solvers can be easily combined with restriction of the righthand side and leveraged to find feasible points more quickly (see booth, hs030, hs098). For 2 out of 12 test problems, even with restriction of the right-hand side, no valid upper bound is determined within the given time and iteration limit. Additionally, for 5 problems, finite upper bounds are determined, but no convergence is achieved in the predefined iteration and time limit, even if for congigmz and ex3_1_2 at least very small relative optimality gaps are reached. This lack of performance can be assumed to be explained by the very simple branchand-bound implementation. In practical applications, a branch-and-bound method using restriction of the right-hand side could be tuned by introducing improved lower bounding procedures, bounds tightening, additional strategies to identify feasible points and several more acceleration techniques. Also IPOPT could be tuned, for instance by providing derivative information. Finally, let us note that even in cases where we only examine box midpoints for feasibility, for 6 out of 12 test problems, the branch-and-bound method terminates 123