JavaScript is disabled for your browser. Some features of this site may not work without it.
Proving Polynomial-Time for Sphere-Constrained Quadratic Programming

Author
Vavasis, Stephen A.; Zippel, Richard
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.
Date Issued
1990-12Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1182
Type
technical report