Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm

Several numerical methods for solving nonlinear systems of equations assume that derivative information is available. Furthermore, these approaches usually do not consider the problem of finding all solutions to a nonlinear system. Rather, most methods output a single solution. In this paper, we address the problem of finding all roots of a system of equations. Our method makes use of a biased random-key genetic algorithm (BRKGA). Given a nonlinear system, we construct a corresponding optimization problem, which we solve multiple times, making use of a BRKGA, with areas of repulsion around roots that have already been found. The heuristic makes no use of derivative information. We illustrate the approach on seven nonlinear equations systems with multiple roots from the literature.     

DC-GRASP: directing the search on continuous-GRASP

Several papers in the scientific literature use metaheuristics to solve continuous global optimization. To perform this task, some metaheuristics originally proposed for solving combinatorial optimization problems, such as Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search and Simulated Annealing, among others, have been adapted to solve continuous global optimization problems. Proposed by Hirsch et al., the Continuous-GRASP (C-GRASP) is one example of this group of metaheuristics. The C-GRASP is an adaptation of GRASP proposed to solve continuous global optimization problems under box constraints. It is simple to implement, derivative-free and widely applicable method. However, according to Hedar, due to its random construction, C-GRASP may fail to detect promising search directions especially in the vicinity of minima, which may result in a slow convergence. To minimize this problem, in this paper we propose a set of methods to direct the search on C-GRASP, called Directed Continuous-GRASP (DC-GRASP). The proposal is to combine the ability of C-GRASP to diversify the search over the space with some efficient local search strategies to accelerate its convergence. We compare the DC-GRASP with the C-GRASP and other metaheuristics from literature on a set of standard test problems whose global minima are known. Computational results show the effectiveness and efficiency of the proposed methods, as well as their ability to accelerate the convergence of the C-GRASP.     

A Metropolis algorithm combined with Hooke-Jeeves local search method applied to global optimization

A hybridization of a recently introduced Metropolis algorithm named the Particle Collision Algorithm (PCA) and the Hooke-Jeeves local search method is applied to a testbed of global optimization functions and to real-world chemical equilibrium nonlinear systems. The results obtained by this method, called HJPCA, are compared against those achieved by two state-of-the-art global optimization methods, C-GRASP and GLOBAL. HJPCA performs better than both algorithms, thus demonstrating its potential for other applications.     

Global optimization by continuous grasp

We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus making it a well-suited approach for solving global optimization problems. We illustrate the effectiveness of the procedure on a set of standard test problems as well as two hard global optimization problems.     

A Python/C library for bound-constrained global optimization with continuous GRASP

This paper describes ${\texttt{libcgrpp}}$ , a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989) and has been used to solve unstable and nondifferentiable problems, as well as hard global optimization problems, such as chemical equilibrium systems and robot kinematics applications (Hirsch et al. in Optim lett 1:201–212, 2007). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an illustrative example.     

The GLOBAL optimization method revisited

The multistart clustering global optimization method called GLOBAL has been introduced in the 1980s for bound constrained global optimization problems with black-box type objective function. Since then the technological environment has been changed much. The present paper describes shortly the revisions and updates made on the involved algorithms to utilize the novel technologies, and to improve its reliability. We discuss in detail the results of the numerical comparison with the old version and with C-GRASP, a continuous version of the GRASP method. According to these findings, the new version of GLOBAL is both more reliable and more efficient than the old one, and it compares favorably with C-GRASP too.     

Speeding up continuous GRASP

Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2007). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In this paper, we describe several improvements that speed up the original C-GRASP and make it more robust. We compare the new C-GRASP with the original version as well as with other algorithms from the recent literature on a set of benchmark multimodal test functions whose global minima are known. Hart’s sequential stopping rule (1998) is implemented and C-GRASP is shown to converge on all test problems.     

On locating all roots of systems of nonlinear equations inside bounded domain using global optimization methods

A novel method of locating all real roots of systems of nonlinear equations is presented here. The root finding problem is transformed to optimization problem, enabling the application of global optimization methods. Among many methods that exist in global optimization literature, Multistart and Minfinder are applied here because of their ability to locate not only the global minimum but also all local minima of the objective function. This procedure enables to locate all the possible roots of the system. Various test cases have been examined in order to validate the proposed procedure. This methodology does not make use of a priori knowledge of the number of the existing roots in the same manner as the corresponding global optimization methodology which does not make use of a priori knowledge of the existed number of local minima. Application of the new methodology resulted in finding all the roots in all test cases. The proposed methodology is general enough to be applied in any root finding problem.     

A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.     

A new filled function method for nonlinear equations

In this paper, a new global optimization approach based on the filled function method is proposed for solving box-constrained systems of nonlinear equations. We first convert the nonlinear system into an equivalent global optimization problem, and then propose a new filled function method to solve the converted global optimization problem. Several numerical examples are presented and solved by using different local minimization methods, which illustrate the efficiency of the present approach.     

An Electromagnetism-like Mechanism for Global Optimization

This paper proposes a new heuristic for global optimization. The method utilizes an attraction-repulsion mechanism to move the sample points towards the optimality. The proposed scheme can be used either as a stand-alone approach or as an accompanying procedure for other methods. Some test results on nonlinear test functions in the category of ``minor to moderate difficulty' are included. The ease of implementation and flexibility of the heuristic show the potential of this new approach.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

Optimization of dual response systems: A comprehensive procedure for degenerate and nondegenerate problems

Most dual response systems (DRSs) arising in response surface modeling can be approximated using a nonlinear (and typically nonconvex) mathematical program involving two quadratic functions. One of the quadratic functions is used as the objective function, the other for imposing a target constraint. This paper describes an effective heuristic for computing global (or near-global) optimal solutions for this type of problem. The first part of the paper addresses the special case of degeneracy, a condition that makes the system more difficult to solve. Included are means for detecting degeneracy as well as issues relating to its likelihood in practice. The subsequent part of the paper describes our new procedure, AXIS, which rotates a degenerate problem and then decomposes it into a finite sequence of nondegenerate subproblems of lower dimension. The nondegenerate subproblems are solved using the algorithm DRSALG developed earlier. In the final parts of the paper, the AXIS and DRSALG algorithms are integrated into a single dual response solver termed DR2. DR2 is tested against two nonlinear optimization procedures that have been used frequently in dual response applications. The new solver proves to be extremely effective at locating best-practice operating conditions.     

Optimizing stochastic production-inventory systems: A heuristic based on simulation and regression analysis

We present a heuristic optimization method for stochastic production-inventory systems that defy analytical modelling and optimization. The proposed heuristic takes advantage of simulation while at the same time minimizes the impact of the dimensionality curse by using regression analysis. The heuristic was developed and tested for an oil and gas company, which decided to adopt the heuristic as the optimization method for a supply-chain design project. To explore the performance of the heuristic in general settings, we conducted a simulation experiment on 900 test problems. We found that the average cost error of using the proposed heuristic was reasonably low for practical applications.     

Multi-Path Approach for Reliability-Redundancy Allocation Using a Scaling Method

The reliability-redundancy allocation problem is an optimization problem that achieves better system reliability by determining levels of component redundancies and reliabilities simultaneously. The problem is classified with the hardest problems in the reliability optimization field because the decision variables are mixed-integer and the system reliability function is nonlinear, non-separable, and non-convex. Thus, iterative heuristics are highly recommended for solving the problem due to their reasonable solution quality and relatively short computation time. At present, most iterative heuristics use sensitivity factors to select an appropriate variable which significantly improves the system reliability. The sensitivity factor represents the impact amount of each variable to the system reliability at a designated iteration. However, these heuristics are inefficient in terms of solution quality and computation time because the sensitivity factor calculations are performed only at integer variables. It results in degradation of the exploration and growth in the number of subsequent continuous nonlinear programming (NLP) subproblems. To overcome the drawbacks of existing iterative heuristics, we propose a new scaling method based on the multi-path iterative heuristics introduced by Ha (2004). The scaling method is able to compute sensitivity factors for all decision variables and results in a decreased number of NLP subproblems. In addition, the approximation heuristic for NLP subproblems helps to avoid redundant computation of NLP subproblems caused by outlined solution candidates. Numerical experimental results show that the proposed heuristic is superior to the best existing heuristic in terms of solution quality and computation time.     

Newton's method for the nonlinear complementarity problem: A B-differentiable equation approach

This paper describes a damped-Newton method for solving the nonlinear complementarity problem when it is formulated as a system of B-differentiable equations through the use of the Minty-map. This general Newton algorithm contains a one-dimensional line search and possesses a global convergence property under certain conditions; modifications and heuristic implementations of the algorithm for the case when these conditions do not hold are also discussed. The numerical experiments show that, in general, this new scheme is more efficient and robust than the traditional Josephy-Newton algorithm.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

Advances in Interval Methods for Deterministic Global Optimization in Chemical Engineering

In recent years, it has been shown that strategies based on an interval-Newton approach can be used to reliably solve a variety of nonlinear equation solving and optimization problems in chemical process engineering, including problems in parameter estimation and in the computation of phase behavior. These strategies provide a mathematical and computational guarantee either that all solutions have been located in an equation solving problem or that the global optimum has been found in an optimization problem. The primary drawback to this approach is the potentially high computational cost. In this paper, we consider strategies for bounding the solution set of the linear interval equation system that must be solved in the context of the interval-Newton method. Recent preconditioning techniques for this purpose are reviewed, and a new bounding approach based on the use of linear programming (LP) techniques is presented. Using this approach it is possible to determine the desired bounds exactly (within round out), leading to significant overall improvements in computational efficiency. These techniques will be demonstrated using several global optimization problems, with focus on problems arising in chemical engineering, including parameter estimation and molecular modeling. These problems range in size from under ten variables to over two hundred, and are solved deterministically using the interval methodology.     

Solution of the least squares method problem of pairwise comparison matrices

The aim of the paper is to present a new global optimization method for determining all the optima of the Least Squares Method (LSM) problem of pairwise comparison matrices. Such matrices are used, e.g., in the Analytic Hierarchy Process (AHP). Unlike some other distance minimizing methods, LSM is usually hard to solve because of the corresponding nonlinear and non-convex objective function. It is found that the optimization problem can be reduced to solve a system of polynomial equations. Homotopy method is applied which is an efficient technique for solving nonlinear systems. The paper ends by two numerical example having multiple global and local minima. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA K 60480.