SOME RANDOMIZED ALGORITHMS FOR CONVEX QUADRATIC-PROGRAMMING

We adapt some randomized algorithms of Clarkson [3] for linear program ming to the framework of so-called LP-type problems, which was introdu ced by Sharir and Welzl [10]. This framework is quite general and allo ws a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function s ubject to convex quadratic constraints as a special case, for which th e algorithms can be implemented efficiently, if only linear constraint s are present. We show that the expected running times depend only lin early on the number of constraints, and illustrate this by some numeri cal results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in thi s paper to a given problem of that type is easy and efficient. Moreove r, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform mann er by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods.