Implementations of the "interior point method" for solving LP (and QP)

Question

I would like to take a look at a couple of IPM implementations. Preferred languages ​​are C / C ++, Java, or any scripting languages ​​such as python, perl. Others are also beautiful.

I’m looking for a good resource that can help me,

• basics of optimization methods,
• the basics of the interior point method and its differences from other methods,
• IPM types
• algorithmic details and
• implementation examples.

I am interested in this as part of my project, where I will use these ideas / logic to solve a system of linear or quadratic equations.

Let me know if you have information about these resources.

Answer 1

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

Bob Vanderbei's Linear Programming Book (http://www.princeton.edu/~rvdb/LPbook/) is a good book to explain the use of internal point algorithms for quadratic programming. The cited website also has links to software, but it does not appear to be "commercial quality" software. Vanderbei also has LOQO, a more industrial internal code for square programming (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Another recent idea at the qp inner point: http://www-personal.umich.edu/~murty/Grav-QP.pdf

Answer 2

Simplex methods and internal point methods take place. One is not better or faster than in general, and you will find that each method works better on different classes of problems.

In terms of codes, the open-source Coin-OR project, Clp has Simplex, Dual Simplex, and internal point methods implemented in C ++.

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

Good luck.