Apakah diketahui bahwa beberapa masalah pengoptimalan setara dengan loncatan waktu?

Diberikan keadaan yang diinginkan $y_0$ dan parameter regularisasi , pertimbangkan masalah menemukan keadaan dan kontrol untuk meminimalkan fungsional tunduk pada kendala \ begin {persamaan} Ay = u. \ end {persamaan} di mana untuk kesederhanaan kita dapat memikirkan y, y_0, u \ in \ mathbb R ^ n dan A \ in \ mathbb R ^ {n \ kali n} . y u $\beta \in \mathbb R$$y$$u$Ay=u. y,y0,u∈RnA∈Rn×

$$\begin{equation} \frac{1}{2} \| y - y_0 \|^2 + \frac{\beta}{2} \| u \|^2 \end{equation}$$ $$\begin{equation} Ay = u. \end{equation}$$ $y, y_0, u \in \mathbb R^n$$A \in \mathbb R^{n \times n}$

Membentuk Lagrangian, mencari titik stasioner, dan menghilangkan kontrol $u$ kita mendapatkan kondisi orde pertama

$$\begin{align*} A^T \lambda &= y_0 - y \\ Ay &= \frac{1}{\beta} \lambda \end{align*}$$ Premultiplying oleh $A$ pada persamaan pertama dan $A^T$ di persamaan kedua, kita dapat menulis persamaan normal $$\begin{align} (I + \beta A A^T) \lambda &= \beta A y_0 \\ (I + \beta A^T A) y &= y_0 \end{align}$$ Kita dapat menafsirkan ini sebagai langkah tunggal perkiraan Euler mundur ke persamaan diferensial $$\begin{align} \frac{\partial \lambda}{\partial b} &= -A A^T \lambda + A y_0, \quad \lambda(0) = 0 \\ \frac{\partial y}{\partial b} &= -A^T A y, \quad y(0) = y_0 \end{align}$$ dengan pseudotimestep $\beta$ .

Pertanyaan saya: Apakah koneksi ini terkenal? Apakah ini dibahas dalam perawatan standar baik pencatat waktu atau optimasi? (Bagi saya, sepertinya memberikan semacam koneksi intuitif di antara mereka.)

Gagasan itu tampaknya cukup sederhana sehingga harus diketahui dengan baik, tetapi tidak mencari literatur atau berbicara dengan orang-orang telah memberi saya sumber yang baik di mana ini dibahas. Yang paling dekat yang saya temukan adalah makalah oleh O. Scherzer dan J. Weichert (J. Math Imaging Vision 12 (2000) hal. 43-63) yang menyatakan hubungan dalam kalimat pertama dari abstrak (!) Tetapi tidak memberikan referensi atau menjelajahi koneksi secara mendalam.

Idealnya saya mencari referensi yang tidak hanya menyatakan koneksi tetapi juga mengeksplorasi beberapa konsekuensi (misalnya, orang bisa membayangkan memprakondisi masalah optimasi dengan langkah Euler maju yang murah).

Seperti yang disebutkan Jed Brown, hubungan antara penurunan gradien dalam optimasi nonlinier dan loncatan waktu dari sistem dinamis ditemukan kembali dengan beberapa frekuensi (dapat dimengerti, karena ini adalah koneksi yang sangat memuaskan dengan pikiran matematika karena menghubungkan dua bidang yang tampaknya berbeda). Namun, ini jarang menjadi koneksi yang bermanfaat , terutama dalam konteks yang Anda gambarkan.

Dalam masalah terbalik, orang yang tertarik dalam memecahkan persamaan operator (ill-posed) dengan tidak di kisaran . (Masalah kontrol optimal Anda dapat dilihat sebagai satu contoh dengan dan .) Beberapa strategi regularisasi (seperti Tikhonov atau Landweber) dapat diartikan sebagai waktu semu tunggal langkah kelas tertentu. Idenya adalah untuk menggunakan interpretasi dari parameter regularisasi sebagai panjang langkah untuk mendapatkan beberapa aturan pilihan (adaptif, a posteriori) untuk parameter - masalah mendasar dalam masalah terbalik - dan mungkin membuat beberapa langkah waktu semu untuk mendekati solusi sejati yang tidak diatur (mirip dengany δ F F = A - 1 y δ = y $F(u)=y^\delta$$y^\delta$$F$$F=A^{-1}$$y^\delta = y_0$kelanjutan numerik ). Ini kadang-kadang disebut regularisasi berkelanjutan , dan biasanya dibahas dalam konteks metode level set; lihat, misalnya, Bab 6.1 dari Kaltenbacher, Scherzer, Neubauer: Metode Regularisasi Iteratif untuk Masalah-Masalah Non-Linier yang Berpose Tidak Benar (de Gruyter, 2008).

Konteks kedua ide ini berulang kali muncul adalah optimasi nonlinier: Jika Anda melihat langkah penurunan gradien untuk , maka Anda dapat menafsirkan ini sebagai maju Euler langkah untuk sistem dinamik Seperti yang Jed Brown tunjukkan, pada pandangan pertama ini hanya menghasilkan pengamatan yang tidak terlalu mengejutkan bahwa metode ini bertemu, asalkan langkah pseudo-time cukup kecil. Bagian yang menarik datang ketika Anda melihat sistem dinamis dan bertanya pada diri sendiri apa sifat solusi kontinu dari apa yang disebut aliran gradienx k + 1 = x k - γ k ∇ f ( x k ) , ˙ x ( t ) = - ∇ f ( x ( t ) ) $\min_x f(x)$

$$x^{k+1} = x^k - \gamma_k \nabla f(x^k),$$ γ k x ( t $$\dot x(t) = -\nabla f(x(t)),\qquad x(0) = x^0.$$ $\gamma_k$$x(t)$memiliki (atau seharusnya memiliki), independen dari penurunan gradien, dan apakah itu mungkin tidak mengarah pada waktu yang lebih tepat melangkah (dan karenanya optimasi) metode daripada standar Euler. Beberapa contoh dari atas kepala saya:

1. Apakah ada ruang fungsi alami di mana aliran gradien hidup? Jika demikian, langkah gradien Anda harus diambil dari ruang yang sama (yaitu, diskritisasi harus sesuai). Ini mengarah, misalnya, untuk menghitung representasi Riesz dari gradien sehubungan dengan produk dalam yang berbeda (kadang-kadang disebut gradien Sobolev ) dan, dalam praktiknya, untuk iterasi yang dikondisikan sebelumnya yang konvergen yang jauh lebih cepat.

2. Mungkin seharusnya bukan milik ruang vektor, tetapi untuk manifold (misalnya, matriks pasti positif simetris), atau aliran gradien harus menghemat norma tertentu . Dalam hal ini, Anda dapat mencoba menerapkan skema loncatan waktu-mempertahankan struktur (misalnya, melibatkan tarik-mundur sehubungan dengan kelompok Lie yang sesuai atau integrator geometrik).$x$$x$

3. Jika tidak dapat dibedakan tetapi cembung, langkah Euler ke depan sesuai dengan metode keturunan subgradien yang bisa sangat lambat karena batasan ukuran langkah. Di sisi lain, langkah Euler implisit berhubungan dengan metode titik proksimal , yang tidak ada batasan seperti itu (dan yang dengan demikian telah menjadi sangat populer di, misalnya, pemrosesan gambar).$f$

4. Dalam nada yang sama, metode seperti itu dapat dipercepat secara signifikan dengan langkah-langkah ekstrapolasi. Salah satu cara untuk memotivasi ini adalah dengan mengamati bahwa metode standar orde pertama menderita karena harus membuat banyak langkah kecil dekat dengan minimizer, karena arah gradien "berosilasi" (pikirkan ilustrasi standar mengapa gradien konjugat mengungguli penurunan curam). Untuk memperbaiki ini, seseorang dapat "meredam" iterasi dengan tidak menyelesaikan sistem dinamika orde pertama, tetapi sistem orde dua teredam : untuk dipilih dengan . Dengan diskritisasi yang tepat, ini mengarah ke iterasi (dikenal sebagai metode bola berat Polyak ) dari formulir

   $$a_1 \ddot x(t) + a_2 \dot x(t) = -\nabla f(x(t))$$ $a_1,a_2$ $$x^{k+1} = x^k - \gamma_k \nabla f(x^k) + \alpha_k (x^k - x^{k-1})$$ (dengan tergantung pada ). Gagasan serupa ada untuk metode titik proksimal, lihat, misalnya, makalah http://arxiv.org/pdf/1403.3522.pdf oleh Dirk Lorenz dan Thomas Pock.$\gamma_k,\alpha_k$$a_1,a_2$

---

(Saya harus menambahkan itu sepengetahuan saya, dalam sebagian besar kasus ini penafsiran sebagai sistem dinamis tidak sepenuhnya diperlukan untuk derivasi atau bukti konvergensi algoritma; orang dapat berpendapat bahwa ide-ide seperti "implisit vs eksplisit" atau turunan Lie) sebenarnya lebih mendasar daripada sistem dinamik atau metode gradient descent. Namun, tidak ada salahnya memiliki sudut pandang lain untuk melihat masalah.)

---

EDIT: Saya baru saja menemukan contoh yang sangat baik dari konteks kedua, di mana interpretasi ODE digunakan untuk menyimpulkan sifat-sifat metode ekstragradien Nesterov dan menyarankan perbaikan: http://arxiv.org/pdf/1503.01243.pdf (Perhatikan bahwa ini juga contoh dari poin Jed Brown, di mana penulis pada dasarnya menemukan kembali poin 4 di atas tanpa tampaknya menyadari algoritma Polyak.)

EDIT 2: Dan sebagai indikasi seberapa jauh Anda dapat mengambil ini, lihat halaman 5 dari http://arxiv.org/pdf/1509.03616v1.pdf .

Sementara saya belum melihat formulasi yang tepat yang telah Anda tulis di sini, saya terus melihat pembicaraan di mana orang-orang "menemukan kembali" koneksi untuk mengintegrasikan beberapa sistem sementara, dan melanjutkan untuk menulis algoritma yang secara aljabar-equilavent ke satu bentuk atau lain dari keturunan gradien yang ada atau metode seperti-Newton, dan gagal mengutip orang lain. Saya pikir itu tidak terlalu berguna karena kesimpulannya pada dasarnya adalah "selama Anda mengambil langkah-langkah yang cukup kecil, metode ini akhirnya menyatu ke minimum lokal". Nah, 2014 menandai peringatan ke-45 makalah Philip Wolfe yang menunjukkan bagaimana melakukan ini dengan cara yang berprinsip. Ada juga teori yang baik untuk memperoleh konvergensi q-kuadratik atau q-superlinear dari kelanjutan pseudotransient dan metode terkait seperti Levenberg-Marquardt.

Jika Anda ingin contoh penemuan kembali ini menggunakan formulasi mirip-Newton untuk menyelesaikan persamaan aljabar (yaitu, kelanjutan pseudotransient klasik) dari seorang ahli matematika dengan lebih dari 600 makalah (jadi mungkin dia akan membuktikan hal-hal yang menurut Anda menarik), lihatlah " Metode Sistem Dinamis "oleh AG Ramm [1].

Jika intuisi diperoleh dengan mempertimbangkan sistem sementara menyebabkan algoritma praktis yang lebih cepat atau lebih dapat diandalkan, saya pikir kita akan melihat artikel yang sangat dikutip tentang masalah itu. Saya pikir bukan misteri bahwa Nocedal dan Wright memiliki lebih dari 13000 kutipan, sementara buku Ramm memiliki sekitar 80 (kebanyakan kutipan sendiri).

[1] Saya dapat menyarankan Anda untuk tidak memberi tahu Prof. Ramm bahwa DSM-nya setara secara aljabar dengan sesuatu yang telah ada dalam paket-paket teknik yang tak terhitung jumlahnya selama beberapa dekade atau Anda mungkin bisa berteriak ke luar ruangan. #gradstudentmemories

Jika metode ODE dapat berkontribusi untuk optimasi, apakah ada contoh masalah yang sangat sederhana untuk menunjukkan ini?
Seorang pria jerami: apakah ada pemecah ODE yang melakukan pekerjaan yang masuk akal
$\qquad \dot{ x } = - \nabla f( x )$
$\quad \ddot{ x } = \beta \dot{ x } - \alpha \nabla f( x ) \ \ $
$f$

Dalam praktiknya, langkah "terlalu besar" jauh lebih bermasalah daripada "terlalu kecil" - osilasi berantakan.
Saya berpikir dengan naif bahwa teori kontrol dapat membantu. Resep Numerik hal. 915 menjelaskan
kontrol stepsize adaptif PI untuk ODE, tapi saya tidak tahu apakah ini digunakan dalam praktik.