Implementions of "Interior Point Method" to solve LP (and QP)

Question

I would like to look at a couple of implementations of IPMs. The languages preferable are C/C++, Java or any scripting languages like python, perl. Others are also fine.

I am searching for a good resource which can help me with,

1. basics of optimization techniques,
2. basics of Interior Point Method and its basics differences with the other techniques,
3. types of IPMs,
4. algorithmic details, and
5. sample implementations.

I am interested in this as part of my project where I would be using these ideas/logic to solve a sys of linear or quadratic equations.

Let me know if you have any info about the above resources.

Jacobs

What is wrong with simplex? As far as I know, it still solves linear equations much faster that any IPM? – Sheldon

Simplex also solves, but it takes time according to Boyd's Convex Optimization Book. So, interested in IPM as of now. – Jacobs

@willem, interior point methods are more efficient than simplex method for solving very sparse LP problems. – Bull

Answer 1

Another open source interior point linear programming solver is GLPK written in C: http://www.gnu.org/software/glpk/ and http://en.wikibooks.org/wiki/GLPK

The linear programming book by Bob Vanderbei (http://www.princeton.edu/~rvdb/LPbook/) is a good book for explaining the use of interior point algorithms for quadratic programming. The cited website also has links to software, but it doesn't seem to be "commercial quality" software. Vanderbei also has LOQO, a more industrial strength interior point code for quadratic programming (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Another recent idea in interior point qp is: http://www-personal.umich.edu/~murty/Grav-QP.pdf

Bedew

Answer 2

Simplex methods and interior point methods both have their place. One is not better or faster than the other in general and you will find that each method performs better on different classes of problems.

As for codes, the open source Coin-OR project, Clp has Simplex, Dual Simplex, and Interior Point methods implemented in C++.

However, if you are just looking to solve a system of linear or quadratic equations of the form f(x) = 0, then this is not what you want at all. If the system you want is linear, then you need to understand direct or iterative linear solvers. If the problem is nonlinear, you should look into Newton's method or quasi-Newton methods.

best of luck.

Soapwort

Answer 3

First of all, don't compare the simplex method and the interior point method. They have different approaches to solve the problem. The simplex method is used to maximize or minimize the function and the interior point method is used to determine all possible points within the given function which satisfies the set function with delta(very small value) by adding or subtracting it. You can find detailed information regarding them here [1]: http://www-personal.umich.edu/~murty/Grav-QP.pdf

Farfamed