Memecahkan program semidefinite dalam waktu polinomial

Kita tahu bahwa program linier (LP) dapat diselesaikan tepat dalam waktu polinomial menggunakan metode ellipsoid atau metode titik interior seperti algoritma Karmarkar. Beberapa piringan hitam dengan jumlah variabel / kendala super-polinomial (eksponensial) juga dapat diselesaikan dalam waktu polinomial, asalkan kita dapat merancang oracle pemisahan waktu polinomial untuk mereka.

Bagaimana dengan program semidefinite (SDP)? Kelas SDP apa yang bisa dipecahkan tepat dalam waktu polinomial? Ketika SDP tidak dapat dipecahkan dengan tepat, bisakah kita selalu merancang FPTAS / PTAS untuk menyelesaikannya? Apa kondisi teknis di mana ini dapat dilakukan? Bisakah kita memecahkan SDP dengan jumlah variabel / kendala eksponensial dalam waktu polinomial, jika kita dapat merancang oracle pemisahan waktu polinomial untuknya?

Bisakah kita menyelesaikan SDPs yang terjadi dalam masalah optimisasi kombinatorial (MAX-CUT, pewarnaan grafik) secara efisien? Jika kita dapat memecahkan hanya dalam faktor, akan tidak memiliki efek pada algoritma faktor pendekatan konstan (seperti 0,878 untuk Goemans-Williamson MAX-CUT algoritma)? $1+\epsilon$

Referensi yang bagus tentang ini akan sangat dihargai.

linear-programming semidefinite-programming convex-optimization Arindam Pal
sumber

Bahkan metode ini bekerja untuk pemrograman cembung pada umumnya

Suresh Venkat

Setidaknya ada dua alasan Anda tidak dapat menyelesaikan SDP umum dalam waktu polinomial. (1) Ada SDP yang solusinya berukuran eksponensial. (2) SDP dapat mengkodekan jumlah masalah akar kuadrat, yang tidak diketahui sebagai waktu polinomial yang dapat dipecahkan.

Robin Kothari

@RobinKothari Untuk SDP, biasanya "dipecahkan dalam waktu polinomial" diganti dengan "mendapat dalam

(aditif) OPT dalam polinomial waktu dalam

" IIRC. ps, bagaimana SDP mengkodekan jumlah akar kuadrat?

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

Suresh Venkat

@ SureshVenkat: Katakanlah kita memiliki matriks 2x2 dengan entri [ab; CD]. Tetapkan bahwa ini adalah semidefinit positif dan d = 1. Ini berarti b = c dan a> = b ^ 2. Jadi b dibatasi oleh akar kuadrat dari a. Sekarang kita dapat memaksimalkan jumlah dari beberapa b's. Nilai optimal adalah jumlah akar kuadrat dari masing-masing a.

Robin Kothari

Ini bukan multiplikatif tetapi aditif. Juga, en.wikipedia.org/wiki/Semidefinite_programming#Algorithms

Suresh Venkat

Memecahkan program semidefinite dalam waktu polinomial

Jawaban: