3. Lower bound for the value of v(P



A new random projection method for Linear Programming


05000745 東京大学 ロウレンソ ブルノ フィゲラ LOURENC¸ O Bruno Figueira

01308490 東京大学/RIKEN-AIP 武田朗子 TAKEDA Akiko

1. Introduction

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 [3], 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 [1], 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 cx 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 random mmatrixT we define the following “projected” LP:


x∈Rn cx

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

v(P)−δ≤v(PT)≤v(P) holds.

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


x∈Rn cx

SAx Sb


PT (3)

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:

P(|X|> t)≤2et


K2 (4)

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)≤2eKt (5)



2019年 春季研究発表会


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 [2]). Let X be a set of n points in Rm and let G be a m random matrix whose rows are independent, mean zero, sub-gaussian and isotropic, then with probability 12 exp(−C02), we have that for all xi, xj ∈ X (1−ε)∥xi−xj2 1


(6) whereC0 is an universal constant.

Notice that this lemma implies that k=O(log(n)

ε2 )

3. Lower bound for the value of v(P



Let us consider the duals, Dof (1) andDT of (2):


y∈Rm by Ay = c

y 0




D (7)


y∈Rk bd(TD(y)T) Ad(TD(y)T) = c

y 0




DT (8)

LetyRm+ 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)Tis PSD by definition of y). We will now prove thatyT is almost feasible for (8).

Let us consider the modified dual problem:


y∈Rk bd(TD(y)T)

Ad(TD(y)T) = c+A(d(TD(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 bd(TD(yT)T) can be written as by+O(ε)

the vectorA(d(TD(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(ε).


[1] 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.

[2] R. Vershynin. High-dimensional probability, an in- troduction with applications in data science. 2018.

[3] K. Vu, P.-L. Poirion, and L. Liberti. Random pro- jections for linear programming. Mathematics of Operations Research, 2018.




関連した話題 :

Scan and read on 1LIB APP