Global optimization: Algorithms, complexity, and applications

Global optimization problems appear in many diverse areas of operations research, management science, economics and engineering. Typical applications include allocation and location problems, economies of scale, transportation problems, engineering design and control chip design and database problems. Standard nonlinear optimization methods will usually obtain a local solution or a stationary point when applied to a global optimization problem. The problem of designing algorithms that compute global solutions is in general very difficult because of the lack of criteria in deciding whether a local solution is global or not. Moreover, nonlinear problems may have an exponential number of local solutions, which are not global. Active research in the past two decades has produced many deterministic and stochastic methods for computing global solutions. In this talk, we will focus on deterministic methods which include branch and bound algorithms, homotopy methods, path following techniques, interval analysis methods, and a variety of approximate techniques. In addition, we are going to discuss related complexity questions and implementation issues regarding many of the proposed algorithms.