Random projections of linear and semidefinite problems with linear inequalities
Random projections of linear and semidefinite problems with linear inequalities
复制标题
具有线性不等式的线性和半定问题的随机投影
DOI：
10.1016/j.laa.2023.01.013
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Takeda Akiko
中科院分区：
文献类型：
--
作者：
Poirion Pierre-Louis;Lourenco Bruno F.;Takeda Akiko
Johnson-Lindenstrauss引理指出，存在线性映射，它将向量空间中的一组点投影到低维空间中，使得这些点之间的欧几里德距离近似保持不变。这个引理以前被用来证明我们可以使用一个随机矩阵来随机地聚集线性规划(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.
登录
查看更多内容
DOI：
10.1287/moor.2016.0793
发表时间：
2017-02
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Mirjam Dür;Bolor Jargalsaikhan;G. Still
通讯作者：
Mirjam Dür;Bolor Jargalsaikhan;G. Still
影响因子：
2.7
作者：
C. D’Ambrosio;L. Liberti;Pierre;K. Vu
通讯作者：
K. Vu
随机数值线性代数中的行列式点过程
DOI：
10.1090/noti2202
发表时间：
2020
期刊：
ArXiv
影响因子：
--
作者：
Michal Derezinski;Michael W. Mahoney
通讯作者：
Michael W. Mahoney
影响因子：
1.7
作者：
K. Vu;Pierre;Leo Liberti
通讯作者：
Leo Liberti
通过草图对 SDP 进行降维
影响因子：
1.1
作者：
Andreas Bluhm;Daniel Stilck França
通讯作者：
Daniel Stilck França