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/7022
Title: Proving Polynomial-Time for Sphere-Constrained Quadratic Programming
Authors: Vavasis, Stephen A.
Zippel, Richard
Keywords: computer science
technical report
Issue Date: Dec-1990
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1182
Abstract: Recently Ye and Karmarkar have proposed similar algorithms for minimizing a nonconvex quadratic function on a sphere. These algorithms are based on trust-region work going back to Levenberg and Marquardt. Although both authors state that their algorithm is polynomial time, neither makes estimates necessary to prove that conclusion in a formal sense. In this report we derive estimates for the convergence of the algorithm. Our estimates are based on bounds for separation of roots of polynomials. These bounds prove that the underlying decision problem is polynomial time in the Turing machine sense.
URI: http://hdl.handle.net/1813/7022
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1182.pdf2.26 MBAdobe PDFView/Open
90-1182.ps459.37 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us