#language-agnostic #mathematical-optimization #solver #linear-programming
#не зависит от языка #математическая оптимизация #решатель #линейное программирование
Вопрос:
Я хотел бы взглянуть на пару реализаций IPMS. Предпочтительными языками являются C / C , Java или любые языки сценариев, такие как python, perl. Другие тоже хороши.
Я ищу хороший ресурс, который может помочь мне с,
- основы методов оптимизации,
- основы метода внутренних точек и его отличия от других методов,
- типы IPM,
- алгоритмические детали и
- примеры реализаций.
Меня это интересует как часть моего проекта, где я бы использовал эти идеи / логику для решения системы линейных или квадратных уравнений.
Дайте мне знать, если у вас есть какая-либо информация о вышеупомянутых ресурсах.
Комментарии:
1. Что не так с simplex? Насколько я знаю, он по-прежнему решает линейные уравнения намного быстрее, чем любой IPM?
2. Симплекс также решает, но это требует времени, согласно книге Бойда по выпуклой оптимизации. Итак, на данный момент интересует IPM.
3. @willem, методы внутренней точки более эффективны, чем симплексный метод, для решения очень редких задач LP.
Ответ №1:
Другим решателем линейного программирования с внутренней точкой с открытым исходным кодом является GLPK, написанный на C: http://www.gnu.org/software/glpk / и http://en.wikibooks.org/wiki/GLPK
Книга Боба Вандербея » Линейное программирование » (http://www.princeton.edu /~rvdb /LPbook/) — хорошая книга для объяснения использования алгоритмов внутренней точки для квадратичного программирования. Упомянутый веб-сайт также содержит ссылки на программное обеспечение, но, похоже, это не программное обеспечение «коммерческого качества». У Vanderbei также есть LOQO, более мощный внутренний точечный код для квадратичного программирования (http://www.princeton.edu /~rvdb/ps/loqo5.pdf). Еще одна недавняя идея во внутренней точке qp заключается в следующем: http://www-personal.umich.edu /~murty/Grav-QP.pdf
Ответ №2:
Симплексные методы и методы внутренней точки имеют свое место. В целом ни один из них не лучше и не быстрее другого, и вы обнаружите, что каждый метод работает лучше в разных классах задач.
Что касается кодов, то монета с открытым исходным кодом или проект, Clp, имеет симплексные, Двойные симплексные и методы внутренней точки, реализованные на C .
Однако, если вы просто хотите решить систему линейных или квадратных уравнений вида f (x) = 0, то это совсем не то, что вы хотите. Если вы хотите использовать линейную систему, то вам нужно понимать прямые или итеративные линейные решатели. Если проблема нелинейная, вам следует обратиться к методу Ньютона или квази-ньютоновским методам.
желаю удачи.
Ответ №3:
Прежде всего, не сравнивайте симплексный метод и метод внутренней точки. У них разные подходы к решению проблемы. Симплексный метод используется для максимизации или минимизации функции, а метод внутренней точки используется для определения всех возможных точек внутри данной функции, которая удовлетворяет заданной функции с дельтой (очень малым значением) путем ее добавления или вычитания. Вы можете найти подробную информацию о них здесь [1]: http://www-personal.umich.edu /~murty/Grav-QP.pdf