Implementaciones de "Método de punto interior" para resolver LP (y QP)

Question

Me gustaría ver un par de implementaciones de IPM. Los idiomas preferibles son C/C++, Java o cualquier lenguaje de scripting como python, perl. Otros también están bien.

Estoy buscando un buen recurso que me puede ayudar con,

1. fundamentos de las técnicas de optimización,
2. fundamentos del Método de la temperatura interior y sus diferencias básico con las otras técnicas,
3. tipos de IPM,
4. detalles algorítmicos y
5. implementaciones de muestra.

Me interesa esto como parte de mi proyecto en el que utilizaría estas ideas/lógica para resolver un sistema de ecuaciones lineales o cuadráticas.

Deseo saber si tiene alguna información sobre los recursos anteriores.

Answer 1

Otro punto interior de código abierto solucionador de programación lineal se GLPK escrita en C: http://www.gnu.org/software/glpk/ y http://en.wikibooks.org/wiki/GLPK

El libro de programación lineal por Bob Vanderbei (http://www.princeton.edu/~rvdb/LPbook /) es un buen libro para explicar el uso de algoritmos de puntos interiores para la programación cuadrática. El sitio web citado también tiene enlaces a software, pero no parece ser un software de "calidad comercial". Vanderbei también tiene LOQO, un código de punto interior con mayor fortaleza industrial para programación cuadrática (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Otra idea reciente en el interior del punto qp es: http://www-personal.umich.edu/~murty/Grav-QP.pdf

Answer 2

Los métodos simples y los métodos de punto interior tienen su lugar. Uno no es mejor o más rápido que el otro en general y encontrará que cada método funciona mejor en diferentes clases de problemas .

En cuanto a los códigos, el proyecto Coin-OR de fuente abierta, Clp tiene métodos Simplex, Dual Simplex y Punto interior implementados en C++.

Sin embargo, si solo está buscando resolver un sistema de ecuaciones lineales o cuadráticas de la forma f (x) = 0, entonces esto no es lo que quiere en absoluto. Si el sistema que desea es lineal, entonces necesita comprender solucionadores lineales directos o iterativos. Si el problema no es lineal, debe considerar el método de Newton o los métodos cuasi-Newton.

lo mejor de la suerte.