Global Optimization by Monotonic Transformation

This paper addresses the problem of global optimization by means of a monotonic transformation. With an observation on global optimality of functions under such a transformation, we show that a simple and effective algorithm can be derived to search within possible regions containing the global optima. Numerical experiments are performed to compare this algorithm with one that does not incorporate transformed information using several benchmark problems. These results are also compared to best known global search algorithms in the literature. In addition, the algorithm is shown to be useful for several neural network learning problems, which possess much larger parameter spaces.     

Global Optimization Performance Measures for Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may pes]rform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting.     

On Global Optimality Conditions and Cutting Plane Algorithms

We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems.     

Global one-dimensional optimization using smooth auxiliary functions

In this paper new global optimization algorithms are proposed for solving problems where the objective function is univariate and has Lipschitzean first derivatives. To solve this problem, smooth auxiliary functions, which are adaptively improved during the course of the search, are constructed. Three new algorithms are introduced: the first used the exact a priori known Lipschitz constant for derivatives; the second, when this constant is unknown, estimates it during the course of the search and finally, the last method uses neither the exact global Lipschitz constant nor its estimate but instead adaptively estimates the local Lipschitz constants in different sectors of the search region during the course of optimization. Convergence conditions of the methods are investigated from a general viewpoint and some numerical results are also given. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Global Optimization Using Diffusion Perturbations with Large Noise Intensity

This work develops an algorithm for global optimization.The algorithm is of gradient ascent typeand uses random perturbations.In contrast to the annealing type procedurcs,the perturbation noise intensityis large.We demonstrate that by properly varying the noise intensity,approximations to the global maximumcan be achieved.We also show that the expected time to reach the domain of attraction of the global maximum,which can be approximated by the solution of a boundary value problem,is finite.Discrete-time algorithmsare proposed;recursive algorithms with occasional perturbations involving large noise intensity are developed.Numerical examples are provided for illustration.     

Simple Genetic Algorithm with Local Tuning: Efficient Global Optimizing Technique

Genetic algorithms are known to be efficient for global optimizing. However, they are not well suited to perform finely-tuned local searches and are prone to converge prematurely before the best solution has been found. This paper uses genetic diversity measurements to prevent premature convergence and a hybridizing genetic algorithm with simplex downhill method to speed up convergence. Three case studies show the procedure to be efficient, tough, and robust.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.     

Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions

We present a new strategy for the constrained global optimization of expensive black box functions using response surface models. A response surface model is simply a multivariate approximation of a continuous black box function which is used as a surrogate model for optimization in situations where function evaluations are computationally expensive. Prior global optimization methods that utilize response surface models were limited to box-constrained problems, but the new method can easily incorporate general nonlinear constraints. In the proposed method, which we refer to as the Constrained Optimization using Response Surfaces (CORS) Method, the next point for costly function evaluation is chosen to be the one that minimizes the current response surface model subject to the given constraints and to additional constraints that the point be of some distance from previously evaluated points. The distance requirement is allowed to cycle, starting from a high value (global search) and ending with a low value (local search). The purpose of the constraint is to drive the method towards unexplored regions of the domain and to prevent the premature convergence of the method to some point which may not even be a local minimizer of the black box function. The new method can be shown to converge to the global minimizer of any continuous function on a compact set regardless of the response surface model that is used. Finally, we considered two particular implementations of the CORS method which utilize a radial basis function model (CORS-RBF) and applied it on the box-constrained Dixon–Szegö test functions and on a simple nonlinearly constrained test function. The results indicate that the CORS-RBF algorithms are competitive with existing global optimization algorithms for costly functions on the box-constrained test problems. The results also show that the CORS-RBF algorithms are better than other algorithms for constrained global optimization on the nonlinearly constrained test problem.     

A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems

There is a need for a methodology to fairly compare and present evaluation study results of stochastic global optimization algorithms. This need raises two important questions of (i) an appropriate set of benchmark test problems that the algorithms may be tested upon and (ii) a methodology to compactly and completely present the results. To address the first question, we compiled a collection of test problems, some are better known than others. Although the compilation is not exhaustive, it provides an easily accessible collection of standard test problems for continuous global optimization. Five different stochastic global optimization algorithms have been tested on these problems and a performance profile plot based on the improvement of objective function values is constructed to investigate the macroscopic behavior of the algorithms. The paper also investigates the microscopic behavior of the algorithms through quartile sequential plots, and contrasts the information gained from these two kinds of plots. The effect of the length of run is explored by using three maximum numbers of function evaluations and it is shown to significantly impact the behavior of the algorithms.     

Global optimization algorithms for a CAD workstation

This paper describes two new versions of the controlled random search procedure for global optimization (CRS). Designed primarily to suit the user of a CAD workstation, these algorithms can also be used effectively in other contexts. The first, known as CRS3, speeds the final convergence of the optimization by combining a local optimization algorithm with the global search procedure. The second, called CCRS, is a concurrent version of CRS3. This algorithm is intended to drive an optimizing accelerator, based on a concurrent processing architecture, which can be attached to a workstation to achieve a significant increase in speed. The results are given of comparative trials which involve both unconstrained and constrained optimization.This work was funded by the Science and Engineering Research Council.     

Global convergence of quasi-Newton-type algorithms for some nonsmooth optimization problems

We consider the global convergence properties for a class of quasi-Newton algorithms solving nonsmooth optimization problems. Stationary points are defined, and several relations with optimal points are proven. We show descent properties of the algorithm using approximations for the derivatives. The global convergence results are given for determining the stepsizes inexactly.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

A Hybrid Genetic Algorithm for Nonconvex Function Minimization

In this paper, we consider the problem of minimizing a function in severalvariables which could be multimodal and may possess discontinuities. A newalgorithm for the problem based on the genetic technique is developed. Thealgorithm is hybrid in nature in the sense that it utilizes the genetictechnique to generate search directions, which are used in an optimizationscheme and is thus different from any other methods in the literature.The algorithm has been tested on the Rosenbrock valley functions in 2 and 4dimensions, and multimodal functions in 2 and 4 dimensions, which are of ahigh degree of difficulty. The results are compared with the Adaptive RandomSearch, and Simulated Annealing algorithms. The performance of the algorithmis also compared to recent global algorithms in terms of the number offunctional evaluations needed to obtain a global minimum and results show thatthe proposed algorithm is better than these algorithms on a set of standardtest problems. It seems that the proposed algorithm is efficient and robust.     

Global Optima of Lennard-Jones Clusters

This paper summarizes the current state of knowledge concerning putative global minima of the potential energy function for Lennard-Jones clusters, an intensely studied molecular conformation problem. Almost all known exceptions to global optimality of the well-known Northby multilayer icosahedral conformations for microclusters are shown to be minor variants of that geometry. The truly exceptional case of face-centered cubic lattice conformations is examined and connections are made with the macrocluster problem. Several types of algorithms and their limitations are explored, and a new variation on the growth sequence idea is presented and shown to be effective for both small and large clusters.     

Global search algorithms for minimum concave-cost network flow problems

We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.     

A non-monotone trust region algorithm for unconstrained optimization with dynamic reference iteration updates using filter

We present a non-monotone trust region algorithm for unconstrained optimization. Using the filter technique of Fletcher and Leyffer, we introduce a new filter acceptance criterion and use it to define reference iterations dynamically. In contrast with the early filter criteria, the new criterion ensures that the size of the filter is finite. We also show a correlation between problem dimension and the filter size. We prove the global convergence of the proposed algorithm to first- and second-order critical points under suitable assumptions. It is significant that the global convergence analysis does not require the common assumption of monotonicity of the sequence of objective function values in reference iterations, as assumed by the standard non-monotone trust region algorithms. Numerical experiments on the CUTEr problems indicate that the new algorithm is competitive compared to some representative non-monotone trust region algorithms.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Some theoretical limitations of second-order algorithms for smooth constrained optimization

In second-order algorithms, we investigate the relevance of the constant rank of the full set of active constraints in ensuring global convergence to a second-order stationary point under a constraint qualification. We show that second-order stationarity is not expected in the non-constant rank case if the growth of so-called tangent AKKT2 sequences is not controlled. Since no algorithm controls their growth, we argue that there is a theoretical limitation of algorithms in finding second-order stationary points without constant rank assumptions.     

Feasible Direction Interior-Point Technique for Nonlinear Optimization

We propose a feasible direction approach for the minimization by interior-point algorithms of a smooth function under smooth equality and inequality constraints. It consists of the iterative solution in the primal and dual variables of the Karush–Kuhn–Tucker first-order optimality conditions. At each iteration, a descent direction is defined by solving a linear system. In a second stage, the linear system is perturbed so as to deflect the descent direction and obtain a feasible descent direction. A line search is then performed to get a new interior point and ensure global convergence. Based on this approach, first-order, Newton, and quasi-Newton algorithms can be obtained. To introduce the method, we consider first the inequality constrained problem and present a globally convergent basic algorithm. Particular first-order and quasi-Newton versions of this algorithm are also stated. Then, equality constraints are included. This method, which is simple to code, does not require the solution of quadratic programs and it is neither a penalty method nor a barrier method. Several practical applications and numerical results show that our method is strong and efficient.