TY - GEN
T1 - Random Projections for Quadratic Programs over a Euclidean Ball
AU - Vu, Ky
AU - Poirion, Pierre Louis
AU - D’Ambrosio, Claudia
AU - Liberti, Leo
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Random projections are used as dimensional reduction techniques in many situations. They project a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Usually, random projections are applied to numerical data. In this paper, however, we present a successful application of random projections to quadratic programming problems subject to polyhedral and a Euclidean ball constraint. We derive approximate feasibility and optimality results for the lower dimensional problem. We then show the practical usefulness of this idea on many random instances, as well as on two portfolio optimization instances with over 25M nonzeros in the (quadratic) risk term.
AB - Random projections are used as dimensional reduction techniques in many situations. They project a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Usually, random projections are applied to numerical data. In this paper, however, we present a successful application of random projections to quadratic programming problems subject to polyhedral and a Euclidean ball constraint. We derive approximate feasibility and optimality results for the lower dimensional problem. We then show the practical usefulness of this idea on many random instances, as well as on two portfolio optimization instances with over 25M nonzeros in the (quadratic) risk term.
U2 - 10.1007/978-3-030-17953-3_33
DO - 10.1007/978-3-030-17953-3_33
M3 - Conference contribution
AN - SCOPUS:85065874423
SN - 9783030179526
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 442
EP - 452
BT - Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
A2 - Lodi, Andrea
A2 - Nagarajan, Viswanath
PB - Springer Verlag
T2 - 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Y2 - 22 May 2019 through 24 May 2019
ER -