A general branch-and-bound framework for continuous global multiobjective optimization
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Eichfelder, Gabriele; Kirst, Peter; Meng, Laura; Stein, Oliver Article — Published Version A general branch-and-bound framework for continuous global multiobjective optimization Journal of Global Optimization Provided in Cooperation with: Springer Nature Suggested Citation: Eichfelder, Gabriele; Kirst, Peter; Meng, Laura; Stein, Oliver (2021) : A general branch-and-bound framework for continuous global multiobjective optimization, Journal of Global Optimization, ISSN 1573-2916, Springer US, New York, NY, Vol. 80, Iss. 1, pp. 195-227, https://doi.org/10.1007/s10898-020-00984-y This Version is available at: https://hdl.handle.net/10419/287463 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. https://creativecommons.org/licenses/by/4.0/
Journal of Global Optimization (2021) 80:195–227 https://doi.org/10.1007/s10898-020-00984-y A general branch-and-bound framework for continuous global multiobjective optimization Gabriele Eichfelder1·Peter Kirst2·Laura Meng3·Oliver Stein3 Received: 20 July 2020 / Accepted: 12 December 2020 / Published online: 19 January 2021 © The Author(s) 2021, corrected publication 2021 Abstract Current generalizations of the central ideas of single-objective branch-and-bound to the multiobjective setting do not seem to follow their train of thought all the way. The present paper complements the various suggestions for generalizations of partial lower bounds and of overall upper bounds by general constructions for overall lower bounds from partial lower bounds, and by the corresponding termination criteria and node selection steps. In particular, our branch-and-bound concept employs a new enclosure of the set of nondominated points by a union of boxes. On this occasion we also suggest a new discarding test based on a linearization technique. We provide a convergence proof for our general branch-and-bound framework and illustrate the results with numerical examples. Keywords Multiobjective optimization ·Nonconvex optimization ·Global optimization · Branch-and-bound algorithm ·Enclosure 1 Introduction In this paper we propose a general solution approach for continuous multiobjective optimization problems of the form min f(x)s.t. g(x)≤0,x∈X(MOP) BOliver Stein [email protected] Gabriele Eichfelder [email protected] Peter Kirst [email protected] Laura Meng [email protected] 1Institute for Mathematics, Technische Universität Ilmenau, Ilmenau, Germany 2Operations Research and Logistics (ORL), Wageningen University & Research (WUR), Wageningen, The Netherlands 3Institute of Operations Research (IOR), Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany 123
196 Journal of Global Optimization (2021) 80:195–227 with a vector f:Rn→Rmof continuous objective functions, a vector g:Rn→Rk of continuous inequality constraint functions, and an n-dimensional box X=[x,x]with x,x∈Rn,x≤x. We do not impose any convexity assumptions on the entries of for gso that, in particular, the set of feasible points M={x∈X|g(x)≤0}(1) is not necessarily convex. Nevertheless, the proposed approach will aim at the global solution of MOP,inasensedefinedbelow. The literature on deterministic algorithms for globally solving problems of the type MOP can be divided into two classes. One class comprises methods which use a parametric scalarization approach and then apply a single objective global optimization technique, mostly branch-and-bound, to the resulting auxiliary problems for each parameter. Examples and a discussion of the drawbacks of such approaches are given in [26]. The present paper falls into the second class of solution approaches which try to adapt the ideas of single objective branch-and-bound methods directly to the multiobjective setting, that is, they do without the intermediate step of some scalarization approach. The basic idea of any branch-and-bound algorithm for the minimization of a single function fover a set M starts by subdividing Miteratively into partial sets Mand then discarding all sets Mwhich cannot contain minimal points. The discarding tests rely on partial lower bounds for fon the sets M, and from them also an overall lower bound for the globally minimal value of fon Mcan be computed. In addition, the generation of feasible points during the discarding tests leads to overall upper bounds on the globally minimal value. A standard termination criterion for such algorithms is that the difference between the current overall upper and lower bounds drops below some prescribed tolerance. Consequently, the choice of a partial set Mwhich is branched into smaller sets in the next iteration is typically governed by the aim to reduce the difference between overall upper and lower bounds. As the partial sets Mmay be interpreted as nodes of the underlying branch-and-bound tree, the latter step is known as node selection. The contribution of the present paper is motivated by the fact that current generalizations of the branch-and-bound idea to the multiobjective setting do not seem to follow this train of thought all the way. In fact, while several suggestions for generalizations of partial lower bounds and of overall upper bounds are available, we are not aware of general constructions for overall lower bounds from partial lower bounds, and of the corresponding termination criteria and node selection steps. The aim of the present paper is to close this gap. In particular, in Sect. 2we will discuss in more detail that the single objective branch-andbound idea focuses on constructions in the image space of the optimization problem, whereas some of the known multiobjective branch-and-bound methods invest additional effort into constructions in the decision space. While this may be useful for good approximations of the efficient set (to be defined below), it is unrelated to the basic branch-and-bound idea. The first multiobjective branch-and-bound approach without an intermediate scalarization step, but with convergence considerations, was given in [12]. It is formulated for biobjective problems only and focuses on simple discarding tests based on monotonicity considerations and interval arithmetic. Its node selection rule chooses boxes one by one until all of them are sufficiently small for termination. Branch-and-bound methods for more than two objectives are proposed in [31]and[11]. The convergence results in [31] rely on growth conditions of image boxes in terms of decision space boxes as they hold in, e.g., interval arithmetic. The approach from [11] considers general lower bounding procedures for discarding tests, however in combination with a nonstandard notion of ε-efficient sets (to be defined below). Both in [11]andin[31] the termination criterion and node selection rule resemble the ones from [12]. In [26] significantly more efficient discarding tests for general multiobjective 123
Journal of Global Optimization (2021) 80:195–227 197 problems on convex feasible sets are suggested, which base on computing partial lower bounds by convex underestimators of the objective functions instead of interval arithmetic. Their termination criterion is based on a bound for the possible improvement from some lower bounds compared to upper bounds. A different algorithm for box constrained biobjective problems is presented in [28,37]. In combination with iterative trisections of the feasible set it makes use of the Lipschitz property of the objective functions to compute partial lower bounds via Lipschitz underestimators of the objective functions. An overall lower bound is constructed from these partial lower bounds, and they are compared to some simple overall upper bound in the node selection rule. However, the generalization of this approach to more objective functions and to more general feasible sets does not seem to be straightforward. The remainder of this paper is structured as follows. Section 2reviews some preliminaries from single objective branch-and-bound methods and from multiobjective optimization. Section 3introduces enclosures of the nondominated set of MOP as well as the computation of their widths as the central tools of our approach. Based on the concept of local upper bounds, an explicit choice for an overall upper bounding set within such an enclosure is introduced in Sect. 4. The construction of corresponding overall lower bounding sets bases on the partial lower bounding sets used for discarding tests. These are discussed in Sect. 5along with three explicit discarding techniques, where the construction of the corresponding partial lower bounding sets is based on singletons, convex underestimators and a relaxation-linearization technique, respectively, the latter being novel. Section 6constructs corresponding overall lower bounding sets from such partial lower bounding sets, before Sect. 7explicitly states a natural termination criterion, a related node selection rule, and the resulting multiobjective branch-and-bound framework in Algorithm 1. Section 8provides convergence results for this algorithm, and Sect. 9complements them with a proof of concept by some numerical illustrations. Section 10 concludes the article with final remarks. 2 Preliminaries To motivate the concrete branch-and-bound steps in the case of multiobjective optimization, let us first describe the framework for single objective optimization problems in some more detail. 2.1 Overview of single objective branch-and-bound In single objective optimization of fover Ma globally minimal point is some xmin ∈Msuch that no x∈Msatisfies f(x)< f(xmin)=v,wherevdenotes the globally minimal value. The discarding tests for subsets Mof Mare performed by comparing efficiently computable partial lower bounds bof fon Mwith the currently best known overall upper bound ub on the globally minimal value of fon M.Thevalueub =f(xub)results from the evaluation of fat the currently best known feasible point xub ∈M. In fact, any set Mwith b>ub may safely be discarded without deleting a globally minimal point of fon M, since all x∈M then satisfy f(x)≥b>ub ≥v. Of course also any empty set Mcan be discarded. The algorithm keeps a list Lof subsets Mwhich have not yet been discarded. A branch-and-bound iteration proceeds by choosing and deleting a subset Mfrom L, splitting this subset into two or more parts, and checking if the new subsets may be discarded or if some of them must again be written to L. If during the latter tests a point x ub ∈Mwith 123
198 Journal of Global Optimization (2021) 80:195–227 f(x ub)< f(xub)is generated, the currently best known feasible point and the corresponding upper bound are updated to x ub and f(x ub), respectively, and possibly further subsets may be discarded from Lby this updated information. These constructions do not only upper bound the globally minimal value vby ub = f(xub)≥v, but they also yield the overall lower bound v≥b:= minM∈Lb,since the partial minimal values vof fon Msatisfy v=minM∈Lvand the lower bounding property v≥bthus implies v≥b. Consequently, the minimal value vis sandwiched between band ub. If for a given tolerance ε>0 the branch-and-bound method generates bounds satisfying the termination criterion ub−b<ε, then, in addition to v≤f(xub),the point xub also satisfies f(xub)=ub <b+ε≤v+εand is hence ε-minimal, that is, no x∈Msatisfies f(x)< f(xub)−ε. For any ε>0 the above termination criterion will be met after finitely many branch-andbound steps if the method chooses points xk ub such that ubk=f(xk ub)converges to vfrom above, and if for the sets M∈Lkthe values bk=minM∈Lkbconverge to vfrom below. The latter is usually guaranteed by employing a node selection rule which in the hypothetical case ε=0 would select a set Mwith b=bkinfinitely often, along with choosing a lower bounding procedure with appropriate convergence properties. In practical implementations of such a branch-and-bound framework, the feasible set is usually assumed to be given in the form M=M(X)={x∈X|g(x)≤0}from (1) with a box X. Subdividing Mcan then be performed by subdividing Xinto subboxes Xand putting M:= M(X)={x∈X|g(x)≤0}. The list Lthen only needs to contain the information on subboxes Xalong with their corresponding partial lower bound bfor fon M(X). A common subdivision step consists in choosing some box Xfrom Land halving it along a longest edge into two subboxes X1and X2, which corresponds to splitting the set M=M(X)into M1=M(X1)and M2=M(X2). Upon termination of the branch-and-bound method the list Lwill contain at least one subbox Xwith xub ∈M(X),sothatfortheentireremainingboxes XinLthesetX∈LM(X) as well as its superset X∈LXare nonempty. In addition to the information that xub is εminimal, the described construction also implies that both latter sets form coverings of the set of all globally minimal points Xmin of fon M. This approach, however, neither forces the sizes of the remaining boxes Xor of the intervals f(M(X)) to become small, nor does it guarantee that the points in the covering X∈LM(X)form a subset of the set of ε-minimal points Xε min.Infact,examplesshow that the latter property may not even hold if the termination criterion ub−b<εis ignored, but the algorithm terminates after an arbitrary large number of iterations. Note that, in particular, the single objective branch-and-bound method does not focus on goodapproximations of minimalpoints xmin,but mainly on theapproximationofthe minimal value v. Moreover, the discarding tests and the termination criteria solely rely on bounds on objective function values, that is, the approach mainly works in the image set f (M).Below weshallseehow this carries over to the multiobjective setting. Clearly, working exclusivelyin the image space may be algorithmically beneficial since in many multiobjective applications its dimension is significantly smaller than the decision space dimension. 2.2 Efficient and nondominated points In the presence of more than one objective function there is in general no feasible point xmin ∈ Mwhich minimizes all objective functions simultaneously, that is, such that f(xmin)≤f(x) holds for all x∈M. Instead, one takes the equivalent negative formulation of optimality from 123
Journal of Global Optimization (2021) 80:195–227 199 the single objective case, namely, for xmin ∈Mthere exists no x∈Mwith f(x)< f(xmin), and transfers it to vector-valued functions f. In fact, a point xwE∈Mis called weakly efficientforMOP ifthere exists no x∈Mwith f(x)< f(xwE),wheretheinequalityismeant componentwise (cf., e.g., [10,25]). Since in some situations weakly efficient points allow the improvement of one objective function without any trade-off against other objectives, usually a stronger concept is employed in which the strict inequality f(x)< f(xmin)from the single objective case is rewritten as f(x)≤f(xmin)and f(x)= f(xmin). A feasible point xE∈M is called efficient for MOP if there exists no x∈Mwith f(x)≤f(xE)and f(x)= f(xE). The set of all efficient points XEis called efficient set of MOP and forms a subset of the set XwEof all weakly efficient points of MOP. We remark that under our assumptions the problem MOP possesses efficient points whenever Mis nonempty [10]. They usually form a set of infinitely many alternatives from which the decision maker has to choose. The notion of ε-minimality from the single objective case can be generalized to multiobjective problems as well. For ε>0 a point xε E∈Mis called ε-efficient for MOP (cf. [23] with choice εe∈Rm +) if there exists no x∈Msuch that f(x)≤f(xε E)−εeand f(x)= f(xε E)−εehold, where estands for the all ones vector. We denote the set of all ε-efficient points by Xε E. It is not hard to see that the chain of inclusions XE⊆XwE⊆Xε E holds for any ε>0 so that, in particular, under our assumptions all three sets are nonempty. Whereas efficiency, weak efficiency and ε-efficiency are notions in the decision space Rn, as mentioned above the branch-and-bound idea focuses on constructions in the image space Rm. These are covered by the following concepts. For points y1,y2∈Rmwe say that y1 dominates y2if y1≤y2and y1= y2holds. In this terminology a point xE∈Mis efficient if and only if f(xE)is not dominated by any f(x)with x∈M. Hence, the set YN=f(XE)of points yN∈f(M)which are not dominated by any y∈f(M)is called the nondominated set (also known as Pareto set) of MOP. The nondominated set YNplays the role of the minimal value vfrom the single objective case. Analogously,the weakly nondominated setYwN=f(XwE)of MOP consistsof thepoints ywN∈f(M)such that no y∈f(M)satisfies y<ywN, that is, such that no element of f(M)strictly dominates ywN,andtheε-nondominated set Yε N=f(Xε E)of MOP consists of the points yε N∈f(M)such that no element of f(M)dominates yε N−εe. In the single objective case Yε Ncorresponds to the (rarely discussed) set [v,v +ε]∩f(M)of ε-minimal values, whereas YwNbehaves like YNand collapses to v. In view of our above remarks, the three sets satisfy YN⊆YwN⊆Yε Nfor any ε>0, and they are nonempty for M=∅. 3 Enclosing the nondominated set The first aim of our multiobjective generalization of the branch-and-bound framework is to sandwich the nondominated set YNofMOP in some sense between an overall lower bounding set LB and an overall upper bounding set UB,whereLB is constructed from partial lower bounding sets. In Sect. 7this will lead to a termination criterion and a node selection rule. Since in set notation the single objective sandwiching condition b≤v≤ub may be rewritten as {v}⊆(b+R+)∩(ub−R+)(where, e.g., the expression b+Rm +is shorthand for the Minkowski sum {b}+Rm +), let us generalize it to the requirement YN⊆(LB+Rm +)∩(UB−Rm +)(2) with nonempty and compact sets LB,UB ⊆Rm. This is in line with the sandwiching approaches reviewed in [30] which, however, have not been combined with branch-andbound ideas. 123
200 Journal of Global Optimization (2021) 80:195–227 The enclosing interval [b,ub]for vfrom the single objective case thus generalizes to the enclosure E(LB,UB):= (LB+Rm +)∩(UB−Rm +) for YN. Since the single objective termination criterion ub−b<εmay be interpreted as an upper bound on the interval length of the enclosing interval [b,ub], a natural multiobjective termination criterion is to upper bound some width w(LB,UB)of the enclosure E(LB,UB) by a tolerance ε. In view of the special structure of the enclosure we suggest to measure its width with respect to the direction of the all ones vector e, that is, we define w(LB,UB)as the supremum of the problem max y,t(y+te)−y2/√ms.t. t≥0,y,y+te ∈E(LB,UB). ( W(LB,UB)) Thanks to the normalization constant √mthe objective function of W(LB,UB)equals t. Imposing the nonnegativity constraint on tis possible due to symmetry. Lemma 3.3 will provide a sufficient condition for the solvability of W(LB,UB)which is, however, only needed later. The following lemma first justifies the choice of this width measure. Lemma 3.1 For sets L B ,UB ⊆Rmwith YN⊆LB +Rm +and some ε>0let w(LB,UB)<ε. Then the relation E(LB,UB)∩f(M)⊆Yε N holds. Proof For any ¯y∈E(LB,UB)∩f(M)assume that there exists some y∈f(M)with y≤ ¯y−εeand y=¯y−εe. Since our assumptions imply external stability [32, Theorem 3.2.9], the point yeither lies in YNor is dominated by some yN∈YN. This implies y∈YN+Rm +⊆ LB +Rm +, and together with y≤¯y−εe≤¯y∈UB −Rm +it shows y∈E(LB,UB). Moreover, the point y+εeclearly lies in LB +Rm +, and with y+εe≤¯y∈UB−Rm +we also obtain y+εe∈E(LB,UB). Consequently (y,ε)is a feasible point of W(LB,UB), resulting in the contradiction w(LB,UB)≥εe2/√m=ε. Lemma 3.1 states that for w(LB,UB)<εall attainable points in the enclosure E(LB,UB)are ε-nondominated. In the single objective case (m=1) this statement collapses to the simple observation that for ub−b<εall values in the interval [b,ub]∩f(M) are ε-minimal, that is, they lie in [v,v+ε]∩f(M). Recall that, in combination with discarding tests based on ub, this does not entail that the elements of X∈LM(X)are ε-minimal points. Analogously one may not expect that the multiobjective discarding tests based on UB, as discussed in Sect. 5, will yield X∈LM(X)⊆Xε Efor w(LB,UB)<ε. As the condition y∈(LB +Rm +)∩(UB−Rm +)is equivalent to the existence of some b∈LB and ub ∈UBwith b≤y≤ub, the enclosure E(LB,UB)can be written as the union of the nonempty boxes which can be constructed with lower and upper bound vectors from LB and UB, respectively, E(LB,UB)= (b,ub)∈LB×UB b≤ub [b,ub].(3) This shows, in particular, that appropriate choices of LB and UB might lead to a disconnected enclosure E(LB,UB), thus correctly capturing the topological structure of YN. Moreover, the following result relates the computation of w(LB,UB)to the description 123
Journal of Global Optimization (2021) 80:195–227 201 (3)ofE(LB,UB)and implies that w(LB,UB)coincides with the largest value s(b,ub) among the above boxes [b,ub],where s(b,ub):= min j=1,...,m(ubj−bj)(4) denotes the length of a shortest edge of [b,ub]. Lemma 3.2 For any sets L B,UB ⊆Rmthe width w(LB,UB)of E(LB,UB)coincides with the supremum of max b,ub s(b,ub)s.t. (b,ub)∈LB×UB,b≤ub.(W(LB,UB)) Proof Since the objective function of W(LB,UB)satisfies (y+te)−y2/√m=t,in particular it does not depend on y. Hence the supremum of W(LB,UB)coincides with the supremum of max tts.t. t≥0,∃y∈Rm:y,y+te ∈(LB+Rm +)∩(UB−Rm +). (W(LB,UB)) Asthecondition y∈LB+Rm +implies y+te ∈LB+Rm +and,analogously, y+te ∈UB−Rm + implies y∈UB−Rm +, the latter existence constraint simplifies to ∃y∈Rm:y∈LB+Rm +,y+te ∈UB−Rm + or, equivalently, ∃(b,ub)∈LB ×UB :te ≤ub −b. The supremum of W(LB,UB)thus coincides with the supremum of max b,ub,tts.t. 0 ≤te ≤ub −b,(b,ub)∈LB ×UB which, after explicitly computing the upper bound s(b,ub)for t, yields the assertion. The next result immediately follows from Lemma 3.2 in view of the Weierstrass theorem. Lemma 3.3 Let the sets L B,UB ⊆Rmbe nonempty and compact, and let E(LB,UB)be nonempty. Then the problem W(LB,UB)is solvable. In particular, the width w(LB,UB)is a real number, and there exists some box [b,ub]with (b,ub)∈LB×UB,b≤ub and w(LB,UB)=s(b,ub). Note that under our assumptions the enclosure E(LB,UB)is nonempty whenever LB and UBsatisfy (2), as then ∅ = YN⊆E(LB,UB)holds. The combination of Lemmas 3.1,3.2 and 3.3 yields the following explicit sufficient condition for ε-nondominance of the attainable points in the enclosure E(LB,UB). Theorem 3.4 For nonempty and compact sets L B,UB ⊆Rmwith (2) and some ε>0let max {s(b,ub)|(b,ub)∈LB ×UB,b≤ub}<ε. (5) Then the relation E(LB,UB)∩f(M)⊆Yε N holds. FortheapplicationofTheorem3.4weshallsubsequentlyconstructsequencesofnonempty sets (LBk), (UBk)⊆Rmwith (2)forallk∈Nas well as limkw(LBk,UBk)=0. Then, 123
202 Journal of Global Optimization (2021) 80:195–227 in analogy to the single objective case, (5) may be employed as the termination criterion of a multiobjective branch-and-bound method for any prescribed tolerance ε>0. 4 Upper bounding the nondominated set Regardingthe generalization of the concept ofupper bounds ub =f(xub)forvwith xub ∈M from the single objective case, observe that the notion of a currently best feasible point does not make sense in the multiobjective setting. 4.1 The provisional nondominated set Instead, different feasible points xub ∈Mmay provide good approximations for different efficient points. Consequently, in the course of the algorithm one keeps a subset Xub of the finitely many feasible points generated so far or, as we wish to work in the image space, we rather keep the set F:= f(Xub), whose elements are to approximate different nondominated points of MOP. Itwouldbe useless, however, to store a point f(x1)with x1∈Xub in Fwhich isdominated by f(x2)for some x2∈Xub, as in this case the statement that x2is a better feasible point than x1does make sense. Hence, whenever some new point xub ∈Mis generated in the course of the algorithm, its image f(xub)is only inserted into Fif f(xub)is not dominated by any element from F. Moreover, all elements of Fwhich are dominated by f(xub)are deleted from F. In the following we will refer to this procedure as updating Fwith respect to f(xub). The source of the points xub will be elements of subboxes Xof X(e.g., their midpoints mid(X)) which are chosen for the discarding tests described below. If such an xub ∈Xis feasible for MOP the list Fwill be updated with respect to f(xub). As a consequence of this construction, no element of Fdominates any other element of F. Any subset of Rmwith the latter property is called stable, so that Fforms a finite and stable subset of the image set f(M)of MOP. Observe that also the nondominated set YNof MOP is a (not necessarily finite) stable subset of f(M). This motivates to call Fa provisional nondominated set [12]. From the single objective construction one may expect that the choice UB =Ffor the upper bounding set in (2) is possible. However, while the inclusion YN⊆F∪(F+Rm +)cdoes hold, simple examples show that the required inclusion YN⊆F−Rm +may fail. Fortunately the following concept, already used in [26], allows us to construct an upper bounding set UB from the information in F. 4.2 Local upper bounds The subsequent construction assumes the existence of a sufficiently large box Z=[z,z]with f(M)⊆int(Z)(where int denotes the topological interior). In the present setting of MOP the set f(M)is contained in the compact set f(X), so that the existence of such a box Z is no restriction. The explicit construction of some suitable Zis possible, for example, by interval arithmetic, which we shall discuss in more detail in Sect. 5.3. Given a finite and stable set F⊆f(M), the elements of the nondominated set YNcan, in particular, not be dominated by any q∈F. This motivates to define the so-called search 123
Journal of Global Optimization (2021) 80:195–227 209 Corollary 5.12 (Discarding via convex underestimators) Let Fbe a finite and stable subset of f (M), and let Xbe a subbox of X. If the infimum ϕLB αBB(p)of min t,xts.t.p+te ≥fα(x), gα(x)≤0,x∈X(DαBB(p)) satisfies ϕLB αBB(p)>0for all p ∈lub(F)with p ≥a αBB,thenX can be discarded. Note that DαBB(p)is the lifted version of the problem D(p,LB αBB), in analogy to the lifting (11). We remark that here the computation ofa αBB requires the solution of mconvex optimization problems, and the computation of each value ϕLB αBB(p)requires the solution of another convex optimization problem. It is not hard to see that the set {a αBB}+Rm +may be essentially larger than its subset fα(Mα(X)) +Rm +, so that for a box Xwhich is discarded via the partial lower bounding set LB αBB =fα(Mα(X)), this may not be possible via LB αBB,S={a αBB}. In [26] this discarding test is further refined by an iterative construction of polyhedral outer approximations of the convex set fα(M(X)) +Rm +in the spirit of a cutting plane method, starting from the polyhedral outer approximation {a αBB}+Rm +.Moreprecisely,firstthe infimum ϕLB αBB(¯p)of DαBB(¯p)is computed for some ¯p∈{p∈lub(F)|p≥a αBB}.In the case that ϕLB αBB(¯p)is positive and finite, also the remaining elements in {p∈lub(F)| p≥a αBB}\{¯p}must be checked for being elements of LB αBB +Rm +.However,thisis not necessarily done by computing their values ϕLB αBB(p). Instead information from the Lagrange multipliers corresponding to the optimal point of DαBB(¯p)lead to an inequality a,y≤bwhich is violated by y=¯pbut satisfied for all y∈LB αBB (see [26, Section 3.2] fordetailsandillustrations).Hence,subsequentlyinfimaϕLB αBB(p)onlyhavetobecomputed for the elements of the set {p∈lub(F)|p≥a αBB,a,p≤b}(if any). This generation of cutting planes is repeated as long as local upper bounds pwith ϕLB αBB(p)>0 are identified and speeds up the discarding test significantly. 5.5 Lower bounding via a linearization technique Instead of constructing polyhedral relaxations of the partial upper image set f(M(X))+Rm + by the generation of cutting planes to a convex relaxation, there is also a more direct method to generate polyhedral relaxations. To the best of our knowledge this has not yet been used in the framework of multiobjective branch-and-bound, and we shall present it next. This approach assumes that all entries of fand gare factorable. By introducing auxiliary variables it first reformulates the description of f(M(X)) such that nonlinear elementary functions only appear in single equations, and then the graphs of these nonlinear functions are relaxed to polyhedral sets. This so-called reformulation-linearization technique (RLT, also known as auxiliary variable method; AVM) is based on the reformulation analysis in [33,34]. The complete RLT approach is explained in, e.g., [4,35]. Example 5.13 Let us briefly illustrate the main idea of RLT for the polyhedral relaxation of the graph of the function ψ(x)=sin(x1exp(x2)) on the set X=[0,1]2. This graph may be written as gph(ψ, X)={(x,x3)∈X×R|x3=sin(x1exp(x2))} ={(x,x3)∈X×R|x3=sin(x4)with x4=x1exp(x2)} ={(x,x3)∈X×R|x3=sin(x4)with x4=x1x5,x5=exp(x2)}. 123
210 Journal of Global Optimization (2021) 80:195–227 Next, enclosing intervals Xifor the new variables xi,i=3,4,5 may be computed by interval arithmetic, e.g., x5∈X5:= EXP([0,1])=[exp(0), exp(1)], where EXP is the interval version of the elementary function exp. Hence, if x+denotes the vector of auxiliary variables and x:= (x,x+)the vector of all variables, we may recursively compute a box X=X×X+with x∈ X. This means that gph(ψ, X)may be written as the projection of the lifted graph gph(ψ, X):= {x∈ X|x3=sin(x4), x4=x1x5,x5=exp(x2)} to the space of the first three variables. This completes the reformulation step. The linearization step constructs a polyhedral relaxation of the lifted graph by relaxing each set defined by an individual equality constraint. For example, a polyhedral relaxation of the individual graph {(x2,x5)∈X2×X5|x5=exp(x2)}is given by the points in X2×X5= [0,1]×[1,exp(1)]below the secant to the function exp through the points (0,exp(0)) and (1,exp(1)), and above the two tangents to exp in (0,exp(0)) and in (1,exp(1)).Inthe factorization of a function usually most of those factors whose graphs must be relaxed are such univariate functions. Among the few exceptions is the multiplication of two variables as in the above expression x4=x1x5. However, the convex hull of the graph of a product of two variables over a box is explicitly known, and it is actually polyhedral [2]. Proceeding in this manner we arrive at a collection of linear inequalities Ax≤bwhich describe the polyhedral relaxation {x∈ X|Ax≤b}of the lifted graph gph(ψ, X).The projection of this set to the first three variables then is a polyhedral relaxation of gph(ψ, X). Fortunately, in our application of this technique in the framework of optimization problems it will not be necessary to compute a representation of the polyhedral relaxation in the original variables, but we will be able to work with the explicitly known lifted polyhedron. With a subbox Xof X, the reformulation-linearization technique for the construction of a partial lower bounding set LBfor f(M(X)) first views the partial image set f(M(X)) as the projection of the graph gph(f,M(X)) := {(x,f(x)) ∈X×Rm|g(x)≤0} to Rm. Then we introduce auxiliary variables xf∈Rmand xg∈Rkto lift this graph to the set gph(f,M(X)) := {(x,xf,xg)∈X×Xf×X g|xg≤0,xf=f(x), xg=g(x)} where the boxes Xf⊆Rmand X g⊆Rkare computed by interval arithmetic. Clearly, also the projection of gph(f,M(X)) to the xf-space Rmcoincides with f(M(X)). Next, each of the m+kfactorable equations xf=f(x)and xg=g(x)is treated as in Example 5.13, yielding a further lifting step to the set gphRLT(f,M(X)) := {x∈ X|xg≤0,Afx≤bf,A gx≤b g}. The projection of gphRLT(f,M(X)) to the (x,xf,xg)-space Rn×Rm×Rkthen is a polyhedral relaxation of the lifted graph gph(f,M(X)), and its further projection to the xf-space Rmconstitutes a polyhedral relaxation of the original partial image set f(M(X)). This projection to Rmis the desired partial lower bounding set LB RLT. Note that the latter set is closed as the projection of a closed polyhedron and thus compact as a closed subset of the compact box Xf⊆Rm. For the formulation of the corresponding auxiliary optimization problem D(p,LB RLT) an explicit description of the set LB RLT is fortunately not required, but due to the projection 123
Journal of Global Optimization (2021) 80:195–227 211 property we may as well solve the lifted problem min t,xts.t. p+te ≥xf,xg≤0,Afx≤bf,A gx≤b g,x∈ X,(DRLT(p)) that is, a box constrained linear program. Corollary 5.11 thus yields the following discarding test, where the entries of the corresponding lower estimate a RLT of the ideal point of fon M(X)are the optimal values of the mlinear optimization problems min x(xf)js.t. xg≤0,Afx≤bf,A gx≤b g,x∈ X with j∈{1,...,m}. Corollary 5.14 (Discarding via a linearization technique) Let Fbe a finite and stable subset of f (M), and let Xbe a subbox of X. If the infimum ϕLB RLT (p)of DRLT(p)satisfies ϕLB RLT (p)>0for all p ∈lub(F)with p ≥a RLT,thenX can be discarded. In the discarding test from Corollary 5.14 the computation of a value ϕLB RLT (p)can actually be terminated prematurely as soon as a dually feasible point with positive dual objective value has been generated, as weak duality then implies ϕLB RLT (p)>0. 6 Lower bounding the nondominated set After the concept of a partial lower bounding set LBfor f(M(X)) has been clarified, let us turn to the generalization of the overall lower bound b=minX∈Lbfor vfrom the single objective case. Recall that for the sandwiching property (2) we wish to define a set LB ⊆Rmwith YN⊆LB+Rm +, that is, an overall lower bounding set LB for YN. 6.1 Previous suggestions for overall lower bounding The convexification based branch-and-bound method from [26] guarantees that for its termination tolerance ε>0 the boxes X∈Lsatisfy (lub(F)−(ε/2)e−int(Rm +))∩(fα(M(X))+ Rm +)=∅. From thisparticularpropertyonecanconclude YN⊆(lub(F)−(ε/2)e−int(Rm +))c which leads to the overall lower bounding set LB =F−(ε/2)e.However,in[26]thisset LB is not used for node selection or a termination criterion, but solely to interpret the accuracy of the algorithm’s output. A similar construction is suggested in [11], but without an algorithmically suitable description and again only for an error estimate upon termination. As mentioned above, [37] suggests to compute partial lower bounds via Lipschitz underestimators of the objective functions. An overall lower bound is constructed from them by taking the nondominated set of the union of partial lower bounds. While this is in the spirit of our suggestion in Sect. 6.3,in[37] it remains unclear how the latter nondominated set is computed. Furthermore, the generalization of this approach to more than two objective functions and to feasible sets other than boxes does not seem to be straightforward. 6.2 Overall lower bounding via partial lower bounding sets The following result shows that for any lower bounding technique Twe may choose LB = X∈LLB T. Note that this set is compact as the union of the finitely many compact sets LB T,X∈L. 123
212 Journal of Global Optimization (2021) 80:195–227 Lemma 6.1 For any lower bounding technique T and partial lower bounding sets L B Tfor f(M(X)) define L BT:= X∈LLB T. Then the inclusion YN⊆LB T+Rm + holds. Proof Corresponding to any yN∈YNthere exists some efficient point xE∈M(X)with yN=f(xE). Assume that the subbox XEwith xE∈M(XE)does not lie in L.Thenithas been discarded, and since all discussed discarding tests are based on the general condition (12) from Proposition 5.8 with the set of local upper bounds lub(F)of some provisional nondominated set F, the box XEalso satisfies (8) with this set lub(F). Proposition 5.3 thus yields YN∩(f(M(XE)) +Rm +)=∅which contradicts yN∈f(M(XE)). Consequently there is some XE∈Lwith yN∈f(M(XE)) which implies yN∈f(M(XE)) +Rm +⊆LB T,E+Rm +⊆ X∈L LB T+Rm + and shows the assertion. In view of YN=∅Lemma 6.1 particularly guarantees LB T=∅. More importantly, together with (7) we have shown that the desired enclosing property (2) for the nondominated set YNmay in fact be formulated as YN⊆LB T+Rm +∩lub(F)−Rm +,(14) that is, the enclosure E(LB T,lub(F)) satisfies (2). In the single objective case it is clear that not only the function value v=f(xmin)of any minimal point xmin lies in the enclosing interval [b,ub], but also the function value f(xub)=ub of the currently best known feasible point. In the multiobjective setting this corresponds to the set E(LB T,lub(F)) not only enclosing the nondominated set YN,butalso the provisional nondominated set F=f(Xub). The following result verifies this. Lemma 6.2 For any lower bounding technique T the inclusion YN∪F⊆E(LB T,lub(F)) (15) holds. Proof Inview of (14) we only need to showF⊆E(LB T,lub(F)).Asexternalstabilityholds by [32, Theorem 3.2.9], we have F⊆YN+Rm +. By Lemma 6.1 this implies F⊆LB T+Rm +. From Lemma 5.1 we additionally know F⊆lub(F)−Rm +, so that the assertion is shown. Since both, LB Tand lub(F), are nonempty and compact sets, and since F⊆f(M) consists of attainable points, Lemma 6.2 and Theorem 3.4 even yield the following result, which prepares the termination criterion and node selection rule suggested in Sect. 7. Proposition 6.3 For some ε>0let max {s(b,p)|(b,p)∈LB T×lub(F), b≤p}<ε. Then all elements of the provisional nondominated set Fare ε-nondominated points of MOP. 123
Journal of Global Optimization (2021) 80:195–227 213 6.3 Overall lower bounding by nondominated ideal point estimates For efficient handling of the set LB T+Rm +=X∈LLB T+Rm +in the definition of the enclosure E(LB T,lub(F)) as well as in the resulting termination criterion and node selection rule, one should take into account that many boxes X∈Lmay be redundant in its description. In the single objective case this corresponds to the fact that most X∈Lsatisfy b>b=minX∈Lb, so that we are only interested in a box Xwith b=b. Usually the latter box is unique. In the multiobjective setting one cannot expect the existence of a single box Xwith LB T+Rm +=LB T+Rm +, but several boxes Xmay be nonredundant, namely the ones for which the sets LB Tare ‘nondominated’ in some sense. A situation for which nondominance among the sets LB T,X∈L, is easily defined is the case of singleton sets LB T. Hence, for each X∈Llet us again consider the lower estimate a Tfor the ideal point of f(M(X)) induced by LB T. Recall that LB T,S={a T}is a singleton partial lower bounding set for f(M(X)),sothatbyLemma6.1 the finite set LB T,S={a T|X∈L} is an overall lower bounding set, that is, YN⊆LB T,S+Rm +holds. Let us now consider only boxes X∈Lwhich correspond to the nondominated points of LB T,S, that is, to the (unique) stable subset LB T,S,Nof LB T,Sso that no element of LB T,S,N is dominated by some point in LB T,S. Lemma 6.4 With the nondominated set L BT,S,Nof L BT,Sthe inclusions LB T+Rm +⊆LB T,S+Rm +⊆LB T,S,N+Rm + hold. Proof The first inclusion is valid because of LB T+Rm += X∈L LB T+Rm += X∈L (LB T+Rm +)⊆ X∈L ({a T}+Rm +) = X∈L{a T}+Rm +=LB T,S+Rm +. Furthermore, for each y∈LB T,S+Rm +there is some X∈Lwith a T≤y.As|L|<∞, eithera T∈LB T,S,Nholds or there exists some a∈LB T,S,Nwith a≤a T≤y. This shows the second inclusion. The first inclusion in the assertion of Lemma 6.4 means that, as expected, LB T,Sis a coarser overall lower bound for YN∪Fthan LB T. The second inclusion implies that the ‘relevant’ boxes for the definition of LB T,S+Rm +are the ones from the sublist LN:= {X∈L|a T∈LB T,S,N}. The combination of Lemma 6.2 with Lemma 6.4 and (3) immediately yields the next result. Lemma 6.5 For any lower bounding technique T the inclusion YN∪F⊆E(LB T,S,N,lub(F)) = (a,p)∈LB T,S,N×lub(F) a≤p [a,p].(16) holds. 123
214 Journal of Global Optimization (2021) 80:195–227 7 Termination criterion, node selection rule, and conceptual algorithm In view of Lemma 6.5 and Theorem 3.4 we can now state the basis for the termination criterion of the multiobjective branch-and-bound method. Theorem 7.1 In some iteration of the branch-and-bound method let L BT,S,Nbe the nondominated set of the current set of induced ideal point estimates L BT,S={a T|X∈L}, let Fdenote the current provisional nondominated set, and for some ε>0let max s(a,p)|(a,p)∈LB T,S,N×lub(F), a≤p<ε (17) hold. Then all q ∈Fare ε-nondominated points of MOP. We point out that the maximum in condition (17) is taken over finitely many choices so that checking (17) is algorithmically tractable. Moreover, if for given ε>0 the condition (17) is violated, that is, w(LB T,S,N,lub(F)) =max s(a,p)|(a,p)∈LB T,S,N×lub(F), a≤p≥ε holds, then we expect to reduce the width w(LB T,S,N,lub(F)) of E(LB T,S,N,lub(F)) by branching a box X∈LNsuch that with the corresponding ideal point estimatea Tand some p∈lub(F)witha T≤pwe have s(a T,p)=max s(a,p)|(a,p)∈LB T,S,N×lub(F), a≤p. Observe that in single objective optimization the rule to select a box Xwith b=b= minX∈Lbdoes not need information about the upper bound ub =f(xub), since increasing breduces the length of the enclosing interval [b,ub]anyway. In the multiobjective setting decreasing w(LB T,S,N,lub(F)) reduces the worst case width of the enclosure, which is still a natural generalization of the single objective case since there no worst case over several instances has to be considered. Selection rules employed in the literature so far are to choose X∈Lwith minimal value (a LB)j,forsome j∈{1,...,m}[12,26] or with maximal width of F(X)[31]. Recall that, as opposed to our above suggestion, such node selection rules are unrelated to the basic branch-and-bound idea. In contrast to this, [37] proposes a node selection rule in the spirit of our approach where however, as mentioned above, it remains unclear how the overall lower bounding set is computed. The multiobjective branch-and-bound framework resulting from our considerations is stated in Algorithm 1. It does not need our previous assumption of a nonempty feasible set M. Subsequently we shall comment on the implementation of some of its lines. In line 1 of Algorithm 1one may choose, for example, Z:= F(X)with the interval enclosure F(X)of f(X). In the node selection rule from line 9 the function sdenotes the length of a shortest box edge, as defined in (4). Possibilities for the computation of partial lowerboundingsetsinline14andoftheirinducedidealpointestimatesinline15arediscussed in Sects. 5.3,5.4 and 5.5. Line 16 and line 21 base on the modified general discarding test from Corollary 5.11. We point out that, if in line 14 the infeasibility of M(Xk,)is detected by the computation of an empty partial lower bounding set LBk, T, then line 15 results in ak, T=+∞e, so that in line 16 there does not exist any p∈lub(Fk)with p≥ak, T,andXk, isdiscarded. Inline 18onemaycheck, forexample,if thechoice xk, =mid(Xk,)isfeasible. We will discuss more general constructions for xk, in Sect. 8. The update in line 20 can be implemented with the algorithms from [8,22]. Line 21 can become numerically expensive for long lists Lk, so that one may decide not to use it in each iteration, but only occasionally. 123
Journal of Global Optimization (2021) 80:195–227 215 Algorithm 1 Conceptual Multiobjective Branch-and-Bound Method Input: Problem MOP with f:Rn→Rm,g:Rn→Rk,X=[x,x],x,x∈Rn,x<x, termination tolerance ε>0, partial lower bounding technique T. 1: Compute a box Z=[z,z]with f(M(X)) ⊆int(Z). 2: Initialize list L0←(X,{z},z}. 3: Initialize set of nondominated ideal point estimates LB0 T,S,N←{z}. 4: Initialize provisional nondominated set F0←∅. 5: Initialize set of local upper bounds lub(F0)={z}. 6: Initialize iteration counter k←0. 7: repeat 8: k←k+1. 9: Choose some (Xk,LBk T,ak T)from Lk−1with (ak T,pk)∈LBk−1 T,S,N×lub(Fk−1), ak T≤pk,and s(ak T,pk)=max{s(a T,p)|(a T,p)∈LBk−1 T,S,N×lub(Fk−1), a T≤p}. 10: Lk←Lk−1\{(Xk,LBk T,ak T)}. 11: Divide Xkalong the midpoint of a longest edge into Xk,1and Xk,2. 12: Fk←Fk−1,lub(Fk)←lub(Fk−1). 13: for =1,2do 14: Determine a partial lower bounding set LBk, Tfor f(M(Xk,)). 15: Determine the ideal point estimateak, Tinduced by LBk, T. 16: if there is some p∈lub(Fk), p≥ak, Twith ϕLBk, T (p)≤0then 17: Lk←Lk∪{(Xk,,LBk, T,ak, T)}. 18: if some xk, ∈M(Xk,)is available then 19: Fk←update of Fkwith respect to f(xk,). 20: lub(Fk)←update of lub(Fk). 21: Remove all (X,LB T,a T)from Lkfor which ϕLB T(p)>0 holds for all p∈lub(Fk)with p≥a T. 22: if Lk=∅then 23: Determine the nondominated set LBk T,S,Nof {a T|(X,LB T,a T)∈Lk}. 24: until Lk=∅or max{s(a T,p)|(a T,p)∈LBk T,S,N×lub(Fk), a T≤p}<ε. Output: 25: if Lk=∅then Fkis a set of ε-nondominated points of MOP, and E(LBk T,S,N,lub(Fk)) is an enclosure of YNwith w(LBk T,S,N,lub(Fk)) < ε. 26: else MOP is inconsistent. In line 23 one can either do a pairwise comparison for determining the nondominated set, or, in case of a long list Lk, one can use for instance the Jahn-Graef-Younes method, see [17,19]. 8Convergence In this section we show that for any ε>0 Algorithm 1terminates after a finite number of iterations. To this end, we extend results from the single objective case to our multiobjective branch-and-boundapproach. Themainobservation forthefollowing isthatfor agivensubbox X⊆Xthe entries (a T)jof the induced ideal point estimate for f(M(X)) can be interpreted as the results of a lower bounding procedure for fjon M(X). 123
216 Journal of Global Optimization (2021) 80:195–227 In preparation of the convergence proof we briefly review the definition and some important properties of such lower bounding procedures in the single objective branch-and-bound framework. As common in global optimization, a sequence of boxes (Xk)is called exhaustive if we have Xk+1⊆Xkfor all k∈N, and limkdiag(Xk)=0 where diag(X)denotes the diagonal length of a box X⊆X. The following definitions are taken from [20]. Definition 8.1 Let f:Rn→R,g:Rm→Rkand M(X)={x∈X|g(x)≤0}. (a) A function from the set of all subboxes Xof Xto R∪{+∞}is called M-dependent lower bounding procedure if (X)≤infx∈M(X)f(x)holds for all subboxes X⊆X and any choice of the functions fand g. (b) An M-dependent lower bounding procedure is called convergent if every exhaustive sequence of boxes (Xk)and all choices of fand gsatisfy lim k(Xk)=lim kinf x∈M(Xk) f(x). We remark that for any exhaustive sequence of boxes (Xk)the set k∈NXkis a singleton, say {x}. In the case x/∈M(X)we have M(Xk)=∅for all sufficiently large k, so that with the usual convention infx∈∅ f(x)=+∞the convergence of a lower bounding procedure then requires limk(Xk)=+∞. Moreover, if in the case x∈M(X)we have xk∈Xk for all k, then in view of limkdiag(Xk)=0 the sequence (xk)also converges to x,andthe convergence of and continuity yield lim k(Xk)=lim kinf x∈M(Xk) f(x)=f(x)=lim kf(xk). (18) Basically all lower bounding procedures that are commonly used in global optimization are convergent in the sense of Definition 8.1, in particular the ones considered throughout this article, that is, interval arithmetic [18,27], convex relaxations via the αBB method [1,3]as well as lower bounds based on linearization techniques as described in [4,33–35]. Note that in the above casex/∈M(X)these lower bounding procedures even satisfy (Xk)=+∞for almost all k, thus implying the convergence property limk(Xk)=+∞. While this stronger property is employed for discarding inconsistent subproblems in line 16 of Algorithm 1,we will not use it in our convergence analysis. As mentioned above, in Algorithm 1the entries (a T)jof the induced ideal point estimate for f(M(X)) are the results T,j(X)of a lower bounding procedure T,jfor fjon M(X). For the following let T(X)denote the vector with entries T,j(X), so that we may write a T=T(X). We start by showing that problems with empty feasible sets are handled by our branchand-bound method as expected. Lemma 8.2 Let the feasible set of problem MOP be empty and assume that in Algorithm 1the entries of the induced ideal point estimates are computed by some convergent M-dependent lower bounding procedure. Then for any ε>0Algorithm 1terminates after a finite number of iterations. Proof We assume the contrary and derive a contradiction. First of all, note that due to the absenceoffeasiblepointsthelocalupperboundsareneverupdated,sothatwehavelub(Fk)= {z}in each iteration k. Under our assumption that the algorithm does not terminate it is well-known from the theory of spatial branch-and-bound methods that an exhaustive sequence of boxes (Xkν)is generated. Since none of these boxes contains a point from M(X), the convergence of the 123
Journal of Global Optimization (2021) 80:195–227 217 lower bounding procedure yields T(Xk¯ν)=ak¯ν T>zfor some sufficiently large ¯ν. Thus in line 16 of Algorithm 1the box Xk¯νis discarded. For that reason, the sequence of boxes (Xkν) actually terminates after finitely many iterates and cannot be exhaustive. Analogously to the single objective case, we must assume that in line 18 of Algorithm 1 feasible points are eventually available to improve the local upper bounds. This is formally stated in the following assumption, which we shall discuss in some detail after the proof of convergence. Assumption 8.3 There exist some δ>0 and some procedure so that for all boxes X⊆X created by Algorithm 1with diag(X)<δand M(X)=∅a feasible point x∈M(X)can be computed. Lemma 8.4 Let the feasible set of problem MOP be nonempty, assume that in Algorithm 1the entries of the induced ideal point estimates are computed by some convergent M-dependent lower bounding procedure, and let Assumption 8.3 hold. Then for any ε>0Algorithm 1 terminates after a finite number of iterations. Proof Assumethatthealgorithmdoesnotterminate.Thenitgeneratesanexhaustivesequence of boxes (Xkν)all of which contain a feasible point. Note that otherwise the sequence of boxes would terminate after finitely many iterations, for a similar reason as in the proof of Lemma 8.2 (see, e.g., [20] for a more detailed explanation). As the sequence (Xkν)is exhaustive and due to Assumption 8.3, for all sufficiently large νa point xkν∈M(Xkν) is available in line 18 of Algorithm 1. Since the image point f(xkν)is used to update the provisional nondominated set in line 19, it either becomes an element of Fkνor it is ignored since it is dominated by some point from Fkν. In any case, there is some qkν∈Fkνwith qkν≤f(xkν). (19) Due to (18), for some sufficiently large ν∈Nwe additionally have f(xkν)−T(Xkν)≤ε 2e,(20) where eagain stands for the all ones vector. Finally, as the termination criterion was violated in iteration k¯ν−1, the ideal point estimate ak¯ν T∈LBk¯ν−1 T,S,Nand the local upper bound pk¯ν∈lub(Fk¯ν−1)with ak¯ν T≤pk¯ν, in which the maximum is attained, satisfy pk¯ν−T(Xk¯ν)=pk¯ν−ak¯ν T≥εe, and thus T(Xk¯ν)+ε 2e≤pk¯ν−ε 2e.(21) The combination of (19), (20)and(21) yields the chain of inequalities qkν≤f(xkν)≤T(Xkν)+ε 2e≤pkν−ε 2e<pkν and, thus, qkν<pkν. This contradicts property (ii) of Definition 4.1 and, hence, the assertion is shown. From Lemma 8.2 and Lemma 8.4 we immediately obtain the main convergence theorem of the present article. 123
218 Journal of Global Optimization (2021) 80:195–227 Theorem 8.5 Assume that in Algorithm 1the entries of the induced ideal point estimates are computed by some convergent M-dependent lower bounding procedure, and let Assumption 8.3 hold. Then for any ε>0Algorithm 1terminates after a finite number of iterations. Since, as discussed above, in global optimization usually convergent lower bounding procedures are used, the seemingly restrictive assumption of Theorem 8.5 is Assumption 8.3. In the remainder of this section we shall briefly comment on this. First note that the difficulty of finding feasible points also arises in single objective branch-and-bound methods: In case that no sufficiently good feasible point is found, the algorithms do not terminate since the gap between upper and lower bound does not drop below the termination tolerance ε. Usually the objective function is evaluated at feasible points in order to obtain upper bounds at the globally minimal value. These feasible points can be obtained by means of different approaches. In a very simple case one may check if the midpoint of a box that is currently examined is feasible and use this for an update of the current upper bound, if the objective value is sufficiently good. In practice, commonly a local procedure is used to solve the original problem locally where, for instance, the midpoint of the current box is used to initialize the starting point. Under Assumption 8.3 one may eventually expect the box midpoint to lie sufficiently close to the feasible set to make this local concept work. Although this approach in fact works well on many instances of practical interest, in general there is no guarantee that always sufficiently good upper bounds are computed in this way. One possibility to transfer this approach from the single objective case to multiobjective branch-and-bound problems might be to consider a scalarization approach and solve the resulting single objective problem locally. However, although this attempt might work in practice, we prefer to not follow this line of research here since the drawback of this approach from the single objective case still remains and, in general, there is no proof of convergence. Instead,insingleobjectiveoptimizationitisoftenproposedtoacceptso-calledεM-feasible points, meaning that a point x∈Xis accepted if gi(x)≤εM,i∈{1,...,k}, holds for some predefined value εM>0. Unfortunately, a reasonable value for εMis hard to determine in advance, since even for εMclose to zero usually one cannot be sure that an εM-feasible point is actually close to the feasible set. For that reason, so-called upper bounding procedures have been developed that ensure Assumption 8.3 and, thus, termination of a branch-and-bound method by computing a convergent sequence of upper bounds, as for instance proposed in [20] for the purely inequality constrained case. For problems that also involve equality constraints we refer to [14]. These techniques can be adapted to multiobjective problems which is, however, beyond the scope of the present paper. 9 Numerical illustrations The present section provides a brief proof of concept for Algorithm 1.Notethatweneither aim at studying its numerical behavior for increasing dimensions mand n, nor do we intend to compare the performance of the lower bounding procedures from Sects. 5.3,5.4 and 5.5 among each other or in comparison to other lower bounding procedures like, for example, Lipschitz based underestimators. In fact, a thorough numerical study is beyond the scope of the present paper and postponed to future research. In contrast, the aim of the article at hand is the introduction of a general framework which allows to consider such comparisons in the first place. 123
Journal of Global Optimization (2021) 80:195–227 225 (a) (b) (c) (e) (d) Fig. 6 Test problem TP5 set X∈LXform coverings of the set of efficient points XEof MOP. Consequently the set X∈Lf(M(X)), its superset X∈Lf(X), and any further supersets like X∈LF(X) for an interval extension Fof f, form coverings of the set of nondominated points YN. In the framework of our approach it is clearly also important to study approximation properties of the enclosing sets E(LB T,S,N,lub(F)) for w(LB T,S,N,lub(F)) →0. Observe that YNis known to be a subset of the boundary of the image set f(M)[10] so that, if f(M) is a topological manifold with boundary, the dimension of YNcan be at most m−1. At the same time, for w(LB T,S,N,lub(F)) →0 all boxes [a,p]in (16) ‘become flat at least in one 123
226 Journal of Global Optimization (2021) 80:195–227 direction’ and thus at most (m−1)-dimensional. This fits well to the expected dimension of YN. However, in general one may not expect that the enclosures E(LB T,S,N,lub(F)) uniformly approximate the nondominated set YNfor w(LB T,S,N,lub(F)) →0. This is due their different connectedness structure. In fact, examples like Test Problem 9.2 and Test Problem 9.3 show that, as opposed to the convex case [10], in the nonconvex case the set YNmay be disconnected while E(LB T,S,N,lub(F)) is connected. One way to construct a subset of E(LB T,S,N,lub(F)) with the same connectedness structure as YNmay be to intersect it with the above union of interval enclosures X∈L F(X)⊇YN for sufficiently small boxes F(X),X∈L. However, in our framework this is not desirable as we wish to avoid the effort of constructing such small boxes in the first place. We would also like to mention that our branch-and-bound framework can be generalized to the presence of equality constraints in the description of the feasible set of MOP. The crucial modifications for this are appropriate generalizations of the lower bounding procedures as well as meeting Assumption 8.3 for the convergence proof. As the details of this are mainly technical, we did not include them in the present paper for the clarity of presentation. Acknowledgements Open Access funding enabled and organized by Projekt DEAL. The authors wish to thank the two anonymous referees and Anne-Sophie Reichhardt for their valuable comments and remarks on an earlier version of this manuscript. Data Availability Statement Data sharing not applicable to this article as no datasets were generated or analysed during the current study. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, aBB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998) 2. Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983) 3. Androulakis, I.P., Maranas, C.D., Floudas, C.A.: αBB: a global optimization method for general constrainted nonconvex problems. J. Glob. Optim. 7, 337–363 (1995) 4. Belotti, P.: Disjunctive cuts for nonconvex MINLP. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, pp. 117–144. Springer, Berlin (2012) 5. Binh, T.: A multiobjective evolutionary algorithm: the study cases. In: Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp 127–128 (1999) 6. Branke, J., Deb, K., Dierolf, H., Osswald, M.: Finding knees in multi-objective optimization. In: Parallel Problem Solving from Nature: PPSN VIII, Springer, pp 722–731 (2004) 7. Chen, G., Huang, X., Yang, X.: Vector Optimization. Springer, Berlin (2005) 123
Journal of Global Optimization (2021) 80:195–227 227 8. Dächert, K., Klamroth, K., Lacour, R., Vanderpooten, D.: Efficient computation of the search region in multi-objective optimization. Eur. J. Oper. Res. 260, 841–855 (2017) 9. Deb, K.: Multi-objective optimization using evolutionary algorithms. Wiley, New York (2001) 10. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005) 11. Evtushenko, YuG, Posypkin, M.A.: Method of non-uniform coverages to solve the multicriteria optimization problems with guaranteed accuracy. Autom. Remote Control 75, 1025–1040 (2014) 12. Fernández, J., Tóth, B.: Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Comput. Optim. Appl. 42, 393–419 (2009) 13. Fonseca, C.A., Fleming, P.J.: Multiobjective genetic algorithms made easy: selection sharing and mating restriction. In: Proceedings of the 1st International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, pp 45–52. IEEE Press, Piscataway, NJ (1995) 14. Füllner, C., Kirst, P., Stein, O.: Convergent upper bounds in global minimization with nonlinear equality constraints. Math. Program. (2020). https://doi.org/10.1007/s10107-020-01493-2 15. Gerth (Tammer), C., Weidner, P.: Nonconvex separation theorems and some applications in vector optimization. J. Optim. Theory Appl. 67, 97–320 (1990) 16. Göpfert, A., Riahi, H., Tammer, C., Zalinescu, C.: Variational Methods in Partially Ordered Spaces. CMS Books. Springer, New York (2003) 17. Günther, C., Popovici, N.: New algorithms for discrete vector optimization based on the Graef–Younes method and cone-monotone sorting functions. Optimization 67, 975–1003 (2018) 18. Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis. Marcel Dekker Inc., New York (2004) 19. Jahn, J., Rathje, U.: Graef–Younes method with backward iteration. In: Küfer, K.-H., et al. (eds.) Multicriteria Decision Making and Fuzzy Systems-Theory. Methods and Applications, pp. 75–81. Shaker, Aachen (2006) 20. Kirst, P., Stein, O., Steuermann, P.: Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints. TOP 23, 591–616 (2015) 21. Klamroth, K.: Personal communication (2017) 22. Klamroth, K., Lacour, R., Vanderpooten, D.: On the representation of the search region in multi-objective optimization. Eur. J. Oper. Res. 245, 767–778 (2015) 23. Loridan, P.: ε-solutions in vector minimization problems. J. Optim. Theory Appl. 43, 265–276 (1984) 24. McCormick, G.P.: Computability of gobal solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10, 147–175 (1976) 25. Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, Berlin (1998) 26. Niebling, J., Eichfelder, G.: A branch-and-bound based algorithm for nonconvex optimization problems. SIAM J. Optim. 29, 794–821 (2019) 27. Neumaier,A.:IntervalMethodsforSystems ofEquations.Cambridge University Press,Cambridge(1990) 28. Pardalos, P., Žilinskas, A., Žilinskas, J.: Non-convex Multi-Objective Optimization. Springer, Berlin (2017) 29. Rump, S.M.: INTLAB-interval laboratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp 77–104. Springer, Dordrecht (1999) 30. Ruzika, S., Wiecek, M.M.: Approximation methods in multiobjective programming. J. Optim. Theory Appl. 126, 473–501 (2005) 31. Scholz, D.: The multicriteria big cube small cube method. TOP 18, 286–302 (2010) 32. Sawaragi, Y., Nakayama, H., Tanino, T.: Theory of Multiobjective Optimization. Elsevier, Amsterdam (1985) 33. Smith, E., Pantelides, C.: Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21, 791–796 (1997) 34. Smith, E., Pantelides, C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23, 457–478 (1999) 35. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous Mixed-Integer Nonlinear Programming. Springer, Dordrecht (2002) 36. Žilinskas, A.: On the worst-case optimal multi-objective global optimization. Optim. Lett. 7, 1921–1928 (2013) 37. Žilinskas, A., Žilinskas, J.: Adaptation of a one-step worst-case optimal univariate algorithm of biobjective Lipschitz optimization to multidimensional problems. Commun. Nonlinear Sci. Numer. Simul. 21, 89–98 (2015) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123