Introduction

In this paper, we aim to investigate the performance of a repulsion algorithm that is based on a penalty function and the Nelder-Mead (N-M) [1] local search procedure to compute multiple roots of a system of nonlinear equations of the form (1) where f(x) = (f₁(x), f₂(x), …, f_n(x))^T, each f_i:Ω ⊂ ℝⁿ → ℝ, i = 1, …, n is a continuous and possibly nonlinear function in the search space, and Ω is a closed convex set defined as [l, u] = {x:−∞ < l_i ≤ x_i ≤ u_i < ∞, i = 1, …, n}. Since we do not assume that the functions f_i(x), i = 1, …, n are differentiable, neither analytical nor numerical derivatives are used. To compute a solution of a nonlinear system of equations is equivalent to compute a global minimizer of the optimization problem (2) in the sense that they have the same solutions. Thus, a global minimizer and not just a local one, of the function M(x), known as merit function, in the set Ω, is required. Although finding a single root of a system of nonlinear equations is a trivial task, finding all roots is one of the most demanding problems. Multistart methods are stochastic techniques that have been used to compute multiple solutions to problems [2, 3]. In a multistart strategy, a local search procedure is applied to a set of randomly generated points of the search space to converge sequentially along the iterations to the multiple solutions of the problem, in a single run. However, the same solutions may be located over and over again along the iterations resulting in a very expensive process. Other recent approaches combine metaheuristics with techniques that modify the merit function (2) as solutions are being found [4–8]. Mostly, the techniques rely on the assignment of a penalty term to each previously computed root so that a repulsion area around each previously computed root is created. The repulsion areas force the algorithm to move to other areas of the search space and look for other roots, avoiding repeated convergence to already located solutions. The main idea of this type of methods, designated by repulsion method, is to solve a sequence of global optimization problems aiming to minimize the modified merit function $\bar{M}$ that creates a repulsion area around each computed solution ξ_i, for i = 1, …, N_r, where N_r represents the number of previously computed minimizers, as follows (3) The function P(x;ξ_i, ⋯) is the penalty term that depends on ξ_i and one or more parameters [6–8]. The goal of these parameters is to adjust the penalty for already located minimizers. They may be used to reduce the radius of the repulsion area or to highly penalize the proximity to located solutions.

In this study, we further explore this penalty-type approach to create repulsion areas around previously detected roots and propose a repulsion algorithm that is capable of computing multiple roots of a system of nonlinear equations invoking the N-M local procedure with modified merit functions. The herein proposed repulsion algorithm is of a stochastic nature in the sense that a sequence of points are randomly generated inside the search space Ω aiming to increase the exploration ability of the algorithm. The exploitation ability of the algorithm is carried out by implementing the N-M local search starting from each of the generated points. The N-M method is a derivative-free local search procedure that is capable of converging to a minimizer of a merit function, provided that a good initial approximation is given, with a reduced computational effort when compared with most metaheuristics available in the literature.

Design of experiments (DoE) is a powerful statistical tool that is capable of developing an experimentation strategy to learn and identify crucial factors that influence experimental data, using a minimum of resources [9, 10]. Our main challenge here is to analyze the effect of imposing slightly different strategies on the classical N-M algorithm, namely

• randomly generating points for the initial simplex when they fall outside the search space Ω;
• dynamically setting the simplex parameters to generate expansion, contraction and shrinkage vertices;
• generating renewal positions for randomly selected vertices of the simplex to overcome simplex degeneracy;
• generating vertices around the best vertex according to the Lévy distribution to replace the classical shrinkage of the simplex.

We aim to conclude if the observed differences in the performance, measured by different criteria, are considered statistically significant, or are they just explained by normal variation like noise. Usual performance criteria measure robustness and efficiency. For robustness, we consider the percentage of runs that converge to all roots of the system of equations, and for efficiency, we use the number of function evaluations and time required to compute each root.

The paper is organized as follows. First, we address the proposed repulsion algorithm based on an ‘erf’ penalty merit function; second, a summary of the main steps of the classical N-M algorithm, as well as the description of different strategies for testing and performance assessment are presented. Afterwards, a two-level factorial DoE is introduced and the corresponding statistical analysis is carried out. Finally, a performance comparison is reported and the conclusions are presented.

Repulsion algorithm

This section aims to briefly describe a penalty-type approach to create repulsion areas around previously computed roots of a system of nonlinear equations, so that convergence to already located solutions is avoided. Algorithms based on repulsion merit functions have been used for locating multiple roots of systems of equations [6, 8]. The merits of a repulsion algorithm are that multiple roots can be located with a reduced computational effort in a single run of the algorithm. The pseudo code of the repulsion algorithm is presented in Algorithm 1 in Table 1.

The algorithm solves a sequence of global optimization problems by invoking a local search procedure that is capable of locating a local minimizer of a merit function. This function is modified as the roots are located. See steps 1 and 1 of Algorithm 1 in Table 1. The first call to the local search considers the original merit function (2). Thereafter the merit function is modified to avoid locating previously computed minimizers.

In the algorithm, ‘k_R’ is the iteration counter, ‘Ξ’ is the set where the roots are saved, ‘N_r’ contains the number of located roots so far, ‘r₁, …, r_Nr’ are variables that contain the number of times each root is relocated and ‘k_uns’ represents the number of consecutive unsuccessful iterations, i.e., consecutive iterations that are not able to find any new root. To identify a root of the system the algorithm requires that its merit function value is under 10⁻¹⁰. A located root ξ is considered to be different from the previously computed roots ξ_i, i = 1, …, N_r (saved in Ξ) if ‖ξ−ξ_i‖ > ε, for all i = 1, …, N_r, where ε is a small positive error tolerance.

The repulsion algorithm terminates when a maximum number of iterations, k_Rmax, is exceeded or when a pre-specified number of consecutive iterations (15, in this algorithm) are not able to locate any new root. Thus, if the algorithm stops.

The algorithm explores the search space by randomly generating points in Ω in a sequential manner (see steps 1 and 1 of the algorithm). Starting from the sampled point y, the algorithm exploits the region in order to locate a minimizer of the merit/modified merit function by invoking a local search procedure (see steps 1 and 1 of Algorithm 1 in Table 1). Since the goal is to produce a derivative-free effective algorithm for locating multiple roots, our proposal for computing a minimizer of the merit function, given a sampled point y, is the N-M local procedure. This is the subject of the next section.

The herein implemented penalty-type merit function is based on the error function, known as ‘erf’, which is a mathematical function defined by the integral and satisfies the following properties erf(0) = 0, erf(−∞) = −1, erf(+∞) = 1 and erf(−x) = −erf(x). In a penalty function context aiming to prevent convergence to a located root ξ_i, thus defining a repulsion area around it, the newly developed ‘erf’ penalty term is: (4) which depends on the parameter δ > 0 to scale the penalty for approaching the already computed solution ξ_i and on the parameter ρ to adjust the radius of the repulsion area. To better understand the effect of the ‘erf’ penalty around 0, we plot in Fig 1 the function (4) for different values of the parameter δ (1, 10 and 100).

We note that the penalty term tends to δ when x approaches a root ξ_i, meaning that δ should be made large enough so that ξ_i is no longer a minimizer of the modified penalty merit function. Further, as x moves away from ξ_i, the penalty P(x;ξ_i, δ, ρ) → 0 meaning that the modified merit function $\bar{M}(x)=M(x)+P(x;{\xi }_i,\delta ,\rho )$ is not affected when x is far from a previously located root.

N-M Algorithm Variants

The N-M algorithm, also known as simplex search algorithm, originally published in 1965 [1], is probably the best known algorithm for multidimensional derivative-free optimization, and is an improvement over the Spendley’s et al. method [11].

In ℝⁿ, the N-M algorithm uses a set of n+1 vertices, by now denoted by x¹, x², …, xⁿ, xⁿ⁺¹, to define a simplex, which is an n-dimensional polytope—the convex hull of its n+1 vertices. The algorithm moves at least one vertex per iteration defining a new simplex for the next iteration. The main idea is to maintain at each iteration a nondegenerate simplex, i.e., a geometric figure in ℝⁿ of nonzero volume. In [11], either a reflection or a shrink step is performed so that the shape of the simplex does not change along the iterative process. In general, a reflection step is performed when the current simplex is far from the solution, while a shrink step is performed when the simplex is close to the solution. In terms of computational effort, when a reflection step is performed only one or two function evaluations are required, while when a shrink step is performed, n function evaluations are required.

The initial simplex could be computed by performing small perturbations around an initial guess point. Thus, given x¹, an approximation to the minimizer of M (or, it may be a randomly generated point in Ω), the other n vertices are usually generated along the unit coordinate vectors e_j ∈ ℝⁿ with a fixed step size ɛ_e ∈ (0,1] (at an equal distance relative to x¹) as follows: It has been observed that using short edges in the initial simplex is a good strategy for small dimensional problems [12]. Although this is the most popular rule to generate the initial simplex, when the problem contains bound constraints, some (or all) components of the other vertices x^j (j = 2, …, n+1) may fall outside the search space Ω, even if x¹ is inside. Two possible ways of restoring feasibility are: (i) project the component of the point onto the boundary of Ω, as shown in Algorithm 2 in Table 2; or (ii) randomly generate the component of the point inside Ω, as described in Algorithm 3 in Table 3, where τ is a uniformly distributed random number in [0, 1] (τ ∼ U[0, 1]).

To define a set of candidate points to be a vertex of the simplex of the next iteration, the simplex is ordered so that M(z¹) ≤ M(z²) ≤ ⋯M(zⁿ) ≤ M(zⁿ⁺¹), where z¹ is termed the best vertex, zⁿ⁺¹ the worst vertex and zⁿ the second-worst (or next-worst) of the simplex. Note that simplex ordering relabels the vertices according to merit function value and are now represented by z¹, z², …, zⁿ, zⁿ⁺¹. Let the centroid of the n best vertices be defined by then the new candidate points to a vertex are defined along the line defined by $\bar{x}$ and zⁿ⁺¹. They are constructed componentwise as follows (5) for j = 1, …, n, where x_r, x_e, x_oc and x_ic, usually referred to as reflection vertex, expansion vertex, outer contraction vertex and inner contraction vertex, are obtained setting γ to γ_r, γ_e, γ_oc and γ_ic respectively. We remark that the algorithm checks if the component of the vector in (5) stays inside Ω; otherwise, a projection onto the boundary is carried out. The rules that are used to accept one of the above referred candidate points are directed related with their objective function values relative to the function values of the best vertex, second-worst vertex and worst vertex, are shown in Algorithm 4 in Table 4, and are according to [13]. There might be some differences in the literature, for instances in [1]. When one of these vertices is accepted, the worst vertex is discarded and the new point takes the position of a vertex of the simplex for the next iteration.

In classical versions of the N-M method [1, 13–17], when none of these vertices is accepted, according to the rules described in Algorithm 4 in Table 4, the simplex is shrunk towards the best vertex by using (6) for i = 2, …, n+1 and j = 1, …, n. According to [1], the simplex γ parameters that give the step size to generate the points in (5) and (6) must satisfy 0 < γ_r < γ_e, γ_e > 1, −1 < γ_ic < 0 < γ_oc < 1 and 0 < γ_s < 1. The most commonly used values for the parameters are: (7)

The examples reported in [15] showing that N-M may converge to a non-critical point of a strictly convex objective function are well-known in the community. N-M is one of the most popular direct search method and has shown to behave rather well when solving small dimensional problems. Although it has been used in many scientific and engineering applications, there are just a few works on the convergence properties of the algorithm [12, 13, 15, 16]. The performance of N-M gets worse as n increases. The authors in [12] prove that the efficiency of the expansion and contraction steps diminishes as n increases when N-M relies on the standard parameter values (see in (7)) to solve uniformly convex objective functions. Thus, values for the γ parameters for expansion, contraction and shrinking, dependent on n, are proposed in [12] to improve convergence. The golden ratio represented by the Greek letter Φ has been used in many practical situation to bring balance and harmony in life. It is a real number and is the unique positive solution of the quadratic equation Φ²−Φ−1 = 0. Here, we propose to define the N-M γ parameters using the golden value $\Phi =\frac{\sqrt{5}+1}{2}$ and n in order to have balanced expanded and reduced simplices, as follows: (8) Note that we propose to use γ_r = 1 in order to keep the isometric reflection since this is crucial for good performance [12, 16]. We also remark that expansion, contraction and shrinkage vertices are obtained from (5) and (6), using (8) to define the associated parameters dependent on the problem’s dimension. The goal is to reduce the simplex in a smoother way.

The major difficulty with the N-M method is that a sequence of simplices can come arbitrarily close to degeneracy. Let V be the n×n matrix with n-vector columns v¹, v², …, vⁿ where (9) and det(V) denote the determinant of V. To keep the interior angles of the simplex bounded away from 0, the following condition has to be maintained along the process (10) where ε_v is a small positive constant. When (10) fails to be satisfied, the simplex has collapsed and needs to be reshaped. The simplest option is to ‘break’ the iterative process and return to the main repulsion algorithm with no solution. Here, we are interested in testing a renewal strategy that aims to keep the best vertex and has a 75% chance of changing the remaining n vertices (i = 2, …, n + 1), componentwise, as follows: (11) using again the golden ratio to balance the step size of the move around z¹. If the generated components fall outside Ω, a projection onto the boundary is carried out.

When none of the x_r, x_e, x_oc and x_ic vertices is accepted, a procedure based on the randomly generation of points according to a Lévy distribution is also proposed. This is a stable and heavy-tailed distribution that is able to provide occasionally long movements. Similarly to the classical shrinkage procedure (6), the best vertex is maintained, and the other n vertices are generated around z¹: (12) for i = 2, …, n+1 and j = 1, …, n, where L(α) is a random number from the standard Lévy distribution, with location parameter equals to 0, a unit scale parameter, and the shape parameter α = 0.5. Again, if the components fall outside Ω, a projection onto the boundary is carried out. The vector σⁱ in (12) represents the variation around z¹

Two-Level Factorial DoE

In this section, we aim to use a two-level factorial DoE to analyze the effect of imposing the above referred strategies on the N-M algorithm, as well as to know if the observed differences in selected performance criteria are considered statistically significant or are they just due to random variations from normal distribution. Some notation and terminology related to factorial DoE will be introduced. In the previous section, we considered different strategies that can be implemented and manipulated within the N-M algorithm, in order to improve its performance. We aim to analyze the effect of those strategies—hereafter denoted by ‘factor levels’ or ‘treatments’—on the performance of the algorithm. For the design of an experiment, the following main steps must be carried out [9, 10]:

• formulation of the statistical hypotheses;
• definition of the factors and their levels (independent variables) and the measurements (response or dependent variables) to be recorded;
• specification of the number of experimental units;
• specification of the randomization process to assign the experimental units to the treatments;
• determination of the statistical analysis.

The simplest DoE involves randomly assigning experimental units to a factor with two or more levels. However, when more than one factor require to be analyzed, a factorial DoE is preferable. The simplest one involves two factors, each at two levels, denoted by two-by-two design. To analyze the two factor effects—named ‘A’ and ‘B’ –, a set of four experimental conditions should be analyzed. Let us denote the two levels of each factor by ‘low’ (or ‘-1’) and ‘high’ (or ‘+1’). Then, the first experiment combines the low level of A with the low level of B, the second combines the high level of A with the low level of B, the third combines the low level of A with the high level of B, and the fourth combines the high levels of both A and B. Although factorial experiments can involve factors with different number of levels, we are interested in a design where all factors have two levels. We plan to use a factorial DoE with four factors, each at two levels, and overall 2⁴ experimental conditions are to be conducted. In the statistical field, each experimental condition represents a different ‘treatment’ protocol.

We have chosen sixteen problems with different characteristics, dimensions and different number of roots to test the 2⁴ ‘treatments’. The problems and the number of roots are listed in Table 5 and are available in the literature [3, 5, 6, 8, 18, 19]. Due to the stochastic nature of the repulsion algorithm, from which N-M is invoked, we run each ‘treatment’ 30 times with each problem. The results are averaged over the 30 runs for each problem.

Three response variables are considered to analyze the performance of the algorithm variants:

• the proportion of successful runs, ranging from 0 to 1, and hereafter denoted by Y_p;
• the number of function evaluations to locate each root, ranging from 0 to 1500, denoted by Y_e;
• the time (in seconds) to locate each root, ranging from 0 to 1, denoted by Y_t.

To compute Y_p, a run is considered to be successful if all the roots are located at that run. To take into consideration the diversity of problems, the values of the above response variables for the statistical analysis are averaged over the sixteen problems. At the end, for each ‘treatment’ an average value of a total of 480 results is considered in this experiment.

Comparison of results

This section aims to show some performance comparison between the proposed repulsion algorithm based on a Nelder-Mead type local search and some other available techniques for locating multiple roots of a system of nonlinear equations. First, we compare our results with those reported in [7]. The results are summarized in Table 11 that shows:

• ‘SR’ (%), the percentage of runs (out of 30) where all the roots were located;
• ‘N_r’, the average number (out of 30) of located roots per run;
• ‘NFE_r’, the average number of function evaluations required to locate a root;
• ‘T_r’, the average time required to locate a root (in seconds);

relative to twelve problems of the previous set. From the proposed variants of the N-M algorithm, and according to the experimental testing of the previous section, we choose the one that combines the high levels of factors A, B, C, and D. We note that the results reported in [7] were obtained using a repulsion algorithm that uses the metaheuristic known as the harmony search as the local procedure. The differences between the three tested algorithms lie in the penalty term used to modify the merit function and to define the repulsion area as roots are computed. The penalty terms involve an inverse ‘erf’ function [7], an ‘exp’ function [8] and the ‘coth’ function [6]. These results are shown in the last three sets of four columns of Table 11. The first set of four columns of the table contains the results obtained by our study. We may conclude that our method notably wins in efficiency and is comparable to the others in terms of percentage of successful runs.

We aim to further compare the efficiency of our algorithm with the results reported in [3] and [8], regarding five problems of the previous set. In [8], the authors propose a biased random-key genetic algorithm to minimize the merit function coupled with a penalty approach to modify the merit function as roots are found. The penalty term is an ‘exp’ type function and is implemented with two parameters. One aims to create an area of repulsion around previously found roots and the other aims to penalize points inside the repulsion area. In [3], a multistart approach that uses a gradient-based BFGS variant as the local search procedure is implemented. The statistics reported by the authors correspond to three multistart implementations that differ in the stopping rule adopted by the algorithm. Here, we report only the second best value. The results are shown in Table 12. Beside the statistics used in the previous table, we also show the average number of N-M local search calls, L_cal, for our algorithm. In the table, ‘–’ means that the data is not available in the referenced paper. In these comparisons we increase the parameters k_Rmax and the maximum of k_uns of the repulsion algorithm to 100 and 25, respectively, since the computational budget is not an important issue. Although our algorithm did not find all roots in all runs, when solving problems Reactor and Robot, it requires less function evaluations than the other two in comparison. While the average time needed to find each root is significantly lower than that of the heuristic proposed in [8], it exceeds the value of the average time reported in [3] (ranging from one to eight times), on problems Floudas, Merlet and Reactor (R = 0.960).

Performance on standard benchmarks

Since our proposals for the N-M variant seem promising when compared with those of the classical N-M, we decided to extend them to solving more complex and real application systems [18, 20–22]. The benchmark set is a difficult set of problems. For these experiments, k_Rmax and the maximum of k_uns (to stop the Repulsion Algorithm) are set to 75 and 15 respectively, the parameters ρ_ε and δ in the definition of the penalty term in (4) are fixed at 0.01 and 100 respectively, and the N-M algorithm is allowed to run for a maximum of 1000n iterations. We compare our results with two deterministic global search techniques, a traditional interval method that uses range testing and branching, designated as ‘HRB’, and a branch and prune approach denoted by ‘Newton’ in [20]. We also use the results produced by a continuation method designated by ‘CONT’ in [20] and those of a multiobjective evolutionary algorithm approach presented in [18], for comparison. It is mentioned that the algorithm has produced a constant number (≤ 200) of nondominated solutions in each run. We now describe each benchmark and the obtained results with some detail.

Economics modeling application. This is an economic modeling problem that can be tested for a variety of dimensions n: We test for n = 4,5,6,7,8,9 and compare with the results available in [20] considering the set Ω = [−100,100]ⁿ. The results produced by the ‘Newton’ algorithm correspond to interval widths smaller than 1.0E-08. See Table 13. Our algorithm is able to identify several roots. We note here that a located root ξ is considered to be different from any other computed root if they differ in norm more than ε = 0.05. We observe that as n increases, the number of located roots decreases. This means that the difficulty in converging to a root is higher when n is larger and this is related with the performance of the N-M search procedure that deteriorates as n increases. While the computational effort (function evaluations and time) in ‘Newton’ greatly increases with n, the number of function evaluations in our algorithm grows at most by a factor of two, if the number of local search calls is the same (see, for example, the instances with n = 4,5,6,7). However, the total time essentially depends on the time required by the N-M procedure to locate each root.

Neurophysiology application. This is an application from neurophysiology with n = 6 and is defined by: where c_i can be chosen at random. We test this application with c_i = 0, i = 1, …, 4 and consider three intervals [−10,10]⁶, [−100,100]⁶ and [−1000,1000]⁶, as proposed in [20]. See Table 14. In [18] (with 300 initial points and after 200 generations), the multiobjective algorithm produces a set of about 200 nondominated solutions after 28.90 seconds. (The time reported in [18] is based on a 2.4-GHz Intel Duo Core CPU with 2-GB RAM.) The results show that the larger the interval the smaller is the number of located roots. Once again we observe that as the number of located roots increases the larger is the time required to converge to a root (see the aT_r values). This is an important characteristic of the Repulsion Algorithm since the minimization of the modified penalty merit function gets harder as the number of penalty terms increases.

Interval arithmetic benchmarks. The following two sets of functions are benchmarks from the interval arithmetic area. They are designated as instances i1 and i5 and are defined as and respectively [20]. The set Ω for instance i1 is [−2,2]¹⁰ and for i5 is [−1,1]¹⁰. Both have n = 10 and one root in Ω. Our results as well as those available in [20] are reported in Table 15. We note that in [18] a set of nondominated solutions are obtained after 300 generations and 39.08 seconds when solving the benchmark i1 (using an initial population of 500 points), and 366.40 seconds when solving i5. We are able to accelerate our iterative process by setting the maximum of k_uns to 5 since the root is computed during the first iterations of the Repulsion Algorithm. From the results shown in the Table 15 we may conclude that the number of function evaluations and time required to converge to a root are comparable to that of ‘Newton’. Since the repulsion algorithm’s paradigm requires restarting again and again, searching the search space and looking for other roots, the corresponding total values may become large, depending on the number of restarts. Nevertheless, those totals are comparable to the totals of ‘HRB’.

Chemical equilibrium application. This problem addresses the equilibrium of the products of a hydrocarbon combustion process which, reformulated in the variable space, is [21]: where $R_1=10,R_2=0.193,R_3=0.002597/\sqrt{40},R_4=0.003448/\sqrt{40}$, R₅ = 0.00001799/40, $R_6=0.0002155/\sqrt{40},R_7=0.00003846/40$. The problem has one root and we tested it for three different sets: [10⁻⁴,10²]⁵, [10⁻⁴,10³]⁵ and [10⁻⁴,10⁸]⁵. The statistics computed from the results of our algorithm are shown in Table 16, where we report the results available in [20, 21] as well. In [18], 500 generations and an initial population of 500 points are considered to obtain a set of about 200 nondominated solutions in 32.71 seconds. Since we look for just one root, we first set the maximum of k_uns to 10. Although the root was located in only 10% of the runs, when the set Ω = [10⁻⁴,10⁸]⁵ is used, our iterative process takes on average 2,482 function evaluations (and 0.19 seconds) to converge to the solution. While the branch and prune technique ‘Newton’ requires a total of 52,236 function evaluations (and 6.32 seconds) to converge to the required solution, our iterative process computes 179,951 function values when the limit of unsuccessful iterations is set to 10, but it computes 55,913 function values when the limit of unsuccessful iterations is 5.

We now use the following five examples together with the ‘Neurophysiology application’ (with Ω = [−10,10]⁶) and ‘Interval arithmetic’ benchmark i1 (with Ω = [−10,10]¹⁰) to analyze and confirm the performance behavior of our choices for the N-M variant, with a set of problems different from the one used during the DoE analysis.

Bratu system. This is a polynomial system about x₁, …, x_n that arises from the discretization (with a mesh size of h) of the differential equation model for nonlinear diffusion phenomena taking place in combustion and semiconductors—a two-point boundary value problem—[3, 23]: where x₀ = x_n+1 = 0 and $h=\frac{1}{n+1}$. In the set [0, 5]ⁿ, there are two roots for all n. We tested this problem with n = 5.

Brown almost-linear system. This is a system with n variables which has two real roots if n is even and three roots if n is odd. It is a ill-conditioned and difficult to solve for some standard methods [21, 22]. In the interval [−1,1]ⁿ there is one root when n = 10.

Broyden tridiagonal system. This is a sparse polynomial system that has at least two real roots [24], where x₀ = x_n+1 = 0. We set n = 5 and Ω = [−1,2]⁵.

Resistive circuit problem This system of n nonlinear equations describes a nonlinear resistive circuit containing n tunnel diodes [25]. The set Ω is defined by [−10,10]ⁿ and we test this circuit problem with n = 5 and n = 7.

Yamamura problem. Another polynomial system tested for n = 10 [3, 23, 25] which has three roots in the interval [−5,5]¹⁰.

All the experiments were run 30 times with each problem and the reported results are average values over the 30 runs. First, we aim to show that the herein proposed parameter values, defined in (8), make the N-M algorithm to work better. Overall, the number of located roots has in general increased and the number of function evaluations and time have not increased, except when solving problem Brown. See the first two sets of three columns (identified with A₊₁B₊C₊₁D₊₁ and A₊₁B₋₁C₊₁D₊₁) in Table 17. We note that the problems now used are in general of larger dimension than those used during the DoE analysis. The last set of three columns of the table shows the results obtained when the shrinking strategy is selected, A₊₁B₋₁C₊₁D₋₁ (as opposed to the strategy defined in (12)). Improvements are obtained only on the problems Brown and Broyden, when compared to A₊₁B₊C₊₁D₊₁. Here, we consider an improvement when the number of located roots has increased, or the number of function evaluations has decreased provided that a tie in the number of roots is reported.

Second, we show that the strategy defined in (12), in the context of our proposals, is able to locate in general more roots than the classic shrinking methodology, using now this new set of problems. These two variants are identified by A₊₁B₊C₊₁D₊₁ and A₊₁B₊C₊₁D₋₁ respectively in the Table 18. We also include the results of another variant that uses a uniformly distributed random number instead of a number drawn from the Lévy distribution. We observe that the variant A₊₁B₊C₊₁D₊₁ wins on four problems. It is able to locate more roots than the other two in comparison on problems Broyden, Circuit_5 and Circuit_7 and is more efficient than the other two on the problem Interval (for the same number of located roots). The variant A₊₁B₊C₊₁D₋₁ wins on problem Neurophysiology and is more efficient on the problems Brown and Yamamura. The variant A₊₁B₊C₊₁D_+1(Uniform) wins only on the problem Bratu.

The results reported in Table 19 are used to show that the variant A₊₁B₊C₊₁D₊₁ that uses the golden ratio Φ to define the step size in order to generate points around the best vertex of the simplex (see (11)) outperforms the other two variants A₊₁B₊C_+1(random)D₊₁ and A₊₁B₊C₋₁D₊₁ in comparison. C_+1(random) means that in Eq (11) the step size is a multiple of a random number uniformly distributed in [0, 1], and C₋₁ represents the strategy that breaks the N-M iterative process when the simplex has collapsed.

Finally, we aim to show that the maximum target value, ρ_ε, for the radius of the repulsion area ρ (see the definition in (4) and in Subsection ‘Parameters Setting’) slightly affects the performance of the algorithm. In this section and until now we have set the fixed value ρ_ε = 0.01 when solving the eight problems. We test two other different values: 0.1 and 0.001. Table 20 contains the results produced by the variant A₊₁B₊C₊₁D₊₁. We may conclude that the values 0.01 and 0.1 give better results than 0.001. Between the two best values, 50% of the results are better with ρ_ε = 0.01 and the remaining are better with ρ_ε = 0.1.

Conclusions

A repulsion algorithm is presented for locating multiple roots of a system of nonlinear equations. The proposed algorithm relies on a penalty merit function that depends on two parameters. One aims to scale the penalty and the other adjusts the radius of the repulsion area, so that convergence to previously located minimizers of the merit function is avoided. For each randomly generated point in the search space, the algorithm invokes the N-M algorithm to exploit the region for a new minimizer. In the N-M local search context, several alternative strategies have been incorporated in the algorithm aiming to enhance the quality of the solutions and improve efficiency. To analyze the effect of these strategies on the overall performance of the repulsion algorithm, measured by three criteria—the percentage of successful runs, the number of function evaluations and the time required to compute each root -, a two-level factorial design of experiments is carried out. Four factors at two levels each are manipulated and tested to analyze their statistical significance. During these computational experiments, a set of sixteen benchmark problems is used. The values of the response variables used in the factorial design of experiments correspond to the averaged values after 30 independent runs produced by solving the sixteen problems.

From the statistical analysis, we may conclude with 99% confidence that:

• the number of function evaluations to locate each root and the time to locate each root have significantly increased when the simplex parameters are changed from the classical values to those based on the golden ratio and dimension;
• the percentage of successful runs, the number of function evaluations to locate each root and the time to locate each root have significantly been affected when the two approaches to overcome the simplex degeneracy are tested, in particular, they have increased when the new strategy of generating n vertices around the best vertex with probability 0.75 is used, instead of just ‘breaking’ the cycle;
• the number of function evaluations to locate each root has significantly increased when the Lévy distribution is used to generate n vertices around the best vertex instead of using the classical shrinking procedure;
• the number of function evaluations to locate each root has significantly decreased by the interaction that occurs when the simplex parameters change from the classical values to those based on the golden ratio and n, when the generation of n vertices around the best vertex with probability 0.75 is used, instead of the ‘break’ strategy, and when the Lévy distribution is used to generate n vertices around the best one as opposed to the shrinking strategy.

We have also tested our method with other more complex and realistic problems. The results show that our method is capable of converging to the multiple solutions of those problems with a moderate computational effort. To undergo a variety of other modifications to the N-M algorithm using a limited number of experimental units, a fractional factorial experimental design as opposed to the herein operated full factorial design will be used. The techniques for investigating the variation in experiments brought by the Taguchi methods will be explored.

Acknowledgments

The authors would like to thank the academic editor and the two anonymous referees for their valuable comments and suggestions to improve the paper.