Random projections for quadratic programs

Claudia d'Ambrosio (1) , Leo Liberti (1) , Pierre-Louis Poirion (2) , Ky Vu

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 RIKEN AIP - RIKEN Center for Advanced Intelligence Project [Tokyo]

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 in this paper that 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. This yields a feasible solution of the original problem. We then prove lower and upper bounds of this feasible solution w.r.t. the optimal objective function value of the original problem. We then discuss some computational results on randomly generated instances, as well as a variant of Markowitz' portfolio problem. It turns out that our method can finds good feasible solutions of excessively large instances.

Domaines: Recherche opérationnelle [math.OC]

Claudia d'Ambrosio, Leo Liberti, Pierre-Louis Poirion, Ky Vu. Random projections for quadratic programs. Mathematical Programming, In press, 183, pp.619-647. ⟨10.1007/s10107-020-01517-x⟩. ⟨hal-02869240⟩