Apa perbedaan antara berbagai pemecah pemrograman kuadratik R?

9

Saya mencari paket untuk membantu saya memecahkan beberapa masalah optimasi kuadratik dan saya melihat setidaknya ada setengah lusin paket yang berbeda. Menurut halaman ini :

QP (Quadratic programming, 90C20): cplexAPI , kernlab , limSolve , LowRankQP , quadprog , Rcplex , Rmosek

Beberapa di antaranya (Rmosek dan cplexAPI) bergantung pada paket eksklusif lainnya, jadi saya tidak tertarik dengan itu.

Apa perbedaan penting antara paket QP lainnya?

Henry Henrinson
sumber
Sudahkah Anda melihat kertas referensi yang diberikan? Prosedur / algoritma yang sama dapat memiliki implementasi yang berbeda. Jika ada yang bisa memecahkan masalah QP menggunakan metode interior-point , wilayah-kepercayaan atau aktif-set .
usεr11852
1
Ada juga paket osqp - untuk sistem yang jarang, ini adalah implementasi tercepat yang tersedia di R sekarang ...
Tom Wenseleers

Jawaban:

11
  • Cplex (cplexAPI, Rcplex): bukan open source (tetapi ada lisensi akademik gratis tahunan yang dapat diperbarui). Ini mendukung matriks jarang. Adalah pembungkus goto saya untuk QP ketika saya menggunakannya. Ketahuilah bahwa lisensi akademik tidak memungkinkan untuk menggunakannya pada banyak core (katakanlah sampai selesai mclapply()).
  • ipop (yang ada di kernlab) diimplementasikan dalam R. murni yang membuatnya tidak perlu lambat dalam aplikasi besar. Tidak mendukung matriks yang jarang.
  • limSolve tidak menyelesaikan QP lengkap, hanya mereka yang kendala jenis kesetaraannya. Tidak semua masalah QP dapat dibingkai dengan cara ini, tetapi ketika kemudian bisa, mereka memiliki solusi eksplisit. Tidak mendukung matriks yang jarang.
  • LowRankQP: yang ini menurut pengalaman saya bagus (cepat dibandingkan dengan yang open source lainnya). Tidak mendukung matriks yang jarang.
  • quadprog: implementasi dasar dari pemecah Goldfarb & Idnani Dual dan Primal-Dual. Tidak mendukung matriks jarang tetapi tenang cepat untuk masalah berukuran sedang.
  • Rmosek: tidak pernah mencoba.

Edit.

Karena saya menulis jawaban ini, paket baru, ipoptr sekarang tersedia di R-forge. Ini pasca R-blogger membandingkan kinerja pada QP murni dengan quadprog. Singkatnya, ipoptr mendukung triplet matriks jarang dan cenderung jauh lebih cepat daripada quadprod ketika matriks desain jarang. Namun ketika matriks desain padat, quadprog tampaknya masih jauh lebih cepat.

pengguna603
sumber
2
Pengalaman saya adalah bahwa quadprog masih lebih cepat untuk masalah kecil-menengah, dan ipoptr lebih cepat hanya ketika masalahnya cukup besar.
Neal Fultz
2
Ada serangkaian posting blog terbaru tentang topik ini. Lihat, misalnya, blog.ryanwalker.us/2015/02/...
chandler
1
Perhatikan juga bahwa quadprog membutuhkan matriks pasti positif dalam bentuk kuadratik.
ae0709
Ada juga paket osqp - untuk sistem yang jarang, ini adalah implementasi tercepat yang tersedia di R sekarang ...
Tom Wenseleers