Polynomial Linear Programming with Gaussian Belief Propagation

Details Polynomial Linear Programming with Gaussian Belief Propagation Polynomial Linear Programming with Gaussian Belief Propagation

2008-10-09

arxiv.org/abs/0810.1631v1

The 46th Annual Allerton Conference on Communication, Control and Computing, Allerton House, Illinois, Sept. 2008

Computer Science

Information Theory

7 pages, 1 figure, appeared in the 46th Annual Allerton Conference on Communication, Control and Computing, Allerton House, Il

Scientific paper

10.1109/ALLERTON.2008.4797652

Interior-point methods are state-of-the-art algorithms for solving linear programming (LP) problems with polynomial complexity. Specifically, the Karmarkar algorithm typically solves LP problems in time O(n^{3.5}), where $n$ is the number of unknown variables. Karmarkar's celebrated algorithm is known to be an instance of the log-barrier method using the Newton iteration. The main computational overhead of this method is in inverting the Hessian matrix of the Newton iteration. In this contribution, we propose the application of the Gaussian belief propagation (GaBP) algorithm as part of an efficient and distributed LP solver that exploits the sparse and symmetric structure of the Hessian matrix and avoids the need for direct matrix inversion. This approach shifts the computation from realm of linear algebra to that of probabilistic inference on graphical models, thus applying GaBP as an efficient inference engine. Our construction is general and can be used for any interior-point algorithm which uses the Newton method, including non-linear program solvers.

Affiliated with

Also associated with

No associations

Rating

Polynomial Linear Programming with Gaussian Belief Propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial Linear Programming with Gaussian Belief Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Linear Programming with Gaussian Belief Propagation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460832