The objective that freed me: a multi-objective local search approach for continuous single-objective optimization

We earlier described the general scheme of converting a single-objective optimization problem into a multi-objective one by adding an additional objective. Here, we formally introduce some of the necessary terminology summarized and extended by Grimme et al. (2021):

As we focus on continuous multi-objective optimization, the MOP’s search space \({\mathcal {X}}\) is real-valued, i.e., \({\mathcal {X}} \subseteq {\mathbb {R}}^n\). It is clear that the domination of a solution over another solution is not as simple as in SO optimization. In contrast to a totally ordered set \(({\mathbb {R}}, \le )\) in SO optimization, with its natural total order \(\le \) on \({\mathbb {R}}\), the set of solution candidates of an MOP follows the weak Pareto order \(\preceq \) on \({\mathbb {R}}^m\), which is defined as follows:

Thus, the solution set of an MOP, the Pareto set, consists of optimal trade-off solutions, i.e., nondominated solutions in decision space. The image of the Pareto set is called Pareto front:

Traditional multi-objective solvers specifically aim for approximating (or even exactly determining) the Pareto sets and Pareto fronts. However, as shown in Grimme et al. (2021), local structures in decision space and objective space thereby not necessarily hinder algorithm success but can rather be efficiently exploited by sophisticated approaches. Thus, with the methodological concept of multiobjectivization in mind, we need to define locality and locally efficient sets following the aforementioned work in terminology and notation (see Fig. 1 for a schematic visualization).

Yet, as the consideration of locally efficient sets goes beyond the definition of locally efficient points, this additionally requires a notion of connectedness.

Now it is possible to define the locally efficient set as a structure in search space and with its corresponding image in objective space.

Clearly, solutions in locally efficient sets, which are not dominated by any other solution, are contained in the Pareto set. This implies \({\mathcal {X}}_E \subseteq {\mathcal {X}}_{LE}\). Following the defined distinction of globally and locally efficient points, we can also speak of a globally efficient set of solutions and a globally efficient front of solutions instead of a Pareto set or a Pareto front, respectively. Examples for both globally and locally efficient sets are shown in Fig. 1.

To even further sharpen the notion of localness, we adopt the definition of the \(\varepsilon \)-neighborhood of a set in analogy to the \(\varepsilon \)-ball, which surrounds a single solution (refer to Definition 4).

Then, a strict locally efficient set is completely surrounded by an \(\varepsilon \)-neighborhood for some \(\varepsilon \) (see also Fig. 1, set \({\mathcal {X}}_{L,2}\)).

For a schematic example on how a locally efficient set fails being a strict locally efficient set see Fig. 1, again. Therein, the set \({\mathcal {X}}_{L,1}\) is a half-open segment of a straight line, whose leftmost end point is excluded (indicated by an open circle). Moreover, it is an accumulation point of \({\mathcal {X}}_E^{(\varepsilon _0)}\), i.e., for a fixed \(\varepsilon _0 >0\) there exists \(\varepsilon _1 > 0\) such that none of the points of \({\mathcal {X}}_E^{(\varepsilon _0)} \cap {\mathcal {X}}_{L,1}^{(\varepsilon _1)}\) (the blue intersecting area) is dominated by \({\mathcal {X}}_{L,1}\).

The non-strict locally efficient sets are of special interest here. Their \(\varepsilon \)-neighborhood is—as demonstrated visually—obviously superposed by the \(\varepsilon \)-neighborhood of a dominating efficient set. We now consider the \(\varepsilon \)-neighborhood of a locally efficient set as subset of the basin of attraction of a local set. Therefore, we define a basin of attraction as the set of points for which a multi-objective gradient-based descent (w.l.o.g. for minimization problems) strategy leads to the same locally efficient set. This multi-objective gradient descent can be considered as movement from one point in decision space to a (neighboring) dominating point in decision space following the common direction of the normalized gradients of all objectives.

The superposition which makes a locally efficient set non-strict thus opens up the way along the effcient set into the superposing (i.e., dominating) basin of attraction. This can be algorithmically exploited and is the motivation for the method presented and investigated in this paper.

For this work, we consider the optimization of box-constrained single-objective continuous optimization problems as our main goal. These problems are formally given by \(\min _{x \in [l, u]} f(x)\) with \(f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}\), and \(l,u \in {\mathbb {R}}^n\) being the problem’s (lower and upper) box constraints.

However, instead of optimizing the single-objective problem directly – w.l.o.g. we denote this objective \(f_1\)—we transform the single-objective problem into a bi-objective problem \(F = (f_1, f_2)\) by introducing a second objective \(f_2\), which w.l.o.g. shall be minimized as well. This simple concept is known as multiobjectivization (Knowles et al. 2001; Jensen 2004; Neumann and Wegener 2008; Steinhoff et al. 2020) and its motivation is that the resulting bi-objective problem landscape possesses structural properties which could potentially be exploited by a sophisticated multi-objective optimizer.

Among these characteristics are the previously defined locally efficient sets (see Def. 6, i.e., the multi-objective pendants of local optima). Per definition, each of these sets is a connected set of locally efficient points.

Interestingly, in multi-objective optimization, the existence of locally efficient sets can be very beneficial for local solvers. In contrast to their SO counterparts, these optima oftentimes are no traps for local solvers, but instead guide the way to more promising regions of the search space (Grimme et al. 2019b; Kerschke and Grimme 2021; Schäpermeier et al. 2022), sometimes even towards the globally efficient set.

This is rooted in superpositions of basins of attraction as described in Sect. 2.1 and exemplarily visualized in Fig. 2. This figure presents the sequential construction of a multi-objective problem from two single-objective functions. The left-hand image shows a heatmap-based landscape plot of the highly multimodal Rastrigin problem (Hoffmeister and Bäck 1991), which we consider as \(f_1\). The middle plot shows a respective plot of the sphere function, which we consider as \(f_2\). The right-hand plot shows a heatmap-based gradient field plot (Kerschke and Grimme 2017) of the multi-objective problem \(F=(f_1,f_2)^T\), where the color denotes proximity to the next locally efficient set from red (far) to blue (close). In a nutshell, the gradient heatmap-based plot of a multi-objective problem depicts by color for each point in a discretized decision space the distance (number of necessary steps via neighboring points) towards a local efficient point, if we follow the normalized multi-objective gradient direction. More detailed information on this visualization technique, related approaches, and visualization tools can be found in Schäpermeier et al. (2020, 2021). Obviously, the multi-objective landscape of the combined problems exposes many locally efficient sets (visible as green-yellow lines) surrounded by red colored basins of attraction. However, in contrast to the classical view on the Rastrigin problem with its many local traps (and local basins of attraction) the multi-objective basins superpose each other: basins of one set directly cut locally efficient sets of superposed basins. This innovative structural view allows for new ideas how to roam the search space in a directed way.

What we have observed formally means: if we are not trapped in a strict locally efficient set (see Def. 8), then dominating basins of attraction overlap dominated basins. As shown schematically in Fig. 1 and exemplarily in Fig. 2, it is then possible to move from the dominated basin towards the dominating one along the efficient set. Thereby, we definitely reach a “better” multi-objective locally efficient set—and possibly also a better area of the single-objective search space.

By making use of the Fritz John necessary condition (John 1948), potentially local efficient points can be identified easily during multi-objective downhill movement in the search space: let \(x \in {\mathbb {R}}^n\) be a locally efficient point and all objective functions of F, i.e., \(f_1\) and \(f_2\), continuously differentiable in \({\mathbb {R}}^n\). Then, there is a weight vector \(v \in [0,1]^m\) with \(\sum _{i=1}^m v_i=1\), such thatIn the bi-objective case, when we are looking at a locally efficient point, the (single-objective) gradients of \(f_1\) and \(f_2\) cancel each other out given a suitable weight vector \(v\in {\mathbb {R}}^2\). This property provides useful fundamentals for understanding and optimizing multi-objective optimization problems and (as will be shown within this work) for single-objective problems as well. For instance, it can be used for visualizing MO landscapes (Kerschke and Grimme 2017; Schäpermeier et al. 2020), and is essential for the lately proposed multi-objective gradient sliding algorithm (MOGSA) (Grimme et al. 2019a, b). As recently shown by Steinhoff et al. (2020), multiobjectivization enables the aforementioned multi-objective algorithm to even optimize single-objective problems. In the following subsection, we will describe this single-objective variant of MOGSA—dubbed SOMOGSA—in more detail.

Contrary to previous research in which global methods were applied to multiobjectivized problems—for an extensive review, we refer to Segura et al. (2013, 2016)—we will use a deterministic MO local search algorithm. It efficiently exploits properties of MO landscapes, which we previously identified using a recently developed visualization method based on gradient field heatmaps (Grimme et al. (2019b), see Fig. 2 for an example). In our setting the multi-objective problem (MOP) degenerates to a bi-objective problem \(F(x)=(f_1(x), f_2(x))^T\in {\mathbb {R}}^2\). To ensure simplicity of our approach and maximal comprehensibility, we used a simple sphere function \(f_2(x) = \sum _{i = 1}^n (x_i-y^{*}_i)^2\) as second objective with \(x,y^{*}\in {\mathbb {R}}^n\). It comes with two benefits: (1) the resulting bi-objective problem is simple enough to avoid unwanted distractions, but still capable of guiding an MO algorithm, and (2) it allows for direct, analytical determination of the corresponding gradient (which is utilized by SOMOGSA). As such, this choice seems to be cost-effective and logical for this study. Note that in principle a different and more complex choice of \(f_2\) is possible. A clever choice of \(f_2\) could help in creating specific MO descent structures to guide SOMOGSA directly towards a desired path. It is still unclear, however, what effort has to be put into finding such a structure of \(f_2\) and how the interaction of \(f_1\) and \(f_2\) can be predicted for generating a beneficial MO structure, specifically if \(f_1\) is a gray or even a black box problem. In this study we rely on Occam’s principle of choosing the simplest model for evaluation.

The general idea of our proposed hybrid and modularized search heuristic SOMOGSA is given schematically in Fig. 3. While SOMOGSA enables the exploitation of the multi-objective landscape structures, it can encapsulate an arbitrary local search for refinement of \(f_1\) results. In Sect. 3, we will exemplarily show this for the Nelder–Mead local search algorithm. The SOMOGSA framework is described in more detail in Algorithm 1. Apart from adding a sphere as second objective (line 1), SOMOGSA essentially (repeatedly) performs the following steps: Note that the criterion for stopping multi-objective downhill movement is based on the Fritz-John condition, which is only a necessary criterion and may lead to premature termination of step 1. This case is not explicitly handled by our approach. Instead, we heuristically assume that the following single-objective local search w.r.t. \(f_1\) will lead the search near a locally efficient solution again, where step 3 will continue as planned.

The above mentioned steps are repeated until either (a) SOMOGSA has reached the sphere’s optimum (line 3), or (b) the objective value of \(f_1\) got worse between two subsequently found local optima of \(f_1\) (line 8). In the latter case, we interrupt the optimization, as SOMOGSA wouldn’t improve any longer w.r.t. \(f_1\) but instead waste the remaining budget to eventually reach the optimum of \(f_2\). Note that the gradient of the original objective function \(f_1\) usually needs to be computed numerically, e.g., by two-sided finite differences, while the gradient of the helper objective \(f_2\) may be known analytically.

As described above, SOMOGSA basically provides a modularized framework, which allows to make use of the strengths of MOGSA. However, the performance of SOMOGSA obviously depends on its configuration (e.g., which problem is used as objective \(f_2\), where is the optimum of \(f_2\) located, which local search strategy is used, which starting point is chosen etc.). Therefore, in the following, we will investigate the sensitivity of our method w.r.t. different parameters and module choices. In addition, we experimentally demonstrate that SOMOGSA can significantly boost the potential of simple single-objective local search algorithms.

In this work, we expand our test environment used in Aspar et al. (2021) and consider the 24 noiseless single-objective BBOB problems from the COCO platform (Hansen et al. 2009) in the two-dimensional decision space. For SOMOGSA, these functions are referred to as objective \(f_1\) in the multiobjectivized problem. As second objective, we consider \(f_2(x) = \sum _{i = 1}^2 (x_i-y^{*}_i)^2\) with \(x,y^{*}\in {\mathbb {R}}^2\), as explained above. Besides investigating the principal benefits of applying SOMOGSA together with a classical SO local search, we specifically focus on the sensitivity of the approach w.r.t the starting position of the search, as well as the location of the optimum of \(f_2\). We thus discretize the decision space using a regular grid X for generating \(N = d \times d\) starting points. We choose \(d = 50\), as (empirically) larger values of d do not provide additional insights and lower values do not reveal all desired structures. The methods to be assessed are executed for all points in the grid centers of X. Ten positions \(y^{*}\) of the \(f_2\) optimum were generated¹ by using Latin Hypercube Sampling (McKay et al. 1979) and subsequently mapping those points to their nearest neighbors in X². The (default) parameters mentioned in Algorithm 1 were set to \(t_\angle = 170\) as angle for denoting sufficient proximity to a potentially local efficient set, \(\sigma _{MO} = 0.05\) as step size for multi-objective descent, and \(\sigma _{SO} = 0.1\) as step size for fast traversal by following the approximated gradient of \(f_2\) for reaching the next basin of attraction. In Aspar et al. (2021) Gradient Search (GS) and Nelder–Mead (NM) (Nelder and Mead 1965) were used as local search mechanisms inside the SOMOGSA framework, resulting in two variants of SOMOGSA: SOMOGSA+GS and SOMOGSA+NM. As a baseline, we also evaluated GS and NM as stand-alone methods on each considered SO problem. In order to prevent possible infinite cycling of local search (specifically NM can run into cyclic behavior), the number of local search steps was restricted to a maximum of 400. Since the method SOMOGSA+NM consistently outperformed SOMOGSA+GS, in this work, we solely focus on SOMOGSA+NM and Nelder–Mead as the corresponding stand-alone method. Furthermore, our previous research revealed that both algorithms barely require more than 2000 function evaluations for \(n=2\) until one of the internal termination criteria has been reached. Therefore, we set the optimizer budget to \(n \times 1000 = 2000\) function evaluations. Thereby, an optimizer run is considered successful, if it comes sufficiently close to the optimum, i.e., if it stagnates in an \(\varepsilon \)-neighborhood of the optimum of \(f_1\) (using a precision of \(p = \varepsilon = 0.01\)). This is a common experimental approach within the BBOB benchmark setting (Hansen et al. 2009). Moreover, we report the amount of function evaluations the optimizers actually need. For Nelder–Mead, we assume an average number of 1.5 function evaluations per iteration due to varying simplex generation procedures depending on the local landscape structure³.

In order to ensure to stay within the boundaries of our box-constrained problems, we integrate the following approach: As soon as Nelder–Mead spans the next simplex beyond any boundary, this simplex is clipped at the crossed boundary, respectively, and the best reached solution by the time is selected. This kind of constraint handling is advantageous, but may lead to early stoppings in some cases, especially for the stand-alone method of Nelder–Mead. For starting points near a boundary, the algorithm often passes the closest boundary rapidly and thus stops.

As a proof-of-concept study, we investigate how our findings generalize to higher decision space dimensions and expand our experiments to the two highly multimodal BBOB functions 21 and 22 (called Gallagher’s 101 and 21 Peak functions) in the 5-dimensional decision space. Likewise, these problems are evaluated for ten different sphere positions and 2500 starting points. Both the center of the sphere function and the starting points are generated via the Latin Hypercube Sampling method (McKay et al. 1979). The precision value remains at \(p = 0.01\). We have assigned the optimizers a fixed budget of \(n \times 1000\) function evaluations as well (with \(n = 5\)).

We investigate the sensitivity of SOMOGSA regarding (a) the parametrization of the second objective, (b) the position of the starting point, and (c) the local search strategy. We define specific metrics for capturing the performances of each variant in all considered settings (see Fig. 4).

As first metric, we define the gain (a value we want to maximize) aswhere \(x_s\) is a starting point, \(x_b\) the best local search result and \(x^{*}\) the known global optimum w.r.t. \(f_1\). This measure quantifies the achieved performance gain by the applied local search. Therefore, we compute the ratio of the gap between \(f(x_s)\) and \(f(x^{*})\), which is closed by applying the considered search heuristic. As a (global) performance measure, we also compare the gap (a value we want to minimize) that cannot be closed by the local search, relating to all starting points. This is quantified byThis measure expresses the gap between \(f(x_b)\) and \(f(x^{*})\) w.r.t the global maximum gap of all starting points function values from X to the optimum value. For a schematic representation of both measures refer to Fig. 4.

Both measures are evaluated for all combinations of N starting points and considered benchmark problem. The overall aggregated performance of each method can be statistically analyzed and visualized in the decision space, see, e.g., Fig. 5.

Furthermore, we assess the algorithm’s capability to reach the optimal solution (of \(f_1\)) from any of the starting points of the (discretized) search space X by determining the relative frequency of success (to be maximized by the algorithm), denoted as (success) ratiowhere \(H_N(LS)\) is the absolute frequency of the N algorithm runs that successfully converged to the optimum of \(f_1\) w.r.t. the precision \(p=0.01\).