Random projections for quadratic programs
| Autor: | Ky Khac Vu, Claudia D’Ambrosio, Leo Liberti, Pierre-Louis Poirion |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), RIKEN Center for Advanced Intelligence Project [Tokyo] (RIKEN AIP), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
General Mathematics Numerical analysis 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Space (mathematics) 01 natural sciences Set (abstract data type) Linear inequality Quadratic equation Euclidean geometry Applied mathematics Pairwise comparison Quadratic programming 0101 mathematics Software Mathematics |
| Zdroj: | Mathematical Programming Mathematical Programming, Springer Verlag, In press, 183, pp.619-647. ⟨10.1007/s10107-020-01517-x⟩ |
| ISSN: | 0025-5610 1436-4646 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink