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 … Read more
Random projections are random linear maps, sampled from appropriate distributions, that approximately preserve certain geometrical invariants so that the approximation improves as the dimension of the space grows. The well-known Johnson-Lindenstrauss lemma states that there are \LL{random matrices with surprisingly few rows} that approximately preserve pairwise Euclidean distances among a set of points. This is … Read more
The trust region method is an algorithm traditionally used in the field of derivative free optimization. The method works by iteratively constructing surrogate models (often linear or quadratic functions) to approximate the true objective function inside some neighborhood of a current iterate. The neighborhood is called “trust region” in the sense that the model is … Read more
We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this … Read more