Random Projections for Quadratic Programs over a Euclidean Ball

Ky Vu; Pierre Louis Poirion; Claudia D&#x2019;Ambrosio; Leo Liberti

doi:10.1007/978-3-030-17953-3_33

Random Projections for Quadratic Programs over a Euclidean Ball

Ky Vu
, Pierre Louis Poirion
, Claudia D’Ambrosio
, Leo Liberti

FPT University
RIKEN AIP
Laboratoire d'Informatique (LIX)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
Editors	Andrea Lodi, Viswanath Nagarajan
Publisher	Springer Verlag
Pages	442-452
Number of pages	11
ISBN (Print)	9783030179526
DOIs	https://doi.org/10.1007/978-3-030-17953-3_33
Publication status	Published - 1 Jan 2019
Event	20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States Duration: 22 May 2019 → 24 May 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11480 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Country/Territory	United States
City	Ann Arbor
Period	22/05/19 → 24/05/19

Access to Document

10.1007/978-3-030-17953-3_33

Cite this

Vu, K., Poirion, P. L., D’Ambrosio, C., & Liberti, L. (2019). Random Projections for Quadratic Programs over a Euclidean Ball. In A. Lodi, & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings (pp. 442-452). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17953-3_33

Vu, Ky ; Poirion, Pierre Louis ; D’Ambrosio, Claudia et al. / Random Projections for Quadratic Programs over a Euclidean Ball. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. editor / Andrea Lodi ; Viswanath Nagarajan. Springer Verlag, 2019. pp. 442-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bd236c9e97f74c708b150c49c53c70a0,

title = "Random Projections for Quadratic Programs over a Euclidean Ball",

abstract = "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.",

author = "Ky Vu and Poirion, \{Pierre Louis\} and Claudia D\&\#x2019;Ambrosio and Leo Liberti",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 ; Conference date: 22-05-2019 Through 24-05-2019",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-17953-3\_33",

language = "English",

isbn = "9783030179526",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "442--452",

editor = "Andrea Lodi and Viswanath Nagarajan",

booktitle = "Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings",

}

Vu, K, Poirion, PL, D’Ambrosio, C & Liberti, L 2019, Random Projections for Quadratic Programs over a Euclidean Ball. in A Lodi & V Nagarajan (eds), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480 LNCS, Springer Verlag, pp. 442-452, 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, United States, 22/05/19. https://doi.org/10.1007/978-3-030-17953-3_33

Random Projections for Quadratic Programs over a Euclidean Ball. / Vu, Ky; Poirion, Pierre Louis; D’Ambrosio, Claudia et al.
Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. ed. / Andrea Lodi; Viswanath Nagarajan. Springer Verlag, 2019. p. 442-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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 -

Vu K, Poirion PL, D’Ambrosio C, Liberti L. Random Projections for Quadratic Programs over a Euclidean Ball. In Lodi A, Nagarajan V, editors, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Springer Verlag. 2019. p. 442-452. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17953-3_33

Random Projections for Quadratic Programs over a Euclidean Ball

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this