Apa yang bisa diselesaikan dengan pemrograman semidefinite yang tidak dapat diselesaikan dengan pemrograman linier?

9

Saya kenal dengan program linier karena mereka dapat memecahkan masalah dengan fungsi objektif linear dan batasan linear. Tetapi apa yang bisa diprogram pemrograman semidefinite yang tidak bisa diprogram oleh pemrograman linier? Saya sudah tahu bahwa program semidefinite adalah generalisasi dari program linear.

Juga, bagaimana seseorang mengenali masalah yang dapat dipecahkan menggunakan pemrograman semidefinite? Apa masalah khas yang digunakan pemrograman semidefinite yang tidak dapat diselesaikan melalui pemrograman linier?

Terima kasih banyak atas tanggapannya.

linear-programming convex-optimization semidefinite-programming pengguna11094
sumber
2
Mungkin Anda bisa membuat pertanyaan Anda lebih tepat? Bagaimanapun, pemrograman linier adalah -complete. P
Kristoffer Arnsfelt Hansen
5
@KristofferArnsfeltHansen Saya tidak pernah berhenti bertanya-tanya mengapa orang terus mengemukakan fakta ini dalam diskusi serupa. Kelengkapan P tidak relevan kecuali kita berbicara tentang memisahkan P dari L atau NC - jika kita berbicara tentang polytime, semua yang ada di P adalah "P-selesai". Untuk menyarankan jawaban pada OP: setelah Anda memperbaiki pengkodean linear suatu masalah, (yaitu menulis sebagai pengoptimalan fungsi linier di atas polytope), masuk akal untuk bertanya apakah LP / SDP poliassi dapat menyelesaikan masalah.
Sasho Nikolov

Jawaban:

18

Masalah khasnya adalah MaxCut: menghasilkan potongan dalam grafik yang (kurang-lebih) memaksimalkan jumlah potongan sisi. Goemans dan Williamson menunjukkan SDP mendekati nilai MaxCut dalam faktor setidaknya 0,878. Baru-baru ini, Chan, Lee, Raghavendra, dan Steurer menunjukkan bahwa untuk pengkodean linear alami masalah MaxCut, semua piringan hitam ukuran polinom mencapai perkiraan tidak lebih baik dari 0,5.

Sulit untuk mengatakan secara singkat masalah apa yang biasanya mendapat manfaat dari SDP. Pendekatan sistematis untuk membangun relaksasi SDP adalah melalui hierarki, yang paling kuat darinya adalah hierarki Lasserre: lihat survei Rothvoß untuk pengantar yang bagus. Sekarang ada terlalu banyak contoh keberhasilan SDP dalam optimasi untuk dicantumkan. Juga, Raghavendra menunjukkan bahwa satu SDP tertentu memberikan perkiraan terbaik untuk semua masalah MaxCSP, jika dugaan Unique Games benar.

Periksa buku-buku Gaertner dan Matousek , bab 6 dan 13 buku Willimson dan Shmoys , survei Lovasz .

Sasho Nikolov
sumber
12

Untuk banyak masalah optimisasi kombinatorial (misalnya Max-Cut), pemrograman semidefinite menghasilkan relaksasi yang jauh lebih kuat daripada relaksasi LP formulasi IP. Hal ini memungkinkan desain algoritma aproksimasi, dan algoritma yang tepat yang lebih efisien daripada rekan liniernya karena kualitas batas yang lebih baik. Contohnya dapat ditemukan dalam tesis Habilitasi Christoph Helmberg , survei ini , dan halaman kursus ini .

Urutan terbaru lain dari hasil spektakuler yang memanfaatkan pemrograman semidefinite adalah penerapan aljabar bendera Razborov untuk membuktikan hasil pada masalah jenis Turan (lihat survei ini dan proyek flagmatic ).

Thomas Kalinowski
sumber