Memecahkan masalah kuadrat terkecil dengan batasan linear dalam Python

12

Saya harus menyelesaikannya

minxAxb22,s.t.ixi=1,xi0,i.

Saya pikir ini adalah masalah kuadrat yang harus dipecahkan dengan CVXOPT , tapi saya tidak bisa mengatasinya.

untsten
sumber
Saya harap pertanyaan ini tidak terlalu spesifik untuk compsci.
tillsten
Geoff Oxberry: Hanya ingin tahu, tetapi mengapa Anda mengedit bagian linier? Saya pikir itu adalah bagian yang cukup impoten dari deskripsi masalah, solusinya akan sangat berbeda untuk optimasi kuadrat terkecil non-linear.
tillsten
Btw, suntingan lainnya bagus!
tillsten
Anda dapat dengan mudah menyelesaikan ini dengan kode Anda sendiri dengan cara yang sangat efisien. Tidak perlu untuk CVXOPT.
Royi

Jawaban:

11

Saya menulis jawaban lengkap (di bawah garis) sebelum menemukan CVXPY , yang (seperti CVX untuk MATLAB) melakukan semua hal sulit untuk Anda dan memiliki contoh yang sangat singkat yang hampir sama dengan milik Anda di sini . Anda hanya perlu mengganti jalur yang relevan dengan

 p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)])

Jawaban lama saya, melakukannya dengan cara yang lebih sulit dengan CVXOPT:

Mengikuti saran Geoff untuk mengatur fungsi objektif Anda

Axb22=xTATbT,Axb=xTATAxbTAxxTAbbTb

Tentu saja, semua istilah adalah skalar, sehingga Anda dapat mengubah urutan yang ketiga dan menjatuhkan yang terakhir (karena itu tidak bergantung pada dan karena itu tidak akan mengubah mana memberi Anda minimum, meskipun Anda perlu menambahkannya kembali setelah menyelesaikan untuk mendapatkan nilai yang benar dari tujuan Anda) untuk mendapatkan Ini (termasuk kendala Anda) memiliki bentuk program kuadratik, seperti yang diberikan dalam dokumentasi CVXOPT di sini , di mana ada juga contoh kode untuk menyelesaikan masalah seperti itu.xx

xTATAxbT(A+AT)x
David Ketcheson
sumber
4

Alih-alih masalah yang Anda selesaikan, selesaikan

minxAxb22,s.t.ixi=1,xi0,i.

Masalah ini adalah masalah optimasi terdiferensiasi, cembung, nonlinier yang dapat diselesaikan di CVXOPT, IPOPT, atau pemecah optimasi cembung lainnya.

Geoff Oxberry
sumber