Implémentation de "Interior Point Method" pour résoudre LP (et QP)

Question

Je voudrais examiner quelques implémentations d'IPM. Les langages préférables sont C/C++, Java ou n'importe quel langage de script comme python, perl. D'autres sont aussi bien.

Je suis à la recherche d'une bonne ressource qui peut me aider,

1. bases de techniques d'optimisation,
2. bases de l'intérieur Méthode du point et de ses bases différences avec les autres techniques,
3. types de IPM,
4. détails algorithmiques, et
5. exemples d'implémentations.

Je suis intéressé par cela dans le cadre de mon projet où j'utiliserais ces idées/logique pour résoudre un système d'équations linéaires ou quadratiques. Faites-moi savoir si vous avez des informations sur les ressources ci-dessus.

Answer 1

Un autre point intérieur open source solveur de programmation linéaire est GLPK écrit en C: http://www.gnu.org/software/glpk/ et http://en.wikibooks.org/wiki/GLPK

Le livre de programmation linéaire par Bob Vanderbei (http://www.princeton.edu/~rvdb/LPbook /) est un bon livre pour expliquer l'utilisation des algorithmes de points intérieurs pour la programmation quadratique. Le site Web cité a également des liens vers des logiciels, mais il ne semble pas être un logiciel de "qualité commerciale". Vanderbei a également LOQO, un code de point intérieur de force industrielle plus pour la programmation quadratique (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Une autre idée récente dans qp point intérieur est: http://www-personal.umich.edu/~murty/Grav-QP.pdf

Answer 2

Les méthodes simplex et les méthodes de points intérieurs ont toutes deux leur place. L'un n'est pas meilleur ou plus rapide que l'autre en général et vous constaterez que chaque méthode fonctionne mieux sur différentes classes de problèmes . En ce qui concerne les codes, le projet OR-Coin open source, Clp a des méthodes Simplex, Dual Simplex et Interior Point implémentées en C++. Cependant, si vous cherchez simplement à résoudre un système d'équations linéaires ou quadratiques de la forme f (x) = 0, alors ce n'est pas ce que vous voulez du tout. Si le système que vous voulez est linéaire, alors vous devez comprendre les solveurs linéaires directs ou itératifs. Si le problème est non linéaire, vous devriez vous pencher sur la méthode de Newton ou les méthodes de quasi-Newton.

bonne chance.