Random projections map a set of points in a high dimensional space to a lower dimen- sional one while approximately preserving all pairwise Euclidean distances. While 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 show 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.
Citation
CNRS Ecole Polytechnique May 2019 (preliminary version published in IPCO Proceedings 2019).