Global optimization

The optimization community has long been interested in solving multiextremal optimization problems to global optimality. Some of the first exact approaches to nonconvex nonlinear programs (NLPs) and mixed-integer nonlinear programs (MINLPs) relied on convexification via cutting planes 23, as well as branch-and-bound, i.e. bounding combined with progressive partitioning of the space of continuous, in addition to integer, variables 9. Approximations based on the a priori discretization of nonlinear functions were also proposed and capitalized on the availability of fast linear integer programming techniques 3. Activities in the field of global optimization started to intensify in the early 1990s, when the Journal of Global Optimization was launched. Today, the global optimization community has grown considerably, as evidenced by flourishing publications and conference activities in this area. The book by Horst and Tuy 11, an indispensable resource for anyone working in this area, has received over 1200 citations (according to Google Scholar as of 17 June 2009). At the same time, the 20th International Symposium on Mathematical Programming (Chicago, 2009) is scheduled to include 20 sessions in its global optimization cluster, with many additional related sessions in its MINLP cluster. Clearly, global optimization has grown into an area of major focus in the field of mathematical programming over the past two decades.

The purpose of this special issue is to showcase current research activities in the area of global optimization. The papers of this issue reflect the broad range of activities in this area and address deterministic as well as stochastic algorithms, the development of software and computational experience with a variety of algorithms, and a number of applications in engineering and science. Corresponding to these three thematic areas, the papers have been grouped into three parts.

Part 1 – Theory and algorithms

In the first part, there are five papers that present and analyse, mostly theoretically, a variety of algorithms and methodologies:

•	Contrary to the widespread practice of building relaxations of nonconvex problems by outer approximating one term of a nonconvex constraint at a time, Bao et al. 2 investigate relaxations that consider multiple terms simultaneously.
•	Lundell and Westerlund 17 propose underestimation strategies for signomial functions, which are sums of products of powers and arise often in the engineering literature. The relaxations proposed in this paper follow a power or exponential transformation of the signomialfunctions.
•	Burer and Chen 5 use a p-cone program to inject an initial linear relaxation of a 0–1 integer program to a higher dimension. Projection to the original space gives rise to a relaxation that is tighter than the original one. Applied repeatedly, this method asymptotically provides the convex hull of the original problem. Furthermore, it generalizes and subsumes existing methods, including the Lovász–Schrijver construction 16 for ∞, while p=2 enjoys better iteration complexity.
•	The eigenvalue complementarity problem is addressed in 12 for the case where at least one of the defining matrices is asymmetric. Several structural results are obtained and a branch-and-bound global optimization algorithm is developed for this problem.
•	Wang et al. 26 generalize the sampling distribution of a Monte Carlo random search algorithm. A parameterization of the sampling step is introduced and bounds on the probability of improvement at each iteration are obtained theoretically and studied computationally.

Part 2 – Computations and software

In the second part, there are nine papers, all of which are associated with a specific global optimization software. Until very recently, BARON 21 was the only widely available software that offered a deterministic guarantee of global optimality for NLPs and MINLPs. This issue includes papers describing four alternatives to BARON:

•	Like BARON, the solver Couenne 4 and the global solver in the LINDO API 15 implement branch-and-bound algorithms. Couenne is a free solver. Unlike BARON and Couenne, which require an LP solver to solve relaxations, the LINDO solver requires an NLP solver for this purpose.
•	While BARON, Couenne, and the LINDO solver are implemented in floating point arithmetic, GlobSol 13 and ICOS 14 rely on interval arithmetic to guarantee the correctness of the results. Both apply branch-and-bound principle.

Interval arithmetic techniques are also the basis of the GloptLab solver developed by Domes 8 for quadratic constraint satisfaction problems and the global solver developed by Pál and Csendes 20 for bound-constrained global optimization problems. The GloptiPoly 3 solver developed by Didier et al. 7 relies on semidefinite programming techniques and solves the generalized problem of moments, an infinite-dimensional optimization problem that subsumes the problem of global optimization over polynomials. In addition to the above deterministic solvers, two papers of the special issue implement and study the computational performance of stochastic global search software:

•	Ugray et al. 24 describe the MSNLP global solver, which implements a multi-start global optimization algorithm that relies on dynamic filters and randomized drivers.
•	Vaz and Vicente 25 present PSwarm, a hybrid particle swarm algorithm for linearly constrained global derivative-free optimization.

All papers in this part come with extensive computational experimentation. For instance, Belotti et al. 4 present and analyse several existing and new branching rules, for which they present extensive computational experience.

Part 3 – Modelling and applications

There are five papers in this part:

•	In addition to the commonplace piecewise linear approximations of nonlinear functions, Natali and Pinto 19 consider low-order piecewise polynomial approximations. Mixed-integer linear programming formulations are developed for finding the best locations of a predetermined number of piecewise approximators and extensive computations are presented for problems from MINLPLib.
•	Anjos and Yen 1 address the global optimization of one-dimensional facility layouts. Through a new semidefinite programming relaxation, the authors are able to solve problems with up to 100 facilities, a problem size that is outside the reach of earlier approaches.
•	Cassioli et al. 6 present computational experience with basin-hopping algorithms to find the structure of atomic clusters under the binary Lennard-Jones potential, a problem that has been extensively studied in the past. The authors report 95 improved solutions for problems from the Cambridge Cluster Database.
•	McAllister and Floudas 18 develop bounding techniques to reduce the search space for protein conformation problems. The authors’ strategy provides sharper bounds on backbone di\-hedral angles and alpha-Carbon distances, thus significantly enhancing the predictive ability of structure prediction algorithms.
•	Henderson and Smith 10 present an application of the reformulation-linearization technique 22 to solve a difficult nonconvex parameter estimation optimization problem that arises in the design of electronic chip packages.

Acknowledgements

All the papers of this issue went through a rigorous review process. In most cases, papers went through two and, in certain cases, three review rounds. This would not have been possible without the hard work of referees, whose contribution is acknowledged here with gratitude. Finally, many thanks to Oleg Burdakov, who invited me to put this special issue together, handled the review process of Bao et al. 2, and oversaw the publication of this volume in all its details.