论文标题
线性不平等的线性和半决赛问题的随机投影
Random projection of Linear and Semidefinite problem with linear inequalities
论文作者
论文摘要
Johnson-Lindenstrauss Lemma指出，存在线性图，该线性图将矢量空间的一组点投射到一个尺寸较低的空间中，以便将这些点之间的欧几里得距离近似保留。此引理先前已被用来证明我们可以使用随机矩阵，其条目是从零均值的亚高斯分布中绘制的随机矩阵，即线性程序的平等约束（LP），同时保留了问题的值。在本文中，我们将这些结果扩展到不等式案例中，通过引入具有非负条目的随机矩阵，该矩阵允许随机汇总LP的不等式约束，同时保留问题的值。通过二元性，我们提出的方法允许减少问题的数量和问题的维度，同时在最佳价值上获得一些理论保证。我们还将将结果扩展到某些半决赛编程实例。
The Johnson-Lindenstrauss Lemma states that there exist linear maps that project a set of points of a vector space into a space of much lower dimension such that the Euclidean distance between these points is approximately preserved. This lemma has been previously used to prove that we can randomly aggregate, using a random matrix whose entries are drawn from a zero-mean sub-Gaussian distribution, the equality constraints of an Linear Program (LP) while preserving approximately the value of the problem. In this paper we extend these results to the inequality case by introducing a random matrix with non-negative entries that allows to randomly aggregate inequality constraints of an LP while preserving approximately the value of the problem. By duality, the approach we propose allows to reduce both the number of constraints and the dimension of the problem while obtaining some theoretical guarantees on the optimal value. We will also show an extension of our results to certain semidefinite programming instances.
