Random projections for quadratic programs

• 成果类型: Article
• 署名作者: D'Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Vu, Ky
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; RIKEN; FPT University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01517-x
• 发表日期: 2020
• 页码: 619-647
• 关键词: algorithm

摘要

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 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 find good feasible solutions of very large instances.