State of the Art in Global Optimization

A Lagrangian duality theory is formulated for a large class of nonconvex optimization problems. The theoiy is based on the recent characterizations of global and local optima for partly convex programs. It uses basic notions from convex and parametric programming, such as the minimal index set of active constraints and continuity of the feasible set point-to-set mapping. The results are applied to the classic navigation problem of Zermelo. The primal problem consists of finding a steering angle that minimizes the sailing time to a target. Its dual solution is a function that associates, with every steering angle, the sensitivity of the sailing time relative to small perturbations of the target. The unconstrained minima of the dual solution yield the most “robust” steering angles.

We propose a new numerical method for finding the global minimum of a real-valued function defined on a d-dimensional box. Our method is based only on function values at the hyperbolic cross points and uses an adaptive order of these points. We motivate our method by complexity results and also give numerical examples.

Two types of new finite branch and bound algorithms are proposed for global minimization of a separable concave function under linear constraints with a totally unimodular matrix and additional box constraints. The key idea for establishing these algorithms is based upon the fact that the underlying problem can be viewed as an integer global optimization problem. For the case that a fixed number of the components of the objective function is nonlinear, an upper bound for the running time is given, which is polynomial in the data of the box constraints.

The concepts of robustness of sets and functions were proposed for the theory of integral global optimization. A robust minimizer of a nonlinear minimization problem can be approximated by a sequence of points at which the objective function is continuous. In this paper, we discuss the existence of robust minimizers. With the integral global optimality conditions, we extend the Palais-Smale condition to establish the existence results of robust minimizers for nonlinear programs whose objective function may be discontinuous.

In this paper, we study a branch and bound algorithm for the quadratic assignment problem (QAP) that uses a lower bound based on the linear programming (LP) relaxation of a classical integer programming formulation of the QAP. We report on computational experience with the branch and bound algorithm on all QAP test problems of dimension n ≤ 15 of QAPLIB, a standard library of QAP test problems. The linear programming relaxations are solved with an implementation of an interior point algorithm that uses a preconditioned conjugate gradient algorithm to compute directions. The branch and bound algorithm is compared with a similar branch and bound algorithm that uses the Gilmore-Lawler lower bound (GLB) instead of the LP-based bound. The LP-based algorithm examines a small portion of the nodes explored by the GLB-based algorithm. Extensions to the implementation are discussed.

This paper concerns the use of linear programming based methods for the exact solution of the Quadratic Assignment Problem (QAP). The primary obstacles facing such an approach are the large size of the formulation resulting from the linearization of the quadratic objective function and the poor quality of the lower bounds. Special purpose linear programming methods using dynamic matrix factorization provide a promising avenue for solving these large scale linear programs (LP). This enables a large portion of the LP basis to be represented implicitly and generated from the remaining explicit part. Computational results demonstrating the strength of this approach are also presented. For this approach to be effective in the solution of QAPs, dynamic matrix factorization should be combined with formulations that yield superior lower bounds. Lifting techniques have been theoretically proven to improve bound strength at the cost of a dramatic increase in formulation size. A formulation including third order interactions is derived using this methodology. However, degeneracy poses a significant problem in the solution of these linear programs. Incorporation of third order interaction costs in the objective function is proposed as a possible way to mitigate problems due to stalling. Computational results indicate that this formulation yields much stronger lower bounds than the currently best known lower bounds. Unifying these various observations, it is suggested that the development of specialized dual simplex algorithms using dynamic matrix factorization can provide a promising approach to overcome these barriers.

We introduce in this paper some conical coercivity conditions, which are applied to the study of the global minimum on a convex cone in an infinite dimensional Banach space

We consider the problem of maximizing a quadratic function on the set { −1, l}n. This problem is related to some graph partitioning problems. We propose a path following method to compute an upper bound to the previous maximization problem. Numerical implementation of the proposed method and related numerical experience are presented.

The coupling of process estimation and controller design has proved to be a natural way to proceed with the control of engineering systems. In adaptive control, well-known and efficient algorithms have been developed for linear systems. However, it has been observed that when the estimation problem is poorly conditioned, the process becomes unstable, at least locally. In control experiments, this is manifested as a “bursting” phenomenon where both the inputs and outputs have huge oscillations. Several authors have suggested coupling the estimation and controller design problem and solving it as a single nonlinear program. This problem is nonconvex and typically consists of a convex objective with bilinear equations. In this paper, we develop a global branch and bound optimization algorithm that follows the prototype of Horst [6] and exploits the NLP structure to address the stability problem. In addition to an exposition of the algorithm as well as development of stability and convergence results, the approach is applied to a small example in order to demonstrate how bursting has been eliminated.

The paper presents a decomposition based global optimization approach to bilevel linear and quadratic programming problems. By replacing the inner problem by its corresponding KKT optimality conditions, the problem is transformed to a single yet non-convex, due to the complementarity condition, mathematical program. Based on the primal-dual global optimization approach of Floudas and Visweswaran (1990, 1993), the problem is decomposed into a series of primal and relaxed-dual subproblems whose solutions provide lower and upper bounds to the global optimum. By further exploiting the special structure of the bilevel problem, new properties are established which enable the efficient implementation of the proposed algorithm. Computational results are reported for both linear and quadratic example problems.

The TRUST methodology addresses the unconstrained global optimization problem in terms of the evolution of a novel deterministic nonlinear dynamical system, which combines the concepts of subenergy tunneling and non-Lipschitzian “terminal” repellers. In this paper, the TRUST algorithms are generalized by extending the formalism to lower semicontinuous objective functions, and by allowing gradient-directed tunneling with componentwise flow direction reversal at the boundaries of the parameter domain. Known limitations of the methodology are summarized, and the reduction of a multi-dimensional problem to a one-dimensional case (e.g., via hyperspiral embedding) is discussed with regards to a formal convergence proof. Benchmark results are presented, which demonstrate that TRUST is substantially faster than previously published global optimization techniques.

Various techniques have been proposed for incorporating constraints in interval branch and bound algorithms for global optimization. However, few reports of practical experience with these techniques have appeared to date. Such experimental results appear here. The underlying implementation includes use of an approximate optimizer combined with a careful tesselation process and rigorous verification of feasibility. The experiments include comparison of methods of handling bound constraints and comparison of two methods for normalizing Lagrange multipliers. Selected test problems from the Floudas / Pardalos monograph are used, as well as selected unconstrained test problems appearing in reports of interval branch and bound methods for unconstrained global optimization.

The envelope used by the algorithm of Breiman and Cutler [4] can be smoothed to create a better algorithm. This is equivalent to an accelerated algorithm developed by the third author and Cutler in [3] which uses apparently poor envelopes. Explaining this anomaly lead to a general result concerning the equivalence of methods which use information from more than one point at each stage and those that only use the most recent evaluated point. Smoothing is appropriate for many algorithms, and we show it is an optimal strategy.

Global optimization methods based on interval arithmetic have potential to efficiently solve problems that standard nonlinear programming techniques cannot handle well. In interval arithmetic the machine arithmetic is performed by approximating a real number with an enclosing interval, rather than with a single floating point number. Hence, an automatic control over rounding errors is provided. To use interval arithmetic in practice either a language with built-in interval arithmetic or a suitable subroutine library is needed. Such a library can with advantage be implemented in C++, realizing intervals as objects with well defined interfaces. In this paper we report experience from implementing and using a C++ class library for global optimization using interval arithmetic. Measurements show that the use of object oriented programming and operator overloading does not affect performance negatively. In fact, our C++ implementation of interval arithmetic is actually faster than a comparable Fortran implementation.

Localisation Search, a generalisation of Pure Adaptive Search, is a stochastic global optimisation algorithm in which iterates are chosen randomly from a superset, or localisation, of the improving region. Recent theoretical results are applied to determine how closely the localisation must track the improving region in order that the number of function evaluations to convergence increases at most polynomially with dimension, for Lipschitz objective functions and uniformly bounded domains.

A major concern of adaptive IIR filter is that with the objective function being non- convex, currently used gradient methods have a tendency to converge to the local minimum. The stochastic approximation with convolution smoothing represents a simple approach for deriving a global optimization algorithm for adaptive filtering. This stochastic approximation method has been derived for adaptive system identification. Optimization is based on minimizing the mean square error objective function. The mean square error is a function of time series data that is statistically varying. An experimental result demonstrates the viability of using stochastic approximation for adaptive filtering.

An important class of difficult optimization problems are grouping problems, where the aim is to group together members of a set (i.e. find a good partition of the set). In this paper we present the Grouping Genetic Algorithm (GGA), which is a Genetic Algorithm (GA) heavily modified to suit the structure of grouping problems. We first show why both the standard and the ordering GAs fare poorly in this domain, by pointing out their inherent difficulty to capture the regularities of the functional landscape of the grouping problems. We then propose a new encoding scheme and genetic operators adapted to these problems, embodied by the GGA. An experimental evaluation of the GGA on several different problems shows its superiority over standard GAs when applied to grouping problems. The potential of the algorithm is further illustrated by its application to the Bin Packing Problem, where a hybridised GGA outperforms one of the best Operations Research techniques to date.

We consider methods for finding global solutions to quadratically constrained programs. We present a branch-and-bound algorithm which solves a sequence of linear programs, each of which approximates the original problem over a hyperrectangular region. Tightening the bounds produces arbitrarily tight approximations as the volume of the hyperrectangle decreases. Computational experiments are given which relate the efficiency of the algorithm to the input parameters. In order to reduce the amount of work necessary to isolate global solutions within a small region, local optimization techniques are embedded within the branch-and-bound scheme. In particular, the use of the interval Newton method applied to the KKT system is discussed and shown to be computationally beneficial. Extensions are considered which allow the branch-and- bound algorithm to process more general nonlinear functions than quadratic.

Recent advances in the theory of deterministic global optimization have resulted in the development of very efficient algorithmic procedures for identifying the global minimum of certain classes of nonconvex optimization problems. The advent of powerful multiprocessor machines combined with such developments make it possible to tackle with substantial efficiency otherwise intractable global optimization problems. In this paper, we will discuss implementation issues and computational results associated with the distributed implementation of the decomposition-based global optimization algorithm, GOP, [5], [6]. The NP-complete character of the global optimization problem, translated into extremely high computational requirements, had made it difficult to address problems of large size.The parallel implementation made it possible to successfully tackle the increased computational requirements in in order to identify the global minimum in computationally realistic times. The key computational bottlnecks are identified and properly addressed. Finaly, results on an Intel-Paragon machine are presented for large scale Indefinite Quadratic Programming problems, with up to 350 quadratic variables, and Blending-Pooling Problems, with up to 12 components and 30 qualities.

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches nonlinear programming to be explored. This paper proposes a new finite algorithm for solving this problem. In addition to providing a proof of finiteness, the paper discusses a new way of designing branch-and-bound algorithms for concave programming that ensures finiteness. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 concave variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC.

While the picture of approximation complexity class becomes clear for most combinatorial optimization problems, it remains an open question whether Feedback Vertex Set can be approximated within a constant ratio in directed graph case. In this paper we present an approximation algorithm with performance bound L _max −1, where L _max is the largest length of essential cycles in the graph G(V,E). The worst case bound is $$\left\lfloor {\sqrt {{{\left| V \right|}^2} - \left| V \right| - \left| E \right| + 1} } \right\rfloor $$ which, in general, is inferior to Seymour’s recent result [14], but becomes a small constant for some graphs. Furthermore, we prove the so-called pseudo ∈-approximate property, i.e. FVS can be divided into a class of disjoint NP -complete subproblems, and our heuristic becomes ∈-approximate for each one of these subproblems.

In topographical global optimization a sample of points that super-uniformly cover the region of interest, A, is used in combination with the function evaluations f(x) in these points to obtain a topographical graph of/on A from which candidate points are easily extracted for local minimizations. This paper discusses some of the problems in obtaining such a cover and presents some solutions. These solutions are based on an iterative use of the topographical method. Several iterations of the topographical algorithm are run and the information gathered is collected into a single graph. Using multiple iterations speeds up the sampling process and also allows using the topographical method for constrained problems.

This paper addresses the problem of minimizing the Gibbs free energy in the n _c -component, multi-phase chemical and phase equilibrium problem involving different thermodynamic models. The algorithmic approach used is based on the tangent-plane criterion of Gibbs: the global optimization problem considered, which involves a search space of n(n + 1) dimensions, is reduced to a finite sequence of global optimization steps in n-space, and local optimization steps in nK-space, K ≤ n + 1.We describe an algorithm performing the global optimization step involved in this lower-dimensional search space using techniques from interval analysis. We report good numerical results on instances of the Gibbs free energy minimization problem.

New results are presented for solving the well-known nonlinear programming problem: Minimize F= ∑ f_i(x_i) subject to ∑ x_i=r and x_i ≥ 0; which has been studied over the past thirty years in numerous application areas. Whereas current solution methods are restricted to convex f_i(x_i), the new results allow the functions f_i(x_i) to be nonconvex and multimodal with any number of maxima and minima over [0, X]. Necessary conditions for the local minima of F(x₁, x₂,… x_n) are derived. The necessary conditions for local minima are used to determine a superset M of the set of all local minima. Minimization of the objective function F over M leads to the global minimum. The results are used to solve examples which no other analytical criteria can solve.

In this paper, we present a d.c. approach for solving the largest empty sphere problem, i.e., given m points Ph ∈ Rn and a polytope maxmin $$\mathop {\max }\limits_{x \in D} \min \left\{ {\left\| {x - {p_h}} \right\|\left| {h = 1, \ldots ,m} \right.} \right\}.$$. We reduce the problem to a global optimizational problem. Employing the special structure of this problem, our algorithm, which utilizes a combination of branch-and-bound and outer-inner-approximation, finds an optimal solution within finitely many iterations under a mild assumption.

We show that many important location problems (Weber’s problem with attraction and repulsion, constrained multisource and multifacility problems,…) can be formulated as d.c. optimization problems in low-dimensional spaces and thereby can be solved practically by recently developed d.c. optimization techniques. Two typical algorithms are described in detail.

The main purpose of this paper is to demonstrate that even a very minimal cooperation between multiple processors (each executing the same general purpose probabilistic global optimization algorithm) can significantly improve the computational efficiency as compared to executing the algorithm without cooperation. We describe one such cooperative general purpose algorithm for global optimization and its implementation on a parallel computer. The algorithm, called Parallel Constrained Biased Random Search (PCBRS), can be classified as a probabilistic random search method. It needs just one user supplied parameter which is related to the accuracy of the solution. Comparisons to several algorithms using the Dixon-Szegö test functions are presented. PCBRS has been implemented on a multiprocessor system and on a distributed system of workstations following a Multiple Instruction Multiple Data model. Its parallel performance is evaluated using an eight-dimensional pattern classification problem. Our results make apparent that the PCBRS algorithm is computationally efficient for large problems and especially for functions with many local minima. It is shown that the cooperative work of several processors ensures an efficient solution to the global optimization problem.

In the field of computer vision, computer scientists extract knowledge from an image by manipulating it through image transforms. In the mathematical language of image algebra an image transformation often corresponds to an image-template product. When performing this operation on a computer, savings in time and memory as well as a better fit to the specific computer architecture can often be achieved by using the technique of template decomposition. In this paper we use global optimization techniques to solve a general problem of morphological template decomposition.

The objective of this paper is to demonstrate a methodology whereby reductions of greenhouse gas emissions can be allocated on a regional level with minimal deviation from the “business as usual emission scenario”. The methodology developed employs a two stage optimization process utilizing techniques of mathematical programming. The stage one process solves a world emission reduction problem producing an optimal emission reduction strategy for the world by maximizing an economic utility function. Stage two addresses a regional emission reduction allocation problem via the solution of an auxiliary optimization problem minimizing disruption from the above business as usual emission strategies. Our analysis demonstrates that optimal CO₂ emission reduction strategies are very sensitive to the targets placed on CO₂ concentrations, in every region of the world. It is hoped that the optimization analysis will help decision-makers narrow their debate to realistic environmental targets.

We consider visualization as a decision optimization tool in problems where the model and/or the objectives are not well defined. We investigate four specific problems representing different degrees of determination. The first problem concerns a smooth dynamic representation of data collected at fixed locations. In the example we want to minimize the deviations from a desired temperature over space and time. The second and third problems are the dynamic representation of observations in the form of averages over regions in space and time, and they are exemplified by epidemiological data. We are looking for spatial-temporal patterns that can suggest the most efficient ways of prevention and control. The fourth problem may be referred to as visual indexing. We perform exploratory analysis of a large collection of complex objects. The example is a dynamic index to a collection of 30,000 images. We search for the“most interesting” subsets of images via visual inspection of the index. In all cases we define appropriate techniques for the visual representation. We describe the software and hardware.

A general framework for handling a wide range of short-term scheduling problems arising in multiproduct/multi-purpose batch chemical plants is presented. Time events arising in the schedule are modeled directly and thus the use of binary variables over periods during which no changes in system state occur is avoided. The problem is formulated as a mixed integer nonlinear program (MINLP). The Bayesian Heuristic (BH) approach is used to implement a global optimization algorithm which effectively solves the resulting model. Computational comparisons using two test examples are made against a UDM (uniform discretization model) formulation. The results suggest that the BH approach combined with the nonuniform time discretization formulation shows promise for the solution of batch scheduling problems.

Nonconvexity in nonlinear and quadratic programming is studied in the context of a full space successive quadratic programming (SQP) method with analytical second derivatives. It is shown that nonconvexity can lead to indefinite quadratic programs and multiple Kuhn-Tucker points in both the quadratic and nonlinear programs. It is also shown that some quadratic programming solutions are not descent directions for the parent SQP method and can lead to increased computational work or failure in the nonlinear programming calculations. A simple heuristic-based methodology is proposed to improve the chances of calculating a descent direction for the nonlinear programming algorithm. The associated algorithmic logic is based on pruning and mirroring. Several chemical process optimization problems are used to show that the proposed methodology is useful in calculating descent directions from indefinite quadratic programs and often results in convergence to the desired nonlinear programming solution in a reliable and efficient manner.

Many systems in chemical engineering are difficult to optimize using gradient-based algorithms. These include process models with multimodal objective functions and discontinuities. Herein, a stochastic algorithm is applied for the optimal design of a fermentation process, to determine multiphase equilibria, for the optimal control of a penicillin reactor, for the optimal control of a non-differentiable system, and for the optimization of a catalyst blend in a tubular reactor. The advantages of the algorithm for the efficient and reliable location of global optima are examined. The properties of these algorithms, as applied to chemical processes, are considered, with emphasis on the ease of handling constraints and the ease of implementation and interpretation of results. For the five processes, the efficiency of computation is improved compared with selected stochastic and deterministic algorithms. Results closer to the global optimum are reported for the optimal control of the penicillin reactor and the non-differentiable system.

In this paper the MINLP problem for the optimal synthesis of process networks is modeled as a discrete optimization problem involving logic disjunctions with nonlinear equations and pure logic relations. The logic disjunctions allow the conditional modeling of equations. The outer approximation algorithm is used as a basis to derive a logic-based OA solution method which naturally gives rise to NLP subproblems that avoid zero flows and a disjunctive LP master problem. The NLP subproblems are selected through a set covering problem for which we consider both the cases of disjunctive and conjunctive normal form logic. The master problem, on the other hand, is converted to mixed-integer form using a convex-hull representation. Furthermore, based on some interesting relations of outer-approximation with Generalized Benders Decomposition it is also shown that it is possible to derive a logic-based method for the latter algorithm. The performance of the proposed algorithms illustrated with two process network problems.

Process network synthesis (PNS) has enormous practical impact; however, its mixed integer programming (MIP) model is tedious to solve because it usually involves a large number of binary variables. The present work elucidates the recently proposed accelerated branch-and- bound algorithm that exploits the unique feature of the MIP model of PNS. Implementation of the algorithm is based on the so-called decision-mapping that consistently organizes the system of complex decisions. The accelerated branch-and-bound algorithm of PNS reduces both the number and size of the partial problems. The efficacy of the algorithm is demonstrated with a realistic example.

The use of discrete programming techniques for the synthesis of process flowsheets in chemical engineering is a well established approach. Recently, improvements in the basic algorithms have been made to deal with the generation of complete processes, including heat exchange networks and processes with reactors, absorbers, flash units, etc. This paper describes a new approach to the use of dynamic programming using string encodings both for subproblem definition and for solution description. These encodings, combined with the use of dynamic hash tables, are used to implement a dynamic programming based optimization algorithm for the synthesis of chemical processes. The implementation shows an increase in both efficiency and usefulness.