Pemrograman quadratic ketika matriks tidak pasti positif

8

http://cran.r-project.org/web/packages/quadprog/quadprog.pdf

Paket R quadprogtampaknya dapat menyelesaikan masalah pemrograman kuadrat hanya ketika matriks pasti positif.D

Namun, ada kasus ketika matriks tidak pasti positif. sepertiD

min(x2+y2−6xy)subject tox+y≤1,3x+y≤1.5,x,y≥0.

Bagaimana saya bisa menyelesaikan masalah seperti ini?

r optimization pengguna67275
sumber
Masalahnya mungkin berhubungan dengan fakta bahwa jika kuadratik tidak pasti positif, ia tidak memiliki minimum lokal. Dalam hal ini masih harus ada minimum global, karena wilayah tersebut dibatasi.
Glen_b -Reinstate Monica
1
Jika bukan PSD, maka masalahnya bukan cembung. Algoritma gradient descent apa pun akan mendaratkan Anda pada minimum lokal, lebih atau kurang tergantung pada titik awalnya. Anda mungkin harus datang dengan heuristik untuk memutuskan kapan harus menghentikan pencarian. D
user603
4
Tidak terlalu sulit untuk memutuskan segmen batas mana yang menjadi batas minimum. Kemudian mengingat kendala itu, cukup mudah untuk melemparkannya sebagai masalah yang memang memiliki minimum lokal ... tetapi saran @ user603 tentang menggunakan algoritma minimalisasi standar seperti gradient descent dapat sangat berguna sebagai pendekatan umum.
Glen_b -Reinstate Monica

Jawaban:

4

Ada rutin optimasi khusus untuk optimasi lokal atau global masalah Pemrograman Kuadratik, apakah fungsi objektifnya cembung atau tidak.

BARON adalah pengoptimal global tujuan umum yang dapat menangani dan memanfaatkan masalah pemrograman kuadratik, cembung atau tidak.

CPLEX memiliki pemecah pemrograman kuadratik yang dapat dipanggil dengan solutiontarget = 2 untuk menemukan optimum lokal atau = 3 untuk menemukan global optimal. Dalam MATLAB, itu bisa dipanggil dengan cplexqp.

Pengoptimal lokal tujuan umum yang dapat menangani kendala linier juga dapat digunakan untuk menemukan optimal lokal. Contoh dalam R adalah https://cran.r-project.org/web/packages/trust/trust.pdf . Pengoptimal untuk R tercantum di https://cran.r-project.org/web/views/Optimization.html .

Dalam MATLAB, fungsi quadprog dalam Kotak Alat Pengoptimalan dapat digunakan untuk menemukan optimal lokal.

Di Julia, ada berbagai pengoptimal yang tersedia.

Algoritma gradient descent "Any" mungkin tidak mendaratkan Anda pada apa pun, apalagi berurusan dengan kendala. Gunakan paket yang dikembangkan oleh seseorang yang tahu apa yang mereka lakukan.

Contoh masalah yang diberikan mudah diselesaikan untuk membuktikan optimalitas global. Mungkin dengan berlalunya lebih dari 2 tahun itu tidak lagi diperlukan, atau mungkin menjadi contoh yang tidak pernah ada, tetapi dalam hal apa pun, optimum global adalah pada x = 0,321429, y = 0,535714

Mark L. Stone
sumber
1
+1. Metode pengali lagrange untuk menyelesaikan masalah seperti itu secara rutin diajarkan di kelas Kalkulus tahun kedua. Dengan mereka, satu siap memperoleh dan (yang dicapai sepanjang batas ). x=9/28y=15/283x+y=3/2
whuber
1

Anda dapat membangun solusi dengan menggunakan nearPDdari Matrixpaket seperti:
nearPD(D)$mat.

nearPD menghitung matriks pasti positif terdekat.

vonjd
sumber
2
+1 karena merupakan solusi perkiraan yang relatif mudah . (Saya tidak ingat melihat pertanyaan ini kalau tidak saya akan memberikannya sendiri dalam komentar.) Karena itu, seseorang pada dasarnya menetapkan nilai eigen negatif ke nol ketika menggunakan teknik ini dan kemudian merekonstruksi matriks asli; jika mode variasi yang sesuai signifikan, perkiraan ini dapat cacat serius.
usεr11852
3
Setuju dengan kalimat terakhir dalam komentar sebelumnya. Ini adalah teknik yang sangat baik untuk digunakan selama Anda tidak peduli sedikitpun apakah jawaban Anda benar, atau bahkan di stadion baseball, kota, atau negara bagian yang tepat. Jika tujuan Anda "Hessian" matriks berada dalam "toleransi" jauh dari positif pasti, pendekatan ini sebenarnya bisa masuk akal, jika tidak, tidak.
Mark L. Stone