We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimizationproblems. The scheme can be used to speed up existing algorithms on problems which have many mor...
详细信息
We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimizationproblems. 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.
暂无评论