A RANDOMIZED SCHEME FOR SPEEDING-UP ALGORITHMS FOR LINEAR AND CONVEX-PROGRAMMING PROBLEMS WITH HIGH CONSTRAINTS-TO-VARIABLES RATIO

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems with n constraints, d variables, and input length L, if n = OMEGA(d2), the expected total number of major Karmarkar's iterations is O(d2(log n)L), compared to the best known deterministic bound of O(square-root n L). We also present several other results which follow from the general scheme.