A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
Determining the cells of an arrangement of hyperplanes is a classical problem in combinatorial geometry. In this paper we present an efficient recursive procedure to solveit. In fact, by considering a connection between the latter problem and optimality conditions of unconstrained quadratic optimization problems in the following form: ( Q P ) min { x t Q x ? x ? { ? 1 , 1 } n } , with Q?Rnn Q ? R n  n , we can show the proposed algorithm solves problems of the form (QP) ( Q P ) in polynomial time when the rank of the matrix Q Q is fixed and the number of its positive diagonal entries is O(log(n)) O ( log ( n ) ) .
arrangements unconstrained quadratic programming complexity