Реализация «метода внутренних точек» для решения LP (и QP)

Question

Я хотел бы взглянуть на пару реализаций IPM. Предпочтительными языками являются C / C ++, Java или любые языки сценариев, такие как python, perl. Другие тоже в порядке.

Я ищу хороший ресурс, который может помочь мне,

1. основы методов оптимизации,
2. основы метода внутренних точек и его отличия от других методов,
3. типов IPM,
4. алгоритмические детали и
5. Пример реализации.

Меня интересует это как часть моего проекта, где я буду использовать эти идеи / логику для решения системы линейных или квадратичных уравнений.

Дайте мне знать, если у вас есть информация о вышеупомянутых ресурсах.

Answer 1

Другой решатель линейного программирования с открытым исходным кодом - GLPK, написанный на C: http://www.gnu.org/software/glpk/ а также http://en.wikibooks.org/wiki/GLPK

Книга линейного программирования Боба Вандербея (http://www.princeton.edu/~rvdb/LPbook/)) - хорошая книга для объяснения использования алгоритмов внутренних точек для квадратичного программирования. На цитируемом веб-сайте также есть ссылки на программное обеспечение, но, похоже, это не "коммерческое качество". "программное обеспечение. Вандербей также имеет LOQO, более промышленный код внутренней точки для квадратичного программирования (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Еще одна недавняя идея в области внутренней точки qp: http://www -personal.umich.edu / ~ murty / Grav-QP .pdf

Answer 2

Симплексные методы и методы внутренних точек имеют свое место. Один не лучше и не быстрее чем другие в целом, и вы обнаружите, что каждый метод работает лучше на разных классы задач.

Что касается кодов, проект Coin-OR с открытым исходным кодом, Clp имеет методы Simplex, Dual Simplex и Interior Point, реализованные в C ++.

Однако, если вы просто хотите решить систему линейных или квадратных уравнений форма f (x) = 0, тогда это совсем не то, что вы хотите. Если система, которую вы хотите линейный, то вам нужно понимать прямые или итеративные линейные решатели. Если проблема является нелинейным, вы должны посмотреть на метод Ньютона или квазиньютоновские методы.

удачи.