Optimization Online


Random projections for quadratic programs

Claudia D'Ambrosio(dambrosio***at***lix.polytechnique.fr)
Leo Liberti(liberti***at***lix.polytechnique.fr)
Pierre-Louis Poirion(kiwisensei***at***gmail.com)
Ky Vu(vukhacky***at***gmail.com)

Abstract: 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.

Keywords: nonlinear programming, polynomial optimization, large-scale optimization, approximation, Johnson-Lindenstrauss Lemma

Category 1: Nonlinear Optimization (Quadratic Programming )

Citation: CNRS Ecole Polytechnique May 2019 (preliminary version published in IPCO Proceedings 2019).

Download: [PDF]

Entry Submitted: 07/31/2019
Entry Accepted: 07/31/2019
Entry Last Modified: 07/31/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society