Kapan kesenjangan dualitas pemrograman semidefinite (SDP) nol?

10

Saya belum bisa menemukan karakterisasi yang tepat dalam menghilangnya kesenjangan dualitas SDP. Atau, kapan "dualitas kuat" bertahan?

Misalnya, ketika seseorang bolak-balik antara Lasserre dan SOS SDP, pada prinsipnya seseorang memiliki celah dualitas. Namun, entah mengapa ada alasan "sepele" mengapa celah ini tidak ada.

Kondisi Slater tampaknya cukup tetapi tidak perlu dan itu berlaku untuk semua program cembung. Saya berharap bahwa untuk SDP khususnya sesuatu yang lebih kuat mungkin benar. Saya juga akan senang melihat contoh eksplisit menggunakan kondisi Slater untuk membuktikan lenyapnya kesenjangan dualitas.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual lulusan
sumber

10

Ada teori dualitas yang lebih rumit untuk SDP yang pasti: tidak ada 'kondisi ekstra' seperti kondisi Slater. Ini karena Ramana . (Untuk pandangan lain mengenai SOS yang melibatkan ini, lihat [KS12] .) Sejujurnya, saya tidak pernah mencoba memahami makalah ini dan akan senang jika seseorang membodohi mereka untuk saya.

Salah satu konsekuensi penting dari pekerjaan ini adalah bahwa masalah pengujian apakah SDP yang diberikan layak dalam NP jika dan hanya jika itu ada dalam coNP. (Namun, saya pikir para ahli memperkirakan masalahnya tidak ada. Batas atas yang paling dikenal adalah PSPACE.)

Ryan O'Donnell
sumber

Terima kasih banyak atas balasan yang sangat membantu! Biarkan saya melihat ini! (Sungguh suatu kebetulan bahwa selama minggu-minggu terakhir saya juga telah mencoba untuk mengerjakan makalah Anda dengan Daniel Kane di sirkuit bawah jaring dalam batas bawah! Ini adalah kertas edukatif! Saya telah bertanya-tanya apakah apa yang Anda lakukan untuk LTF juga terjadi untuk lebih aktivasi realistis seperti ReLU.)

gradstudent

9

Untuk SDP dalam bentuk standar kondisi Slater mengurangi keberadaan positif pasti yang memenuhi batasan affine . Saya kira ini puas untuk setiap SDP yang dapat Anda temukan dalam literatur algoritma optimasi / pendekatan kombinatorial. Misalnya, untuk Goemans-Williamson Max-Cut SDP, batasan kelayakan adalah dan matriks identitas adalah solusi layak yang pasti positif.

min {t r (C^{T} X) : t r (A_{1}^{T} X) = b_{1}, \dots, t r (A_{m}^{T} X) = b_{m}, X ⪰ 0},

$\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},$

X ≻ 0

$X\succ 0$

t r (A_{i}^{T} X) = b_{i}

$\mathrm{tr}(A_i^T X) = b_i$

{X : X_{1, 1} = 1, \dots, X_{n, n} = 1, X ⪰ 0}

$\{X: X_{1,1} = 1, \ldots, X_{n,n} = 1, X\succeq 0\}$

Sejauh hierarki Lasserre / Sum of Squares, Lasserre menunjukkan bahwa jika set yang layak ditentukan oleh kendala polinomial memiliki titik interior, maka tidak ada kesenjangan kualitas. Anda dapat menemukan kondisi yang lebih lemah di makalah ini .

Sasho Nikolov
sumber

Terima kasih banyak untuk referensi! Jadi, apakah kondisi Slater yang ditransformasikan juga merupakan kondisi yang diperlukan untuk SDP? Atau adakah persyaratan lain yang diperlukan? (Saya akan segera melihat-lihat makalah yang Anda maksudkan tetapi saya bertanya-tanya apakah Anda bisa mengatakan sesuatu tentang apa yang Anda maksud dengan "kondisi yang lebih lemah"? Maksud Anda kondisi di koran kedua masih dalam kondisi cukup dan tidak perlu kondisi tetapi lebih sederhana daripada kondisi yang cukup di koran pertama?)

gradstudent

Ini adalah kondisi standar Slater, saya baru saja mengkhususkan diri pada SDP, yang menyederhanakan masalah karena semua kendala terkait, kecuali untuk kendala PSD. Kondisi ini tidak perlu. Saya tidak berpikir salah satu syarat SoS diperlukan, tetapi yang "lebih lemah" tidak memerlukan keberadaan titik interior, jadi mungkin lebih mudah untuk memverifikasi.

Sasho Nikolov

Terima kasih! Jadi kondisi yang diperlukan tidak diketahui?

gradstudent

1

Ada karakterisasi yang bagus (saya pikir ....) ketika dualitas kuat berlaku, atau gagal untuk fungsi objektif {\ em all}.

Kami mengatakan bahwa semidefinite {\ em system}

$(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$

adalah berperilaku buruk jika di sini adalah fungsi tujuan yang SDP $c$

$\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$

memiliki nilai optimal yang terbatas, tetapi dual SDP tidak memiliki solusi dengan nilai yang sama: yaitu, dualitas yang kuat gagal untuk beberapa $c.$

$(P_{SD})$ adalah berperilaku baik jika tidak berperilaku buruk. Yaitu, untuk setiap fungsi objektif, dualitas kuat berlaku. (Yaitu, untuk setiap yang SDP primal memiliki nilai optimal yang terbatas, dual memiliki solusi dengan nilai yang sama). $c$

Tentu saja, jika kondisi Slater berlaku, maka berperilaku baik, tetapi sebaliknya tidak benar. $(P_{SD})$

https://arxiv.org/pdf/1709.02423.pdf

Makalah ini segera keluar di SIAM Review. Saya harap orang-orang akan menyukainya :)

distrik9
sumber

Kapan kesenjangan dualitas pemrograman semidefinite (SDP) nol?

Jawaban: