Proving Polynomial-Time for Sphere-Constrained Quadratic Programming

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.