Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6972
Title: Black-box complexity of local minimization
Authors: Vavasis, Stephen A.
Keywords: computer science
technical report
Issue Date: Jun-1990
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1132
Abstract: We study the complexity of local minimization in the black-box model, that is, the model in which the objective function and possibly its gradient are available as external subroutines. This is the model used, for example, in all the optimization algorithms in the 1983 book by Dennis and Schnabel. Our first main result is that the complexity grows polynomially with the number of variables n, in contrast to other related black-box problems (global minimization, Brouwer fixed points) for which the worst case complexity is exponential in n. Our second contribution is the construction of a family of functions that are bad cases for all possible black-box local optimization algorithms.
URI: http://hdl.handle.net/1813/6972
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1132.pdf2.35 MBAdobe PDFView/Open
90-1132.ps721.79 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us