Covering a compact polygonal set by identical circles

The paper considers the problem of covering compact polygonal set by identical circles of minimal radius. A mathematical model of the problem based on Voronoi polygons is constructed and its characteristics are investigated. On the ground of the characteristics a modification of the Zoutendijk feasible directions method is developed to search local minima. A special approach is suggested to choose starting points. Many computational examples are given.     

Packing cylinders and rectangular parallelepipeds with distances between them into a given region

This paper considers the problem of packing cylinders and parallelepipeds into a given region so that the height of the occupied part of the region is minimal and the distances between each pair of items, and the distance between each packed item and the frontier of the region must be greater than or equal to given distances. A mathematical model of the problem is built and some characteristics of the mathematical model are investigated. Methods for fast construction of starting points, searching for local minima, and a special non-exhaustive search of local minima to obtain good approximations to a global minimum are offered. A numerical example is given. Runtimes to obtain starting points, local minima and approximations to a global minimum are adduced.     

A novel three-phase trajectory informed search methodology for global optimization

A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases. The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method.     

A quasi-multistart framework for global optimization of expensive functions using response surface models

We present the AQUARS (A QUAsi-multistart Response Surface) framework for finding the global minimum of a computationally expensive black-box function subject to bound constraints. In a traditional multistart approach, the local search method is blind to the trajectories of the previous local searches. Hence, the algorithm might find the same local minima even if the searches are initiated from points that are far apart. In contrast, AQUARS is a novel approach that locates the promising local minima of the objective function by performing local searches near the local minima of a response surface (RS) model of the objective function. It ignores neighborhoods of fully explored local minima of the RS model and it bounces between the best partially explored local minimum and the least explored local minimum of the RS model. We implement two AQUARS algorithms that use a radial basis function model and compare them with alternative global optimization methods on an 8-dimensional watershed model calibration problem and on 18 test problems. The alternatives include EGO, GLOBALm, MLMSRBF (Regis and Shoemaker in INFORMS J Comput 19(4):497–509, 2007), CGRBF-Restart (Regis and Shoemaker in J Global Optim 37(1):113–135 2007), and multi level single linkage (MLSL) coupled with two types of local solvers: SQP and Mesh Adaptive Direct Search (MADS) combined with kriging. The results show that the AQUARS methods generally use fewer function evaluations to identify the global minimum or to reach a target value compared to the alternatives. In particular, they are much better than EGO and MLSL coupled to MADS with kriging on the watershed calibration problem and on 15 of the test problems.     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

Global optimization by random perturbation of the gradient method with a fixed parameter

The paper deals with the global minimization of a differentiable cost function mapping a ball of a finite dimensional Euclidean space into an interval of real numbers. It is established that a suitable random perturbation of the gradient method with a fixed parameter generates a bounded minimizing sequence and leads to a global minimum: the perturbation avoids convergence to local minima. The stated results suggest an algorithm for the numerical approximation of global minima: experiments are performed for the problem of fitting a sum of exponentials to discrete data and to a nonlinear system involving about 5000 variables. The effect of the random perturbation is examined by comparison with the purely deterministic gradient method.     

Deterministic global optimization in isothermal reactor network synthesis

The reactor network synthesis problem involves the simultaneous determination of the structure and operating conditions of a reactor system to optimize a given performance measure. This performance measure may be the yield of a given product, the selectivity between products, or the overall profitability of the process. The problem is formulated as a nonlinear program (NLP) using a superstructure based method in which plug flow reactors (PFRs) in the structure are modeled using differential-algebraic equations (DAEs). This formulation exhibits multiple local minima. To overcome this, a novel deterministic global optimization method tailored to the special structure and characteristics of this problem will be presented. Examples of isothermal networks will be discussed to show the nature of the local minima and illustrate various components of the proposed approach.     

Interaction of faults under slip‐dependent friction. Non‐linear eigenvalue analysis

We analyse the evolution of a system of finite faults by considering the non‐linear eigenvalue problems associated to static and dynamic solutions on unbounded domains. We restrict our investigation to the first eigenvalue (Rayleigh quotient). We point out its physical significance through a stability analysis and we give an efficient numerical algorithm able to compute it together with the corresponding eigenfunction. We consider the anti‐plane shearing on a system of finite faults under a slip‐dependent friction in a linear elastic domain, not necessarily bounded. The static problem is formulated in terms of local minima of the energy functional. We introduce the non‐linear (static) eigenvalue problem and we prove the existence of a first eigenvalue/eigenfunction characterizing the isolated local minima. For the dynamic problem, we discuss the existence of solutions with an exponential growth, to deduce a (dynamic) non‐linear eigenvalue problem. We prove the existence of a first dynamic eigenvalue and we analyse its behaviour with respect to the friction parameter. We deduce a mixed finite element discretization of the non‐linear spectral problem and we give a numerical algorithm to approach the first eigenvalue/eigenfunction. Finally we give some numerical results which include convergence tests, on a single fault and a two‐faults system, and a comparison between the non‐linear spectral results and the time evolution results. Copyright © 2004 John Wiley & Sons, Ltd.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems

Satisfiability is a class of NP-complete problems that model a wide range of real-world applications. These problems are difficult to solve because they have many local minima in their search space, often trapping greedy search methods that utilize some form of descent. In this paper, we propose a new discrete Lagrange-multiplier-based global-search method (DLM) for solving satisfiability problems. We derive new approaches for applying Lagrangian methods in discrete space, we show that an equilibrium is reached when a feasible assignment to the original problem is found and present heuristic algorithms to look for equilibrium points. Our method and analysis provides a theoretical foundation and generalization of local search schemes that optimize the objective alone and penalty-based schemes that optimize the constraints alone. In contrast to local search methods that restart from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of a local minimum and move it in the direction provided by the Lagrange multipliers. In contrast to penalty-based schemes that rely only on the weights of violated constraints to escape from local minima, DLM also uses the value of an objective function (in this case the number of violated constraints) to provide further guidance. The dynamic shift in emphasis between the objective and the constraints, depending on their relative values, is the key of Lagrangian methods. One of the major advantages of DLM is that it has very few algorithmic parameters to be tuned by users. Besides the search procedure can be made deterministic and the results reproducible. We demonstrate our method by applying it to solve an extensive set of benchmark problems archived in DIMACS of Rutgers University. DLM often performs better than the best existing methods and can achieve an order-of-magnitude speed-up for some problems.     

Deterministic Global Optimization in Nonlinear Optimal Control Problems

The accurate solution of optimal control problems is crucial in many areas of engineering and applied science. For systems which are described by a nonlinear set of differential-algebraic equations, these problems have been shown to often contain multiple local minima. Methods exist which attempt to determine the global solution of these formulations. These algorithms are stochastic in nature and can still get trapped in local minima. There is currently no deterministic method which can solve, to global optimality, the nonlinear optimal control problem. In this paper a deterministic global optimization approach based on a branch and bound framework is introduced to address the nonlinear optimal control problem to global optimality. Only mild conditions on the differentiability of the dynamic system are required. The implementa-tion of the approach is discussed and computational studies are presented for four control problems which exhibit multiple local minima.     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

Packing unequal circles into a strip of minimal length with a jump algorithm

The paper considers a problem of packing unequal circles into a rectangular strip with fixed width and minimal length. We develop the idea of increasing the dimension of the solution space by assuming radii of circles to be variables. A mathematical model of the problem is constructed and its characteristics are investigated. Taking into account the characteristics we offer a solution strategy of the problem including a number of non-linear programming subproblems of packing circles of variable radii. The solution strategy involves special ways of construction of starting points, calculation of local minima, jump from one local extremum to another, decrease of the problem dimension and rearrangement of pairs of circles. For calculating local extrema an interior point optimizer together with the concept of active inequalities are used. We compare 146 numerical benchmark examples and give seven new ones for 125, 150, 175, 225, 250, 275 and 300 circles.     

Error estimates for the numerical approximation of Neumann control problems governed by a class of quasilinear elliptic equations

We study the numerical approximation of Neumann boundary optimal control problems governed by a class of quasilinear elliptic equations. The coefficients of the main part of the operator depend on the state function, as a consequence the state equation is not monotone. We prove that strict local minima of the control problem can be approximated uniformly by local minima of discrete control problems and we also get an estimate of the rate of this convergence. One of the main issues in this study is the error analysis of the discretization of the state and adjoint state equations. Some difficulties arise due to the lack of uniqueness of solution of the discrete equations. The theoretical results are illustrated by numerical tests.     

A Staged Continuous Tabu Search Algorithm for the Global Optimization and its Applications to the Design of Fiber Bragg Gratings

A novel staged continuous Tabu search (SCTS) algorithm is proposed for solving global optimization problems of multi-minima functions with multi-variables. The proposed method comprises three stages that are based on the continuous Tabu search (CTS) algorithm with different neighbor-search strategies, with each devoting to one task. The method searches for the global optimum thoroughly and efficiently over the space of solutions compared to a single process of CTS. The effectiveness of the proposed SCTS algorithm is evaluated using a set of benchmark multimodal functions whose global and local minima are known. The numerical test results obtained indicate that the proposed method is more efficient than an improved genetic algorithm published previously. The method is also applied to the optimization of fiber grating design for optical communication systems. Compared with two other well-known algorithms, namely, genetic algorithm (GA) and simulated annealing (SA), the proposed method performs better in the optimization of the fiber grating design.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

A global optimization algorithm using adaptive random search

A new random-search global optimization is described in which the variance of the step-size distribution is periodically optimized. By searching over a variance range of 8 to 10 decades, the algorithm finds the step-size distribution that yields the best local improvement in the criterion function. The variance search is then followed by a specified number of iterations of local random search where the step-size variance remains fixed. Periodic wide-range searches are introduced to ensure that the process does not stop at a local minimum. The sensitivity of the complete algorithm to various search parameters is investigated experimentally for a specific test problem. The ability of the method to locate global minima is illustrated by an example. The method also displays considerable problem independence, as demonstrated by two large and realistic example problems: (1) the identification of 25 parameters in a nonlinear model of a five-degrees-of-freedom mechanical dynamic system and (2) solution of a 24-parameter inverse problem required to identify a pulse train whose frequency spectrum matched a desired reference spectrum.     

Complexity of local search for the p-median problem

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0–1 local saddle points, and classical Karush–Kuhn–Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.     

An Infeasible Point Method for Minimizing the Lennard-Jones Potential

Minimizing the Lennard-Jones potential, the most-studied modelproblem for molecular conformation, is an unconstrained globaloptimization problem with a large number of local minima. In thispaper, the problem is reformulated as an equality constrainednonlinear programming problem with only linear constraints. Thisformulation allows the solution to approached through infeasibleconfigurations, increasing the basin of attraction of the globalsolution. In this way the likelihood of finding a global minimizeris increased. An algorithm for solving this nonlinear program isdiscussed, and results of numerical tests are presented.     

The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.