Menguji apakah sebuah matriks positif semi-pasti

11

Saya memiliki daftar dari matriks simetris yang saya perlu periksa untuk semi-definiteness positif (yaitu nilai eigennya non-negatif.)L

Komentar di atas menyiratkan bahwa seseorang dapat melakukannya dengan menghitung nilai eigen masing-masing dan memeriksa apakah nilainya tidak negatif (mungkin harus mengurus kesalahan pembulatan.)

Menghitung nilai eigen cukup mahal dalam skenario saya, tetapi saya perhatikan bahwa perpustakaan yang saya gunakan memiliki tes yang cukup cepat untuk kepastian positif (yaitu, jika nilai eigen dari suatu matriks benar-benar positif.)

Karenanya idenya adalah, yang diberi matriks , satu tes jika adalah pasti positif. Jika tidak maka tidak positif semi-pasti, jika tidak maka seseorang dapat menghitung nilai eigen untuk memastikan itu memang positif semi-pasti. B + ϵ I B BBLB+ϵIBB

Pertanyaan saya sekarang adalah:

Apakah ada cara yang lebih langsung dan efisien untuk menguji apakah sebuah matriks positif semi-pasti, asalkan diberikan tes yang efisien untuk kepastian positif?

Jernej
sumber
1
Tes yang Anda perhatikan di perpustakaan kemungkinan didasarkan pada proposisi bahwa matriks simetris nyata pasti positif jika dan hanya jika setiap prinsip utama minor memberikan penentu positif, sesuatu yang bisa diperiksa dengan eliminasi tanpa berputar dalam aritmatika yang tepat. Kesulitan halus untuk memperluas ini ke kasus semi-pasti telah membuat banyak penulis salah saji. Saya tahu topik ini telah dibahas dalam Pertanyaan Math.SE, jadi saya akan mencoba memberikan tautan. A
hardmath
1
Untuk orang-orang yang lebih berpengetahuan di sini - apakah akan bekerja untuk menggeser spektrum menjadi positif dengan menambahkan untuk besar , kemudian menemukan nilai eigen minimum dari sistem yang bergeser (misalnya dengan iterasi terbalik), lalu periksa apakah nilai eigen terkecil dari sistem shift lebih kecil dari shift ? Pergeseran dapat, misalnya, nilai eigen besarnya terbesar yang dapat ditemukan dengan cepat. c c cB+cIccc
Nick Alger
Ya, Anda dapat menggeser nilai eigen dan menghitung nilai eigen terkecil, tetapi Anda masih memiliki masalah dalam menetapkan toleransi untuk apa yang akan Anda terima (dan memastikan bahwa nilai eigen Anda dihitung setidaknya untuk toleransi itu!)
Brian Borchers
Tidak yakin apakah ini akan membantu, tetapi perhatikan bahwa setelah Anda tahu sebuah matriks tidak pasti positif, untuk memeriksa apakah itu semidefinit positif, Anda hanya perlu memeriksa apakah kernelnya non-kosong.
Abel Molina

Jawaban:

20

Apa definisi kerja Anda dari "semidefinite positif" atau "positif pasti"? Dalam aritmatika floating point, Anda harus menentukan semacam toleransi untuk ini.

Anda bisa mendefinisikan ini dalam hal nilai eigen yang dihitung dari matriks. Namun, pertama-tama Anda harus memperhatikan bahwa nilai eigen yang dihitung dari skala matriks linear dengan matriks, sehingga misalnya, matriks I dapatkan dengan mengalikan dengan faktor satu juta, nilai eigennya dikalikan satu juta. Apakah nilai eigen negatif? Jika semua nilai eigen lainnya dari matriks Anda positif dan pada urutan , maka secara efektif 0 dan tidak boleh diperlakukan sebagai nilai eigen negatif. Karena itu, penting untuk mempertimbangkan penskalaan. λ = - 1.0 10 30 λ = - 1.0Aλ=1.01030λ=1.0

Pendekatan yang masuk akal adalah dengan menghitung nilai eigen dari matriks Anda, dan menyatakan bahwa matriks adalah semidefinit positif numerik jika semua nilai eigen lebih besar dari, di mana adalah nilai eigen terbesar. λ maksϵ|λmax|λmax

Sayangnya, menghitung semua nilai eigen dari suatu matriks agak memakan waktu. Pendekatan lain yang umum digunakan adalah bahwa matriks simetris dianggap pasti positif jika matriks memiliki faktorisasi Cholesky dalam aritmatika floating point. Menghitung faktorisasi Cholesky adalah urutan besarnya lebih cepat daripada menghitung nilai eigen. Anda dapat memperluas ini ke semidefiniteness positif dengan menambahkan beberapa kecil identitas ke matriks. Sekali lagi, ada masalah penskalaan. Salah satu pendekatan cepat adalah melakukan penskalaan simetris dari matriks sehingga elemen diagonal adalah 1.0 dan menambahkan ke diagonal sebelum menghitung faktorisasi Cholesky. ϵ

Anda harus berhati-hati dengan ini, karena ada beberapa masalah dengan pendekatan tersebut. Sebagai contoh, ada keadaan di mana dan pasti pasti dalam arti bahwa mereka memiliki titik mengambang faktorisasi Cholesky, tetapi tidak memiliki faktorisasi Cholesky. Dengan demikian himpunan "floating point Cholesky berpola positif pasti matriks" tidak cembung! B ( A + B ) / 2AB(A+B)/2

Brian Borchers
sumber
Bisakah Anda menguraikan paragraf terakhir atau memposting tautan ke sumber? Itu sangat aneh.
Daniel Shapero
1
Referensi klasik untuk penskalaan ini adalah A. van der Slui. Nomor kondisi dan keseimbangan matriks Numerische Mathematik 14 (1): 14-23, 1969. Ini juga dibahas dalam buku pelajaran seperti Golub dan van Loan. Bit dalam paragraf terakhir adalah dari pengalaman pribadi yang sulit dimenangkan dalam pencarian baris pengkodean dalam kode pemrograman semidefinite - Saya pernah mengalami situasi di mana dan memiliki faktorasi Cholesky oleh LAPACK, tetapi tidak memiliki faktorisasi Cholesky menurut LAPACK. Masalah-masalah semacam ini mulai terjadi ketika Anda hampir tunggal. XX + 0,95 α Δ XX+αΔXX+0.95αΔX
Brian Borchers
Ini juga tidak biasa untuk menemukan bahwa beberapa matriks dapat diperhitungkan Cholesky dalam presisi diperpanjang atau empat kali lipat tetapi tidak dalam presisi ganda biasa atau aritmatika floating point presisi tunggal.
Brian Borchers
3
Beberapa kode titik interior primal-dual untuk SDP (CSDP, SDPT3, SDPA) selalu mengembalikan matriks yang pasti positif dan memiliki faktorisasi Cholesky, sementara pemecah populer lainnya (SeDuMi) menggunakan dekomposisi nilai eigen dan akan mengembalikan solusi yang memiliki sangat kecil negatif nilai eigen.
Brian Borchers
3
Thomas H. Kerr III
sumber
4
Sepertinya nama pengguna cukup banyak mengungkapkan hubungan antara penulis jawaban dan penulis makalah. Sedikit info lebih lanjut tentang apa yang terkandung di koran akan menyenangkan; meskipun, bagaimanapun, ini sangat menarik dan relevan dengan daftar pertanyaan makalah!
Anton Menshov