Apakah ada pemecah pemrograman nonlinier berkualitas tinggi untuk Python?


Saya memiliki beberapa masalah optimisasi global non-cembung yang menantang untuk dipecahkan. Saat ini saya menggunakan MATLAB's Optimization Toolbox (khusus, fmincon()dengan algoritma = 'sqp'), yang cukup efektif . Namun, sebagian besar kode saya menggunakan Python, dan saya ingin melakukan optimasi dengan Python juga. Apakah ada pemecah NLP dengan binding Python yang dapat bersaing dengan fmincon()? Itu harus

  • dapat menangani kendala kesetaraan dan ketidaksetaraan nonlinier
  • tidak mengharuskan pengguna untuk menyediakan Jacobian.

Tidak apa-apa jika tidak menjamin global optimal ( fmincon()tidak). Saya mencari sesuatu yang konvergen kuat ke optimal lokal bahkan untuk masalah yang menantang, dan bahkan jika itu sedikit lebih lambat daripada fmincon().

Saya telah mencoba beberapa solver yang tersedia melalui OpenOpt dan menemukan mereka lebih rendah daripada MATLAB fmincon/sqp.

Hanya untuk penekanan saya sudah memiliki formulasi yang mudah disalurkan dan pemecah yang baik. Tujuan saya hanyalah mengubah bahasa agar memiliki alur kerja yang lebih ramping.

Geoff menunjukkan bahwa beberapa karakteristik masalah mungkin relevan. Mereka:

  • 10-400 variabel keputusan
  • 4-100 batasan kesetaraan polinomial (derajat polinom berkisar dari 1 hingga sekitar 8)
  • Sejumlah kendala ketimpangan rasional sama dengan sekitar dua kali lipat jumlah variabel keputusan
  • Fungsi obyektif adalah salah satu variabel keputusan

Jacobian dari batasan kesetaraan adalah padat, seperti Jacobian dari batasan ketidaksetaraan.


2
David, sayangnya ini adalah pertanyaan yang sama sekali berbeda :) Perbedaan antara minimum lokal dan global adalah subjek dari sejumlah PhD potensial, dan oleh Teorema Tanpa Makan Siang Gratis, pemecah masalah apa pun yang bagus untuk satu masalah umum pengoptimalan global adalah terbukti buruk untuk orang lain. Saya mungkin menyarankan agar Anda mulai dengan mempertimbangkan opsi formulasi (Apakah ada bentuk bilangan bulat campuran? Apakah ada perkiraan cembung?)
Aron Ahmadia

David, Aron membuat poin yang bagus. Formulasi jelas merupakan kunci dalam hal memperoleh solusi numerik NLP non-cembung, apalagi mendapatkan solusi yang baik dengan cepat. Mungkin ada baiknya mempertimbangkan formulasi alternatif, dan kemudian menggunakan struktur formulasi tersebut untuk memandu pilihan solver Anda. Menggunakan pemecah yang mengeksploitasi struktur apa pun (seperti sparsity, pemrograman stochastic multi-tahap, menggunakan kendala untuk menghasilkan potongan) yang dapat Anda sebabkan dalam masalah Anda adalah kunci untuk mendapatkan solusi yang baik.
Geoff Oxberry

@DavidKetcheson: Karena Anda memiliki formulasi yang ingin Anda gunakan, bisakah Anda setidaknya mengomentari karakteristik formulasi Anda? Apakah Jacobian dari Lagrangian padat atau jarang? Kira-kira berapa banyak variabel yang dimilikinya? Tidak ada gunanya bagi kami untuk merekomendasikan perangkat lunak yang mengimplementasikan metode solusi yang tidak sesuai untuk masalah Anda, dan itulah satu-satunya alasan orang berbicara tentang formulasi.
Geoff Oxberry

coopr menyediakan binding ke ipopt menggunakan asl: ipopt
denfromufa

Jawaban:


fmincon(), seperti yang Anda sebutkan, menggunakan beberapa strategi yang terkenal dalam optimasi nonlinier yang berupaya untuk menemukan minimum lokal tanpa banyak memperhatikan apakah optimum global telah ditemukan. Jika Anda setuju dengan ini, maka saya pikir Anda telah mengutarakan pertanyaan dengan benar (optimasi nonlinear).

Paket terbaik yang saya ketahui untuk optimasi nonlinear umum adalah IPOPT [1]. Rupanya Matthew Xu memelihara satu set binding Python ke IPOPT , jadi ini mungkin tempat untuk memulai.

[1]: Andreas Wachter adalah teman pribadi, jadi saya mungkin sedikit bias.


Andreas melakukan pekerjaan yang baik, tetapi solvernya juga memerlukan informasi matriks Jacobian (atau paling tidak, informasi sparsity untuk matriks Jacobian). Ketika Anda mengatakan bahwa Anda menginginkan solver yang tidak memerlukan matriks Jacobian, maksud Anda bahwa Anda menginginkan solver yang tidak mengharuskan Anda untuk memberikan matriks Jacobian secara analitis (sehingga perhitungan perbedaan hingga akan cukup) atau apakah Anda ingin seorang pemecah yang tidak memerlukan informasi matriks Jacobian sama sekali (yang akan membatasi Anda untuk metode optimasi bebas derivatif)?
Geoff Oxberry

Tangkapan yang bagus. Maksud saya yang pertama; Saya telah memperbarui pertanyaan.
David Ketcheson

Saya akhirnya bisa menerapkan IPOPT untuk masalah saya menggunakan sage.openopt.org . Itu bagus!
David Ketcheson

4
Hari ini (2017) Anda juga dapat menggunakan IPOPT di Python melalui Pyomo . Anda mendapatkan bahasa pemodelan aljabar dan auto diff untuk jacobian dan hessian.
Antonello

@Antonello tautan yang diperbaiki adalah pyomo.org
Moonwalker

Saya bekerja di lab yang melakukan optimasi global masalah bilangan bulat dan non-cembung. Pengalaman saya dengan pemecah pengoptimalan sumber terbuka adalah bahwa yang lebih baik biasanya ditulis dalam bahasa yang dikompilasi, dan harganya lebih murah dibandingkan dengan paket pengoptimalan komersial.

Jika Anda dapat merumuskan masalah Anda sebagai sistem persamaan eksplisit dan membutuhkan pemecah gratis, taruhan terbaik Anda mungkin IPOPT, seperti kata Aron. Pemecah gratis lainnya dapat ditemukan di situs web COIN-OR . Setahu saya, pemecah nonlinier tidak memiliki binding Python yang disediakan oleh pengembang; setiap binding yang Anda temukan akan menjadi pihak ketiga. Untuk mendapatkan solusi yang baik, Anda juga harus membungkus pemecah cembung nonlinier yang Anda temukan dalam heuristik optimisasi global stokastik yang sesuai, atau dalam algoritma optimisasi global deterministik seperti cabang-dan-terikat. Sebagai alternatif, Anda dapat menggunakan Bonmin atau Couenne, yang keduanya merupakan pemecah optimisasi non-cembung deterministik yang berkinerja baik dengan baik dibandingkan dengan pemecah canggih, BARON .

Jika Anda dapat membeli pemecah optimasi komersial, Anda dapat mempertimbangkan melihat bahasa pemodelan GAMS , yang mencakup beberapa pemecah optimasi nonlinier. Disebutkan secara khusus adalah antarmuka untuk pemecah CONOPT, SNOPT, dan BARON. (CONOPT dan SNOPT adalah pemecah cembung.) Solusi kludgey yang saya gunakan di masa lalu adalah dengan menggunakan ikatan bahasa Fortran (atau Matlab) ke GAMS untuk menulis file GAMS dan memanggil GAMS dari Fortran (atau Matlab) untuk menghitung solusi masalah optimisasi. GAMS memiliki ikatan bahasa Python, dan staf dukungan yang sangat responsif bersedia membantu jika ada masalah. (Penafian: Saya tidak berafiliasi dengan GAMS, tetapi lab saya memiliki lisensi GAMS.) Pemecah masalah komersial tidak boleh lebih buruk darifmincon; sebenarnya, saya akan terkejut jika mereka tidak jauh lebih baik. Jika masalah Anda cukup kecil, maka Anda mungkin tidak perlu membeli lisensi GAMS dan lisensi untuk solver, karena salinan evaluasi GAMS dapat diunduh dari situs web mereka. Jika tidak, Anda mungkin ingin memutuskan solver mana yang akan dibeli bersamaan dengan lisensi GAMS. Perlu dicatat bahwa BARON membutuhkan pemecah pemrograman linear bilangan bulat, dan lisensi untuk dua pemecah program linear bilangan bulat bilangan bulat terbaik CPLEX dan GUROBI gratis untuk akademisi, jadi Anda mungkin bisa pergi hanya dengan membeli antarmuka GAMS sebagai gantinya daripada antarmuka dan lisensi pemecah, yang dapat menghemat banyak uang.

Poin ini diulangi: untuk setiap pemecah optimasi non-cembung deterministik yang telah saya sebutkan di atas, Anda harus dapat merumuskan model sebagai set persamaan eksplisit. Jika tidak, algoritma optimasi non-cembung tidak akan berfungsi, karena semuanya bergantung pada analisis simbolik untuk membangun relaksasi cembung untuk algoritma branch-and-bound-like.

UPDATE: Satu pemikiran yang tidak terpikir oleh saya pada awalnya adalah bahwa Anda juga dapat memanggil Toolkit untuk Pengoptimalan Tingkat Lanjut ( TAO ) dan PETSc menggunakan tao4py dan petsc4py , yang akan memiliki potensi manfaat tambahan dari paralelisasi yang lebih mudah, dan meningkatkan keakraban dengan PETSc dan alat ACTS .

PEMBARUAN # 2: Berdasarkan informasi tambahan yang Anda sebutkan, metode pemrograman kuadratik sekuensial (SQP) akan menjadi taruhan terbaik Anda. Metode SQP secara umum dianggap lebih kuat daripada metode titik interior, tetapi memiliki kelemahan karena membutuhkan pelarut linier padat. Karena Anda lebih peduli tentang ketahanan daripada kecepatan, SQP akan menjadi taruhan terbaik Anda. Saya tidak dapat menemukan pemecah SQP yang baik di luar sana yang ditulis dengan Python (dan tampaknya, tidak juga Sven Leyffer di Argonne dalam laporan teknis ini ). Saya menduga bahwa algoritma yang diimplementasikan dalam paket seperti SciPy dan OpenOpt memiliki kerangka dasar dari beberapa algoritma SQP yang diimplementasikan, tetapi tanpa heuristik khusus yang digunakan oleh kode yang lebih maju untuk mengatasi masalah konvergensi. Anda dapat mencoba NLopt, ditulis oleh Steven Johnson di MIT. Saya tidak memiliki harapan yang tinggi untuk itu karena tidak memiliki reputasi yang saya ketahui, tetapi Steven Johnson adalah orang yang cerdas yang menulis perangkat lunak yang baik (setelah semua, ia menulis bersama FFTW). Itu mengimplementasikan versi SQP; jika ini perangkat lunak yang bagus, beri tahu saya.

Saya berharap bahwa TAO akan memiliki sesuatu di jalan pemecah optimasi dibatasi, tetapi tidak. Anda tentu dapat menggunakan apa yang mereka miliki untuk membangunnya; mereka punya banyak komponen di sana. Seperti yang Anda tunjukkan, akan jauh lebih sulit bagi Anda untuk melakukan itu, dan jika Anda akan mengalami masalah seperti itu, Anda mungkin juga seorang pengembang TAO.

Dengan informasi tambahan itu, Anda lebih mungkin mendapatkan hasil yang lebih baik dengan memanggil GAMS dari Python (jika itu pilihan), atau mencoba menambal antarmuka IPOPT Python. Karena IPOPT menggunakan metode titik interior, itu tidak akan sekuat, tetapi mungkin implementasi Andreas dari metode titik interior jauh lebih baik daripada penerapan Matlab tentang SQP, dalam hal ini, Anda mungkin tidak mengorbankan ketahanan sama sekali. Anda harus menjalankan beberapa studi kasus untuk mengetahui dengan pasti.

Anda sudah mengetahui trik untuk merumuskan kembali batasan ketimpangan rasional sebagai kendala ketidaksetaraan polinomial (ada di buku Anda); alasan ini akan membantu BARON dan beberapa pemecah nonconvex lainnya adalah bahwa ia dapat menggunakan istilah analisis untuk menghasilkan ketidaksetaraan valid tambahan yang dapat digunakan sebagai potongan untuk meningkatkan dan mempercepat konvergensi pemecah.

Tidak termasuk pengikatan GAMS Python dan antarmuka Python ke IPOPT, jawabannya tidak, belum ada pemecah pemrograman nonlinier berkualitas tinggi untuk Python. Mungkin @Dominique akan mengubahnya dengan NLPy.

UPDATE # 3: Lebih banyak tikaman liar menemukan solver berbasis Python menghasilkan PyGMO , yang merupakan seperangkat ikatan Python ke PaGMO, sebuah solver optimisasi global multiobjective optimizer berbasis C ++. Meskipun ini dibuat untuk optimisasi multiobjek, ia juga dapat digunakan untuk pemrograman nonlinier objektif tunggal, dan memiliki antarmuka Python ke IPOPT dan SNOPT, di antara pemecah lainnya. Itu dikembangkan dalam Badan Antariksa Eropa , jadi mudah-mudahan ada komunitas di belakangnya. Itu juga dirilis relatif baru (24 November 2011).


harap dicatat PaGMO berlisensi GPL
denfromufa

APM Python

Pembaruan: lihat paket GEKKO baru yang baru saja kami rilis.

APM Python adalah kotak alat optimasi gratis yang memiliki antarmuka untuk APOPT, BPOPT, IPOPT, dan pemecah lainnya. Ini memberikan informasi pertama (Jacobian) dan kedua (Hessian) ke pemecah dan menyediakan antarmuka web opsional untuk melihat hasil. Klien APM Python diinstal dengan pip:

 pip install APMonitor

Itu juga dapat diinstal dalam skrip Python dengan:

try:
    from APMonitor.apm import *
except:
    # Automatically install APMonitor
    import pip
    pip.main(['install','APMonitor'])
    from APMonitor.apm import *

Kami telah melakukan beberapa tes benchmark dan menemukan bahwa kombinasi APOPT (metode set aktif) dan IPOPT (metode titik interior) dapat menyelesaikan sebagian besar masalah benchmark. Ada sejumlah contoh masalah yang disertakan dengan file zip unduhan. Salah satu yang mungkin ingin Anda mulai adalah masalah Hock Schittkowski # 71. Ini adalah contoh paling sederhana dan menunjukkan cara mengatasi masalah optimisasi terbatas.

Ada antarmuka browser dan API ke Python / MATLAB. API ke Python adalah skrip tunggal (apm.py) yang tersedia untuk diunduh dari beranda apmonitor.com. Setelah skrip dimuat ke dalam kode Python, skrip memberikan kemampuan untuk memecahkan masalah:

  • Persamaan nonlinier
  • Pemrograman integer campuran nonlinier campuran
  • Persamaan diferensial dan aljabar
  • Pemasangan model kuadrat terkecil
  • Estimasi cakrawala bergerak
  • Kontrol prediktif model nonlinier
  • dll.

Untuk pengguna baru, perangkat lunak APM Python memiliki forum Google Groups di mana pengguna dapat memposting pertanyaan. Ada webinar yang menampilkan masalah optimisasi dalam riset dan rekayasa operasi.

Di bawah ini adalah contoh masalah optimasi (hs71.apm).

Model
  Variables
    x[1] = 1, >=1, <=5
    x[2] = 5, >=1, <=5
    x[3] = 5, >=1, <=5
    x[4] = 1, >=1, <=5
  End Variables

  Equations
    x[1] * x[2] * x[3] * x[4] > 25
    x[1]^2 + x[2]^2 + x[3]^2 + x[4]^2 = 40

    minimize  x[1] * x[4] * (x[1]+x[2]+x[3]) + x[3]
  End Equations
End Model

Masalah optimisasi diselesaikan dengan skrip Python berikut:

from APMonitor.apm import *
server = 'http://byu.apmonitor.com'

# Application name
app = 'eqn'

# Clear previous application
apm(server,app,'clear all')

# Load model file
apm_load(server,app,'hs71.apm')

# Option to select solver (1=APOPT, 2=BPOPT, 3=IPOPT)
apm_option(server,app,'nlc.solver',3)

# Solve on APM server
solver_output = apm(server,app,'solve')

# Display solver output
print(solver_output)

# Retrieve results
results = apm_sol(server,app)

# Display results
print('--- Results of the Optimization Problem ---')
print(results)

# Display Results in Web Viewer 
url = apm_var(server,app)
print("Opened Web Viewer: " + url)

APM Python adalah layanan web gratis untuk pengoptimalan. Masalah optimisasi diselesaikan pada server jarak jauh dan hasilnya dikembalikan ke skrip Python lokal. Server lokal APMonitor juga tersedia untuk diunduh sehingga koneksi Internet tidak diperlukan ( Unduh server ). Kami baru-baru ini menambahkan dukungan pemrosesan paralel untuk MATLAB dan Python. Modul Python kompatibel dengan Python 2.7 atau Python 3+.


2
John, saya melihat bahwa APM Python tersedia secara bebas, tetapi saya tidak dapat mengetahui dari melihat paket apakah berisi pemecah yang digunakan secara lokal atau memerlukan koneksi ke situs web AP Monitor untuk melakukan perhitungan. Saya ingin tahu yang mana.
Aron Ahmadia

3
Aron, skrip MATLAB atau Python memerlukan koneksi internet ke server APM untuk menyelesaikan masalah optimisasi. Ini memiliki sejumlah kelebihan dan kekurangan. Di sisi positifnya, layanan web untuk optimasi memungkinkan kompatibilitas lintas platform, akses gratis ke beberapa pemecah komersial, dan peningkatan perangkat lunak yang transparan bagi pengguna. Pada sisi negatifnya, APM tidak sefleksibel beberapa alternatif open-source tetapi dirancang untuk pengguna industri yang menyukai solusi turn-key untuk aplikasi optimasi.
John Hedengren

@JohnHedengren Saya memiliki beberapa perhitungan di MATLAB menggunakan perpustakaan lain untuk membangun masalah optimasi itu sendiri, terutama, kendala melibatkan panggilan eksternal ini. Apakah menurut Anda APM masih cocok untuk tujuan ini?
gpavanb

Saya pikir istilah umum untuk itu adalah optimasi blackbox.
gpavanb

@ gpavanb Paket APMonitor membutuhkan persamaan yang akan ditulis dalam bahasa pemodelan. Salah satu opsi untuk memuat kode eksternal adalah membuat objek yang menyediakan residu dan setidaknya turunan analitik pertama. Kami biasanya memberi kode objek-objek ini dalam F90 untuk kecepatan seperti yang tercantum di sini: apmonitor.com/wiki/index.php/Main/Objects Saya tidak berpikir APMonitor adalah pilihan terbaik untuk aplikasi dengan optimasi blackbox.
John Hedengren

Meskipun ini tidak sepenuhnya menjawab pertanyaan Anda, saya menulis paket Python untuk pemrograman nonlinier bernama NLPy. Versi terbaru dapat diambil dari https://github.com/dpo/nlpy

Saya harus menekankan bahwa NLPy adalah riset-grade dan solver yang disertakan tidak sekuat kode yang lebih berpengalaman seperti IPOPT. Selain itu, mereka saat ini mensyaratkan agar orang-orang Jacobian disediakan. Yang sedang berkata, titik NLPy adalah untuk menyediakan alat yang dibutuhkan bagi para peneliti untuk mengumpulkan pemecah kustom jika mereka perlu. Bagaimanapun, saya akan tertarik untuk mendengar komentar Anda secara offline jika Anda mencobanya. Anda juga dapat menemukan paket terkait https://github.com/dpo/pykrylov dan https://github.com/dpo/pyorder berguna. Saat ini, dokumentasi NLPy jelas kurang. Dua lainnya harus masuk akal.


pyomo adalah lingkungan pemodelan penuh seperti GAMS / AMPL untuk optimisasi dalam python. Ini sangat kuat, memiliki antarmuka untuk semua pemecah yang didukung oleh AMPL, dan menghasilkan Jacobian dll secara otomatis. Namun, karena itu berjalan di 'lingkungan python virtual', mungkin tidak sepele untuk menautkannya ke kode yang ada.


GEKKO Python

Kami baru-baru ini merilis (2018) paket GEKKO Pythonuntuk pemrograman nonlinear dengan solver seperti IPOPT, APOPT, BPOPT, MINOS, dan SNOPT dengan set aktif dan metode titik interior. Salah satu masalah dengan menggunakan pemecah ini adalah bahwa Anda biasanya perlu menyediakan setidaknya turunan pertama dan opsional turunan kedua. Ada beberapa bahasa pemodelan bagus yang dapat melakukan ini untuk Anda, sebagaimana disebutkan dengan jawaban lain. GEKKO mengkompilasi persamaan ke kode byte sehingga seperti Anda menulis model dalam Fortran atau C ++ dalam hal kecepatan. Diferensiasi otomatis memberikan turunan 1 dan 2 dalam bentuk jarang ke pemecah berbasis gradien. Kami merancang GEKKO untuk masalah kontrol yang optimal tetapi juga dapat memecahkan masalah yang mirip dengan fmincon. Di bawah ini adalah contoh cepat dari masalah pemrograman nonlinear dengan kendala kesetaraan dan ketidaksetaraan. Pertama kamu'

pip install gekko

Masalah Hock Schittkowski # 71 ditunjukkan di bawah ini sebagai contoh fungsi objektif, kendala ketimpangan, kendala kesetaraan, dan empat variabel dengan batas atas dan bawah.

from gekko import GEKKO
m = GEKKO() # Initialize gekko
# Initialize variables
x1 = m.Var(value=1,lb=1,ub=5)
x2 = m.Var(value=5,lb=1,ub=5)
x3 = m.Var(value=5,lb=1,ub=5)
x4 = m.Var(value=1,lb=1,ub=5)
# Equations
m.Equation(x1*x2*x3*x4>=25)
m.Equation(x1**2+x2**2+x3**2+x4**2==40)
m.Obj(x1*x4*(x1+x2+x3)+x3) # Objective
m.options.IMODE = 3 # Steady state optimization
m.solve() # Solve
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('x3: ' + str(x3.value))
print('x4: ' + str(x4.value))    

GEKKO berfungsi pada semua platform (Windows, MacOS, Linux, prosesor ARM) dan dengan Python 2.7 dan 3+. Opsi sepenuhnya lokal tersedia tanpa koneksi Internet dengan mengatur opsi "remote = False". Opsi lokal saat ini hanya tersedia untuk Windows dan kami sedang mengerjakan versi lain seperti Linux, MacOS, prosesor ARM untuk dijalankan secara lokal tanpa koneksi internet. Versi lokal hanya mencakup pemecah gratis yang tidak memerlukan lisensi. Secara default, masalahnya dikirim ke server publik tempat solusinya dihitung dan dikembalikan ke Python.

Meskipun pertanyaan ini secara khusus tentang menyelesaikan pemrograman nonlinear dengan Python, saya juga akan menyoroti beberapa jenis masalah lain yang dapat dipecahkan oleh GEKKO dan beberapa sumber daya untuk mempelajari pengoptimalan. GEKKO juga memecahkan persamaan aljabar campuran-bilangan bulat dan diferensial dan memiliki beberapa objek yang diprogram untuk kontrol tingkat lanjut (mirip dengan DMC, RMPCT, dll). Mode operasi termasuk rekonsiliasi data, optimasi waktu nyata, simulasi dinamis, dan kontrol prediktif nonlinier.

Saya mengajar dua kursus tentang optimasi (optimasi desain dan optimasi dinamis ) dan telah memposting materi kursus online. Kursus optimisasi dinamis ditawarkan setiap tahun mulai bulan Januari dan kami menggunakan paket GEKKO Python (dan MATLAB) untuk kursus tersebut. GEKKO adalah perpanjangan dari APMonitor Optimization Suite tetapi telah mengintegrasikan pemodelan dan visualisasi solusi langsung dalam Python. Referensi APMonitor dan GEKKO memberikan contoh jenis aplikasi yang dapat diselesaikan dengan paket ini. GEKKO dikembangkan di bawah Hibah Penelitian Yayasan Sains Nasional # 1547110 .


Bisakah Anda mengedit jawaban Anda untuk menjelaskan bagaimana perangkat lunak Anda memenuhi persyaratan khusus yang disebutkan dalam pos? Kalau tidak, ini lebih mirip posting iklan selimut daripada jawaban untuk pertanyaan (dan kemungkinan akan ditutup).
Christian Clason

Christian, saya sudah mengedit respons untuk lebih spesifik pada pertanyaan. Saya memindahkan informasi tambahan tentang GEKKO dan kursus online hingga akhir tetapi dapat menghapusnya jika diperlukan.
John Hedengren


1
Terima kasih, tapi itulah yang saya coba (melalui OpenOpt, yang menyediakan antarmuka tambahan untuk itu). Itu tidak pernah lebih baik daripada fmincon / sqp dan gagal dalam banyak kasus di mana yang terakhir berhasil.
David Ketcheson

1
Pembaruan: Saya mencoba yang ini langsung dari SciPy. Gagal bahkan pada masalah di mana fmincon dapat secara konsisten menemukan optimum global dalam beberapa detik.
David Ketcheson

PyGMO berisi beberapa pemecah, menyediakan antarmuka yang sama dengannya. IPOPT dan slsqp licik disertakan jika Anda mengkompilasi kode dan mengunduh / menginstal kode pihak ketiga secara independen.

Sebagai bonus, penggunaan paralel solver dibuat sangat mudah (multistart) via kelas nusantara!


Ada cvxmod , pembungkus Python di sekitar perangkat lunak optimasi cembung Stephen Boyd. Itu bagian dari paket Sage .


Tetapi OP bertanya tentang masalah optimasi non-cembung.
Alejandro

1
OP bertanya tentang masalah optimasi non-cembung, tetapi semua solver yang disebutkan sejauh ini hanya dijamin untuk menemukan solusi optimal epsilon untuk masalah optimisasi cembung tanpa metaheuristik tambahan (multistart, atau algoritme optimasi global stokastik lainnya yang menyerukan deterministik, nonlinier, pemecah optimasi cembung) atau algoritma branch-and-bound-like (seperti branch-and-bound, branch-and-cut, dan branch-and-reduction) yang membutuhkan relaksasi fungsi dan kendala objektif. Jawaban ini tidak lebih buruk daripada yang lain yang disebutkan pada 11 Desember.
Geoff Oxberry

Geoff, bagaimana saya bisa menerapkan cvxmod ke masalah non-cembung?
David Ketcheson

Saya belum menggunakan perangkat lunak, tetapi secara teori, seperti pemecah cembung lainnya, Anda akan menggunakannya untuk menemukan solusi optimal secara lokal seperti Anda menggunakan fmincon sekarang (yang juga merupakan pemecah cembung). Salah satu cara untuk menggunakannya adalah multistart. Hasilkan daftar poin yang akan digunakan sebagai tebakan awal untuk pemecah cembung Anda. Untuk setiap titik yang digunakan sebagai tebakan, catat solusi yang dikembalikan oleh pemecah. Titik yang sesuai dengan nilai fungsi obyektif minimum atas semua solusi yang dikembalikan adalah perkiraan terbaik ke optimal global.
Geoff Oxberry

1
@ Geoff: Ya, saya menggunakan multistart. Sedangkan untuk CVXMOD, itu hanya menerima masalah yang dapat diutarakan dalam hal pemrograman cembung disiplin. Masalah pemrograman nonlinier umum tidak bisa. Seperti yang Anda katakan, saya bisa mencari relaksasi cembung berturut-turut yang mendekati masalah saya, tetapi seluruh tujuan di sini adalah agar saya melakukan lebih sedikit pekerjaan.
David Ketcheson







Pada Rilis 2014b, ini sekarang didukung oleh Matlab secara langsung; lihat mathworks.de/help/matlab/matlab-engine-for-python.html
Christian Clason

@Christian Clason, sepertinya tidak melakukan numpy-to-Matlab sama sekali? seperti halnya python-matlab-bridge. (Saya belum menggunakannya.)
denis

Tidak secara langsung (tampaknya memiliki kelas array matlab khusus), tetapi pasti ada cara untuk mengkonversi antara itu dan numpy. Akan ada beberapa overhead, tentu saja, karena penyalinan data, tapi itu mungkin kurang masalah untuk ukuran masalah yang disebutkan OP. (Belum menggunakannya sendiri; hanya berpikir saya akan menunjukkan pilihan.)
Christian Clason


Bagaimana dengan CMA-ES? Ini memiliki binding Python dan sangat cocok untuk nonconvex, masalah optimasi nonlinear dan saya telah menggunakannya sedikit: https://www.lri.fr/~hansen/cmaesintro.html

Instalasi melalui pip:

pip install cma

Berikut beberapa contoh kode dari situs web mereka:

import cma
help(cma)  # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol')  # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0]  # best evaluated solution
res[5]  # mean solution, presumably better with noise

Pengoptimal ini jauh dari yang diminta OP. Misalnya, tidak ada cara yang jelas tentang bagaimana menangani kendala kesetaraan atau ketidaksetaraan dengan CMA-ES.
ares

Karena MATLAB memiliki kompiler JIT sementara CPython belum (setidaknya, sampai Pypy mendapat dukungan penuh numpy). Sepertinya Anda menginginkan pemecah gratis yang mengungguli yang diproduksi secara komersial fmincon. Bukankah terlalu banyak?

IIRC di antara pemecah NLP komersial, hanya snopt yang menyediakan API Python sampai sekarang (meskipun agak jelek).

Pemecah OpenOpt mana yang sudah Anda coba? Berapa banyak variabel dan kendala yang Anda miliki dalam tugas nonkonversi Anda?

Anda dapat mencoba IPOPT melalui OpenOpt / Funcdesigner API tanpa instalasi pada server OpenOpt Sage (perhatikan gambar "switch from sage to python").

10300(x0.1)2+10300(y0.2)2(x,y)=(1,1)


2
Jika Anda membaca dengan seksama, saya hanya meminta sesuatu dengan kekuatan yang mirip dengan fmincon. Tidak perlu lebih baik, dan bahkan bisa lebih lambat.
David Ketcheson


Baik untuk disebutkan di sini bahwa pemecah Google Ceres sebenarnya adalah pengoptimal non-linear yang sangat kuat, yang digunakan dalam banyak proyek.

Ada juga pembungkus python yang tersedia di sini: https://github.com/rll/cyres


Bukankah itu Levenbeg-Marquardt? yang, meskipun bagus, jauh dari yang diinginkan OP
denis

Walaupun ceres adalah pemecah yang sangat bagus, ia tidak mendukung batasan kesetaraan sama sekali dan hanya mendukung batasan ketimpangan sebagai batas atas / bawah dari parameter (pada versi saat ini 1.12).
orzechow

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.