Optimization Online


Random projections for linear programming

Ky Vu(vukhacky***at***gmail.com)
Pierre-Louis Poirion(kiwisensei***at***gmail.com)
Leo Liberti(liberti***at***lix.polytechnique.fr)

Abstract: 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 commonly used to speed up algorithms based on Euclidean distances. We prove that these matrices also preserve other quantities, such as the distance to a cone. We exploit this result to devise a probabilistic algorithm to solve linear programs approximately. We show that this algorithm can approximately solve very large randomly generated LP instances. We also showcase its application to an error correction coding problem.

Keywords: Johnson-Lindenstrauss lemma, concentration of measure, dimension reduction

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 06/08/2017
Entry Accepted: 06/08/2017
Entry Last Modified: 06/08/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society