Apakah memberikan perkiraan gradien ke pengoptimal berbasis gradien tidak berguna?

Apakah tidak ada gunanya menggunakan algoritma optimasi berbasis gradien jika Anda hanya dapat memberikan gradien numerik? Jika tidak, mengapa memberikan gradien numerik di tempat pertama jika itu sepele untuk melakukan diferensiasi terbatas untuk perpustakaan optimasi itu sendiri?

[EDIT]

Hanya untuk memperjelas, pertanyaan saya memang lebih umum daripada aplikasi tertentu. Meskipun bidang aplikasi saya kebetulan optimasi kemungkinan di bawah berbagai kerangka kerja statistik.
Masalah saya dengan diferensiasi otomatis adalah sepertinya selalu ada masalah. Entah perpustakaan AD tidak dapat merambat ke panggilan perpustakaan eksternal (seperti BLAS) atau Anda harus mengolah ulang alur kerja Anda secara drastis sehingga membuatnya sulit untuk ditangani ... terutama jika Anda bekerja dengan jenis bahasa yang sensitif. Keluhan saya dengan AD adalah masalah yang terpisah sama sekali. Tapi saya ingin percaya!
Saya kira saya perlu merumuskan pertanyaan saya dengan lebih baik, tetapi saya melakukan pekerjaan dengan buruk. Jika memiliki opsi untuk menggunakan algoritma optimasi derivatif-bebas atau algoritma optimasi berbasis derivatif dengan peringatan bahwa saya hanya dapat memberikan gradien numerik, yang mana yang rata-rata akan lebih unggul?

optimization profesor bigglesworth
sumber

Apakah Anda mencoba bertanya mengapa orang memberikan gradien analitik alih-alih hanya menghitung perkiraan menggunakan perbedaan terbatas?

spektr

Pertanyaan saya adalah, dengan kata lain, misalkan persamaan Anda terlalu terlibat bagi Anda untuk menghitung gradien analitik, dapatkah algoritma optimisasi dependen gradien masih lebih unggul daripada yang tidak memerlukan gradien sama sekali?

profesor bigglesworth

Itu adalah pertanyaan berbeda yang Anda ajukan di atas. Anda mungkin dapat menghitung turunan numerik dengan cara lain, misalnya, elemen hingga.

nicoguaro

@nicoguaro Ya, dalam konteks pengoptimalan dengan persamaan diferensial parsial, itulah yang terjadi (dan, ini adalah salah satu bidang penelitian saya, itu adalah pemikiran pertama saya juga). Tetapi pertanyaannya tidak menyebutkan apa pun ke arah itu (dan lebih berguna dalam generalitas ini. Saya pikir).

Christian Clason

Juga, bahkan dalam kasus itu, itu adalah pertanyaan yang masuk akal: Bagaimana jika (sistem) PDE Anda begitu rumit sehingga Anda tidak dapat menurunkan persamaan adjoint untuk diselesaikan secara numerik untuk mendapatkan gradien? (Hal-hal ini dapat menjadi sangat buruk, terutama jika syarat batas non-standar terlibat.)

Christian Clason

Jawaban:

Untuk melengkapi jawaban Brian yang luar biasa, izinkan saya memberikan sedikit latar belakang (editorial). Metode optimisasi bebas turunan didefinisikan sebagai metode yang hanya menggunakan evaluasi fungsi, dan pada dasarnya semua variasi "sampel yang ditetapkan lebih atau kurang secara sistematis dan menyimpan nilai fungsi terbaik" - hanya itu yang dapat Anda lakukan dengan memberikan informasi. Metode-metode ini secara kasar dapat dibagi lagi menjadi

Metode stokastik , di mana pemilihan sampel secara acak acak (yang berarti bahwa keacakan adalah komponen penting; mungkin ada komponen deterministik lainnya). Metode-metode ini sering dimotivasi oleh proses fisik atau biologis dan memiliki nama yang sesuai seperti "simulasi anil", "algoritma genetika", atau "metode kawanan partikel / kunang-kunang / semut". Jarang ada teori konvergensi di luar "jika Anda mencoba cukup lama, Anda akan mencapai semua titik (termasuk minimizer) dengan probabilitas " (apakah itu akan terjadi - dengan probabilitas apa pun - sebelum kematian panas alam semesta adalah masalah lain ...) Sebagai ahli matematika, saya akan mempertimbangkan metode ini sebagai upaya terakhir: Jika Anda tidak tahu apa - apa $1$ tentang fungsi Anda, ini yang bisa Anda lakukan, dan Anda mungkin beruntung.
Metode deterministik , di mana pemilihan sampel tidak acak, yaitu berdasarkan murni pada evaluasi fungsi sebelumnya. Contoh paling terkenal mungkin adalah metode simpleks Nelder - Mead; yang lain menghasilkan metode pencarian yang ditetapkan . Penting untuk disadari bahwa ini hanya dapat berfungsi jika ada hubungan (yang dapat dieksploitasi) antara nilai fungsi pada titik yang berbeda - yaitu, beberapa kelancaran fungsi. Bahkan, teori konvergensi untuk, misalnya, metode Nelder - Mead didasarkan pada membangun non-seragampendekatan beda hingga dari gradien berdasarkan pada nilai-nilai fungsi pada simpul simpleks dan menunjukkan bahwa ia konvergensi dengan gradien yang tepat dan nol ketika simpleks berkontraksi ke suatu titik. (Varian berdasarkan pada pendekatan beda hingga standar disebut pencarian kompas .)
Metode berbasis model , di mana nilai-nilai fungsi digunakan untuk membangun model fungsi lokal (misalnya, dengan interpolasi), yang kemudian diminimalkan dengan menggunakan metode standar (berbasis gradien / Hessian). Karena pendekatan beda hingga sama dengan turunan pasti dari polinomial interpolant, pendekatan klasik "gradien numerik" juga termasuk dalam kelas ini.

Seperti yang Anda lihat, batasan antara kelas-kelas ini lancar, dan seringkali hanya masalah interpretasi. Tetapi moral harus jelas: Pastikan Anda menggunakan semua informasi yang tersedia tentang fungsi yang Anda minimalkan. Mengutip Cornelius Lanczos:

Kurangnya informasi tidak dapat diatasi dengan tipu daya matematika apa pun.

Lagi pula, jika Anda tidak tahu apa - apa tentang fungsi Anda, itu mungkin juga benar-benar acak, dan meminimalkan nilai acak adalah tugas orang bodoh ...

Christian Clason
sumber

Jika sasaran Anda lancar, maka menggunakan perkiraan perbedaan hingga ke turunan seringkali lebih efektif daripada menggunakan algoritme pengoptimalan gratis derivatif. Jika Anda memiliki kode yang menghitung turunannya dengan tepat maka biasanya lebih baik menggunakan kode itu daripada menggunakan perkiraan perbedaan hingga.

Meskipun beberapa pustaka optimasi akan menghitung perkiraan perbedaan hingga untuk Anda secara otomatis menggunakan heuristik untuk menentukan parameter ukuran langkah, akan lebih baik untuk menggunakan rutinitas Anda sendiri untuk menghitung perkiraan perbedaan hingga baik karena Anda memiliki pengetahuan yang lebih baik tentang ukuran langkah yang tepat atau karena struktur khusus dalam fungsi yang dapat dieksploitasi oleh kode Anda.

Pilihan lain yang sering bernilai sementara adalah menggunakan teknik diferensiasi otomatis untuk menghasilkan subrutin yang menghitung turunan analitik dari kode sumber untuk menghitung fungsi objektif itu sendiri.

Brian Borchers
sumber

+1 untuk diferensiasi otomatis . Ini sering jauh lebih baik daripada ekspresi simbolik a-priori untuk gradien atau pendekatan beda hingga.

leftaroundabout

Saya juga akan merekomendasikan menggunakan diferensiasi otomatis. Untuk fortran, coba tapenade dari INRIA Sophia-Antipolis, yang didasarkan pada transformasi sumber. Untuk C / C ++, ada lebih banyak pilihan seperti adol-c, mahir, sacado (bagian dari Trilinos). Semua ini didasarkan pada overloading operator dan lebih mudah digunakan, meskipun tidak terlalu efisien untuk masalah yang sangat besar.

cfdlab

Ada juga beberapa keadaan di mana diferensiasi otomatis (AD) mungkin sulit untuk diterapkan, tetapi diferensiasi langkah kompleks, yang kadang-kadang bisa berjumlah hampir sama dengan AD (selain mampu menghitung seluruh gradien sekaligus dengan mode terbalik) AD) dapat diterapkan dan relatif mudah diterapkan.

Mark L. Stone

Menanggapi pertanyaan yang direvisi: Jika tujuan Anda lancar (tidak ada gunanya menggunakan algoritma pengoptimalan berbasis turunan jika tidak) dan jika jumlah variabel cukup kecil (melakukan turunan beda hingga tidak bekerja dalam optimisasi terbatas PDE ), maka kemungkinan besar Anda akan lebih baik menggunakan metode optimisasi berbasis turunan dengan perkiraan perbedaan hingga daripada menggunakan teknik DFO.

Brian Borchers

Pertanyaan Anda bertanya tentang pengoptimal berbasis gradien, jadi saya pikir Brian benar. Saya hanya akan berbagi, karena saya sendiri saat ini berjuang dengan itu, beberapa masalah.

Masalah dengan perbedaan hingga adalah 1) kinerja, karena Anda harus mengevaluasi kembali fungsi lagi untuk setiap dimensi, dan 2) mungkin sulit untuk memilih ukuran langkah yang baik. Jika langkah terlalu besar, asumsi linearitas fungsi mungkin tidak berlaku. Jika langkahnya terlalu kecil, itu mungkin mengalami gangguan dalam fungsi itu sendiri, karena turunan memperkuat kebisingan. Yang terakhir dapat menjadi masalah nyata jika fungsi melibatkan penyelesaian persamaan diferensial. Jika dimungkinkan untuk menghitung gradien secara analitis, atau menggunakan persamaan sensitivitas, tentu akan lebih akurat dan mungkin lebih cepat.

Ada pendekatan lain yang dapat Anda coba jika Anda belum menginvestasikan terlalu banyak waktu dalam perangkat lunak, dan menjalankannya dengan aritmatika kompleks. Ini disebut diferensiasi langkah yang kompleks . Ide dasarnya adalah ketika Anda mengevaluasi fungsi, jika Anda ingin gradien sehubungan dengan parameter X, Anda mengatur bagian imajiner X ke angka eps yang sangat kecil . Setelah Anda melakukan perhitungan, bagian imajiner dari nilai fungsi, dibagi dengan eps , adalah gradien terhadap X. Ketika Anda ingin gradien terhadap Y, Anda harus melakukan semuanya lagi, tentu saja. Yang menarik dari itu adalah eps itubisa dibuat sangat kecil. Alasan kerjanya adalah bahwa aturan normal kalkulus diferensial secara tepat dicerminkan dalam aturan aritmatika kompleks.

Yang mengatakan, saya menganggapnya bukan obat mujarab, karena itu tidak selalu mudah untuk melakukan fungsi yang rumit dalam aritmatika kompleks, itu tidak layak jika gradien dapat dihitung secara analitis, dan dalam kasus persamaan diferensial itu persis sama dengan persamaan sensitivitas , yang saya lakukan seperlunya.

Mike Dunlavey
sumber

Saya pikir salah satu manfaat utama adalah kenyataan bahwa Anda tidak melakukan pengurangan dalam rumus beda hingga kompleks ini. Ketika saya membaca makalah beberapa waktu lalu berbicara tentang derivasi untuk metode ini, itu adalah salah satu poin yang tampaknya mereka valid secara eksperimen dibandingkan dengan rumus perbedaan hingga lainnya. Perbedaan ini memungkinkan ukuran langkah yang lebih kecil untuk dipilih sebelum kesalahan pembulatan menjadi masalah.

spektr

@ Choward: Benar. Itu yang cantik tentang itu. Saya skeptis. Beberapa rekan saya sepertinya berpikir itu adalah peluru ajaib. Saya menduga itu setara dengan persamaan sensitivitas, dan salah satu rekan kerja saya, ahli matematika terapan, membuktikannya.

Mike Dunlavey

Itu keren tentang persamaan sensitivitas. Ini adalah pendekatan yang menarik tetapi tentu saja dapat memiliki trade offs implementasinya. Dengan asumsi Anda ingin menggunakannya, Anda harus mendefinisikan versi kompleks dari fungsi Anda dan kemudian melakukan aljabar / perhitungan variabel kompleks tambahan, yang membuat evaluasi fungsi masing-masing lebih lama. Ini adalah salah satu dari hal-hal yang Anda harus mencari tahu apakah evaluasi fungsi yang lebih lambat sepadan dengan akurasi turunan yang ditambahkan.

spektr

@ Choward: Itulah kesimpulan saya datang, ditambah kami biasanya mengoptimalkan vektor, yang berarti evaluasi berulang. Tentu saja, alternatifnya adalah persamaan sensitivitas bisa sulit untuk diturunkan. Saya menggunakan diferensiasi simbolis, dan mereka masih rumit. Seluruh subjek adalah bidang pertambangan.

Mike Dunlavey