Penalty functions and two-step selection procedure based DIRECT-type algorithm for constrained global optimization

Abstract

Applied optimization problems often include constraints. Although the well-known derivative-free global-search DIRECT algorithm performs well solving box-constrained global optimization problems, it does not naturally address constraints. In this article, we develop a new algorithm DIRECT-GLce for general constrained global optimization problems incorporating two-step selection procedure and penalty function approach in our recent DIRECT-GL algorithm. The proposed algorithm effectively explores hyper-rectangles with infeasible centers which are close to boundaries of feasibility and may cover feasible regions. An extensive experimental investigation revealed the potential of the proposed approach compared with other existing DIRECT-type algorithms for constrained global optimization problems, including important engineering problems.

1 Introduction

Many real-world problems in engineering and applied sciences can be formulated as nonlinear programming global optimization problems (Biegler and Grossmann 2004; Floudas 1999; Pintér 1996; Shan and Wang 2010b).

In this paper, we are seeking the global solution of the general nonlinear programming problem:

$$ \begin{array}{ll} \min\limits_{\mathbf{x} \in D} & f(\mathbf{x})\\ \mathrm{ s.t.} & \mathbf{g} (\mathbf{x}) \leq \mathbf{0},\\ & \mathbf{h} (\mathbf{x}) = \mathbf{0}, \end{array} $$

(1)

where $f: \mathbb {R}^{n} \rightarrow \mathbb {R}, \mathbf {g}: \mathbb {R}^{n} \rightarrow \mathbb {R}^{m}, \mathbf {h}: \mathbb {R}^{n} \rightarrow \mathbb {R}^{r}$ are (possibly nonlinear) continuous functions and $D = [ \mathbf {a}, \mathbf {b}] = \{ \mathbf {x} \in \mathbb {R}^{n}: a_{j} \leq x_{j} \leq b_{j}, j = 1, \dots , n\}$. The feasible region consisting of points that satisfy all the constraints is denoted by D^feas = D ∩Ω, where ${\Omega } = \{ \mathbf {x} \in \mathbb {R}^{n}: \mathbf {g} (\mathbf {x}) \leq \mathbf {0} \text { and } \mathbf {h} (\mathbf {x}) = \mathbf {0} \}$. We also assume that all functions are Lipschitz-continuous (with unknown Lipschitz constants) but can be nonlinear, nondifferentiable, and nonconvex.

The original DIRECT algorithm (Jones et al. 1993), as well as various modifications (Liu and Cheng 2014; Paulavičius et al. 2014, 2018; Paulavičius and žilinskas 2013, 2014; Sergeyev and Kvasov 2006), addresses optimization problems only with bounds on the variables. The first DIRECT-type approach for problems with general constraints was proposed by one of the original DIRECT authors (Jones 2001). A few years later, the comparison of three different constraint handling strategies withing the DIRECT framework was carried out (Finkel 2005). The first three strategies revealed disadvantages of handling infeasible hyper-rectangles and opened many ways for researchers to improve existing and create new strategies. Only in recent years, several promising extensions of the original DIRECT algorithm have been proposed (Basudhar et al. 2012; Costa et al. 2017; Liu et al. 2017; Pillo et al. 2010, 2016) for general engineering global optimization problems.

In this paper, we introduce the extension for general engineering optimization problems to our recently proposed DIRECT-GL (Stripinis et al. 2018) algorithm, which is based on a new strategy (compared to the most of DIRECT-type methods) for the selection of the extended set of potentially optimal hyper-rectangles (POH). The proposed DIRECT-GLce algorithm uses an auxiliary function approach, that combines information on the objective and constraint functions and does not require any penalty parameters. The DIRECT-GLce algorithm works in two phases, where during the first phase, the algorithm handles infeasible initial points, while in the second phase seeks to find a feasible global solution. A separate phase for handling infeasible initial points is especially useful when the feasible region is small compared to the design space. When feasible solutions are located, the efforts may be switched to finding better feasible solutions.

The rest of the paper is organized as follows. In Section 2, we briefly review existing extensions of original DIRECT algorithm for generally constrained optimization. In Section 3, we review the existing DIRECT-type approaches based on the exact L1 penalty function schemes. The description of the new DIRECT-GLce algorithm is given in Section 4. In Sections 5 and 6, we compare our algorithm with filter-based DIRECT, EPGO, DF-EPGO, and eDIRECT-C on 80 test problems and 4 engineering instances. Finally, we conclude the paper in Section 7.

2 DIRECT-type methods for general optimization problem

In this section, we review and summarize existing DIRECT-type methods for (1) optimization problems.

The first DIRECT-type approach for problems with general constraints was presented in Jones (2001). The author extended the original DIRECT algorithm to handle nonlinear inequality constraints by using an auxiliary function that combines information on the objective and constraint functions in a special manner.

The second DIRECT-type approach is based on the neighborhood assignment strategy (NAS) (Gablonsky 2001). The idea of this strategy is to change the value of the objective function at the infeasible point $\bar {\mathbf {x}} \notin D^{\text {feas}}$ with the objective value attained in the feasible point from the neighborhood of $\bar {\mathbf {x}}$. Such a strategy does not allow the DIRECT algorithm to move beyond the feasible region. As the NAS strategy does not use all the available information, such as constraint violations, it is slower in general compared to other approaches and should be used only for optimization problems with hidden constraints.

Another strategy is based on the exact L1 penalty functions (Fletcher 1987). An exact L1 penalty approach is a transformation of the original constrained problem (1) to the form:

$$ \min\limits_{\mathbf{x}\in D} f(\mathbf{x})+\sum\limits_{i = 1}^{m} \max\{p_{i} g_{i}(\mathbf{x}),0\}+\sum\limits_{i = 1}^{r} p_{i+m} |h_{i}(\mathbf{x})|, $$

(2)

where p_i are penalty parameters. Comparison in Finkel (2005) showed promising results. The biggest drawback is the requirement for the users to set penalty parameters for each constraint function. In practice, choosing penalty parameters is very important task and can have a huge impact on the performance of the algorithm (Finkel 2005; Liu et al. 2017; Paulavičius and žilinskas 2014, 2016). Recently, two new approaches based on penalty functions were proposed: EPGO (Pillo et al. 2010) and DF-EPGO (Pillo et al. 2016). The main feature of these algorithms is an automatic update rule for the penalty parameter and under the weak assumptions; the penalty parameters are updated only a finite number of times. Another recently proposed DIRECT-type approach filter-based DIRECT (Costa et al. 2017) aims to minimize the constraint violations and the objective function value simultaneously. While other strategies work only with one general set of all hyper-rectangles, filter-based DIRECT algorithm adapts filter methodology from Fletcher and Leyffer (2002) and splits the main set into three separate sets. The filter strategy prioritizes the selection of potentially optimal candidates: first, hyper-rectangles with feasible center points are selected, followed by those with infeasible but nondominated center points, and finally by those that have infeasible and dominated center points.

A metamodel-based (Forrester and Keane 2009; Shan and Wang 2010a, b) constrained DIRECT-type global optimization algorithm (eDIRECT-C) was recently also proposed in Liu et al. (2017). One of the main differences and features of the algorithm is employed Voronoi diagrams for partitioning the design space in Voronoi cells. Voronoi cells have irregular boundaries and eDIRECT-C generates a set of random points to describe the cells. In order to speed up the convergence, the algorithm employs a pure greedy search on the objective metamodel f̂. Also eDIRECT-C separately handles feasible and infeasible cells.

The summary of discussed and proposed algorithms is presented in Table 1.

Table 1 Summary of the main algorithmic characteristics of DIRECT-type methods for (1) optimization problem

3 Experimental investigation of the exact L1 penalty strategy within DIRECT-GL algorithm

In Stripinis et al. (2018), the comparison of DIRECT-GL algorithm against the original DIRECT as well as several other well-known DIRECT-type approaches was carried out on a class of well-known box-constrained global optimization test problems from Hedar (2005). The results revealed, that for simpler (lower dimensional and unimodal) problems the original DIRECT algorithm performs well, but for more challenging (higher dimensional and multimodal) problems, DIRECT-GL performs significantly faster compared to other tested DIRECT-type approaches. Motivated by the potential of the DIRECT-GL algorithm, we integrate the exact L1 penalty function strategy within DIRECT-GL and call the extended algorithm DIRECT-GL-L1. In the first implementation, for each constraint, the penalty parameters for L1 functions are kept fixed during the optimization process. Analogously to Paulavičius and žilinskas (2014), we use three different penalty parameters (p = 10, p = 10², and p = 10³) for all constraint functions. Algorithmic comparison was carried out using a collection of 56 generally constrained test problems. Key characteristics of the used optimization test problems are summarized in Appendix B, Table 11. Description of all test problems used in this and subsequent section in a Matlab format is provided in the online resource (Stripinis and Paulavičius 2018). Note that problem G12* has the global minimum point in the center of the feasible region; thus, we have modified bound constraints in the same way as in Liu et al. (2017). Since all the global minima f^∗ are known for all collected test problems in advance, tested algorithms were stopped either when a point $\bar {\mathbf {x}}$ was generated such that the percent error as follows:

$$ pe \le \varepsilon_{\text{pe}}, $$

(3)

where,

$$pe = \left\{\begin{array}{ll} \frac{f(\bar{\mathbf{x}}) - f^{*}}{|f^{*}|}, & f^{*} \neq 0, \\ f(\bar{\mathbf{x}}), & f^{*} = 0, \end{array}\right. $$

often ε_pe = 10^− 4, or when the number of function evaluations exceeds the prescribed limit of 10⁶.

Experimental results are presented in Table 2 (the best results are given in bold). Here, in the second column (label), we report the name of the problem, while in the third one—the dimensionality (n) of the problem. In the fourth column (cons. type), we specify type of constraints: linear (L) or nonlinear (NL). Next, in the consecutive columns, the total number of function evaluations are reported using four different algorithms: DIRECT-GL-L1, DIRECT-L1, DIRECT-GLc, and DIRECT-GLce, accordingly. Note that the DIRECT-GLc and DIRECT-GLce algorithms are extensions of the DIRECT-GL-L1 algorithm and fully described in Section 4.

Table 2 The number of function evaluations solving optimization problems described in Table 11 and using different algorithms

The exact L1 penalty function approach integrated within DIRECT-GL (DIRECT-GL-L1 algorithm) gives on average (aver.(overall)) significantly better results compared to DIRECT-L1. However, none of tested fixed penalty parameters for L1 penalty function can ensure the convergence to the feasible solution for all tested problems. Contrary to DIRECT-L1 which works better using smaller penalty parameters (p = 10), the better performance of DIRECT-GL-L1 is achieved when larger penalty parameter values are used. When larger penalty values (p = 10³) are used, the DIRECT-L1 algorithm fails for 67.9% (38/56) cases, while DIRECT-GL-L1 fails only for 28.6% (16/56) cases accordingly. Also, larger penalty parameter values reduce the chance of obtaining a solution from the infeasible region. On the other hand, larger penalty values can bias the algorithm away from the boundary of the feasible region where the solution is often located.

Another important feature, that even for low-dimensional test problems (n ≤ 3) DIRECT-L1 with (p = 10³) fails for 36% (9/25) cases, but the DIRECT-GL-L1 algorithm have none such cases at all. Moreover, the smallest dimensionality when DIRECT-L1 exceeds the maximal number of function evaluation is equal to n = 2, while using DIRECT-GL-L1 the lowest dimensionality when the algorithm failed to converge withing the budged is equal to n = 7. When solving problems with linear (L) constraints using DIRECT-L1, the maximal number of function evaluation is exceeded for 51.5% (17/33) cases, while for DIRECT-GL-L1, this happens for 9.1% (3/33) cases accordingly. Even more, using the DIRECT-L1 algorithm with all three different penalty parameters, the median value is more than 10⁶, which means that more than half of test problems were not solve in allowed time, while much better (smaller) median values were obtained using the DIRECT-GL-L1 approach. To sum up, while lower penalty values give a better performance for the DIRECT-L1 algorithm, larger penalty values suit better within the DIRECT-GL-L1 scheme.

In recent years, performance (Dolan and Moré 2002) and data profiles (Moré and Wild 2009) have become a popular and widely used tool for benchmarking and evaluating the performance of several algorithms (solvers) when run on a large problem set. Thus, in this section, we also compare the performance of the algorithms using both these tools with the convergence test (3). Benchmark results are generated by running a certain algorithm s (from a set of algorithms $\mathcal {S}$ under consideration) for each problem p from a benchmark set $\mathcal {P}$, and recording the performance measure of interest, which could be, for example, the number of function evaluations, the computation time, the number of iterations or the memory used. In our case, the number of function evaluations criterion is used.

Performance profiles asses the overall performance of algorithms (solvers) using a performance ratio (r_p,s) as follows:

$$ r_{p,s} = \frac{t_{p,s}}{\min\{ t_{p,s} : s \in \mathcal{S} \}}, $$

(4)

where t_p,s > 0 is the number of function evaluations required to solve problem p by the algorithm s and $\min \{ t_{p,s} : s \in \mathcal {S} \}$ is the smallest number of function evaluations by any algorithm on this problem. Then, the performance profile (ρ_s(α)) of an algorithm $s \in \mathcal {S}$ is given by the cumulative distribution function for the performance ratio as follows:

$$ \rho_{s}(\alpha) = \frac{1}{|\mathcal{P}|}\text{size} \{ p \in \mathcal{P} : r_{p,s} \le \alpha \}, \quad \alpha \ge 1, $$

(5)

where $|\mathcal {P}|$ is the cardinality of $\mathcal {P}$. Thus, ρ_s(α) is the probability for an algorithm $s \in \mathcal {S}$ that a performance ratio r_p,s for each $p \in \mathcal {P}$ is within a factor α of the best possible ratio.

The performance profiles seek to capture how well the certain algorithm s performs compared to other algorithms in $\mathcal {S}$ on the set of problems from $\mathcal {P}$. In particular, ρ_s(1) gives the fraction of the problems in $\mathcal {P}$ for which algorithm s is the winner, i.e., the best according to the t_p,s criterion. In general, algorithms with high values for ρ_s(α) are preferable.

On the other hand, performance profiles do not provide the percentage of problems that can be solved with a given budget of function evaluations. The data profiles are designed to provide this information. The data profile defined in a such way is shown as follows:

$$ d_{s}(\alpha) = \frac{1}{|\mathcal{P}|}\text{size} \{ p \in \mathcal{P} : t_{p,s} \le \alpha \}, $$

(6)

and shows the percentage of problems that can be solved with α function evaluations.

Figure 1 shows the performance and data profiles of DIRECT-GL-L1 and DIRECT-L1 algorithms on the whole set of optimization problems described in Table 11. The data profiles show that DIRECT-GL-L1 algorithm outperforms DIRECT-L1 with all penalty parameter values for all sizes of the computational budget. Moreover, the performance differences between the DIRECT-GL-L1 and DIRECT-L1 algorithms tend to be larger when the computational budget is bigger. The performance profiles reveal that all three DIRECT-GL-L1 algorithm variations solve ≈ 30% with the best efficiency, while only ≈ 10% using any of DIRECT-L1 variations.

Fig. 1

Data profiles (left) and performance profiles (right) of DIRECT-GL-L1 and DIRECT-L1 algorithms on the whole set of optimization problems described in Table 11

4 DIRECT-GLce algorithm for generally constrained global optimization problems

4.1 Handle the case with infeasible initial regions

In this section, we present a new way to handle hyper-rectangles with infeasible centers. In the first extension of DIRECT-GL-L1, we consider a situation when initial sampling points are infeasible and finding at least one feasible point can be costly. In such a situation of DIRECT-type algorithms, DIRECT-GL-L1 and DIRECT-L1 are likely to fail in finding feasible points in a reasonable number of function evolutions. For such a situation, we employ an additional procedure into DIRECT-GL-L1 scheme, which samples the search space and minimizes not the original objective function, but the sum of constraint violations, i.e.,

$$ \min\limits_{\mathbf{x}\in D}\varphi(\mathbf{x}), $$

(7)

where,

$$ \varphi(\mathbf{x})=\sum\limits_{i = 1}^{m} \max\{p_{i} g_{i}(\mathbf{x}),0\}+\sum\limits_{i = 1}^{r} p_{i+m} |h_{i}(\mathbf{x})|, $$

(8)

until a feasible point $\mathbf {x}\in D^{\text {feas}}_{\varepsilon _{\varphi }}$ is found, where,

$$ D^{\text{feas}}_{\varepsilon_{\varphi}} = \{\mathbf{x} : 0 \leq \varphi(\mathbf{x}) \leq \varepsilon_{\varphi}, \mathbf{x} \in D \}. $$

(9)

Penalty parameters p_i are simply set to 1 and ε_φ is a very small acceptable constraint violation. The authors of the eDIRECT-C algorithm use a very similar idea, but for treating the constraints equally, they recommend to normalize every constraint function. And in the same step, they sample the search space and minimize the sum of normalized constraint violations φ^N(x), i.e.,

$$ \min\limits_{\mathbf{x}\in D} \varphi^{N}(\mathbf{x}). $$

(10)

In Table 3, we present the impact of this procedure on the selected subset of test problems (from Tables 10 and 11) having a small feasible region (the best results are given in bold). For problems G03, G05, and G10, the L1 penalty-based approaches can fail to produce a feasible solution within 10⁶ function evaluations, but using (7) or (10), we avoid such a situation.

Table 3 The number of function evaluations needed by algorithms to find a feasible point

By the second extension to DIRECT-GL-L1, we transform problems (2) to (11) as follows:

$$ \begin{array}{ll} & \min\limits_{\mathbf{x}\in D} f(\mathbf{x}) + \xi(\mathbf{x},f_{\min}^{\text{feas}}),\\ & \xi(\mathbf{x},f_{\min}^{\text{feas}})= \left\{\begin{array}{ll} 0, & \mathbf{x} \in D^{\text{feas}}_{\varepsilon_{\varphi}} \\ \begin{array}{l} \varphi(\mathbf{x}) + {\Delta}, \end{array} & \text{otherwise,} \end{array}\right. \end{array} $$

(11)

i.e., instead of the exact L1 penalty approach, we introduce an auxiliary function $\xi (\mathbf {x},f_{\min }^{\text {feas}})$ which depends on the sum of constraint functions and only one parameter ${\Delta } = |f(\mathbf {x}) - f_{\min }^{\text {feas}}|$, which is equal to absolute value of the difference between the best feasible function value found so far $f_{\min }^{\text {feas}}$ and the objective value at an infeasible center point. The main purpose of the parameter Δ is to forbid the convergence of the algorithm to infeasible regions by penalizing objective value obtained at infeasible points. In such a way, formulation (11) does not require any penalty parameters and determine the convergence of the algorithm to a feasible solution. The value of $\xi (\mathbf {x},f_{\min }^{\text {feas}})$ is updated when a smaller value of $f_{\min }^{\text {feas}}$ is found. The new algorithm with these two extensions is called DIRECT-GLc. Note that this comes with a slight performance overhead, compared to DIRECT-GL-L1, which uses the fixed penalty values during the entire minimization process.

Since at the beginning of the search the difference between $f_{\min }^{\text {feas}}$ and the global solution f^∗ can be large, therefore the value of $\xi (\mathbf {x},f_{\min }^{\text {feas}})$ can be increased too much. We take into account this by modifying (11) to (12) as follows:

$$ \begin{array}{ll} & \min\limits_{\mathbf{x}\in D} f(\mathbf{x}) + \tilde{\xi}(\mathbf{x},f_{\min}^{\text{feas}}),\\ & \tilde{\xi}(\mathbf{x},f_{\min}^{\text{feas}}) = \left\{\begin{array}{ll} 0, & \mathbf{x} \in D^{\text{feas}}_{\varepsilon_{\varphi}} \\ 0, & \mathbf{x} \in D_{\varepsilon_{\text{cons}}}^{\inf}\\ \begin{array}{l} \varphi(\mathbf{x}) + {\Delta}, \end{array} & \text{otherwise,} \end{array}\right. \end{array} $$

(12)

where $D_{\varepsilon _{\text {cons}}}^{\inf } = \{\mathbf {x} : f(\mathbf {x}) \!\leq \! f_{\min }^{\text {feas}}, \varepsilon _{\varphi } \!<\! \varphi (\mathbf {x}) \!\leq \! \varepsilon _{\text {cons}}, \mathbf {x} \!\in \! D \}$ and ε_cons is a small tolerance for constraint function sum, which automatically varies during the optimization process. More detailed behavior of ε_cons is described in algorithm 1, lines 19–28. With the introduction of this modification, the new DIRECT-GLce algorithm divides more hyper-rectangles with the center points lying close to the boundaries of the feasible region, i.e., potential solution. A geometrical illustration of ε_cons parameter is shown in Fig. 2.

Fig. 2

Geometric interpretation of DIRECT-GLce algorithm on T1 (n = 2) test problem in (a) the sixth iteration, (b) the seventh iteration, (c) the eighth iteration

Experimental performance using both introduced methods are presented in Table 2. No constraint violation was allowed in this experiment and the parameter ε_φ was set to 0. First, it is easy to notice that for the low-dimensional test problems (n ≤ 3), the number of function evaluations is most often smaller for DIRECT-GLc algorithm 46.3% (26/56), also DIRECT-GL-L1 algorithm looks more promising with bigger penalty parameters solving the same test problems. ε_cons parameter in DIRECT-GLce algorithm requires more function evaluations for simpler test problems (low dimension and with linear constrains) comparing with other algorithms, but solving more complicated test problems DIRECT-GLce is much more promising. The main advantage of ε_cons parameter can be seen solving higher dimensional and nonlinear (NL) test problems, where DIRECT-GLce outperforms other methods in average function evaluations and solved problems. Also looking in a general context, DIRECT-GLce requires less function evaluations and fails to solve only three test problems from which for two, the algorithm reached the region of the global solution and only for one 20-dimensional test problem, the algorithm was not able to locate the region.

Figures 3, 4, and 5 show the data and performance profiles for all the algorithms in the interval [1,10]. The data profiles from Fig. 3 display that introduced DIRECT-GLc and DIRECT-GLce algorithms significantly outperform all previously tested exact L1 penalty function-based approaches, and the performance differences increase even more when the computational budget is bigger. The performance profiles in Fig. 3 reveal that DIRECT-GLc algorithm has the most wins, and it can solve about 50% of the problems with the highest efficiency. The difference is even bigger for simpler problems (with linear constraints or n ≤ 3), where the probability that DIRECT-GLc is the optimal solver is close to 0.6 (see, Figs. 4, and 5). However, solving more challenging problems (with nonlinear constraints and n ≥ 4) DIRECT-GLce outperforms other algorithms, and the performance difference increases as the performance ratio increases. Also, if we choose being within a performance ratio of 10 of the best algorithm, then DIRECT-GLce is also the most effective algorithm, with the exception for simpler problems (n ≤ 3), where DIRECT-GLc is the leader.

Fig. 3

Data profiles (left) and performance profiles (right) of DIRECT-GLce, DIRECT-GLc, DIRECT-GL-L1, and DIRECT-L1 algorithms on the whole set of optimization problems described in Table 11

Fig. 4

Performance profiles of DIRECT-GLce, DIRECT-GLc, DIRECT-GL-L1, and DIRECT-L1 algorithms solving problems with linear (left) and nonlinear (right) constraints from Table 11

Fig. 5

Performance profiles of DIRECT-GLce, DIRECT-GLc, DIRECT-GL-L1, and DIRECT-L1 algorithms solving n ≤ 3 (left) and n ≥ 4 (right) problems from Table 11

4.2 Algorithmic steps

The complete description of the DIRECT-GLce algorithm is given in algorithm 1 and additionally is presented in a flowchart in Fig. 6. The input for the algorithm is one (or few) stopping criteria: required tolerance (ε_pe), the maximal number of function evaluations (FE_max), and the maximal number of DIRECT-GLce iterations (K_max). After termination, DIRECT-GLce returns the found objective value $f_{\min }^{\text {feas}}$ and the solution point $\mathbf {x}_{\min }^{\text {feas}}$ together with algorithmic performance measures: the final tolerance—percent error (pe), the total number of function evaluations (fe), and the total number of iterations (k).

Fig. 6

Flowchart of the DIRECT-GLce algorithm

DIRECT-GLce uses the new two-step-based strategy for the selection of potentially optimal hyper-rectangles, which is presented in Stripinis et al. (2018). The DIRECT-GLce performs the selection twice in each iteration. First, the globally enhanced set of potentially optimal candidates is determined and fully processed (sampled and partitioned) (see, algorithm 1, lines 11–16; second, the locally enhanced set is identified and fully processed, see, lines 32–45).

The algorithm operates in two phases, which depends on whether a feasible point in D^feas is already found or not (see, lines 6–10). If it is not yet found, the algorithm minimizes only sum of constraint violation (8) and attempts to find a feasible point. After such a point is found, the algorithm switches to the second phase and minimizes problem (12). Lines 19–28 are controlled by constraint tolerance parameter ε_cons determining infeasible points which will not be penalized at all. In the proposed strategy, the number of such points (the cardinality of the set $D_{\varepsilon _{\text {cons}}}^{\inf }$), cannot exceed 10 × n³, if this happens, ε_cons should be reduced. In the opposite case when the cardinality of the set $D_{\varepsilon _{\text {cons}}}^{\inf }$ is zero, ε_cons should be increased. We set the boundaries for the rate of change 10^− 4 ≤ ε_cons ≤ 10.

5 Comparison with other DIRECT-type approaches for constrained global optimization

In this section, we present an exhaustive comparison of the newly proposed DIRECT-GLce algorithm with other existing DIRECT-type algorithms devoted to (1) problems.

5.1 Comparison with eDIRECT-C algorithm

First, we perform comparison against the recently proposed eDIRECT-C (Liu et al. 2017) algorithm. Authors compared their eDIRECT-C vs. CORBA (Regis 2014), ConstrLMSRBF (Regis 2011), CiMPS (Kazemi et al. 2011), and DIRECT-L1 (Finkel 2005) algorithms. The numerical experiments revealed the potential of eDIRECT-C algorithm for expensive constrained problems in terms of the convergence speed, the quality of final solutions, and the success rate. We use two versions of DIRECT-GLce: the first is presented in Section 4, while the second version is based on DIRECT-GLce and is enriched with a local minimization procedure (let us call the algorithm DIRECT-GLce-min).

To perform the comparison as fair as possible, we use the same 13 test problems from Liu et al. (2017). Key characteristics of these constrained global optimization test problems (G01–G13) are listed in Appendix B, Tables 11 and 10. Note that several of these test problems: G03, G05, G11, and G13 contain equality constraints, which we transform (by the same strategy as in Liu et al. (2017)) into two inequality constraints as follows:

$$ \mathbf{h} (\mathbf{x}) = 0 \rightarrow \left\{\begin{array}{ll} \mathbf{h} (\mathbf{x}) - \varepsilon_{\mathrm{h}} &\leq 0\\ -\mathbf{h} (\mathbf{x}) - \varepsilon_{\mathrm{h}} &\leq 0, \end{array}\right. $$

(13)

where ε_h > 0 is set to 10^− 4. The stopping criterion is the same relative error (3) as we used in the previous analysis. In these experiments, allowed constraint violation ε_φ = 0 was used. In Liu et al. (2017), the maximal allowed number of function evaluations was set to 1000. According to the authors, eDIRECT-C was developed primarily for expensive constrained global optimization problems, in which a simulation of the problem may require several hours or even days. Thus, the eDIRECT-C algorithm requires much more running time than the other compared methods, especially this is the case for higher dimensional problems. On the contrary, in Section 4, we showed that our approach works faster compared to DIRECT-L1, and the difference increases for larger problems. Thus, we use the maximum limit equal to 10⁶ function evaluations for our algorithm. The obtained results are given in Table 4 (as usual, the best results are given in bold). Here, f_min is the minimal objective function value found by the corresponding algorithm; f_eval is the number of objective function evaluations required by an algorithm to reach the solution within specified accuracy; and SR (success rate) records the number of success runs among the total ten runs. Note that our approach is deterministic and there is no requirement to run our algorithm several times.

Table 4 Comparison of different algorithms for 13 test problems (see Tables 11 and 10 for the description) from Liu et al. (2017)

First, observe that DIRECT-GLce algorithm solves 11/13 of test problems while eDIRECT-C solves only 8/13. When we combine DIRECT-GLce with the local search procedure in DIRECT-GLce-min algorithm, the hybridized algorithm outperforms eDIRECT-C by both criteria: the number solved problems 12/13 and the quality of the final solution. Moreover, the incorporated local minimization procedure into DIRECT-GLce-min significantly reduces the total number of function evaluations compared to DIRECT-GLce, but eDIRECT-C required the smallest number of function evaluations on the average. On the other hand, authors in Liu et al. (2017) stated that eDIRECT-C requires much more running time compared to other algorithms used in the comparison; therefore, the number of function evaluations criterion alone does not represent the real performance of the algorithms very well.

5.2 Comparison with filter-based DIRECT algorithm

In the second part, we compare the proposed algorithms with the filter-based DIRECT algorithm (Costa et al. 2017). Note that in this comparison, we omit two other DIRECT-type algorithms based on the exact penalty functions: EPGO, DF-EPGO, as comparison with them was already carried out in Costa et al. (2017).

We consider the same 20 global optimization test problems (P01(x)–P16) see Tables 10 and 11 in Appendix B for the detailed description) used in Costa et al. (2017) and collected from Birgin et al. (2010). In order to provide as fair as possible comparison, in the same vein as in Costa et al. (2017), we have performed algebraic manipulation aiming to reduce the number of variables and equality constraints:

• Test problems P02(a), P02(b), and P02(c) after reformulation contain 5 variables and 10 inequality constraints. In the original problem formulation, there were 9 variables, 4 equality, and 2 inequality constraints.

• Test problem P02(d) after reformulation contains 5 variables and 12 inequality constraints. In the original problem formulation, there were 10 variables, 5 equality, and 2 inequality constraints.

• Test problem P05 after reformulation contains 2 variables, 2 equality, and 2 inequality constraints. In the original problem formulation, there were 3 variables and 3 equality constraints.

• Test problem P09 after reformulation contains 3 variables and 9 inequality constraints. In the original problem formulation, there were 6 variables, 3 equality, and 3 inequality constraints.

• Test problem P12 after reformulation contains 1 variable and 2 inequality constraints. In the original problem formulation, there were 2 variables and 1 equality constraints.

• Test problem P14 after reformulation contains 3 variables and 4 inequality constraints. In the original problem formulation, there were 4 variables, 1 equality, and 2 inequality constraints.

• Test problem P16 after reformulation contains 2 variables and 6 inequality constraints. In the original problem formulation, there were 5 variables and 3 equality constraints.

In Costa et al. (2017), the authors stopped considered algorithms when the point $\bar {\mathbf {x}}$ was generated such that the percent error $(\tilde {pe})$ was as follows:

$$ \tilde{pe} =\frac{|f({\bar{\mathbf{x}}}) - f^{*}|}{\max\{1,|f^{*}|\}} < 10^{-4}, $$

(14)

or when the number of iterations exceeds the prescribed limit of 200. Note that although all considered algorithms belong to DIRECT-type class, the cost of one iteration can vary significantly. Therefore, we stopped our tested algorithms either when (14) was satisfied or when the maximal number of function evaluations equal to 200,000 was reached. In the same vein as in Costa et al. (2017) allowed constrain violation ε_φ was set to 10^− 4. The obtained experimental results are presented in Table 5. Our algorithms (DIRECT-GLc and DIRECT-GLce) give on average (aver.(overall)) significantly better results compared to filter-based DIRECT and failed to locate solution point with required tolerance (14) only for 3/20 of test problems (highlighted in red color in the colored version), and none of those three problems was solved by the filter-based DIRECT algorithm among with two others. However, for simpler test problems, i.e., lower dimensionality cases (n ≤ 3) and on problems with linear (L) constraints filter-based DIRECT is a very promising option. The completely different behavior for harder test problems, i.e., higher dimensionality cases (n ≥ 4) and on problems with nonlinear (NL) constraints where our approaches give much better results. Finally, our enriched version with a local minimization procedure DIRECT-GLce-min failed only on P02(b) test problem, where the algorithm converged to a local minimum point and gave the best results based on all used comparison criteria.

Table 5 Comparison between algorithms on 20 test problems from Costa et al. (2017)

6 Comparison on four engineering problems

In this section, we conclude our experimental investigation by applying the algorithms from the previous section to four important real-world engineering problems. The detailed description of these engineering problems can be found in Liu et al. (2017), while in Appendix A, we provide the short description and mathematical formulations. The same stopping rule (3) as in the previous section is used. No constraint violation was allowed in this experiments and the parameter ε_φ was set to 0. Note that some of the problems contain integer variables; thus, by the same analogy to Liu et al. (2017), we regard them as continuous ones.

Tables 6, 7, 8, and 9 list the best found solutions and the total number of function evaluations using each of the algorithms solving four engineering problems. We note that using the eDIRECT-C algorithm sometimes obtained solution is better compared to ours, but in all these cases, the reported solution point violates constraints of the problem. Possibly, this is within constraint violation tolerances allowed by the authors of eDIRECT-C, but our algorithms provide final solutions without any constraint violation. As we tried to maintain the same number of decimals across the manuscript, we acknowledge that some provided rounded solution points can slightly violate constraints. For the NASA speed reducer design problem (E01) (see, Table 6), the variable bounds for x₅ are 7.8 ≤ x₅ ≤ 8.3; however, the value of x₅ from the reported optimal solution point for eDIRECT-C algorithm is equal to x₅ = 7.71532.

Table 6 The best solutions obtained by the algorithms for problem E01

Table 7 The best solutions obtained by the algorithms for problem E02

Table 8 The best solutions obtained by the algorithms for problem E03

Table 9 The best solutions obtained by the algorithms for problem E04

A similar situation is when solving the pressure vessel design problem (E02). The variable x₁ is bounded within 1 ≤ x₁ ≤ 1.375, but the fifth constraint function g₅(x) : 1.1 − x₁ ≤ 0 reduces the feasible interval to 1.1 ≤ x₁ ≤ 1.375. However, the value of x₁ for the reported optimal solution point using eDIRECT-C is equal to x₁ = 1.

Once again, we notice the similar situation solving tension spring design problem (E03). The reported optimal solution point for eDIRECT-C algorithm violates the constrain $g_{1}(\mathbf {x}): 1 - \frac {{x_{2}^{3}}x_{3}}{71875{x_{1}^{4}}} \leq 0$. At the solution point, the feasible value of the first constraint should be nonpositive, but the reported value is g₁(x) = 0.0012 > 0.

Only in three-bar truss design problem (E04) reported optimal solution point for eDIRECT-C algorithm did not violate any constraint. Our DIRECT-GLce-min version obtained the identical solution point. In overall view, our algorithms for all engineering problems are able to locate solution points which meet the stopping rule (3) and satisfy all the constraints.

7 Conclusions, challenges, and further work

In this paper, we introduced a new strategy for constrained optimization problems in the DIRECT-type algorithmic framework. Two well-known weaknesses of DIRECT-L1 algorithms were addressed in the proposed approaches. First, we have demonstrated that the exact L1 penalty function based new DIRECT-GL-L1 algorithm gives on average significantly better results compared to DIRECT-L1. Moreover, the performance differences between DIRECT-GL-L1 and DIRECT-L1 algorithms tend to be larger when solving harder problems.

Next, instead of the exact L1 penalty approach, we introduced an auxiliary function-based approach in the DIRECT-GLc and DIRECT-GLce algorithms, which does not require any penalty parameters. The proposed DIRECT-GLc and DIRECT-GLce algorithms significantly outperform all previously tested exact L1 penalty function-based approaches, and the performance differences increases when the computational budget is larger. The DIRECT-GLc algorithm has the most wins, and it can solve about 50% of the problems with the highest efficiency. However, solving more challenging problems (with nonlinear constraints and n ≥ 4), DIRECT-GLce outperforms other algorithms, and the performance difference increases as the performance ratio increases. Also, solving higher-dimensional test problems, DIRECT-GLce outperforms the original DIRECT-L1 algorithm in running speed.

To improve the solution accuracy and improve the efficiency solving high-dimensional problems, we have enriched DIRECT-GLce with a local minimization procedure and called the new algorithm DIRECT-GLce-min. The further experimental investigation revealed the advantage of the DIRECT-GLce and DIRECT-GLce-min algorithms over most test problems and four engineering problems comparing with recent relevant approaches DIRECT-L1, filter-based DIRECT, and eDIRECT-C.

One of the most significant challenges of the partitioned based DIRECT-type approaches is dealing with optimization problems with equality constraints. Proposed DIRECT-GLce showed promising results solving such problems, but effectiveness strongly depends on the allowed equality constraints violation.

Finally, as global optimization problems are computationally expensive, one of the primary upcoming goals is to develop and investigate a parallel version of our algorithm. There are very few works devoted to the parallelization of the DIRECT-type methods. One of the primary motivations stems from the fact that the set of potentially optimal hyper-rectangles in our algorithms is larger (compared to DIRECT); thus, we can expect better efficiency compared to existing parallel DIRECT-type approaches.

Appendices

Appendix A: The mathematical formulations of engineering problems

NASA speed reducer design problem (Liu et al. 2017; Ray and Liew 2003).

The overall weight subject to constraints on bending stress of the gear teeth, surface stress, and transverse deflections of the shafts and stresses in the shafts is minimized. This problem has 7 design variables and 11 constraints. The optimization problem is formulated as following:

$$ \begin{array}{ll} \min & f(\mathbf{x}) = 0.7854x_{1}{x_{2}^{2}}(3.3333{x_{3}^{2}} + 14.9334x_{3} - 43.0934) \\ & -1.508x_{1}({x_{6}^{2}}+{x_{7}^{2}})+ 7.4777({x_{6}^{3}}+{x_{7}^{3}}) \\ & + 0.7854(x_{4}{x_{6}^{2}}+x_{5}{x_{7}^{2}}) \\ \mathrm{ s.t.} & g_{1}(\mathbf{x}) = \frac{27}{x_{1}{x_{2}^{2}}x_{3}}-1 \leq \mathbf{0},~ g_{2}(\mathbf{x})=\frac{397.5}{x_{1}{x_{2}^{2}}{x_{3}^{2}}} - 1 \leq \mathbf{0}, \\ & g_{3}(\mathbf{x})=\frac{1.93{x_{4}^{3}}}{x_{2}x_{3}{x_{6}^{4}}} - 1 \leq \mathbf{0},~ g_{4}(\mathbf{x})=\frac{1.93{x_{5}^{3}}}{x_{2}x_{3}{x_{7}^{4}}} - 1 \leq \mathbf{0},\\ & g_{5}(\mathbf{x})= \frac{((\frac{745x_{4}}{x_{2}x_{3}})^{2}+ 16.9 \times 10^{6})^{0.5}}{110{x_{6}^{3}}} - 1 \leq \mathbf{0}, \\ & g_{6}(\mathbf{x})=\frac{((\frac{745x_{5}}{x_{2}x_{3}})^{2}+ 157.5 \times 10^{6})^{0.5}}{85{x_{7}^{3}}} - 1 \leq \mathbf{0}, \\ & g_{7}(\mathbf{x})=\frac{x_{2}x_{3}}{40} - 1 \leq \mathbf{0},~ g_{8}(\mathbf{x})= \frac{5x_{2}}{x_{1}} - 1 \leq \mathbf{0}, \\ & g_{9}(\mathbf{x})=\frac{x_{1}}{12x_{2}} - 1 \leq \mathbf{0},~ g_{10}(\mathbf{x})=\frac{1.5x_{6}+ 1.9}{x_{4}} - 1 \leq \mathbf{0}, \\ & g_{11}(\mathbf{x})=\frac{1.1x_{7}+ 1.9}{x_{5}} - 1 \leq \mathbf{0} \end{array} $$

where 2.6 ≤ x₁ ≤ 3.6, 0.7 ≤ x₂ ≤ 0.8, 17 ≤ x₃ ≤ 28, 7.3 ≤ x₄ ≤ 8.3, 7.8 ≤ x₅ ≤ 8.3, 2.9 ≤ x₆ ≤ 3.9, 5 ≤ x₇ ≤ 5.5.

Table 10 Key characteristics of the optimization test problems with equality constraints

Pressure vessel design problem (Kazemi et al. 2011; Liu et al. 2017).

The total cost of material, forming, and welding of a cylindrical vessel is minimized. This problem has four design variables and six constraints The optimization problem formulated as following:

$$ \begin{array}{ll} \min & f(\mathbf{x})= 0.6224x_{1}x_{3}x_{4}+ 1.7781x_{2}{x_{3}^{2}}+ 3.1661{x_{1}^{2}}x_{4} \\ & + 19.84{x_{1}^{2}}x_{3}\\ \mathrm{ s.t.} & g_{1}(\mathbf{x})= -x_{1}+ 0.0193x_{3} \leq \mathbf{0}, \\ & g_{2}(\mathbf{x})= -x_{2}+ 0.00954x_{3} \leq \mathbf{0}, \\ & g_{3}(\mathbf{x})=- \pi {x_{3}^{2}}x_{4}- \frac{4}{3} \pi {x_{3}^{3}}+ 1296000 \leq \mathbf{0}, \\ & g_{4}(\mathbf{x})= x_{4}-240 \leq \mathbf{0},~ g_{5}(\mathbf{x})= 1.1-x_{1} \leq \mathbf{0}, \\ & g_{6}(\mathbf{x})= 0.6-x_{2} \leq \mathbf{0} \end{array} $$

where 1 ≤ x₁ ≤ 1.375, 0.625 ≤ x₂ ≤ 1, 25 ≤ x₃ ≤ 150, 25 ≤ x₄ ≤ 240.

Tension/compression spring design problem (Kazemi et al. 2011; Liu et al. 2017).

The weight subject to constraints on minimum deflection, shear stress, surge frequency, and limits on outside diameter is minimized. This problem has three design variables and four constraints. The optimization problem formulated as following:

$$ \begin{array}{ll} \min & f(\mathbf{x})={x_{1}^{2}}x_{2}(x_{3}+ 2)\\ \mathrm{ s.t.} & g_{1}(\mathbf{x})= 1- \frac{{x_{2}^{3}}x_{3}}{71875{x_{1}^{4}}} \leq \mathbf{0}, \\ & g_{2}(\mathbf{x})= \frac{x_{2}(4x_{2}-x_{1})}{12566{x_{1}^{3}}(x_{2}-x_{1})}+ \frac{2.46}{12566{x_{1}^{2}}}-1 \leq \mathbf{0}, \\ & g_{3}(\mathbf{x})= 1- \frac{140.54x_{1}}{x_{3}{x_{2}^{2}}} \leq \mathbf{0},~ g_{4}(\mathbf{x})= \frac{x_{1}+x_{2}}{1.5}-1 \leq \mathbf{0} \end{array} $$

where 0.05 ≤ x₁ ≤ 0.2, 0.25 ≤ x₂ ≤ 1.3, 2 ≤ x₃ ≤ 15.

Three-bar truss design problem (Liu et al. 2017; Ray and Liew 2003).

The volume subject to stress constraints is minimized. This problem has two design variables and three constraints. The optimization problem formulated as following:

$$ \begin{array}{ll} \min & f(\mathbf{x})= 100(2 \sqrt{2} x_{1}+x_{2})\\ \mathrm{ s.t.} & g_{1}(\mathbf{x})= \frac{\sqrt{2} x_{1}+x_{2}}{\sqrt{2} {x_{1}^{2}}+ 2x_{1}x_{2}}2-2 \leq \mathbf{0}, \\ & g_{2}(\mathbf{x})= \frac{x_{2}}{\sqrt{2} {x_{1}^{2}}+ 2x_{1}x_{2}}2-2 \leq \mathbf{0}, \\ & g_{3}(\mathbf{x})= \frac{1}{x_{1}+\sqrt{2} x_{2}}2-2 \leq \mathbf{0} \end{array} $$

where 0 ≤ x₁ ≤ 1, 0 ≤ x₂ ≤ 1.

Appendix B: Test problems with linear and nonlinear constraints

Table 11 Key characteristics of the constrained global optimization test problems