Skip to main content


eCommons@Cornell

eCommons@Cornell >
Faculty of Computing and Information Science >
Center for Advance Computing >
Cornell Theory Center Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/5489
Title: Complexity Issues in Global Optimization: A Survey
Authors: Vavasis, Stephen A.
Keywords: theory center
Issue Date: Jan-1993
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.tc/93-117
Abstract: 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.
URI: http://hdl.handle.net/1813/5489
Appears in Collections:Cornell Theory Center Technical Reports

Files in This Item:

File Description SizeFormat
93-117.pdf186.67 kBAdobe PDFView/Open
93-117.ps142.08 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us