Complexity Issues in Global Optimization: A Survey

Complexity theory refers to the asymptotic analysis of problems and algorithms. How efficient is an algorithm for a particular optimization problem, as the number of variables gets large? Are there problems for which no efficient algorithm exists? These are the questions that complexity theory attempts to address. The theory originated in work by Hartmanis and Stearns (1965). By now there is much known about complexity issues in nonlinear optimization. In particular, our recent book Vavasis (1991) contains all the details on many of the results surveyed in this chapter. We begin the discussion with a look at convex problems in the next section. These problems generally have efficient algorithms. In Section 3 we study the complexity of two nonconvex problems that also have efficient algorithms because of special structure. In Section 4, we look into hardness results (proofs of the nonexistence of efficient algorithms) for general nonconvex problems. Finally, in Section 5 we look at recent developments in "approximation" algorithms. We follow the notation in this chapter that lower-case boldface letters are vectors, lower-case italic letters are scalars, and upper-case italic letters are sets or matrices. Superscript T indicates matrix transpose, and aTx indicates inner product. The operators 'less than' and 'greater than' are applied component- wise to vectors; we say x is greater than y if each entry of x is greater than or equal to the corresponding entry of y