Каковы различия между различными решателями квадратичного программирования R?

9

Я ищу пакет, который поможет мне решить некоторые задачи квадратичной оптимизации, и я вижу, что есть как минимум полдюжины различных пакетов. Согласно этой странице:

QP (квадратичное программирование, 90C20): cplexAPI , kernlab , limSolve , LowRankQP , quadprog , Rcplex , Rmosek

Некоторые из них (Rmosek и cplexAPI) зависят от других проприетарных пакетов, поэтому я не заинтересован в них.

Каковы заметные различия между другими пакетами QP?

Генри Хенринсон
источник
Вы смотрели на предоставленные справочные документы? Одна и та же процедура / алгоритм могут иметь разные реализации. Во всяком случае, можно решить проблему QP, используя методы внутренней точки , области доверия или активного набора .
usεr11852
1
Существует также пакет osqp - для разреженных систем это, безусловно, самая быстрая реализация, доступная в R сейчас ...
Том Венселерс

Ответы:

11
  • Cplex (cplexAPI, Rcplex): не является открытым исходным кодом (но существует годовая возобновляемая бесплатная академическая лицензия). Поддерживает разреженные матрицы. Был ли у меня оболочка для QP, пока я ее использовал. Остерегайтесь, что академическая лицензия не позволяет использовать ее на многих основных (скажем, через mclapply()).
  • ipop (тот, что в Kernlab) реализован в чистом R. Это делает его излишне медленным в больших приложениях. Не поддерживает разреженные матрицы.
  • limSolve не решает полноценные QP, только те, где ограничения имеют равенство типов. Не все проблемы QP могут быть сформулированы таким образом, но когда это возможно, они имеют явное решение. Не поддерживает разреженные матрицы.
  • LowRankQP: этот, по моему опыту, хороший (быстрый по сравнению с другими открытыми исходниками). Не поддерживает разреженные матрицы.
  • quadprog: базовая реализация решателя Goldfarb & Idnani Dual и Primal-Dual. Не поддерживает разреженные матрицы, но быстро работает для задач среднего размера.
  • Rmosek: никогда не пробовал.

Редактировать.

Поскольку я написал этот ответ, новый пакет ipoptr теперь доступен в R-forge. Этот пост R-blogger сравнивает его производительность на чистом QP с quadprog. Короче говоря, ipoptr поддерживает разреженные тройки матриц и имеет тенденцию быть намного быстрее, чем quadprod, когда матрицы проектирования разрежены. Однако, когда матрицы проектирования плотные, quadprog все равно оказывается значительно быстрее.

user603
источник
2
Мой опыт показывает, что quadprog все еще быстрее для небольших и средних задач, а ipoptr быстрее только тогда, когда проблема достаточно велика.
Нил Фульц
2
По этим темам недавно появилось множество постов в блогах. Смотрите, например, blog.ryanwalker.us/2015/02/...
Чандлер
1
Смотрите также blog.ryanwalker.us/2014/01/... и blog.ryanwalker.us/2015/03/...
Чандлер
1
Также отметим, что quadprog требует положительно определенных матриц в квадратичной форме.
ae0709
Существует также пакет osqp - для разреженных систем это, безусловно, самая быстрая реализация, доступная в R сейчас ...
Том Венселерс