Saya agak bingung dengan literatur optimasi kontinu dan literatur TCS tentang jenis program matematika (MP) yang dapat diselesaikan secara efisien, dan yang tidak. Komunitas optimisasi berkelanjutan tampaknya mengklaim bahwa semua program cembung dapat diselesaikan secara efisien, tetapi saya yakin definisi "efisien" mereka tidak sesuai dengan definisi TCS.
Pertanyaan ini telah banyak mengganggu saya dalam beberapa tahun terakhir, dan sepertinya saya tidak dapat menemukan jawaban yang jelas untuk itu. Saya harap Anda dapat membantu saya menyelesaikan ini sekali dan untuk semua: Kelas anggota parlemen mana yang dapat diselesaikan secara tepat dalam waktu polinomial, dan dengan cara apa; dan apa yang diketahui tentang mendekati solusi optimal dari anggota parlemen yang tidak dapat kita selesaikan secara tepat dalam waktu polinomial?
Di bawah, saya memberikan jawaban yang tidak lengkap untuk pertanyaan ini yang juga mungkin salah di beberapa tempat, jadi saya harap Anda dapat memverifikasi dan memperbaiki saya pada titik-titik di mana saya salah. Itu juga menyatakan beberapa pertanyaan yang tidak bisa saya jawab.
Kita semua tahu bahwa pemrograman linier dapat diselesaikan tepat dalam waktu polinomial, dengan menjalankan metode ellipsoid atau metode titik interior, dan kemudian menjalankan beberapa prosedur pembulatan. Pemrograman linier bahkan dapat diselesaikan dalam waktu polinomial dalam jumlah variabel ketika menghadapi keluarga LP dengan jumlah super besar kendala linier, selama seseorang dapat memberikan "oracle pemisahan" untuk itu: sebuah algoritma yang, diberi titik , menentukan apakah titik tersebut layak atau mengeluarkan hyperplane yang memisahkan titik dari polihedron dari titik yang layak. Demikian pula, pemrograman linier dalam polinomial waktu dalam sejumlah kendala ketika menghadapi keluarga LP dengan jumlah variabel yang sangat besar, jika ada yang menyediakan algoritma pemisahan untuk dual dari LP ini.
Metode ellipsoid juga mampu menyelesaikan program kuadratik dalam waktu polinomial, jika matriks dalam fungsi objektifnya adalah positif (semi?). Saya menduga bahwa, dengan menggunakan trik oracle pemisahan, kita dalam beberapa kasus juga dapat melakukan ini jika kita berurusan dengan sejumlah kendala yang luar biasa. Benarkah?
Pemrograman semidefinite akhir-akhir ini (SDP) telah mendapatkan banyak popularitas di komunitas TCS. Seseorang dapat menyelesaikannya hingga presisi sewenang-wenang dengan menggunakan metode titik interior, atau metode ellipsoid. Saya pikir, SDPs tidak dapat diselesaikan dengan tepat karena masalah yang akar kuadratnya tidak dapat dihitung dengan tepat. (?) Apakah itu benar jika saya mengatakan ada FPTAS untuk SDP? Saya belum melihat yang dinyatakan di mana saja, jadi itu mungkin tidak benar. Tapi kenapa?
Kami dapat memecahkan piringan hitam dengan tepat dan SDP hingga presisi yang sewenang-wenang. Bagaimana dengan kelas program kerucut lainnya? Bisakah kita menyelesaikan program kerucut orde dua hingga presisi sewenang-wenang, menggunakan metode ellipsoid? Saya tidak tahu
Di kelas MP mana kita bisa menggunakan metode ellipsoid? Sifat-sifat apa yang perlu dipenuhi oleh seorang anggota parlemen seperti itu sehingga jawaban dapat diberikan hingga presisi yang sewenang-wenang, dan sifat-sifat tambahan apa yang kita butuhkan untuk dapat memperoleh solusi yang tepat dalam waktu polinomial? Pertanyaan yang sama untuk metode titik interior.
Oh, dan akhirnya, apa yang menyebabkan pengoptimal terus menerus mengatakan bahwa program cembung dapat diselesaikan secara efisien? Benarkah jawaban presisi sembarang untuk program cembung dapat ditemukan dalam waktu polinomial? Saya percaya tidak, jadi dalam aspek apa definisi mereka tentang "efisien" berbeda dari kita?
Setiap kontribusi dihargai! Terima kasih sebelumnya.
Jawaban:
Saya dapat menjawab bagian ini:
Pernyataan itu benar, tetapi kita tidak sering melihatnya karena pernyataan yang lebih kuat berlaku dan lebih penting daripada pernyataan yang lebih lemah ini.
FPTAS adalah algoritma waktu polinomial yang, diberikan masalah dan parameter akurasi 1 k , menghasilkan solusi (1 + 1 / k ) yang sesuai.
Tetapi untuk SDP, metode ellipsoid dan metode interior-titik menyediakan algoritma polinomial-waktu yang, diberikan masalah dan parameter akurasi 1 k , menghasilkan solusi (1 + 2 - k ) -roksimasi. Perhatikan bahwa faktor perkiraan jauh lebih baik daripada yang dibutuhkan untuk FPTAS.
sumber
Saya tidak tahu apakah semua masalah cembung ada di P, tetapi saya bisa menjawab pertanyaan terkait: optimasi nonconvex NP-hard. Lihat "Pemrograman kuadratik dengan satu nilai eigen negatif adalah NP-keras" .
sumber