Leo Liberti, CNRS and Ecole Polytechnique

Abstract

Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. We also show how to retrieve a feasible solution of the original problem from the lower-dimensional solution of the projected problem. We then show that the retrieved solution can be used to bound the optimal objective function value of the original problem from below and above, and prove that the lower and upper bounds are not too far apart. We then discuss a set of computational results on randomly generated instances, as well as a variant of Markowitz’ portfolio problem.

Joint work with C. D'Ambrosio, P.-L. Poirion, K. Vu