Optimization Online


Fast approximate solution of large dense linear programs

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

Abstract: We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this idea works in practice by showcasing its effect on the quantile regression problem, where the state-of-the-art CPLEX solver fails on large or poorly scaled datasets.

Keywords: Johnson-Lindenstrauss lemma, quantile regression

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

Category 2: Applications -- Science and Engineering (Statistics )


Download: [PDF]

Entry Submitted: 11/21/2016
Entry Accepted: 11/22/2016
Entry Last Modified: 11/21/2016

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