A new random projection method for Linear Programming
RIKEN-AIP *POIRION Pierre-Louis
05000745 東京大学 ロウレンソ ブルノ フィゲラ LOURENC¸ O Bruno Figueira
01308490 東京大学/RIKEN-AIP 武田朗子 TAKEDA Akiko
In this paper we propose a new random projec- tion method that allows to reduce the number of in- equalities of a Linear Program (LP). More precisely, we randomly aggregate the constraints of a LP into a new one with much fewer constraints, while pre- serving, approximatively, the optimal value of the LP.
This extends the work in , where the authors con- sidered an LP with equality constraints and proved that we can build a new LP, whose optimal value approximate the original one, with much fewer con- straints by randomly aggregating them using a ma- trix of independent and identically distributed (iid) random variables. The main tool, of the above pa- per, is the Johnson-Lindenstrauss Lemma , which states that a set of high-dimensional points can be projected to a much lower dimensional one, while pre- serving, approximatively, the Euclidean distance be- tween these points. The extension, to the inequality case, proposed in this paper is non-trivial as we need to consider random matrix with sub-exponential (and not sub-gaussian) entries, which forbid the use of the Johnson-Lindenstrauss Lemma directly.
In the whole paper we consider a random projection matrixT ∈Rk×m such thatT = √1
kGwhere G is a random matrix whose entriesgijare independent ran- dom variables normally distributed.
Let us consider the following bounded LP:
x∈Rn c⊤x A x ≥ b
P (1) where c ∈ Rn, b ∈ Rm and A ∈ Rm×n and let us denote byv(P) the value of the objective at an optimal solution (that we assume finite). Given a randomk× mmatrixT we define the following “projected” LP:
d(T D(A x−b)T⊤) ≥ 0
PT (2) where D(·) :Rp7→Rp×p maps a vector to a diagonal matrix and where d(·) :Rp×p7→Rp returns the diag- onal of a matrix.
Notice that for any feasible solutionxofP the matrix T D(A x−b)T⊤ is PSD hence its diagonal is a non- negative vector of Rk which implies that any feasible solution of P is also a feasible solution of PT, hence we deduce that v(PT)≤v(P).
Hence the aim of this paper is to prove that we can findδ >0 such that
LetS∈Rk×mbe the random matrix whose entries are the square of the entries ofT, i.e. Sij =Tij2. We can prove that (2) is equivalent to
SAx ≥ Sb
2. Random projections
In this section we recall some facts about concen- tration inequalities.
定義 1. Let X be a zero mean random variable such that there exists K >0 such that for allt >0:
ThenX is said to be sub-gaussian. The sub-gaussian norm, ∥X∥ψ2, of X is defined to be the smallest K satisfying (4).
定義 2. Let X be a zero mean random variable such that there exists K >0 such that for allt >0:
P(|X|> t)≤2e−Kt (5)
Then X is said to be sub-exponential. The sub- exponential norm, ∥X∥ψ1, of X is defined to be the smallest K satisfying(5).
Sub-gaussian and sub-exponential random variables are closely related, as we can see any sub-gaussian ran- dom variable is also sub-exponential, furthermore, it turns out that the product of two sub-gaussian ran- dom variables is sub-exponential.
We now recall the famous Johnson-Lindenstrauss lemma.
Lemma 2.1(Johnson-Lindentrauss Lemma ). Let X be a set of n points in Rm and let G be a k× m random matrix whose rows are independent, mean zero, sub-gaussian and isotropic, then with probability 1−2 exp(−C0kε2), we have that for all xi, xj ∈ X (1−ε)∥xi−xj∥2≤ 1
(6) whereC0 is an universal constant.
Notice that this lemma implies that k=O(log(n)
3. Lower bound for the value of v(PT
Let us consider the duals, Dof (1) andDT of (2):
y∈Rm b⊤y A⊤y = c
y ≥ 0
y∈Rk b⊤d(T⊤D(y)T) A⊤d(T⊤D(y)T) = c
y ≥ 0
Lety∗∈Rm+ be an optimal solution of (7), we con- sider the following “approximated” projected solution:
yT =d(T D(y∗)T⊤)∈Rk
Notice thatyT ≥0 (asT D(y∗)T⊤is PSD by definition of y∗). We will now prove thatyT is almost feasible for (8).
Let us consider the modified dual problem:
A⊤d(T⊤D(y)T) = c+A⊤(d(T⊤D(yT)T)−y∗) y ≥ 0
(9) ObviouslyyT is a feasible solution of the above LP.
In order to obtain a lower bound for v(PT) we prove the following:
• the value b⊤d(T⊤D(yT)T) can be written as b⊤y∗+O(ε)
• the vectorA⊤(d(T⊤D(yT)T)−y∗) can be written as O(ε)1(where1is the all-ones vector)
Then considering the dual of the modified dual problem we obtain a lower boundv(P)−δforv(PT) where δ=O(ε).
 W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In G. Hedlund, editor,Conference in Modern Analy- sis and Probability, volume 26 of Contemporary Mathematics, pages 189–206, Providence, 1984.
American Mathematical Society.
 R. Vershynin. High-dimensional probability, an in- troduction with applications in data science. 2018.
 K. Vu, P.-L. Poirion, and L. Liberti. Random pro- jections for linear programming. Mathematics of Operations Research, 2018.