proxsuite

ProxSuite adalah kumpulan pemecah numerik open-source, kuat secara numerik, tepat, dan efisien (misalnya, LPS, QPS, dll.) Yang berakar pada algoritma proksimal primal-ganda yang ditinjau kembali. Melalui ProxSuite , kami bertujuan untuk menawarkan pengoptimal yang dapat diskalakan komunitas yang menangani masalah yang padat, jarang, atau bebas matriks. Sementara aplikasi yang ditargetkan pertama adalah robotika, ProxSuite dapat digunakan dalam konteks lain tanpa batas.

ProxSuite secara aktif dikembangkan dan didukung oleh kelompok riset Willow dan Sierra, tim peneliti bersama antara Inria, École Normale Supérieure de Paris dan Center National de la Recherche Scientifique yang terlokalisasi di Prancis.

ProxSuite sudah terintegrasi ke dalam:

• Bahasa pemodelan cvxpy untuk masalah optimasi cembung,
• Kerangka kerja simbolis Casadi untuk optimasi numerik secara umum dan kontrol optimal. ProxQP tersedia di Casadi sebagai plugin untuk menyelesaikan program kuadratik,
• TSID: Perangkat lunak robot untuk dinamika terbalik robot yang efisien dengan kontak dan berdasarkan Pinocchio.

Kami siap untuk mengintegrasikan ProxSuite dalam ekosistem optimasi lainnya.

Fitur Utama ProxSuite

ProxSuite cepat:

• Perpustakaan Template C ++,
• ramah cache.

ProxSuite serba guna, menawarkan melalui algoritma lanjutan API terpadu yang berspesialisasi untuk mengeksploitasi struktur masalah secara efisien:

• Padat, jarang, dan matriks faktorisasi matriks backends,
• Opsi pemulangan hangat canggih (misalnya, tebakan awal yang dibatasi kesetaraan, opsi pemulangan hangat atau cold-start dari hasil sebelumnya),

dengan fitur khusus untuk

• Menangani kendala kotak yang lebih efisien, program linier, QP dengan Hessian diagonal, atau dengan kendala yang jauh lebih banyak daripada variabel primal,
• Memecahkan qps nonconvex,
• Memecahkan batch QP secara paralel,
• Memecahkan QP yang paling layak didekat jika QP tampaknya tidak layak,
• membedakan QPS yang layak dan tidak layak.

ProxSuite fleksibel:

• HANYA tajuk,
• C ++ 14/17/20 sesuai,
• Binding Python dan Julia untuk prototipe kode mudah tanpa mengorbankan kinerja.

ProxSuite dapat diperluas. ProxSuite dapat diandalkan dan diuji secara luas, menunjukkan kinerja terbaik pada masalah literatur yang paling sulit. ProxSuite didukung dan diuji pada Windows, Mac OS X, UNIX, dan Linux.

Dokumentasi

Dokumentasi ProxSuite online dari rilis terakhir tersedia di sini.

Memulai

ProxSuite didistribusikan ke banyak manajer paket terkenal.

Instalasi cepat dengan:

   pip install proxsuite

Pendekatan ini tersedia di Linux, Windows dan Mac OS X.

Instalasi cepat dengan:

   conda install proxsuite -c conda-forge

Pendekatan ini tersedia di Linux, Windows dan Mac OS X.

Instalasi cepat dengan:

   brew install proxsuite

Pendekatan ini tersedia di Linux dan Mac OS X.

Pendekatan alternatif

Instalasi dari sumber disajikan di sini.

Mengkompilasi Program Contoh Pertama

Untuk kinerja tercepat, gunakan perintah berikut untuk mengaktifkan vektorisasi saat menyusun contoh sederhana.

g++ -O3 -march=native -DNDEBUG -std=gnu++17 -DPROXSUITE_VECTORIZE examples/first_example_dense.cpp -o first_example_dense $( pkg-config --cflags proxsuite )

Menggunakan ProxSuite dengan CMake

Jika Anda ingin menggunakan ProxSuite dengan CMake, contoh kecil berikut ini akan membantu Anda:

 cmake_minimum_required ( VERSION 3.10)

project (Example CXX)
find_package (proxsuite REQUIRED)
set (CMAKE_CXX_STANDARD 17) # set(CMAKE_CXX_STANDARD 14) will work too

add_executable (example example.cpp)
target_link_libraries (example PUBLIC proxsuite::proxsuite)

# Vectorization support via SIMDE and activated by the compilation options '-march=native' or `-mavx2 -mavx512f`
add_executable (example_with_full_vectorization_support example.cpp)
target_link_libraries (example_with_full_vectorization_support PUBLIC proxsuite::proxsuite-vectorized)
target_compile_options (example_with_full_vectorization_support PUBLIC "-march=native" )

Jika Anda telah menyusun ProxSuite dengan dukungan vektorisasi, Anda mungkin juga menggunakan CMAKE Target proxsuite::proxsuite-vectorized untuk juga terhubung dengan SIMDE. Jangan lupa menggunakan -march=native untuk mendapatkan kinerja terbaik.

ProxQP

Algoritma ProxQP adalah pendekatan optimasi numerik untuk menyelesaikan masalah pemrograman kuadratik dari bentuk:

$$ begin {align} min_ {x} & ~ frac {1} {2} x^{t} hx+g^{t} x \ text {st} & ~ a x = b & ~ l leq c x leq u end end {align

Di mana $ x di mathbb {r}^n $ adalah variabel optimasi. Fungsi objektif didefinisikan oleh matriks semidefinit positif $ H di mathcal {s}^n _+$ dan vektor $ g di mathbb {r}^n $ . Kendala linier didefinisikan oleh matriks kesetaraan-kontra $ A in mathbb {r}^{n_ text {eq} kali n} $ dan matriks ketimpangan-konservasi $ C in mathbb {r}^{n_ text {in} kali n} $ dan vektor $ b in mathbb {r}^{n_ text {eq}} $ , $ l in mathbb {r}^{n_ text {in}} $ Dan $ u in mathbb {r}^{n_ text {in}} $ sehingga $ b_i di mathbb {r}, ~ forall i = 1, ..., n_ text {eq} $ Dan $ l_i di mathbb {r} cup { - infty} $ Dan $ u_i in mathbb {r} cup { + infty}, ~ forall i = 1, ..., n_ text {in} $ .

Mengutip ProxQP

Jika Anda menggunakan ProxQP untuk pekerjaan Anda, kami mendorong Anda untuk mengutip kertas terkait.

Tolok ukur numerik

Tolok ukur numerik ProxQP terhadap pemecah komersial dan open-source lainnya tersedia di sini.

Untuk program kuadrat cembung padat dengan ketimpangan dan kendala kesetaraan, ketika meminta akurasi yang relatif tinggi (misalnya, 1E-6), seseorang memperoleh hasil berikut.

Pada sumbu y, Anda dapat melihat waktu dalam hitungan detik, dan pada dimensi sumbu x WRT ke variabel primal dari masalah kuadratik acak yang dihasilkan (jumlah kendala dari masalah yang dihasilkan adalah setengah dari ukuran dimensi primal). Untuk setiap dimensi, masalahnya dihasilkan pada benih yang berbeda, dan waktu diperoleh sebagai rata -rata dalam proses berturut -turut untuk masalah yang sama. Bagan ini menunjukkan untuk setiap solver yang dibandingkan dan program kuadratik acak yang dihasilkan, waktu Barplot, termasuk median (sebagai titik) dan nilai minimal dan maksimal diperoleh (mendefinisikan amplitudo batang). Anda dapat melihat bahwa ProxQP selalu di bawah atas pemecah, yang berarti itu adalah yang tercepat untuk tes ini.

Untuk masalah keras dari testset Maros Meszaros, ketika meminta akurasi tinggi (misalnya, 1E-9), seseorang memperoleh hasil di bawah ini.

Bagan di atas melaporkan profil kinerja pemecah yang berbeda. Ini klasik untuk pembandingan pemecah. Profil kinerja sesuai dengan fraksi masalah yang diselesaikan (pada sumbu y) sebagai fungsi runtime tertentu (pada sumbu x, diukur dalam hal kelipatan runtime pemecah tercepat untuk masalah itu). Jadi semakin tinggi, semakin baik. Anda dapat melihat bahwa ProxQP memecahkan tercepat lebih dari 60% dari masalah (yaitu, untuk $ tau = 1 $ ) dan bahwa untuk memecahkan sekitar 90% dari masalah, itu paling banyak 2 kali lebih lambat dari pemecah tercepat yang memecahkan masalah ini (yaitu, untuk $ tau approx2 $ ).

Catatan: Semua hasil ini telah diperoleh dengan Intel Gen Intel (R) (TM) ke-11 (TM) I7-11850H @ 2.50GHz CPU.

Qplayer

QPlayer memungkinkan untuk menggunakan QP sebagai lapisan dalam arsitektur pembelajaran standar. Lebih tepatnya, Qplayer membedakan $ theta $ solusi primal dan ganda dari QP formulir

$$ begin {align} min_ {x} & ~ frac {1} {2} x^{t} h ( theta) x+g ( theta)^{t} x tex {st} & ~ a ( thetA) x = b ( } & ~ a ( theta) x = b ( t theta ( a) C ( theta) x leq u ( theta) end {align} $$

Di mana $ x di mathbb {r}^n $ adalah variabel optimasi. Fungsi objektif didefinisikan oleh matriks semidefinit positif $ H ( theta) in mathcal {s}^n _+$ dan vektor $ g ( theta) in mathbb {r}^n $ . Kendala linier didefinisikan oleh matriks kesetaraan-kontra $ A ( theta) in mathbb {r}^{n_ text {eq} kali n} $ dan matriks ketimpangan-konservasi $ C ( theta) in mathbb {r}^{n_ text {in} kali n} $ dan vektor $ b in mathbb {r}^{n_ text {eq}} $ , $ l ( theta) in mathbb {r}^{n_ text {in}} $ Dan $ u ( theta) in mathbb {r}^{n_ text {in}} $ sehingga $ b_i di mathbb {r}, ~ forall i = 1, ..., n_ text {eq} $ Dan $ l_i di mathbb {r} cup { - infty} $ Dan $ u_i in mathbb {r} cup { + infty}, ~ forall i = 1, ..., n_ text {in} $ .

Qplayer dapat mempelajari lebih banyak arsitektur terstruktur. Misalnya, $ theta $ dapat hanya terdiri dalam mempelajari beberapa elemen dari $ A $ Saat membiarkan $ b $ diperbaiki (lihat misalnya, contoh tentang cara memasukkan qplayer ke dalam pipa pembelajaran). Qplayer juga dapat membedakan lebih dari LPS. QPlayer memungkinkan untuk kalkulus paralel dari CPU, dan dihubungkan dengan Pytorch .

Mengutip qplayer

Jika Anda menggunakan QPlayer untuk pekerjaan Anda, kami menganjurkan Anda untuk mengutip kertas terkait.

Prosedur Instalasi

Silakan ikuti prosedur instalasi di sini.