Apakah mereka menggunakan pemrograman semidefinite di industri?

10

Saya tidak bisa melihat menyebutkannya di daftar pekerjaan. Saya telah melihat pemrograman integer, MIP, pemrograman non-linier campuran-integer, LP, pemrograman dinamis dll, tetapi tidak ada SDP. Apakah jauh lebih trendi di akademi daripada di industri?

Dari paparan terbatas saya kepada akademisi dan peserta industri dalam sistem tenaga listrik, saya pikir ada peluang bagus bahwa SDP akan diterapkan dalam masalah aliran daya optimal oleh operator sistem independen, tetapi tergantung pada sejauh mana kepala telur dapat menskala pendekatan saat ini untuk menangani contoh masalah yang lebih besar.

GrayOnGray
sumber

Jawaban:

8

Dari pengalaman saya sendiri yang terbatas di industri listrik, tidak ada yang memecahkan SDP pada skala seperti itu. Saya memiliki pengetahuan terbatas tentang apa yang dilakukan ISO New England, dan saya pikir mereka lebih tertarik untuk memasukkan stochasticity ke dalam model MILP mereka yang ada. Dari teman-teman yang telah bekerja pada sistem tenaga di laboratorium penelitian pemerintah di AS, mereka juga memikirkan stochasticity (pemrograman stochastic, kendala kesempatan, optimalisasi yang kuat ...).

Dari pengalaman saya di sektor perusahaan teknologi besar, orang memecahkan MILP pada model yang paling rumit, dan biasanya deterministik.

Saya kumpulkan dari sisi teknik kimia, mereka sepertinya tertarik pada MINLP, khususnya optimasi nonconvex yang dibatasi secara kuadratik, yang muncul secara alami dalam masalah pencampuran. Ada juga masalah yang dibatasi oleh PDE dan semua hal menyenangkan lainnya, tapi itu kebanyakan dari keahlian saya.

Jika saya harus berspekulasi, SDP dapat digunakan dalam desain semikonduktor sebagai subrutin (misalnya untuk MAXCUT), tetapi mengingat kurangnya pemecah kualitas, saya kira tidak ada permintaan yang besar (belum, setidaknya).

Menurut saya di dunia akademis, SDP lebih menarik sebagai alat bukti, yaitu "lihat, masalah ini adalah waktu polinomial!" jika Anda bisa mencari cara untuk bertengkar sebagai SDP. Pemecah SDP sangat sensitif (dibandingkan dengan kelas masalah cembung lainnya) sehingga saya pikir orang tidak benar-benar bersemangat tentang ide untuk benar-benar menyelesaikannya.

IainDunning
sumber
SDP tidak diketahui selalu polinomial-waktu, saya pikir. IIRC Anda membutuhkan batasan tambahan untuk mengetahui hal itu dengan pasti.
user541686
Tentu, tetapi jika kendala itu tidak terpenuhi Anda tidak akan melihatnya dalam bukti karena tidak akan ada gunanya.
IainDunning
7

Pemrograman semidefinite dan pemrograman kerucut urutan kedua belum diadopsi secepat ini dalam praktik seperti yang kita harapkan. Saya telah terlibat dalam hal ini selama 20 tahun terakhir, dan sangat mengecewakan melihat kemajuan yang lambat. Izinkan saya menunjukkan beberapa tantangan:

  1. HAI(m2)mHAI(m2) persyaratan penyimpanan adalah topik penelitian aktif tetapi di bidang SDP mereka tidak terbukti cukup kuat untuk digunakan dalam pemecah keperluan umum.

  2. Vendor perangkat lunak LP belum merasa cocok untuk menyertakan dukungan untuk SDP dalam produk mereka. Beberapa dukungan terbatas untuk SOCP mulai muncul.

  3. Pengetahuan tentang pemrograman semidefinite telah menyebar dengan lambat. Buku teks oleh Boyd dan Vandenberghe telah sangat membantu dalam hal ini, tetapi ada jalan panjang sebelum teknologi ini akan dikenal sebagai teknik optimasi yang lebih tua.

  4. Bahasa dan sistem pemodelan (seperti GAMS, AMPL, dll.) Belum memberikan dukungan yang baik untuk SOCP dan SDP. Paket CVX adalah pekerjaan yang paling menarik dalam arah ini, tetapi bahkan membutuhkan kecanggihan pada bagian dari pengguna.

SDP telah menemukan aplikasi di tingkat penelitian di banyak bidang teknik dan sains. Sepertinya ini pada akhirnya akan menjadi penting dalam industri juga.

Brian Borchers
sumber
5
Hanya untuk menambahkan: satu-satunya pemecah SDP komersial afaik adalah MOSEK dan itu masih cukup baru. Saya pikir ketahanan lebih penting daripada yang mungkin dipikirkan: dalam banyak aplikasi Anda dapat mengalokasikan lebih banyak waktu, tetapi jika seorang pemecah gagal apa yang harus dilakukan?
AndreaCassioli
5

Sebagian besar pekerjaan yang saya ketahui di laboratorium untuk masalah aliran daya adalah pada optimasi stokastik juga, sebagian besar berfokus pada MILP.

Dalam teknik kimia, mereka tertarik pada MINLPs, dan contoh klasiknya adalah masalah pencampuran (khususnya, masalah pooling prototipikal Haverly), sehingga istilah bilinear banyak muncul. Istilah trilinear terkadang muncul, tergantung pada model pencampuran termodinamika atau model reaksi yang digunakan. Ada juga sejumlah kecil minat dalam optimasi yang dibatasi oleh ODE atau dibatasi oleh PDE; tidak ada pekerjaan yang menggunakan SDP.

Sebagian besar pekerjaan optimasi yang dibatasi oleh PDE yang saya lihat (saya secara khusus memikirkan optimasi topologi) tidak menggunakan SDP. Kendala PDE bisa linier, dan secara teori, bisa mengakui formulasi SDP tergantung pada apa tujuan dan kendala yang tersisa. Dalam prakteknya, masalah teknik cenderung nonlinier, dan menghasilkan masalah non-konveks yang kemudian dipecahkan dengan optima lokal (mungkin juga menggunakan multistart). Kadang-kadang, formulasi penalti digunakan untuk mengecualikan optima lokal suboptimal yang diketahui.

Saya bisa melihatnya mungkin digunakan dalam teori kontrol. Sejumlah kecil pekerjaan yang saya lihat pada "ketidaksetaraan matriks linear" menunjukkan bahwa itu mungkin bisa bermanfaat di sana, tetapi teori kontrol dalam industri cenderung mengandalkan metode yang sudah terbukti benar daripada pendarahan formulasi matematika, jadi saya ragu SDPs akan digunakan untuk sementara waktu sampai mereka dapat membuktikan kegunaannya.

Ada beberapa pemecah SDP yang baik-baik saja, dan mereka telah memecahkan masalah yang cukup besar untuk akademisi (terakhir saya periksa adalah 3-4 tahun yang lalu, dan mereka memecahkan puluhan hingga ratusan ribu variabel), tetapi skenario aliran daya melibatkan masalah yang jauh lebih besar (puluhan juta hingga miliaran variabel), dan saya tidak berpikir solvernya sudah ada. Saya pikir mereka bisa sampai di sana - sudah ada cukup banyak pekerjaan baru-baru ini tentang metode interior-point bebas-matriks yang menunjukkan bahwa akan layak untuk meningkatkan solver SDP menggunakan teknik-teknik tersebut - tetapi belum ada yang melakukannya, mungkin karena piringan hitam, MILP, dan NLP cembung muncul lebih sering dan merupakan teknologi yang mapan.

Geoff Oxberry
sumber
2
Saya sekarang sangat sedikit tentang ini, tetapi lucunya aplikasi untuk mengendalikan teori telah ada untuk sementara waktu. Ketidaksamaan Linear Matriks dalam Sistem dan Kontrol diterbitkan pada tahun 1994. Stephen Boyd melakukan sebagian besar penelitiannya di persimpangan optimalisasi dan kontrol, dan dia juga sudah melakukan itu sejak setidaknya tahun 1996.
GrayOnGray
Itu benar. Sebagian besar yang saya ketahui tentang kontrol industri berasal dari magang singkat di industri pemrosesan kimia, dan di sana, model kontrol prediktif adalah hal baru yang besar, dan saya percaya bahwa itu dikembangkan antara pertengahan 80-an dan awal-90-an.
Geoff Oxberry