COPOSITIVITY AND THE MINIMIZATION OF QUADRATIC-FUNCTIONS WITH NONNEGATIVITY AND QUADRATIC EQUALITY CONSTRAINTS

The problem of finding the minimum value of a quadratic function on a set defined by nonnegativity and quadratic equality constraints is ana lyzed. The difficulty in finding the solution to this problem is prima rily due to the fact that the feasible region is nonconvex. An algorit hm that requires the Hessian of the quadratic constraint function be s trictly copositive is developed for finding the minimal value of the q uadratic objective function. The problem of finding this global minima can be mapped into the problem of determining whether or not a partic ular matrix is copositive. This result is equivalent to earlier result s characterizing the solutions to a large class of fractional programm ing problems. A more efficient algorithm for finding solutions that sa tisfy the Kuhn-Tucker necessary conditions is developed, and its conve rgence behavior is analyzed. This algorithm requires that the Hessians of the quadratic constraint and objective functions be both positive semidefinite and strictly copositive.