Random projections for quadratic programs
Random projections for quadratic programs
复制标题
二次规划的随机投影
DOI：
10.1007/s10107-020-01517-x
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
K. Vu
中科院分区：
文献类型：
--
作者：
C. D’Ambrosio;L. Liberti;Pierre;K. Vu
随机投影将高维空间中的一组点映射到低维空间，同时近似保持所有成对的欧氏距离。虽然随机预测通常适用于数值数据，我们在本文中表明，它们可以成功地应用于二次规划公式在一组线性不等式约束。而不是解决高维的原始问题，我们更有效地解决投影问题。这就产生了原问题的一个可行解。我们证明了这个可行解的上下界。原问题的最优目标函数值。然后，我们讨论了随机生成的实例，以及一个变体的Markowitz的投资组合问题的一些计算结果。事实证明，我们的方法可以找到很好的可行解非常大的情况。
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.