Tentang edisi terpadu ini
Status dan hak komponen. Pembaca ini menyatukan bahan yang sudah diterima ke dalam satu urutan kursus tanpa mengubah kepemilikan atau lisensi masing-masing komponen. Tulang punggung terstruktur adalah terjemahan lengkap catatan Andreas Habring, arXiv:2607.11664v1, berdasarkan Creative Commons Attribution 4.0 International (CC BY 4.0). Tiga suplemen terbatas dari catatan Stephen Becker yang diketik Mitchell Krock digunakan berdasarkan Lisensi MIT. Bab penghubung, asesmen, solusi, laboratorium, dan proyek yang ditulis khusus untuk edisi ini tersedia berdasarkan Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0). Tidak ada klaim lisensi payung.
Edisi Bahasa Indonesia ini mandiri dan bukan edisi resmi atau dukungan Habring, Becker, Krock, institusi mereka, ataupun penyedia sumber pendamping. Materi MIT OpenCourseWare, Clément Royer, dan Penn State tetap menjadi pembaca pendamping terpisah. Materi O018 tentang program linear atau bilangan bulat, simpleks, sensitivitas LP, dan optimisasi jaringan berada di luar cakupan.
Produksi edisi dan pemeriksaan deterministik menggunakan OpenAI Codex gpt-5.6-sol, Ultra. Semua kredit pengarang sumber dan kontribusi manusia tetap dipertahankan. HTML dan EPUB 3 ini adalah permukaan reflow utama; rumus disajikan sebagai MathML dengan anotasi TeX sumber untuk sistem baca yang mendukungnya.
Tulang Punggung: Optimisasi Konveks
Prakata
Catatan ini dibangun di atas slide kuliah yang disusun oleh Prof. Thomas Pock. Naskah ini belum merupakan versi final dan mungkin masih memuat salah ketik atau kesalahan, serta kekurangan teks penghubung di antara hasil-hasilnya. Catatan ini terutama berfungsi sebagai kumpulan materi untuk kuliah terkait yang saya ampu pada semester musim panas 2026 di Graz University of Technology.
Saya berterima kasih kepada Prof. Christian Clason atas templat LaTeX yang indah ini.
Prasyarat
Ruang vektor, norma, dan hasil kali dalam
Ruang vektor atas suatu medan adalah himpunan yang dilengkapi dengan dua operasi , , dan , , sedemikian sehingga
merupakan grup Abel; yaitu, untuk setiap berlaku:
Asosiativitas: .
Unsur netral: terdapat sehingga . Kita menuliskan .
Unsur invers: terdapat sehingga . Kita menuliskan .
Komutativitas: .
Hukum-hukum skalar berikut berlaku untuk setiap dan :
.
.
.
.
Kita menuliskan .
Mulai sekarang kita membatasi pembahasan pada .
: ruang vektor yang terdiri atas vektor berbentuk dengan , penjumlahan dilakukan komponen demi komponen, dan perkalian skalar diterapkan pada setiap komponen. Suatu hasil matematika penting menyatakan bahwa setiap ruang vektor berdimensi hingga dapat diidentifikasi dengan , dengan dimensinya. Karena itu, ketika bekerja dengan ruang berdimensi hingga, kita biasanya dapat membayangkan .
Ruang fungsi: misalkan dan . Kita dapat mendefinisikan serta, untuk , secara titik demi titik melalui Dengan cara ini kita dapat membentuk berbagai ruang fungsi. Salah satu contohnya ialah ruang fungsi linear. Mengapa ini benar-benar merupakan ruang vektor yang terdefinisi dengan baik?
Norma adalah fungsi sedemikian sehingga, untuk setiap dan , berlaku
Ketegasan positif: jika dan hanya jika .
Homogenitas: .
Ketaksamaan segitiga: .
Pasangan disebut ruang bernorma.
Berdasarkan kodomainnya, norma selalu tak negatif.
Mulai sekarang semua ruang vektor dianggap bernorma. Jika tidak menimbulkan ambiguitas, kita cukup menuliskan normanya sebagai . Untuk menyatakan norma tertentu kita menggunakan, misalnya, , dengan suatu simbol yang menandai norma tersebut; bandingkan [preliminiaries:example:norms].
Norma : untuk kita menuliskan Untuk kita menuliskan
Tinjau ruang matriks , yaitu . Setiap matriks dapat diidentifikasi dengan fungsi linear melalui Norma-norma berikut sering digunakan pada :
Norma Frobenius: .
Norma terinduksi: untuk setiap pasangan norma pada dan pada , kita mendefinisikan Norma terinduksi memenuhi . Jika , kita menuliskan . Secara khusus,
Di sini menyatakan nilai eigen terbesar.
Untuk fungsi terukur Lebesgue , dengan terukur, kita dapat mendefinisikan norma melalui dan1 Dengan mengidentifikasi fungsi-fungsi yang sama hampir di mana-mana, mendefinisikan norma pada ruang vektor
Semua norma pada ekuivalen. Artinya, untuk setiap dua norma dan , terdapat sedemikian sehingga untuk setiap berlaku
Pemetaan disebut hasil kali skalar atau hasil kali dalam jika, untuk setiap dan skalar yang relevan, berlaku
Bilinearitas: pemetaan dan bersifat linear.
Ketegasan positif: , dan kesamaan berlaku jika dan hanya jika .
Simetri: .
Setiap hasil kali dalam mendefinisikan norma melalui . Dalam hal ini, disebut ruang hasil kali dalam.
Pada setiap ruang hasil kali dalam berlaku dan ketaksamaan kedua bersifat ketat apabila dan tidak kolinear.
Proof. Kita boleh mengandaikan , sebab jika tidak hasilnya langsung berlaku. Untuk setiap , Ambil . Maka yang memberikan . Jika dan tidak kolinear, maka untuk setiap , sehingga ketaksamaan dalam [preliminaries:eq:CS], dan dengan demikian ketaksamaan Cauchy–Schwarz, bersifat ketat. ◻
Misalkan memenuhi 2. Untuk setiap yang dilengkapi dengan hasil kali dalam baku, berlaku
Proof. Kita membedakan kasus-kasus berikut.
dan : dengan mudah diperoleh Kasus , mengikuti dengan menukar dan .
: ketaksamaan jelas benar jika atau , sehingga andaikan . Ketaksamaan Young menyatakan bahwa untuk eksponen konjugat dan berlaku . Karena itu, Mengganti dengan dan dengan dalam [eq:prelim:hoelder] memberikan
◻
Dengan ketaksamaan Hölder, kita dapat menunjukkan bahwa norma memenuhi ketaksamaan segitiga, yaitu bagian tersulit dalam membuktikan bahwa besaran tersebut benar-benar merupakan norma.
Untuk setiap berlaku
Proof. Kasus ditinggalkan sebagai latihan sederhana. Jadi, andaikan . Kita boleh mengandaikan , sebab jika tidak hasilnya langsung berlaku. Dengan ketaksamaan Hölder dan hubungan , diperoleh Membagi kedua ruas dengan menyelesaikan bukti. ◻
Barisan dan topologi dasar
Barisan disebut konvergen jika terdapat sedemikian sehingga untuk setiap terdapat dengan
Berdasarkan ekuivalensi norma, kekonvergenan tidak bergantung pada pilihan norma.
Barisan disebut barisan Cauchy jika dan hanya jika untuk setiap terdapat sedemikian sehingga bagi setiap .
Sifat Cauchy serupa dengan kekonvergenan. Namun, perhatikan bahwa sifat Cauchy dapat dirumuskan tanpa gagasan titik limit. Hasil berikut mudah dibuktikan.
Setiap barisan konvergen merupakan barisan Cauchy.
Proof. Misalkan . Ketaksamaan segitiga memberikan dan kedua suku di ruas kanan dapat dibuat sekecil yang diinginkan dengan memilih cukup besar. ◻
Ruang bernorma disebut ruang Banach jika setiap barisan Cauchy konvergen. Artinya, jika merupakan barisan Cauchy, terdapat sehingga ketika . Jika normanya berasal dari suatu hasil kali dalam, ruang Banach tersebut disebut ruang Hilbert.
Ruang merupakan ruang Banach untuk setiap .
Suatu himpunan disebut
terbuka jika untuk setiap terdapat sehingga ;
tertutup jika terbuka. Ketertutupan ekuivalen dengan sifat berikut: jika dan , maka .
Himpunan disebut kompak secara sekuensial jika setiap barisan di mempunyai suatu subbarisan yang konvergen ke titik di . Dengan kata lain, untuk setiap terdapat subbarisan dan titik sedemikian sehingga .
Dalam ruang vektor berdimensi hingga, setiap barisan terbatas mempunyai subbarisan konvergen.
Proof. Pertama andaikan dimensinya satu, sehingga ruangnya adalah . Misalkan terbatas. Secara induktif kita membangun dua barisan dan dengan , , , dan, yang terpenting, memuat tak hingga banyaknya suku untuk setiap .
Karena barisan terbatas, pilih sehingga . Jelas interval ini memuat tak hingga banyaknya suku . Andaikan telah dipilih dan tetapkan . Karena memuat tak hingga banyaknya suku , setidaknya salah satu dari dan juga memuat tak hingga banyaknya suku. Pilih interval tersebut sebagai .
Sekarang kita membangun subbarisan secara induktif. Pilih sehingga . Jika telah dipilih, tetapkan, misalnya, . Pilihan ini selalu mungkin karena interval tersebut memuat tak hingga banyaknya suku barisan.
Akhirnya, ambil sembarang . Karena , berlaku Jadi merupakan barisan Cauchy dan karenanya konvergen.
Untuk dimensi lebih besar, yaitu , mula-mula pilih subbarisan yang komponen pertamanya konvergen. Dari subbarisan itu pilih lagi subbarisan yang komponen keduanya konvergen, dan lanjutkan demikian. Subbarisan diagonal yang diperoleh setelah langkah ke- mempunyai semua komponen yang konvergen; khususnya, subbarisan itu konvergen dalam norma satu. Ekuivalensi norma kemudian memberikan kekonvergenan dalam setiap norma. ◻
Sebagai akibatnya, kita memperoleh hasil berikut.
Di , suatu himpunan kompak jika dan hanya jika tertutup dan terbatas.
Proof. Misalkan tertutup dan terbatas, serta . Berdasarkan keterbatasan dan [thm:bolzano], terdapat subbarisan konvergen; berdasarkan ketertutupan, limitnya berada di . Jadi kompak.
Sebaliknya, andaikan kompak. Jika tidak terbatas, untuk setiap kita dapat memilih dengan . Barisan ini tidak mempunyai subbarisan konvergen, bertentangan dengan kekompakan. Jadi terbatas. Selanjutnya, misalkan dan . Berdasarkan kekompakan, mempunyai subbarisan yang konvergen ke suatu titik di . Setiap subbarisan dari barisan konvergen mempunyai limit yang sama, sehingga . Jadi tertutup. ◻
Fungsi
Misalkan suatu pemetaan di antara dua ruang bernorma. Fungsi disebut kontinu di jika salah satu dari dua syarat ekuivalen berikut dipenuhi:
untuk setiap barisan , berlaku ;
untuk setiap terdapat sedemikian sehingga
Jika kontinu pada setiap , kita cukup mengatakan bahwa kontinu.
Misalkan suatu pemetaan di antara dua ruang bernorma. Fungsi disebut kontinu Lipschitz jika terdapat sedemikian sehingga
Pemetaan linear dan ruang dual
Fungsi disebut linear jika
Pemetaan linear dapat diidentifikasi dengan matriks.
Ruang semua fungsi linear isomorfik3 dengan ruang semua matriks .
Proof. Kita mendefinisikan korespondensi satu-ke-satu dengan mengaitkan setiap pada matriks yang diberikan oleh Pembuktian bahwa korespondensi ini bijektif dan linear ditinggalkan sebagai latihan. ◻
Misalkan suatu ruang bernorma. Ruang dual adalah ruang vektor semua fungsional linear kontinu dari ke , yaitu Unsur disebut fungsional linear pada . Norma kanonik pada adalah norma dual Dengan sedikit penyalahgunaan notasi, penerapan suatu unsur dual juga sering ditulis memakai notasi hasil kali dalam:
Langsung dari definisi diperoleh
Hasil berikut sangat penting: pada ruang Hilbert, ruang dual dapat diidentifikasi dengan ruang itu sendiri. Hasil ini juga membenarkan penggunaan notasi hasil kali dalam untuk penerapan unsur dual.
Misalkan ruang Hilbert. Untuk setiap terdapat tepat satu sedemikian sehingga Pemetaan linear dan memenuhi . Secara khusus, .
Proof. Jika , ambil . Jadi, andaikan . Karena merupakan subruang tertutup, teorema proyeksi ortogonal pada ruang Hilbert memberikan . Komponen ortogonal dari sembarang titik di luar kernel tidak nol; setelah dinormalkan, kita memperoleh dengan dan . Untuk sembarang , sehingga, berdasarkan ortogonalitas terhadap , Akibatnya, Jadi merupakan unsur yang dicari. Ketunggalan, linearitas pemetaan representasi, dan kesamaan normanya ditinggalkan sebagai latihan. ◻
Pada , untuk , norma dual dari tepat sama dengan , dengan .
Sebagian besar pembaca mungkin telah mengenal adjoin atau transpos suatu matriks, yang diperoleh dengan menukar baris dan kolom. Untuk , adjoin didefinisikan oleh Dengan hasil kali dalam baku, mudah diperiksa bahwa untuk setiap dan berlaku Sifat terakhir inilah yang mencirikan definisi formal adjoin suatu pemetaan linear. Secara khusus, adjoin bergantung pada hasil kali dalam yang dipilih.
Misalkan pemetaan linear kontinu di antara dua ruang Hilbert. Operator adjoin didefinisikan oleh
Tunjukkan bahwa adjoin merupakan operator linear yang terdefinisi dengan baik.
Misalkan ruang Hilbert. Untuk pemetaan linear kontinu dan , berlaku
;
;
jika dan linear kontinu, maka .
Proof. Latihan. ◻
Misalkan ruang vektor. Fungsi disebut fungsi bernilai real diperluas. Fungsi disebut proper jika tidak pernah bernilai dan terdapat dengan . Domain efektif suatu fungsi proper didefinisikan sebagai
Fungsi bernilai real diperluas yang sering digunakan adalah fungsi indikator. Untuk , fungsi indikator didefinisikan oleh Dengan fungsi indikator, masalah optimisasi berkendala dapat ditulis ulang sebagai masalah tak berkendala:
Epigraf fungsi didefinisikan sebagai Fungsi disebut tertutup jika epigrafnya merupakan himpunan tertutup.
Jika tertutup, tunjukkan bahwa juga tertutup.
Apakah domain suatu fungsi tertutup harus tertutup? Buktikan atau berikan contoh penyangkal.
Fungsi disebut semikontinu bawah (lower semicontinuous, lsc) jika untuk setiap barisan di berlaku
Fungsi tertutup jika dan hanya jika semikontinu bawah.
Proof. : andaikan tertutup, , dan tuliskan . Jika , ketaksamaan yang diinginkan langsung berlaku. Jika , ambil subbarisan dengan Untuk cukup besar nilainya hingga, sehingga dan Ketertutupan epigraf memberikan , jadi . Terakhir, tidak mungkin: untuk setiap kita dapat memilih subbarisan dengan ; maka dan ketertutupan akan memberikan untuk setiap , bertentangan dengan kodomain .
: sekarang andaikan semikontinu bawah dan dengan dalam . Khususnya, . Oleh semikontinuitas bawah, Jadi , yang membuktikan bahwa epigrafnya tertutup. ◻
Jika pembatasan pada kontinu dan tertutup, maka tertutup.
Proof. Latihan. ◻
Deskripsi figur nonraster. Kegagalan semikontinuitas bawah dapat menyebabkan infimum tidak tercapai.
Deskripsi gambar. Kedua panel menampilkan fungsi sepotong-sepotong yang mempunyai lompatan di . Pada panel kiri, cabang kanan mendekati titik kosong sementara nilai fungsi di adalah titik penuh ; infimum tidak tercapai. Pada panel kanan, titik diisi dan titik dibiarkan kosong, sehingga nilai minimum tercapai.
Fungsi disebut koersif jika
Misalkan berdimensi hingga dan proper, koersif, serta semikontinu bawah. Maka mencapai minimumnya pada .4
Proof. Bukti mengikuti apa yang disebut metode langsung.
Langkah 1: Ambil barisan peminimum.
Misalkan suatu barisan peminimum5, yaitu
Langkah 2: Tunjukkan keterbatasan barisan.
Karena koersif, barisan peminimum harus terbatas. Jika tidak, terdapat subbarisan dengan . Koersivitas kemudian memberikan yang bertentangan dengan
Langkah 3: Gunakan kekompakan untuk mengambil subbarisan konvergen.
Berdasarkan [thm:bolzano], setiap barisan terbatas dalam ruang vektor berdimensi hingga mempunyai subbarisan konvergen. Jadi kita dapat mengambil subbarisan dengan limit .
Langkah 4: Simpulkan dengan semikontinuitas bawah.
Berdasarkan semikontinuitas bawah , Jadi semua ketaksamaan merupakan kesamaan dan adalah peminim. ◻
Kekonveksan
Tujuan kita dalam kuliah ini adalah menyelesaikan masalah berbentuk dengan suatu himpunan bagian konveks dari ruang dan suatu fungsi konveks. Oleh karena itu, pada bagian berikut kita menganalisis secara lebih terperinci arti tepat kekonveksan himpunan dan fungsi serta akibat yang dapat ditarik dari sifat-sifat tersebut.
Himpunan konveks
Suatu himpunan disebut konveks apabila, untuk setiap dua titik di dalamnya, seluruh ruas garis lurus yang menghubungkan kedua titik itu juga termuat di dalam himpunan tersebut. Secara lebih formal:
Suatu himpunan disebut konveks jika dan hanya jika, untuk setiap dan , berlaku
Perhatikan bahwa yang memperlihatkan dengan lebih jelas bahwa menelusuri ruas garis yang menghubungkan dan .
Lebih lanjut, dengan menggunakan kombinasi konveks yang lebih umum, kita dapat dengan mudah menunjukkan hasil berikut.
Himpunan konveks jika dan hanya jika, untuk setiap , , dan , , yang memenuhi , berlaku
Proof. Latihan. ◻
Untuk memudahkan notasi, kita mendefinisikan simpleks satuan sebagai Sekarang kita dapat mendefinisikan himpunan konveks terkecil yang memuat suatu himpunan, yaitu selubung konveks.
Misalkan . Selubung konveks dari didefinisikan sebagai himpunan
Berlaku
Proof. Nyatakan ruas kanan [eq:convex_sets:conv_hull] dengan . Kita akan menunjukkan bahwa dan .
: Misalkan . Untuk setiap yang konveks dan memenuhi , berlaku . Oleh karena itu, berdasarkan definisi pada [eq:convex_sets:defin_conv_hull], diperoleh .
: Dapat diperiksa langsung bahwa memang merupakan himpunan konveks. Selain itu, . Dengan demikian, termasuk salah satu himpunan dalam [eq:convex_sets:defin_conv_hull], sehingga . ◻
Deskripsi rinci: Baris atas menampilkan beberapa himpunan konveks yang memuat seluruh ruas garis di antara tiap dua titiknya. Baris bawah menampilkan himpunan tak konveks dengan lekukan atau komponen terpisah.
Deskripsi gambar. Baris atas memperlihatkan beberapa daerah yang memuat seluruh ruas garis di antara setiap dua titik di dalamnya. Baris bawah memperlihatkan daerah yang memiliki lekukan atau bagian terpisah sehingga terdapat dua titik di dalam himpunan yang ruas penghubungnya keluar dari himpunan.
Himpunan-himpunan berikut bersifat konveks (buktinya ditinggalkan sebagai latihan):
Himpunan kosong .
Setiap ruang vektor.
Setiap bola norma; yaitu, untuk setiap norma , setiap , dan setiap , himpunan dan
Setiap subruang afin; yaitu, untuk setiap vektor , himpunan
Deskripsi rinci: Bola satuan dua dimensi untuk beberapa nilai p: bentuk berubah dari belah ketupat melalui lingkaran menuju persegi; kasus p sama dengan satu per dua melengkung ke dalam dan tidak konveks.
Deskripsi gambar. Gambar membandingkan bola satuan dua dimensi untuk beberapa nilai . Bentuknya berubah dari belah ketupat melalui lingkaran menuju bentuk yang semakin menyerupai persegi ketika bertambah; untuk , sisi-sisinya melengkung ke dalam sehingga himpunannya tidak konveks.
Pernyataan-pernyataan berikut berlaku:
Irisan. Misalkan konveks untuk , dengan suatu himpunan indeks sembarang. Maka irisan bersifat konveks.
Jumlah berbobot. Misalkan konveks untuk , dan misalkan untuk . Maka himpunan bersifat konveks.
Produk Kartesius. Misalkan konveks untuk , dengan suatu himpunan indeks sembarang. Maka produk Kartesius bersifat konveks.
Citra dan pracitra6 di bawah pemetaan linear bersifat konveks. Secara khusus, untuk linear serta dan keduanya konveks, himpunan-himpunan berikut bersifat konveks:
Proof. Kita hanya membuktikan bagian pertama dan meninggalkan sisanya sebagai latihan. Buktinya langsung. Misalkan dan . Karena untuk setiap dan setiap konveks, diperoleh untuk setiap . Dengan demikian, . ◻
Kita hendak mendefinisikan secara formal pengertian hiperbidang, yaitu perumuman bidang dua dimensi di ke dimensi sembarang.
Misalkan suatu ruang hasil kali dalam. Hiperbidang adalah himpunan berbentuk untuk suatu dan .
Parameter menentukan orientasi bidang dan menentukan geserannya. Secara khusus, jika dan hanya jika ; dalam kasus ini merupakan subruang. Jika , hanya merupakan subruang afin.
Perhatikan bahwa jika , maka Jadi, adalah vektor normal terhadap bidang tersebut. Selain itu, dapat diperiksa sebagai latihan bahwa adalah jarak bidang dari titik asal.
Setiap hiperbidang membagi ruang menjadi dua setengah ruang.
Misalkan suatu ruang hasil kali dalam. Setengah ruang adalah himpunan berbentuk untuk suatu dan .
Teorema berikut menyatakan bahwa pemisahan tersebut dapat dipilih dengan cara tertentu. Hasil ini ternyata sangat penting dalam optimisasi dan analisis fungsional.
Misalkan dua himpunan bagian konveks yang tak kosong dan saling lepas dari suatu ruang bernorma real , dan misalkan terbuka. Maka terdapat yang kontinu dan tak nol serta sedemikian sehingga Jika dan keduanya tertutup dan salah satunya kompak, maka terdapat yang kontinu dan tak nol, , dan sedemikian sehingga
Versi kedua memungkinkan kita memperoleh selisih positif tegas antara
Deskripsi figur nonraster. Ilustrasi teorema pemisahan Hahn–Banach dan alasan pemisahan dapat gagal tanpa kekonveksan.
Deskripsi gambar. Panel kiri menampilkan dua himpunan konveks tak beririsan yang dipisahkan oleh sebuah garis putus-putus. Panel kanan menampilkan salah satu himpunan yang tak konveks dan melingkupi sebagian himpunan lainnya, sehingga tidak ada satu garis lurus yang dapat memisahkan keduanya.
Fungsi konveks
Seperti diperlihatkan pada 2.1, kekonveksan sangat memengaruhi pertanyaan tentang keberadaan dan ketunggalan minimum.
Deskripsi rinci: Perbandingan grafik satu dimensi: fungsi konveks berbentuk mangkuk dengan minimum teratur dan fungsi tak konveks dengan beberapa lekukan serta minimum lokal.
Deskripsi gambar. Gambar membandingkan grafik satu dimensi berbentuk mangkuk, yang konveks dan memiliki struktur minimum yang teratur, dengan grafik tak konveks yang memiliki lekukan serta beberapa minimum lokal.
Misalkan konveks dan .
Fungsi disebut konveks jika dan hanya jika, untuk setiap dan , berlaku
Fungsi disebut konveks tegas jika dan hanya jika, untuk setiap dengan dan setiap , berlaku
Fungsi disebut konveks kuat dengan parameter jika dan hanya jika, untuk setiap dan , berlaku
Syarat orde nol menyatakan bahwa ruas garis yang menghubungkan dua titik pada grafik, yaitu garis sekan, selalu berada di atas fungsi. Untuk fungsi konveks tegas, garis sekan berada secara tegas di atas fungsi, sedangkan dalam kasus konveks kuat kita bahkan dapat menyisipkan fungsi kuadrat di antara keduanya.
Deskripsi figur nonraster. Penafsiran geometris syarat orde nol bagi kekonveksan suatu fungsi.
Deskripsi gambar. Sebuah kurva konveks biru ditampilkan bersama dua titik pada grafik dan ruas sekan yang menghubungkannya. Nilai fungsi pada kombinasi konveks kedua titik berada di bawah nilai yang diperoleh melalui interpolasi linear di sepanjang sekan.
Fungsi-fungsi berikut konveks (bukti: latihan):
Fungsi afin dengan dan ; khususnya, fungsi linear ketika .
Semua norma merupakan fungsi konveks.
Serupa dengan hasil untuk himpunan konveks, kekonveksan dapat diperluas ke kombinasi konveks dengan banyak titik yang sembarang.
Misalkan konveks dan . Dengan konvensi , fungsi konveks jika dan hanya jika, untuk setiap , , dan , berlaku
Di atas kita melihat bahwa kekonveksan berarti garis sekan berada di atas fungsi. Kekonveksan juga berarti garis singgung berada di bawah fungsi (bandingkan [convexity:fig:gradients]).
Misalkan konveks dan mempunyai perluasan yang terdiferensialkan secara kontinu pada suatu lingkungan terbuka dari .
Fungsi konveks jika dan hanya jika, untuk semua ,
Fungsi konveks tegas jika dan hanya jika ketaksamaan di atas berlaku tegas untuk semua .
Proof. Kita terlebih dahulu membuktikan butir pertama.
: Misalkan konveks. Maka Dengan menyusun ulang, diperoleh Membiarkan memberikan hasil yang diinginkan.
: Sekarang andaikan syarat gradien berlaku. Tuliskan . Maka dan Kalikan ketaksamaan pertama dengan , ketaksamaan kedua dengan , lalu jumlahkan. Hasilnya
Untuk butir kedua, arah dari syarat orde pertama tegas menuju kekonveksan tegas langsung mengikuti argumen yang sama. Sebaliknya, jika konveks tegas dan , fungsi satu variabel konveks tegas pada . Kemiringan sekan tak menurun dalam dan, untuk setiap , bernilai tegas lebih kecil daripada . Mengambil limit memberikan . ◻
Deskripsi figur nonraster. Penafsiran geometris syarat orde pertama bagi fungsi konveks.
Deskripsi gambar. Grafik sebuah fungsi konveks ditampilkan bersama garis singgungnya pada titik . Garis afin berada di bawah grafik fungsi di seluruh domain yang diperlihatkan.
Misalkan dan .
Titik disebut minimum lokal jika dan hanya jika terdapat sedemikian sehingga
Titik disebut minimum global jika dan hanya jika
Minimum disebut tegas apabila ketaksamaan yang bersesuaian berlaku tegas untuk semua titik pembanding .
Sekarang kita dapat membuktikan hasil penting pertama dalam optimisasi konveks.
Misalkan konveks, konveks dan mempunyai perluasan yang terdiferensialkan secara kontinu pada suatu lingkungan terbuka dari , serta . Jika , maka adalah peminimum global.
Proof. Berdasarkan karakterisasi orde pertama kekonveksan, ◻
Perhatikan bahwa kebalikan [convexity:prop:OC1], yaitu implikasi secara umum hanya benar apabila berada di interior , yang dinyatakan dengan ; yaitu, terdapat sedemikian sehingga .
Misalkan konveks, konveks dan mempunyai perluasan yang terdiferensialkan secara kontinu pada suatu lingkungan terbuka dari , serta . Maka jika dan hanya jika adalah peminimum global.
Proof. Satu arah mengikuti [convexity:prop:OC1]. Untuk arah lainnya, andaikan suatu minimum. Untuk setiap , jika cukup kecil, optimalitas memberikan Karena , pembagian dengan menghasilkan Dengan membiarkan , diperoleh Karena sembarang, argumen yang sama dapat diterapkan pada . Hasilnya
Jadi untuk setiap , dan karenanya (mengapa?). ◻
Dalam satu dimensi, jika suatu fungsi terdiferensialkan, kekonveksannya dapat dikarakterisasi melalui kemonotonan turunannya. Dalam dimensi sembarang berlaku hasil berikut.
Misalkan konveks dan mempunyai perluasan yang terdiferensialkan secara kontinu pada suatu lingkungan terbuka dari . Maka konveks jika dan hanya jika, untuk setiap ,
Proof. : Andaikan konveks. Berdasarkan karakterisasi orde pertama kekonveksan, Menjumlahkan kedua ketaksamaan memberikan hasil yang diinginkan.
: Andaikan monoton. Berdasarkan teorema dasar kalkulus, Pada , integran dipahami melalui perpanjangan kontinu; ketaksamaan monoton digunakan untuk . ◻
Terakhir, turunan kedua juga dapat digunakan untuk mengarakterisasi kekonveksan. Secara intuitif, kekonveksan berarti kelengkungan positif. Untuk memformalkan hal ini, ingat kembali cara mengurutkan matriks. Untuk dua matriks simetris , kita menuliskan dan, serupa dengan itu,
Misalkan terbuka dan konveks, serta terdiferensialkan secara kontinu dua kali.
Fungsi konveks jika dan hanya jika untuk setiap .
Jika untuk setiap , maka konveks tegas.
Proof. Kita membuktikan pernyataan pertama dan arah cukup pada pernyataan kedua.
: Andaikan konveks. Berdasarkan kemonotonan gradien, untuk berlaku Dengan membiarkan , diperoleh Karena sembarang, hasilnya mengikuti.
: Andaikan . Berdasarkan teorema dasar kalkulus, Mengambil hasil kali dalam dengan menghasilkan Kemonotonan gradien kini menyiratkan kekonveksan. Untuk membuktikan bagian tegas, tuliskan . Jika Hessian positif definit pada setiap titik, maka Jadi ketaksamaan orde pertama berlaku tegas dan konveks tegas. ◻
Misalkan konveks pada suatu himpunan konveks.
Untuk setiap , fungsi konveks.
Fungsi konveks.
Proof. Latihan. ◻
Misalkan konveks, , dan . Maka konveks pada .
Proof. Latihan. ◻
Misalkan konveks dan konveks serta tak menurun, dengan suatu interval yang memenuhi . Maka konveks.
Proof. Latihan. ◻
Fungsi log-sum-exp bersifat konveks:
Fungsi kuadratik-per-linear konveks pada .
Fungsi konveks pada karena konveks dan konveks serta tak menurun.
Pertimbangkan pada . Fungsi dan keduanya konveks. Fungsi tidak tak menurun pada seluruh , tetapi tak menurun pada . Akibatnya, konveks.
Pada contoh sebelumnya, jika diganti dengan , maka tidak tak menurun pada ; lihat [convexity:fig:compositions].
Deskripsi figur nonraster. Kekonveksan komposisi fungsi.
Deskripsi gambar. Panel kiri menampilkan dan . Panel tengah menampilkan serta rentang kedua fungsi tersebut; tak menurun pada rentang tetapi tidak pada seluruh rentang . Panel kanan memperlihatkan bahwa konveks, sedangkan memiliki lekukan tak konveks di sekitar titik asal.
Misalkan , , konveks pada himpunan konveks . Maka konveks.
Proof. Kita hitung langsung: ◻
Misalkan konveks pada , dengan dan keduanya konveks. Definisikan dan andaikan infimum tersebut hingga untuk setiap . Maka konveks.
Proof. Pilih barisan dan sedemikian sehingga Maka Mengambil limit ketika menyelesaikan bukti. ◻
Jarak suatu titik ke himpunan tak kosong dan konveks merupakan fungsi konveks. Jadi, untuk setiap himpunan tak kosong dan konveks , pemetaan berikut konveks:
Misalkan konveks dan . Maka konveks jika dan hanya jika, untuk setiap dan , fungsi konveks pada interval .
Proof. : Andaikan konveks untuk setiap dan . Misalkan dan . Pertimbangkan Karena konveks pada interval yang memuat dan , Arah sebaliknya ditinggalkan sebagai latihan. ◻
Contoh pada :
Fungsi konveks:
Fungsi eksponensial pada , dengan .
Fungsi pangkat pada untuk atau .
Pangkat nilai mutlak pada untuk .
Entropi negatif pada .
Fungsi konkaf:
Fungsi pangkat pada untuk .
Logaritma pada .
Contoh pada ruang Euklides berdimensi hingga:
Fungsi konveks:
Norma-, .
Pangkat norma-, , untuk .
Kuadrat terkecil, , dengan dan .
Maksimum fungsi-fungsi afin: dengan dan .
Perspektif suatu fungsi, , dengan fungsi konveks, , dan . Jadi domain perspektif ini adalah .
Fungsi konkaf:
Minimum fungsi-fungsi afin:
Contoh pada :
Fungsi konveks:
Fungsi afin pada , dengan dan .
Norma spektral .
Fungsi penghalang untuk matriks definit positif, pada .
Serupa dengan hasil-hasil di atas, kita dapat menunjukkan karakterisasi kekonveksan kuat berikut.
Misalkan , dengan konveks, serta . Karakterisasi berikut berlaku:
Fungsi konveks kuat berparameter jika dan hanya jika konveks.
Syarat orde pertama: jika mempunyai perluasan yang terdiferensialkan secara kontinu pada suatu lingkungan terbuka dari , maka konveks kuat berparameter jika dan hanya jika, untuk setiap ,
Syarat orde kedua: jika terbuka dan terdiferensialkan secara kontinu dua kali pada , maka konveks kuat berparameter jika dan hanya jika, untuk setiap ,
Proof. Buktinya merupakan penyesuaian langsung dari bukti untuk kekonveksan biasa dan ditinggalkan sebagai latihan. ◻
Subgradien
Ingat kembali definisi turunan (Fréchet).
Sepanjang bab ini, dan menyatakan ruang bernorma real; apabila gradien digunakan, merupakan ruang Hilbert. Setiap kali atau muncul, keduanya menyatakan ruang bernorma real berdimensi hingga. Pada pasangan dual, argumen pertama selalu fungsional dan argumen kedua selalu vektor.
Misalkan . Fungsi dikatakan terdiferensialkan (dalam arti Fréchet) di apabila terdapat pemetaan linear kontinu sedemikian sehingga Kita menuliskan .
Misalkan terdiferensialkan dan merupakan ruang Hilbert. Gradien di titik , yang dilambangkan dengan , adalah unsur tunggal di sedemikian sehingga
Keberadaan dan ketunggalan gradien merupakan akibat langsung dari teorema representasi Riesz, sebab apabila bernilai real. Perhatikan pula bahwa gradien bergantung pada hasil kali dalam yang dipilih.
Walaupun definisi umum di atas mungkin tampak agak abstrak, gradien yang kita temui biasanya cukup sederhana. Secara khusus, apabila dilengkapi dengan hasil kali dalam Euklides baku, maka yaitu, gradien hanyalah transpos dari turunannya.
Turunan dapat ditafsirkan sebagai hampiran linear terbaik terhadap fungsi di suatu titik, yakni dengan kecil menyatakan suatu suku yang meluruh lebih cepat daripada laju linear. Kebanyakan metode optimisasi dapat ditafsirkan sebagai proses berulang untuk meminimumkan hampiran fungsi yang lebih mudah. Akan tetapi, banyak fungsi penting tidak memiliki gradien dalam pengertian di atas. Sebagai contoh, kita mungkin ingin menyelesaikan persoalan dengan dan linear. Persoalan komposit semacam ini sangat umum dalam pengolahan citra. Karena itu, kita dapat bertanya apakah terdapat gagasan hampiran linear yang lebih umum tetapi memiliki sifat serupa dengan gradien. Definisi berikut menjawab pertanyaan ini secara positif.
Misalkan dan . Kita menyebut sebagai subgradien di apabila Subdiferensial di adalah himpunan semua subgradien di , yakni Untuk , kita menetapkan .
Jadi, subdiferensial dapat saja kosong; menurut konvensi di atas, subdiferensial kosong di setiap titik dengan .
Norma: Misalkan . Maka yaitu bola satuan untuk norma dual. Ingat bahwa norma dual didefinisikan oleh Sebagai contoh, apabila pada , maka
Untuk suatu himpunan tak kosong dan titik , tinjau fungsi indikator . Subdiferensialnya adalah yang disebut kerucut normal di . Subdiferensial fungsi indikator dari bola satuan adalah
Kita perlu memastikan bahwa subdiferensial benar-benar memperumum gradien biasa.
Misalkan konveks dan terdiferensialkan di , dengan ruang Hilbert. Maka .
Proof. Kita perlu menunjukkan (i) dan (ii) jika , maka . Bagian (i) langsung mengikuti karakterisasi orde pertama untuk fungsi konveks terdiferensialkan, yang memberikan sehingga . Untuk (ii), menurut definisi subgradien, bagi setiap , , dan yang cukup kecil sehingga , berlaku Dengan mengambil limit , diperoleh . Menerapkan ketaksamaan yang sama pada memberikan ketaksamaan sebaliknya. Karena itu untuk setiap , sehingga . ◻
Dalam dimensi hingga, kebalikannya juga berlaku bagi fungsi konveks yang hingga pada suatu lingkungan titik : jika subdiferensial di hanya terdiri atas satu unsur, maka terdiferensialkan di dan .
Deskripsi rinci: Parabola halus dengan sebuah garis singgung putus-putus pada titik yang ditandai; kemiringan garis merupakan gradien.
Deskripsi rinci: Grafik berbentuk V dengan tiga garis pendukung melalui titik tak mulus; kemiringan masing-masing garis merupakan subgradien yang sah.
Deskripsi gambar. Panel kiri memperlihatkan parabola halus dan satu garis singgung putus-putus pada titik yang ditandai. Panel kanan memperlihatkan grafik berbentuk V untuk norma satu dimensi dan tiga garis pendukung dengan kemiringan berbeda yang semuanya melalui titik sudut yang ditandai. Label matematis pada kedua figur dipertahankan persis dari aset sumber.
Untuk , diperoleh
Khususnya, untuk dan , diperoleh
Jika domain konveks dan subdiferensialnya tak kosong di setiap titik dalam domain, maka konveks.
Proof. Misalkan , , dan . Menurut definisi subdiferensial, atau, setara dengan itu, Dengan membagi ketaksamaan pertama oleh , membagi yang kedua oleh , lalu menjumlahkannya, diperoleh Mengalikan dengan menghasilkan sebagaimana yang diperlukan. ◻
Seperti disebutkan di atas, subdiferensial dapat kosong. Namun, bagi fungsi konveks berdimensi hingga kita mempunyai jaminan berikut.
Fungsi bernilai real diperluas disebut sejati (proper) apabila domain efektifnya tidak kosong dan fungsi itu tidak pernah bernilai minus tak hingga.
Misalkan ruang bernorma real berdimensi hingga dan sejati dan konveks. Maka untuk setiap .
Sebelum membuktikan hasil ini, kita memerlukan beberapa persiapan.
Interior suatu himpunan konveks adalah konveks.
Proof. Misalkan konveks. Jika , tidak ada yang perlu dibuktikan; jadi anggap . Ambil dan . Kita perlu menunjukkan bahwa . Terdapat sedemikian sehingga . Sekarang ambil . Dengan demikian, untuk suatu . Kita dapat menuliskan Karena dan , kekonveksan memberikan . Jadi dan . ◻
Jika konveks dan , maka terdapat hiperbidang sedemikian sehingga .
Proof. Jika kosong, sembarang hiperbidang memenuhi kesimpulan. Selanjutnya anggap tak kosong. Tanpa mengurangi keumuman, kita boleh menganggap . Jika tidak, pilih sembarang dan tinjau ; pada akhir bukti, hiperbidang yang diperoleh ditranslasikan kembali.
Kita akan menunjukkan bahwa merupakan himpunan bagian suatu subruang berdimensi paling besar . Andaikan sebaliknya bahwa memuat unsur yang bebas linear, yaitu terdapat yang bebas linear. Karena konveks, selubung konveks juga merupakan himpunan bagian . Kita mengklaim bahwa . Pertama, dari kekonveksan, Karena bebas linear, setiap dapat ditulis sebagai . Pemetaan adalah pemetaan linear bijektif . Oleh karena itu terdapat sedemikian sehingga mengakibatkan untuk semua . Khususnya, dan . Akibatnya, untuk setiap , Jadi, apabila memuat unsur bebas linear, interiornya tidak mungkin kosong, sebab . Ini bertentangan dengan asumsi. Maka memuat paling banyak unsur bebas linear. Pilih himpunan bebas linear maksimal di dalam ; maksimalitas memberikan Dimensi subruang ini kurang dari , sehingga subruang tersebut termuat dalam suatu hiperbidang. Setelah translasi balik bila diperlukan, diperoleh hiperbidang afin yang memuat himpunan semula. ◻
Dengan kedua hasil sebelumnya, kita dapat membuktikan teorema hiperbidang pendukung.
Misalkan ruang bernorma real berdimensi hingga, tak kosong dan konveks, serta 7. Maka terdapat , , sedemikian sehingga
Proof. Hasil ini merupakan akibat teorema pemisahan Hahn–Banach. Kita membedakan dua kasus. Pertama, andaikan . Himpunan terbuka, konveks, dan tak kosong. Teorema pemisahan Hahn–Banach dapat diterapkan pada dan , sehingga ketaksamaan pendukung berlaku pada interior. Karena dan fungsional pemisah kontinu, ketaksamaan itu meluas ke seluruh .
Sebaliknya, jika kosong, lema sebelumnya memberikan hiperbidang afin yang memuat . Karena tertutup dan , hiperbidang ini juga memuat titik batas tersebut. Ambil yang tak nol dan sedemikian sehingga Fungsional ini memenuhi [subgradient:eq:supporting]. ◻
Sekarang kita dapat membuktikan keberadaan subgradien.
Bukti [convexity:thm:nonempty_subgrad]. Kita ingin menunjukkan bahwa terdapat sedemikian sehingga untuk semua . Ini setara dengan Bentuk ini menyerupai struktur pemisahan Hahn–Banach. Agar dapat menggunakannya, kita beralih ke epigraf. Perhatikan bahwa . Selain itu, kekonveksan mengakibatkan konveks. Dengan menerapkan teorema hiperbidang pendukung, diperoleh unsur tak nol sedemikian sehingga8 Ini setara dengan Kita akan menunjukkan bahwa . Andaikan . Karena untuk setiap , kita dapat membiarkan dan memperoleh kontradiksi. Berikutnya, andaikan . Maka bagi semua . Karena , hal ini memaksa . Padahal teorema pemisahan menghasilkan unsur pemisah yang tak nol; sekali lagi kita memperoleh kontradiksi. Jadi , dan kita dapat membagi [subgrad:eq:nonempty_subdiff2] dengan untuk memperoleh dengan . Memilih memberikan . ◻
Seperti pada turunan biasa, kita dapat menurunkan beberapa aturan hitung untuk memperoleh subgradien dalam praktik.
Misalkan sejati dan konveks serta . Maka, untuk setiap ,
Proof. Latihan. ◻
Misalkan sejati dan konveks. Untuk setiap , berlaku Selain itu, jika terdapat , maka
Proof. Kita hanya membuktikan inklusi pertama. Bukti arah kedua sedikit lebih rumit dan menggunakan teorema pemisahan Hahn–Banach dengan cara yang serupa dengan bukti keberadaan subgradien.
Ambil dan , yaitu Menjumlahkan kedua ketaksamaan memberikan sehingga . ◻
Terakhir, kita mencatat beberapa aturan hitung subdiferensial tanpa bukti.
Misalkan sejati, konveks, dan semikontinu bawah, serta transformasi linear. Definisikan untuk . Bagi setiap berlaku aturan lemah Kesamaan berlaku apabila terdapat dengan .
Turunan komposisi fungsi-fungsi terdiferensialkan dihitung dengan aturan rantai. Jadi, turunan adalah . Rumus ini dapat diperluas ke kalkulus subdiferensial.
Misalkan konveks, konveks dan tak menurun, serta . Ambil dan andaikan terdiferensialkan di . Maka
Misalkan fungsi konveks sejati. Maka jika dan hanya jika .
Proof. Pernyataan ini langsung mengikuti ketaksamaan subgradien bagi setiap . ◻
Misalkan sejati dan konveks, serta konveks dengan . Titik merupakan solusi persoalan optimisasi berkendala jika dan hanya jika terdapat sedemikian sehingga bagi semua .
Penurunan subgradien terproyeksi
Misalkan ruang Hilbert real, himpunan tak kosong, tertutup, dan konveks, serta fungsi konveks. Kita tertarik menyelesaikan masalah Kita mengasumsikan bahwa himpunan peminim tidak kosong dan menetapkan . Masalah berkendala di atas selalu dapat ditulis sebagai masalah tak berkendala melalui dengan fungsi indikator himpunan .9
Ingat kembali metode optimisasi numerik paling dasar untuk masalah semacam ini ketika dan terdiferensialkan: penurunan gradien (atau penurunan tercuram). Kita memilih nilai awal , lalu untuk melakukan pembaruan dengan menyatakan ukuran langkah. Algoritma baru pertama yang kita tinjau ialah versi subgradien dari penurunan tercuram: untuk , Jika , masalah segera dapat muncul: mungkin saja . Dalam hal itu, iterasi yang memakai subdiferensial tidak lagi terdefinisi karena untuk . Karena itu, kita perlu memastikan setiap iterasi baru tetap berada di ; untuk tujuan ini kita memakai proyeksi.
Misalkan ruang Hilbert real dan tak kosong, tertutup, dan konveks. Fungsi berikut terdefinisi dengan baik:
Proof. Kita perlu menunjukkan bahwa minimum tercapai secara tunggal. Tetapkan , dan ambil barisan peminimum , yaitu Karena konveks, . Identitas jajaran genjang memberi Ruas kanan menuju nol ketika , sehingga merupakan barisan Cauchy. Kelengkapan menghasilkan , sedangkan ketertutupan menghasilkan . Dari kontinuitas norma diperoleh jadi peminim memang ada.
Untuk ketunggalan, andaikan keduanya peminim. Identitas jajaran genjang memberikan Namun , yang bertentangan dengan definisi . Jadi peminimnya tunggal. ◻
Dengan proyeksi, kita memperoleh cara mengatasi masalah keluar dari : metode subgradien terproyeksi. Pilih ; kemudian, untuk dan , tetapkan Untuk membuktikan konvergensi metode ini, kita memerlukan beberapa hasil bantu.
Misalkan ruang Hilbert real dan tak kosong, tertutup, dan konveks. Maka Khususnya, jika subruang,10 maka
Proof. Untuk setiap , kita mempunyai Akibatnya, Ambil sebarang , lalu pada ketaksamaan di atas masukkan untuk . Kita memperoleh Setelah dibagi dengan , Dengan mengambil limit , kita memperoleh hasil yang diinginkan. Kesamaan untuk kasus subruang ditinggalkan sebagai latihan. ◻
Misalkan ruang Hilbert real dan tak kosong, tertutup, dan konveks. Proyeksi pada bersifat tak ekspansif, yaitu kontinu Lipschitz dengan konstanta satu:
Proof. Tanpa mengurangi keumuman, andaikan , sebab jika tidak, tidak ada yang perlu dibuktikan. Kita memperoleh Membagi dengan menghasilkan kesimpulan. ◻
Misalkan , dan misalkan adalah iterasi metode subgradien terproyeksi [subgradient:eq:projectedSG], dengan dan . Maka
Proof. Dari definisi subgradien, . Karena , kita mempunyai . Ketakspansifan proyeksi lalu memberikan ◻
Hal yang wajar dilakukan sekarang ialah memakai hasil sebelumnya untuk menentukan ukuran langkah optimal. Lebih tepatnya, dengan meminimumkan ruas kanan [eq:subgradient:fundamental] terhadap , kita memperoleh jika , dan kita menetapkan jika . Ukuran langkah ini disebut aturan ukuran langkah Polyak.
Sebagai latihan, buktikan bahwa jika fungsi konveks bersifat -Lipschitz secara global pada , maka setiap memenuhi . Pada hasil-hasil berikut, kita memakai langsung batas pada subgradien yang dipilih, sehingga juga mencakup situasi berkendala yang tidak memenuhi asumsi Lipschitz global tersebut.
Andaikan subgradien yang dipilih pada iterasi memenuhi . Dengan aturan ukuran langkah Polyak metode subgradien terproyeksi [subgradient:eq:projectedSG] memenuhi
, dengan ketaksamaan ketat jika ;
ketika ; dan
, dengan .
Proof. Tanpa mengurangi keumuman, kita boleh mengasumsikan . Jika tidak, cukup tinjau . Dari [lemma:subgradient:fundamental] dan aturan ukuran langkah diperoleh dengan jika , dan nol jika . Jika , kekonveksan memberi . Karena itu, pengurangan bersifat ketat tepat ketika celah nilai fungsi positif.
Dengan menata ulang dan menjumlahkan untuk , kita memperoleh Karena , Batas ini berlaku untuk setiap , sehingga . Selain itu, yaitu ◻
Untuk mencapai ketelitian , kita memerlukan iterasi.
Ingat bahwa metode gradien mulus standar mencapai kompleksitas .
Walaupun hasil konvergensi dengan aturan ukuran langkah Polyak menarik secara teoretis dan memberi batas kasus terburuk untuk iterasi terbaik, dalam praktiknya ukuran langkah tersebut tidak dapat dihitung tanpa mengetahui . Berikut ini kita berikan hasil konvergensi yang lebih umum.
Andaikan subgradien yang dipilih memenuhi , dan ukuran langkah memenuhi Maka
Proof. Sekali lagi, untuk menyederhanakan notasi, andaikan . Dengan memakai dan menjumlahkan ketaksamaan fundamental [lemma:subgradient:fundamental] untuk , kita memperoleh Tuliskan Karena , Hipotesis juga memaksa ; karena itu, kedua suku pada ruas kanan menuju nol. ◻
Varian hasil konvergensi juga dapat diperoleh, misalnya jika kompak; lihat (Beck 2017) untuk perinciannya.
Konvergensi dapat dipercepat dan juga ditransfer dari nilai fungsi ke iterasi jika kita menambahkan asumsi bahwa konveks kuat.
Andaikan konveks kuat dengan parameter pada , dan subgradien yang dipilih memenuhi .11 Mulai dari , gunakan ukuran langkah untuk . Untuk , metode subgradien terproyeksi [subgradient:eq:projectedSG] memenuhi
; dan
.
Proof. Seperti sebelumnya, tanpa mengurangi keumuman, tetapkan . Kekonveksan kuat memperbaiki ketaksamaan fundamental menjadi Dengan menata ulang dan membagi dengan , diperoleh Memasukkan menghasilkan Kalikan dengan , lalu jumlahkan terhadap . Suku jarak meneleskop, sehingga Karena dan , kita memperoleh Dengan membuang suku jarak yang tak positif, diperoleh
Untuk batas iterasi, buang suku dari ketaksamaan fundamental yang diperbaiki. Dengan , Untuk , ketaksamaan ini memberi . Jika , substitusi pada relasi di atas memberikan Induksi membuktikan untuk setiap . ◻
Metode gradien proksimal
Kita telah melihat dalam bukti (dan latihan praktis) bahwa metode subgradien tidak memberikan konvergensi yang ideal. Dalam kasus dasar atau terburuk, nilai fungsi berkonvergensi dengan orde , dan konvergensi memerlukan ukuran langkah yang mengecil. Dalam bab ini, kita akan memperkenalkan alternatif bagi subgradien (eksplisit) dalam optimisasi.
Perhatikan masalah tak berkendala dengan proper, semikontinu bawah, dan konveks. Ingat pembaruan metode subgradien , , atau, secara ekuivalen, . Untuk , kita usulkan pembaruan implisit Pada tahap ini belum jelas apakah metode tersebut terdefinisi dengan baik. Namun, jika memang terdefinisi, secara intuitif kestabilannya dapat membaik karena arah pembaruan dipilih dengan melihat ke masa depan. Gagasan ini selaras dengan kestabilan metode implisit untuk mendiskretkan persamaan diferensial (bandingkan Euler implisit).
Jika kita amati [proximal:eq:intro] lebih dekat, aturan itu dapat ditulis sebagai yang merupakan kondisi optimalitas untuk Hal ini membawa kita pada definisi berikut.
Operator atau pemetaan proksimal dari didefinisikan sebagai pemetaan
Kita biasanya menyebut sebagai “proks”. Sebagai pemetaan bernilai himpunan, proks selalu dapat dituliskan; tetapi pemetaan itu baru berguna ketika . Kita dapat membuktikan hasil berikut.
Misalkan proper, konveks, dan semikontinu bawah. Pemetaan proksimal bernilai tunggal. Lebih lanjut, jika dan hanya jika .
Berdasarkan karakterisasi , kita sering menulis proks sebagai .
Proof. Demi kesederhanaan, andaikan ; untuk kasus umum, lihat (Beck 2017).
Ambil untuk suatu . Kita mempunyai Oleh karena itu (mengapa?), pemetaan bersifat koersif. Pemetaan ini juga mewarisi sifat semikontinu bawah dan proper dari . Dengan metode langsung untuk fungsi proper, semikontinu bawah, dan koersif di ruang berdimensi hingga, terdapat solusi bagi Untuk keunikan, definisikan dan andaikan adalah dua peminim. Karena suku kuadrat konveks ketat dan konveks, untuk berlaku sebuah kontradiksi. Pernyataan terakhir merupakan kondisi optimalitas bagi [proximal:eq:prox_proof]. ◻
Setelah mengetahui bahwa proks terdefinisi dengan baik, kita dapat mendefinisikan metode gradien proksimal. Secara khusus, perhatikan masalah dengan konveks dan -halus, yakni terdiferensialkan dengan gradien -Lipschitz, sedangkan proper, konveks, dan semikontinu bawah. Masalah semacam ini sering muncul dalam praktik dan mencakup masalah semula dengan mengambil . Untuk , metode gradien proksimal didefinisikan oleh Jadi, kita melakukan langkah gradien atau eksplisit terhadap , lalu langkah proksimal atau implisit terhadap .
Sebagai hasil sederhana pertama, kita menunjukkan bahwa titik tetap metode gradien proksimal tepat sama dengan titik optimal.
Untuk suatu yang tetap dan , pernyataan berikut ekuivalen: Dengan demikian, adalah titik tetap jika dan hanya jika menyelesaikan [proximal:eq:composite].
Proof. Karakterisasi optimalitas proks memberikan ekuivalensi Karena , serta menurut aturan jumlah dan aturan skala untuk subdiferensial, Untuk fungsi konveks , kondisi terakhir ekuivalen dengan optimalitas . ◻
Selain proks, kita mendefinisikan selubung Moreau sebagai nilai infimum dari objektif yang digunakan untuk proks.
Misalkan dan . Selubung Moreau didefinisikan oleh
Misalkan proper, konveks, dan semikontinu bawah, serta . Selubung Moreau selalu bernilai real (yakni berhingga), dan
Proof. Latihan. Terapkan lemma keberadaan dan keunikan proks pada , lalu substitusikan peminim unik tersebut ke dalam definisi infimum. ◻
Kita tinjau beberapa contoh pemetaan proksimal dan selubung Moreau yang sering muncul:
Misalkan tak kosong, tertutup, dan konveks, dan perhatikan fungsi indikator . Maka
Secara khusus, jika , maka
Jika , pemetaan proksimalnya adalah operator ambang lunak Untuk , selubung Moreau-nya tepat merupakan fungsi Huber
Misalkan semua fungsi dasar yang muncul di bawah proper, semikontinu bawah, dan konveks pada domain berdimensi hingga yang dinyatakan. Aturan berikut berlaku:
Jika , , , dan , maka .
Jika dengan dan , maka .
Jika dengan dan , maka .
Jika dengan ortogonal, maka .
Jika dengan dan , maka .
Jika dengan dan , maka , dengan .
Selubung Moreau memberikan efek penghalusan pada fungsi , sebagaimana ditunjukkan oleh hasil berikut.
Misalkan proper, konveks, dan semikontinu bawah, serta . Selubung Moreau bersifat konveks dan terdiferensialkan. Gradiennya -Lipschitz dan dapat ditulis sebagai
Proof. Untuk , fungsi konveks secara bersama pada . Jika dan , evaluasi di menunjukkan bahwa . Jadi, argumen ini tetap sah untuk fungsi bernilai diperluas.
Tetapkan . Dari definisi proks, Dengan mengurangkan dua hubungan itu, kita memperoleh Secara ekuivalen, Definisikan residu keterdiferensialan Kurangkan dua kondisi optimalitas proks, lalu gunakan monotonisitas dan ketaksamaan Cauchy–Schwarz. Hasilnya ialah , sehingga tak ekspansif. Dengan mengevaluasi pada , kita juga mendapatkan Secara keseluruhan, Jadi, . Untuk membuktikan kekontinuan Lipschitz gradien, perhatikan bahwa Kondisi optimalitas memberi . Karena itu, hasil kali dalam terakhir tidak negatif menurut monotonisitas subdiferensial, sehingga Setelah membagi dengan norma gradien yang berbeda dari nol (kasus nol langsung), diperoleh sifat -Lipschitz. ◻
Dengan representasi gradien selubung Moreau di atas, proks dapat ditulis kembali sebagai Jadi, satu langkah proksimal ekuivalen dengan satu langkah gradien pada selubung Moreau.
Untuk fungsi indikator himpunan tak kosong, tertutup, dan konveks , rumusnya adalah . Untuk , setiap koordinat diberikan oleh ambang lunak , dengan . Untuk , penyusutan Euklides adalah jika , dan . Verifikasikan ketiga rumus ini langsung dari kondisi optimalitas proks.
Sekarang kita akan membuktikan konvergensi metode gradien proksimal. Mula-mula kita turunkan lemma penting: untuk fungsi -halus, galat antara fungsi dan hampiran linearnya dibatasi dari atas oleh suku kuadrat.
Misalkan terdiferensialkan kontinu dan gradiennya -Lipschitz. Maka
Proof. Dari teorema dasar kalkulus dan sifat -halus, kita mempunyai ◻
Untuk bukti konvergensi metode gradien proksimal, bagi kita perkenalkan notasi Dengan fungsi ini, pembaruan gradien proksimal dapat ditulis sebagai
Misalkan konveks dan -halus dengan , serta proper, semikontinu bawah, dan konveks. Andaikan dan terdapat sedemikian sehingga untuk semua . Untuk setiap , algoritma gradien proksimal memenuhi Selain itu, berkonvergensi menuju suatu .
Proof. Dari definisi , kita mempunyai Dengan memakai hubungan ini, kekonveksan , Lemma [proximal_gradient:lemma:Lsmoothness], dan , untuk setiap diperoleh Dengan mengambil , kita memperoleh Jadi, nilai objektif tidak meningkat dan turun ketat kecuali jika ; menurut lemma titik tetap, kasus terakhir berarti optimal. Di sisi lain, ambil dan gunakan . Maka Khususnya, , sehingga jarak ke setiap peminim tidak meningkat. Dengan menjumlahkan untuk , kita memperoleh Karena juga tidak meningkat, Jadi, Terakhir, kita buktikan konvergensi . Perhitungan di atas menunjukkan bahwa tidak meningkat untuk setiap peminim . Dengan demikian, terbatas dan, di ruang berdimensi hingga, mempunyai subbarisan konvergen. Misalkan adalah suatu titik akumulasi. Karena dan semikontinu bawah, Jadi, adalah peminim dan tidak meningkat. Karena itu, terdapat dengan . Namun, Maka seluruh barisan berkonvergensi ke , dan bukti selesai. ◻
Akselerasi
Untuk setiap , titik awal , bilangan bulat , dan , serta untuk setiap metode orde pertama yang iterasinya memenuhi terdapat fungsi konveks yang bergradien -Lipschitz dan mempunyai peminim , sedemikian sehingga Perhatikan bahwa sejauh ini kita belum memperoleh laju konvergensi yang lebih baik daripada . Menutup kesenjangan menuju merupakan tujuan bab ini.
Metode bola berat Polyak
Penurunan gradien untuk meminimumkan masalah tak berkendala dapat ditafsirkan sebagai diskretisasi dari aliran gradien Jika fungsi ditafsirkan sebagai potensial, maka merupakan gaya yang ditimbulkan potensial tersebut pada sebuah partikel bermassa satu. Secara alami kita dapat menambahkan gesekan ke dalam model ini. Gaya gesek biasanya dimodelkan sebanding dengan kecepatan, sehingga diperoleh Kita mendiskretkan persamaan diferensial biasa ini melalui dan Dengan menamai , , dan , substitusi ke dalam [acceleration:eq:friction_ode] memberikan Setelah ditata ulang, pembaruannya menjadi Dengan menamai ulang konstanta dan mengizinkannya bergantung pada iterasi, kita sampai pada metode bola berat Polyak Bahkan tanpa penurunan dari sudut pandang persamaan diferensial, aturan pembaruan ini cukup intuitif: selain arah penurunan bagi , pembaruan tersebut memuat suku inersia yang menambahkan komponen searah dengan langkah sebelumnya.
Bukti konvergensi metode bola berat akan memakai hasil dasar aljabar linear berikut, yang disertakan demi kelengkapan.
Untuk setiap , dengan norma operator yang diinduksi oleh norma Euclidean, berlaku , dengan dan nilai eigen . Kesimpulan yang sama berlaku bagi setiap norma matriks yang kompatibel, karena semua norma pada ruang matriks berdimensi hingga ekuivalen.
Proof. Kompleksifikasikan ke operator pada . Norma operator Euclidean untuk matriks real sama pada dan . Ambil nilai eigen kompleks dengan serta vektor eigennya yang dinormalisasi. Maka sehingga .
Untuk ketaksamaan sebaliknya, gunakan bentuk normal Jordan kompleks Setelah blok-blok Jordan diurutkan, matriks dapat ditulis sebagai dengan , dan hanya jika posisi dan berada dalam blok Jordan yang sama sehingga . Tuliskan , dengan diagonal dan bagian nilpoten. Kedua matriks ini komutatif. Jika ukuran blok Jordan terbesar adalah , maka . Untuk dan , ekspansi binomial memberi untuk suatu konstanta yang tidak bergantung pada . Jika , semua elemen diagonal nol, sehingga dan bagi ; jadi kesimpulan langsung berlaku. Untuk , batas di atas menghasilkan Karena , , dan , kita memperoleh Akhirnya, yang, bersama batas bawah, membuktikan hasilnya. ◻
Berlaku jika dan hanya jika . Selain itu, dalam hal ini, untuk setiap terdapat sedemikian sehingga .
Proof. Jika , maka untuk setiap pasangan eigen kompleks berlaku ; akibatnya dan . Sebaliknya, jika , pilih . Berdasarkan [acceleration:lemma:spectral_radius], terdapat sedemikian sehingga untuk , yang menuju nol. Untuk pernyataan kuantitatif dan sembarang , [acceleration:lemma:spectral_radius] memberikan batas tersebut untuk semua yang cukup besar. Dengan memperbesar konstanta untuk indeks awal yang berhingga banyaknya, kita dapat memilih sehingga batas berlaku bagi setiap . ◻
Sekarang kita dapat membuktikan konvergensi metode bola berat. Tekniknya baku: kita menganalisis nilai eigen linearisasi aturan pembaruan.
Misalkan pada suatu lingkungan dari peminim stasioner lokal , dengan Gunakan parameter konstan dan . Terdapat sedemikian sehingga, jika , maka . Lebih khusus, dengan untuk setiap . Jika yang diketahui tentang kurvatur hanya selang , parameter yang meminimumkan radius spektral kasus terburuk dari model kuadratik atau linearisasi lokal adalah
Proof. Tetapkan . Karena , rekursi kedalaman dua dapat ditulis tepat sebagai Untuk menyiapkan linearisasi, definisikan vektor keadaan dan matriks linear Teorema dasar kalkulus memberikan Dengan demikian, rekursi keadaan yang tepat ialah Kontinuitas Hessian menunjukkan ketika .
Berdasarkan [acceleration:cor:spectral_radius], kita menganalisis nilai eigen . Jika merupakan vektor eigen dengan nilai eigen , maka Dengan menghitung determinan blok, atau mengeliminasi relasi di atas tanpa pernah membagi dengan , setiap nilai eigen berkaitan dengan suatu dan memenuhi Jadi, dengan , penyempurnaan kuadrat memberikan Akar dalam [acceleration:eq:heavy_ball1] berada ketat di dalam lingkaran satuan jika dan hanya jika kriteria Schur–Jury untuk polinom monik kuadrat real berikut terpenuhi: Hipotesis teorema memenuhi syarat ini bagi semua , termasuk kasus ; oleh sebab itu .
Ambil . Terdapat norma ekuivalen pada yang norma operator terinduksinya memenuhi . Karena dan semua norma berdimensi hingga ekuivalen, lingkungan dapat diperkecil sehingga suku gangguan memenuhi batas yang diperlukan. Maka rekursi keadaan menghasilkan Dengan memilih cukup dekat ke , bola kecil yang digunakan di atas tetap invarian. Ekuivalensi norma lalu memberikan estimasi dalam pernyataan teorema dan konvergensi lokal.
Tinggal membuktikan optimalitas kasus terburuk yang dinyatakan. Kasus langsung: pilihan dan membuat dan kedua akar nol. Sekarang andaikan . Untuk setiap radius kasus terburuk yang diklaim , kasus tidak dapat memperbaiki laju yang akan diperoleh, jadi cukup tinjau . Terapkan kriteria Schur–Jury setelah penskalaan . Agar kedua akar setiap polinom bermodulus paling besar , perlu dan , dengan .
Tetapkan . Karena , kelayakan kedua titik ujung mengharuskan . Selisih meningkat terhadap pada , sebab dan . Oleh karena itu, bahkan nilai maksimumnya harus tak negatif: . Jadi , yang pada ekuivalen dengan .
Kesamaan memaksa serta dan . Menyelesaikan kedua hubungan ujung tersebut menghasilkan Dengan pilihan ini, bergerak linear dari ke , sehingga semua akar untuk bermodulus paling besar . Batas bawah di atas membuktikan bahwa nilai maksimum tersebut tidak dapat diperkecil. Optimalitas ini merupakan optimalitas radius spektral kasus terburuk bagi fungsi kuadratik dan bagi model asimtotik lokal , bukan jaminan konvergensi global bagi semua fungsi konveks mulus. ◻
Latihan verifikasi.
Verifikasikan kriteria Schur–Jury di atas langsung dari rumus akar, termasuk kasus , dan turunkan kembali parameter kasus terburuk dengan menyamakan perilaku pada dan .
Akselerasi Nesterov
Metode Polyak optimal dalam arti radius spektral kasus terburuk bagi fungsi kuadratik konveks kuat, dan secara lokal bagi model di sekitar peminim. Akselerasi berikut mencapai laju orde optimal di bawah asumsi global yang lebih lemah. Kita kembali meninjau masalah dengan konveks, terdiferensialkan, dan bergradien -Lipschitz untuk , sedangkan proper, semikontinu bawah, dan konveks. Andaikan . Dengan , , ukuran langkah tetap , dan , pembaruan fast iterative shrinkage-thresholding algorithm (FISTA, atau metode gradien proksimal cepat) ialah Jika , metode ini sangat mirip dengan algoritma bola berat. Namun, gradien kini dievaluasi setelah suku inersia ditambahkan, dan konvergensinya bergantung pada pemilihan adaptif parameter inersia yang cermat.
Tetapkan . Maka untuk setiap .
Proof. Bukti mengikuti induksi langsung. Pernyataan benar untuk . Dengan memakai hipotesis induksi, kita memperoleh ◻
Definisikan Di bawah hipotesis komposit di atas, untuk setiap dan , berlaku dengan .
Proof. Pertama, kita dapat menulis Sebagai catatan, identitas ini menunjukkan bahwa metode gradien proksimal dapat ditafsirkan sebagai langkah proksimal terhadap ditambah pendekatan linear terhadap . Definisikan Karena konveks, bersifat -konveks kuat. Oleh karena itu, Lebih lanjut, karena konveks dan -halus serta , lema penurunan memberikan Khususnya, , sehingga Dengan memasukkan definisi dan memakai , penataan ulang hubungan terakhir tepat memberikan dan bukti selesai. ◻
Misalkan konveks, terdiferensialkan, dan bergradien -Lipschitz dengan ; misalkan proper, semikontinu bawah, dan konveks; serta ambil . Inisialisasikan FISTA dengan , , dan ukuran langkah tetap . Untuk setiap ,
Proof. Pilih dan dalam ketaksamaan fundamental gradien proksimal. Karena konveks, . Maka Di sisi lain, menurut kekonveksan dan fakta , Karena , kita mempunyai Menggabungkan [eq:fista1], [eq:fista2], dan [eq:fista3] memberikan Dari pembaruan FISTA berlaku . Jadi, Dengan demikian, Dengan mengiterasikan ketaksamaan ini, untuk diperoleh Selain itu, ketaksamaan fundamental gradien proksimal dengan dan memberikan Dengan membuang suku kuadrat nonnegatif pada ruas kanan estimasi energi dan memakai batas terakhir, kita menemukan Karena , batas dalam pernyataan teorema mengikuti. ◻
Dualitas
Dalam bab ini, semua ruang vektor dipahami sebagai ruang Hilbert riil berdimensi hingga. Dual yang digunakan adalah dual kontinu; melalui representasi Riesz kita mengidentifikasi dan, khususnya, . Untuk setiap ruang demikian , tuliskan bagi kelas fungsi yang proper, konveks, dan semikontinu bawah.
Dualitas Fenchel
Misalkan proper. Konjugat Fenchel, atau konjugat konveks, didefinisikan sebagai
Fungsi indikator: Misalkan dengan tak kosong dan konveks. Maka adalah apa yang disebut fungsi pendukung.
Norma: Misalkan adalah suatu norma. Maka . Artinya, adalah fungsi indikator pada bola satuan tertutup terhadap norma dual.
Sebaliknya, konjugat dari adalah setelah identifikasi .
Misalkan proper dan konveks, serta andaikan bahwa untuk suatu . Dalam dimensi hingga, syarat tambahan ini otomatis dipenuhi pada suatu titik di interior relatif domain efektif; bandingkan (Beck 2017, Corollary 3.19). Maka proper, konveks, dan semikontinu bawah (lsc).
Proof. Karena proper, terdapat sedemikian sehingga . Akibatnya, untuk setiap , Ambil . Berdasarkan definisi subgradien, kita mempunyai dan, dengan demikian, Kekonveksan dan semikontinuitas bawah langsung mengikuti fakta bahwa konjugat konveks merupakan supremum titik demi titik dari fungsi-fungsi afin kontinu, yang karena itu konveks dan lsc12. ◻
Misalkan proper. Maka
Proof. Latihan. ◻
Untuk fungsi proper dengan proper, proses pengambilan konjugat dapat kita iterasikan untuk memperoleh bikonjugat. Kondisi ini dijamin oleh lema sebelumnya pada kasus konveks yang memenuhi hipotesisnya. Demi kesederhanaan, kita tulis . Karena diasumsikan , bikonjugat kembali terdefinisi pada ruang asal .
Misalkan dan proper. Untuk setiap berlaku .
Proof. Pertama, perhatikan bahwa untuk setiap , konjugat memenuhi Oleh karena itu, ◻
Misalkan proper, konveks, dan lsc. Maka .
Proof. Karena selalu berlaku , tinggal ditunjukkan bahwa . Andaikan sebaliknya: terdapat sedemikian sehingga Ini berarti . Karena tertutup dan konveks berdasarkan asumsi, teorema Hahn–Banach dapat diterapkan untuk mendapatkan dan sedemikian sehingga Karena proper, pilih . Dengan memasukkan dan membiarkan , diperoleh . Sekarang andaikan . Kita dapat membagi dengan dan memperoleh Ketaksamaan di atas berlaku untuk setiap dan juga secara otomatis untuk setiap dengan . Mengambil supremum terhadap menghasilkan yang bertentangan dengan ketaksamaan Fenchel. Pada kasus yang tersisa, yaitu , kita mempunyai Ambil sembarang . Untuk , kita memperoleh Perhatikan bahwa dan tetap. Karena itu, dapat dipilih cukup kecil agar ruas kanan tetap negatif ketat. Tuliskan . Setelah membagi dengan , diperoleh Sekali lagi mengambil supremum terhadap semua menghasilkan Hal ini bertentangan dengan ketaksamaan Fenchel. Jadi, asumsi selalu menimbulkan kontradiksi. Karena itu, , dan bukti selesai. ◻
Jika tidak sekaligus konveks dan tertutup, maka, selama keluarga minoran proper di bawah tidak kosong, merupakan minoran konveks semikontinu bawah terbesar dari , yang disebut regularisasi . Lebih tepatnya, tuliskan Jika , maka Jika keluarga minoran tersebut kosong, supremum pada ruas kanan dipahami sebagai fungsi yang identik . Fungsi ini tidak termasuk dalam dan, di bawah konvensi bab ini yang mendefinisikan konjugasi hanya bagi masukan proper, tidak dinotasikan sebagai .
Konjugat mempunyai hubungan yang erat dengan subgradien, sebagaimana ditunjukkan oleh lema berikut.
Misalkan proper, konveks, dan tertutup. Pernyataan-pernyataan berikut ekuivalen:
.
.
.
Proof.
Pernyataan [duality:item1] menyiratkan bahwa untuk setiap , Berdasarkan definisi, ini menyiratkan .
Sebaliknya, pernyataan [duality:item2] menghasilkan, untuk setiap , Dengan mengambil supremum terhadap , diperoleh . Bersama ketaksamaan Fenchel, ini membuktikan hasilnya.
Karena proper, konveks, dan tertutup, pernyataan [duality:item1] ekuivalen dengan Bukti kemudian diperoleh dengan mengulangi argumen di atas.
◻
Misalkan . Maka
Proof. Pertama, perhatikan bahwa kedua pemetaan proksimal terdefinisi dengan baik dan bernilai tunggal (mengapa?). Demi kesederhanaan, tuliskan . Dari syarat optimalitas diperoleh dan, berdasarkan [duality:lemma:subdiff_conjugate], . Pernyataan terakhir menyiratkan , sehingga bukti selesai. ◻
Misalkan dan ruang Hilbert riil berdimensi hingga, , , dan operator linear terbatas. Selain itu, andaikan terdapat dengan . Andaikan masalah (primal) mempunyai solusi . Maka masalah dual juga mempunyai solusi , dan berlaku dualitas kuat, yaitu Selain itu, solusi primal dan dual memenuhi
Proof. Pertama, secara langsung diperoleh Jadi, tinggal dibuktikan ketaksamaan sebaliknya. Hipotesis interior di atas memenuhi syarat kualifikasi bagi aturan jumlah dan rantai subdiferensial. Karena itu, kaidah Fermat pada peminimum memberikan
.
Dengan kata lain, terdapat sedemikian sehingga . Berdasarkan [duality:lemma:subdiff_conjugate], hal ini menyiratkan Oleh karena itu, Ini membuktikan kesamaan dalam [duality:eq:fenchel_rocka] sekaligus menunjukkan bahwa adalah solusi masalah dual. ◻
Optimisasi primal–dual
[duality:eq:fenchel_duality] membuka kemungkinan beberapa metode untuk mencari solusi masalah berbentuk Memang, berdasarkan dualitas kuat, kita dapat menangani masalah primal, masalah dual, atau masalah titik pelana Tujuan utama peralihan di antara formulasi primal dan dual adalah untuk memindahkan operator . Misalnya, jika tidak terdiferensialkan sehingga kita ingin menerapkan langkah proksimal pada , operator dalam [duality:qe:problem] pada umumnya membuat tidak mempunyai bentuk eksplisit. Sebaliknya, dalam formulasi titik pelana [duality:qe:saddlepoint], operator hanya muncul dalam hasil kali skalar. Selain itu, perhatikan bahwa menurut [duality:thm:Moreau:id], proksimal suatu fungsi konjugat sama mudah atau sama sulit dihitung dengan proksimal fungsi asalnya. Lebih tepatnya, untuk berlaku .
Kesenjangan primal–dual didefinisikan sebagai
Di bawah hipotesis dualitas kuat dan ketercapaian primal–dual yang baru saja dinyatakan, kita mempunyai , dan jika dan hanya jika menyelesaikan masalah primal dan menyelesaikan masalah dual. Kesenjangan tersebut mempunyai representasi Khususnya, masing-masing optimal untuk masalah primal dan dual jika dan hanya jika, untuk setiap ,
Proof. Latihan. ◻
Dengan melakukan optimisasi bergantian dalam [duality:qe:saddlepoint], memakai langkah proksimal terhadap dan serta langkah gradien terhadap hasil kali dalam, kita memperoleh aturan pembaruan berikut yang dikenal sebagai metode Arrow–Hurwicz: Ternyata, dalam bentuk ini metode tersebut mempunyai sifat konvergensi yang lebih buruk. Untuk memperoleh pembaruan yang lebih baik, algoritme ditulis ulang secara cermat. Dengan memakai , dapat diperiksa secara langsung bahwa [duality:eq:AH] ekuivalen dengan Setelah membagi masing-masing persamaan dengan dan , serta menggunakan notasi , bentuk ini dapat ditulis sebagai Bahkan tanpa menelaah rincian bukti, wajar diharapkan bahwa pembaruan yang lebih simetris akan lebih baik, khususnya karena sifat menguntungkan matriks simetris. Karena itu, kita mempertimbangkan skema berikut, yang tidak mengubah titik tetap yang mungkin: Matriks pada ruas kanan kini simetris dan definit positif selama . Kembali ke operator proksimal, metode gradien hibrida primal–dual ini, yang sering disebut metode Chambolle–Pock berdasarkan (Chambolle dan Pock 2011), berbentuk
Untuk analisis, PDHG akan ditulis dalam bentuk abstrak Di sini, superskrip plus menyatakan variabel yang telah diperbarui, superskrip minus menyatakan iterasi lama, sedangkan garis atas masing-masing menyatakan nilai yang digunakan untuk pembaruan dan nilai yang digunakan untuk pembaruan .
Misalkan dan ruang Hilbert riil berdimensi hingga, , , linear terbatas, serta . Aturan pembaruan [duality:eq:pdhg2] memenuhi
Proof. Berdasarkan kekonveksan kuat, pembaruan dan memenuhi Menjumlahkan kedua ketaksamaan dan menyusun ulang suku-sukunya memberikan hasil yang diinginkan. ◻
Misalkan dan ruang Hilbert riil berdimensi hingga, , , linear terbatas, serta . Perhatikan pembaruan [duality:eq:pdhg] dan andaikan ukuran langkah memenuhi ; untuk , syarat ini dipahami otomatis terpenuhi. Untuk , definisikan rerata ergodik dan . Maka
Perhatikan bahwa ukuran langkah sama sekali tidak bergantung pada fungsi dan , melainkan hanya pada operator .
Proof. Jika , suku campuran dalam setiap tanda kurung siku lenyap, sehingga semua ekspresi itu tidak negatif. Jika , nonnegativitas mengikuti
,
dengan ketaksamaan terakhir diperoleh dari pilihan dan fakta bahwa . Penjumlahan terhadap menghasilkan Karena pemetaan konveks untuk tetap, kita memperoleh ◻
Metode pengali arah bergantian (ADMM)
Misalkan , linear, dan . Perhatikan masalah optimisasi berkendala Masalah ini dapat dirumuskan ulang sebagai masalah titik pelana tak berkendala untuk Lagrangian teraugmentasi; yaitu, untuk setiap , kita mempertimbangkan Pernyataan berikut dapat ditunjukkan secara langsung.
Masalah [eq:admm1] dan [eq:admm2] ekuivalen.
Proof. Latihan! ◻
Salah satu cara langsung untuk menyelesaikan masalah titik pelana tersebut adalah mengoptimalkan secara bergantian terhadap dan , lalu melakukan langkah kenaikan gradien terhadap : Perhatikan bahwa digunakan sebagai ukuran langkah untuk kenaikan gradien. Pilihan ini dapat dimotivasi secara intuitif oleh fakta bahwa, berdasarkan definisi pembaruan, Dengan mengalikan pembaruan oleh dan memasukkannya ke [duality:eq:admm3], diperoleh Dengan demikian, tripel ADMM yang benar-benar diperbarui melalui [duality:eq:admm_algo] memenuhi Pembaruan bergantian tersebut pada umumnya tidak memberikan stasioneritas terhadap , karena submasalah masih memakai . Hanya dalam skema hipotetis yang meminimumkan dan secara bersama kondisi serupa diperoleh terhadap , sehingga tripel hasil pembaruan bersama itu memenuhi stasioneritas primal penuh untuk . Kita dapat menunjukkan hasil konvergensi dasar berikut untuk ADMM.
Ambil . Andaikan terdapat suatu titik pelana dari dan, pada setiap iterasi, kedua submasalah minimisasi dalam algoritme ADMM di atas mencapai minimumnya; pilih sembarang peminimum tersebut. Dengan , berlaku , , dan
Proof. Bukti menggunakan suatu teknik penting, yaitu fungsional Lyapunov. Kita mendefinisikan fungsional yang tidak negatif (terbatas dari bawah) dan menurun sepanjang iterasi. Pada dasarnya, fungsional Lyapunov menggantikan fungsi objektif ketika penurunan objektif itu sendiri tidak dapat dibuktikan. Dalam kasus ini, kita menggunakan dengan suatu titik pelana bagi . Penurunan fungsional Lyapunov akan memberikan konvergensi melalui argumen penjumlahan teleskopik yang lazim. Akan tetapi, pembuktian penurunan ini memerlukan beberapa taksiran teknis. Demi kesederhanaan, tuliskan residu dan nilai objektif ; gunakan pula dan untuk titik pelana. Bukti dibagi menjadi tiga langkah.
Langkah 1
Karena merupakan titik pelana bagi , untuk setiap berlaku . Pernyataan ini ekuivalen dengan
Langkah 2
Di sisi lain, berdasarkan optimalitas dan dalam [duality:eq:admm_algo], kita memperoleh Selain itu, pembaruan dapat ditulis sebagai , sehingga Ketika dimasukkan ke [duality:eq:proof_admm2], persamaan ini memberikan Hal ini menyiratkan bahwa meminimumkan sedangkan meminimumkan Akibatnya, dari optimalitas diperoleh Karena titik pelana pasti memenuhi , sedikit penyusunan ulang memberikan Terakhir, kita dapat memasukkan untuk memperoleh
Langkah 3
Dengan menjumlahkan [duality:eq:proof_admm1] dan [duality:eq:proof_admm3], lalu mengalikan dengan , diperoleh Kita akan mengolah ketaksamaan ini. Suku ketiga dapat ditulis ulang menggunakan sebagai Dengan mengganti pada dua suku terakhir, diperoleh Dengan mengganti di atas, bentuk ini ekuivalen dengan Jadi, [duality:eq:proof_admm4] ekuivalen dengan Sekarang kita tulis ulang tiga suku pertama, Dengan memperhatikan bahwa kita mendapatkan bahwa [duality:eq:proof_admm5] ekuivalen dengan yang ekuivalen dengan Secara keseluruhan, [duality:eq:proof_admm5] kemudian menghasilkan Terakhir, perhatikan bahwa Kita ingin menunjukkan bahwa suku Untuk , ingat bahwa meminimumkan . Dengan demikian, Penjumlahan kedua ketaksamaan memberikan Dengan memasukkan , diperoleh tanda yang diinginkan. Oleh karena itu, Menjumlahkan terhadap menghasilkan, untuk , Dari penurunan fungsional Lyapunov, segera diperoleh bahwa dan merupakan barisan terbatas. Selain itu, Berdasarkan [duality:eq:proof_admm1] dan [duality:eq:proof_admm3], kita mempunyai Kemudian [duality:eq:proof_admm7] dan keterbatasan menyiratkan bahwa . ◻
Penurunan Gradien Stokastik
Andaikan kita ingin menyelesaikan tetapi hanya mempunyai akses ke estimasi acak yang tak bias bagi suatu subgradien . Artinya, kita mengandaikan dapat mengevaluasi yang memenuhi dengan suatu peubah acak. Ternyata banyak bukti konvergensi dapat dialihkan ke latar stokastik ini dengan hampir tanpa upaya tambahan. Sebelum menunjukkannya, mari kita berikan motivasi untuk latar ini.
Dalam pembelajaran mesin modern, banyak masalah pembelajaran dapat dirumuskan sebagai masalah jumlah hingga. Agar pengambilan sampel seragam menghasilkan estimator gradien yang tak bias, kita memakai normalisasi rerata dengan biasanya merupakan banyaknya sampel pelatihan. Sebagai contoh, andaikan kita ingin mempelajari pemetaan berparameter yang seharusnya menghampiri relasi berdasarkan data pelatihan . Masalah pelatihannya dapat berupa Karena ukuran data pelatihan yang dijumpai, sering kali gradien penuh tidak dapat dihitung secara langsung akibat keterbatasan memori. Jika semua terdiferensialkan, salah satu jalan keluarnya adalah pembaruan stokastik dengan . Dengan mendefinisikan sebagai barisan peubah acak iid yang berdistribusi seragam pada , pembaruan di atas dapat ditulis sebagai dengan . Memang, , sehingga memenuhi [stochastic:eq:gradient].
Misalkan tak kosong, tertutup, dan konveks, serta misalkan konveks dan -Lipschitz. Andaikan masalah mempunyai solusi, pilih , dan ambil . Untuk , misalkan dan jalankan iterasi terproyeksi dengan .
Tuliskan , sehingga terukur terhadap , dan definisikan . Andaikan, hampir pasti untuk setiap , Andaikan pula ukuran langkah memenuhi Untuk , definisikan . Maka ketika .
Proof. Karena , kita mempunyai . Ketakmembangan proyeksi metrik memberikan Perhatikan bahwa sifat terukur dan ketakbiasan bersyarat memberi dengan ketaksamaan subgradien pada baris ketiga. Karena fungsi konveks bersifat -Lipschitz pada , setiap subgradiennya mempunyai norma paling besar . Identitas momen kedua bersyarat kemudian menghasilkan Dengan mengambil ekspektasi pada ketaksamaan pertama, diperoleh Selebihnya mengikuti argumen pada kasus deterministik. Menjumlahkan dari sampai , memakai ketaknegatifan suku jarak terakhir, lalu membagi dengan memberikan Definisikan Karena , minimum terbaik tidak melebihi rerata berbobot. Oleh karena itu, Berdasarkan kedua syarat ukuran langkah, ◻
Selingan tentang Transportasi Optimal
Meskipun tidak sepenuhnya menyatu dengan kuliah ini, kita menutupnya dengan suatu selingan mengenai transportasi optimal, bidang yang sangat penting dalam matematika modern dan pembelajaran mesin. Perlu ditekankan sejak awal bahwa uraian ini hanya pengantar singkat; sejumlah rincian teori ukuran dan topologi yang mendasarinya akan dinyatakan seperlunya.
Notasi
Dalam bagian berikut, dan adalah ruang terukur13. Tuliskan dan untuk himpunan semua ukuran probabilitas, dan untuk ruang ukuran bertanda hingga, serta dan untuk kerucut ukuran tak negatif hingga. Ingat bahwa ukuran bertanda pada adalah fungsi , sedangkan ukuran tak negatif bernilai dalam , dengan suatu aljabar-14, dan memenuhi
;
untuk setiap barisan yang saling lepas, berlaku .
Ukuran probabilitas adalah ukuran tak negatif dengan .
Transportasi optimal Monge dan Kantorovich
Deskripsi figur nonraster. Ilustrasi transportasi optimal. Peta mengangkut tumpukan dari ke .
Motivasi khas untuk transportasi optimal adalah sebagai berikut. Bayangkan kita ingin memindahkan setumpuk pasir dari satu tempat ke tempat lain. Berdasarkan kekekalan massa, kedua tumpukan mempunyai massa total yang sama; tanpa mengurangi keumuman, kita andaikan massanya satu. Karena itu, tumpukan awal dapat digambarkan oleh distribusi probabilitas dan tumpukan akhir oleh distribusi probabilitas . Pertanyaan yang hendak dijawab dalam transportasi optimal adalah:
Bagaimana kita dapat mengangkut tumpukan ke dengan biaya minimum?
Pembaca yang teliti mungkin menyadari bahwa biaya belum ditentukan. Andaikan tersedia fungsi biaya terukur yang terbatas dari bawah, , dengan menyatakan biaya untuk mengangkut satu satuan massa dari ke . Setiap transportasi deterministik dari ke dimodelkan oleh pemetaan terukur . Syarat pengangkutan dapat dirumuskan dengan meminta untuk setiap . Ini mengantar kita pada definisi berikut.
Misalkan dan terukur. Ukuran hasil dorong didefinisikan oleh untuk setiap .
Sekarang kita dapat memperkenalkan secara formal masalah Monge untuk transportasi optimal:
Misalkan dan ruang terukur, , , dan fungsi biaya terukur yang terbatas dari bawah. Masalah Monge untuk transportasi optimal adalah
Masalah Monge untuk transportasi optimal mempunyai beberapa kekurangan. Sebagai contoh, setiap hanya dapat dipetakan oleh ke satu titik , sehingga massa pada satu titik tidak dapat dibagi ke beberapa titik . Karena itu, apabila memberikan massa tak nol pada suatu titik, , dan kontinu mutlak terhadap ukuran Lebesgue15, tidak ada peta yang memenuhi syarat. Selain itu, bergantung pada pilihan , masalah ini umumnya sulit dianalisis karena peubah tak diketahui muncul di dalam biaya .
Perumusan yang lebih umum dan lebih mudah dianalisis adalah transportasi optimal Kantorovich. Alih-alih memakai peta , transportasi juga dimodelkan oleh suatu distribusi. Suatu rencana transportasi adalah distribusi probabilitas pada ruang hasil kali terukur yang mempunyai dan sebagai marginalnya: dan untuk semua dan . Secara intuitif, adalah massa yang diangkut dari ke . Himpunan semua distribusi dengan marginal dilambangkan dengan dan anggotanya disebut kopling (coupling). Sekarang kita dapat mendefinisikan masalah Kantorovich untuk transportasi optimal.
Misalkan dan ruang terukur, , , dan fungsi biaya terukur. Masalah Kantorovich untuk transportasi optimal adalah
Perhatikan bahwa [ot:eq:K_ot] jauh lebih menguntungkan daripada [ot:eq:monge]. Secara khusus, objektifnya kini linear.
Kita juga dapat merumuskan [ot:eq:K_ot] dengan peubah acak. Setiap kopling dapat direalisasikan sebagai vektor acak dengan dan . Biayanya kemudian memenuhi
Kita nyatakan hasil berikut.
Misalkan dan ruang Polish yang dilengkapi aljabar- Borelnya, , dan . Jika terbatas dari bawah dan semikontinu bawah, maka terdapat rencana transportasi optimal , yaitu solusi untuk [ot:eq:K_ot].
Sketsa bukti. Untuk bukti terperinci, lihat misalnya (Villani 2009, Theorem 4.1). Argumennya adalah metode langsung. Ambil barisan yang nilai biayanya menuju infimum. Karena dan ketat pada ruang Polish, keluarga kopling dengan kedua marginal tetap juga ketat. Himpunan tertutup terhadap konvergensi lemah; teorema Prokhorov karena itu menyatakan bahwa himpunan tersebut kompak secara lemah. Setelah mengambil suatu subbarisan, diperoleh . Karena semikontinu bawah dan terbatas dari bawah, pemetaan semikontinu bawah secara lemah. Maka meminimumkan biaya dan bukti selesai. ◻
Satu kasus khusus penting dari transportasi optimal perlu disoroti.
Misalkan ruang metrik Polish dan . Tetapkan dan tuliskan ; definisi ini tidak bergantung pada pilihan . Untuk dan biaya , besaran disebut jarak Wasserstein-.
Secara khusus, adalah metrik pada ruang ukuran probabilitas bermomen ke- hingga, yaitu .
Dualitas Kantorovich
Dari 7 kita telah mengenal konsep dualitas. Dualitas memainkan peran penting dalam transportasi optimal dan menghasilkan teorema terkenal berikut.
Misalkan dan ruang Polish dengan aljabar- Borelnya, , , dan semikontinu bawah. Tuliskan dan untuk fungsi kontinu terbatas bernilai riil. Maka
Sketsa bukti. Kita mulai dengan ketaksamaan yang mudah. Ambil sedemikian sehingga untuk semua , dan ambil sembarang . Maka Karena dan sembarang, kita dapat mengambil infimum di ruas kanan dan supremum di ruas kiri untuk memperoleh Ketaksamaan sebaliknya lebih rumit. Pertama, kita dapat menulis ulang [ot:eq:K_ot] sebagai dengan fungsi indikator seperti biasa. Untuk , berlaku Jika , ekspresi di dalam supremum pada ruas kanan bernilai nol untuk setiap , sehingga supremumnya nol. Sebaliknya, jika , sedikitnya satu marginal berbeda. Ukuran Borel hingga yang berbeda pada ruang Polish dapat dipisahkan oleh suatu fungsi kontinu terbatas; tanpa mengurangi keumuman, terdapat sedemikian sehingga dengan marginal- dari . Mengganti dengan dan memilih tanda ketika menunjukkan bahwa supremumnya adalah .
Langkah taktrivial untuk ketaksamaan sebaliknya adalah pertukaran infimum dan supremum. Pertukaran itu tidak mengikuti perhitungan formal semata; di bawah hipotesis ruang Polish dan biaya semikontinu bawah tak negatif di atas, pertukaran tersebut dijamin oleh teorema dualitas Kantorovich standar, lihat (Villani 2009, Theorem 5.10). Dengan justifikasi dualitas kuat ini, diperoleh Pada persamaan terakhir, infimum terhadap ukuran tak negatif bernilai nol jika di setiap titik (ambil ), dan bernilai jika ketaksamaan itu gagal (skalakan massa Dirac pada titik pelanggaran). Ini sama dengan fungsi indikator kendala dual, sebagaimana pada [ot:eq:duality]. ◻
Diskretisasi transportasi optimal: Algoritme Sinkhorn–Knopp
Untuk mendiskretisasi [ot:eq:K_ot], kita modelkan dan sebagai ukuran diskret. Tuliskan dan . Untuk suatu vektor dan titik , tetapkan dan, serupa dengan itu, untuk dan , tetapkan Selanjutnya, definisikan . Rencana transportasi adalah matriks sedemikian sehingga Kendala marginal dapat ditulis ringkas sebagai dan . Masalah transportasi optimal diskret kemudian berbentuk Dalam praktik, masalah ini sering diregularisasi. Untuk pembahasan regularisasi entropik berikut, andaikan , sehingga semua biaya diskret berhingga. Untuk , definisikan regularisasi entropik dengan konvensi kontinu ; di luar ortan tak negatif, tetapkan . Untuk , pertimbangkan masalah
Andaikan , , , dan . Solusi masalah [ot:eq:disc_entropic] unik dan mempunyai representasi dengan dan . Vektor penskalaan unik hingga transformasi untuk .
Proof. Himpunan layak adalah politop transportasi tak kosong dan kompak: matriks layak, bahkan . Karena fungsi objektif kontinu pada politop ini, suatu peminimum ada. Fungsi dengan bersifat konveks ketat pada ; karena itu, jumlah entropik bersifat konveks ketat dan peminimumnya unik.
Peminimum tidak dapat mempunyai entri nol. Memang, jika untuk sedikitnya satu pasangan , maka tetap layak untuk . Pada setiap entri nol, turunan searah satu sisi dari suku entropi memenuhi ketika , sedangkan kontribusi biaya linear dan turunan pada entri positif tetap hingga. Jadi, untuk yang cukup kecil, nilai objektif pada lebih kecil daripada pada , suatu kontradiksi. Dengan demikian, untuk semua , dan kondisi pengali Lagrange untuk kendala marginal afin dapat diterapkan.
Lagrangian masalah ini adalah Kondisi optimalitasnya adalah Kondisi pertama menyiratkan Dengan dan , diperoleh representasi yang dinyatakan. Jika pasangan positif menghasilkan rencana yang sama, maka dari dan diperoleh untuk setiap . Karena ruas kiri hanya bergantung pada dan ruas kanan hanya pada , semua rasio itu sama dengan suatu ; jadi . ◻
Kendala yang masih harus dipenuhi adalah dan . Ini memotivasi algoritme Sinkhorn–Knopp. Pilih , misalnya , lalu untuk perbarui dengan menyatakan pembagian komponen demi komponen. Berdasarkan positivitas , , dan , semua penyebut dan iterat tetap positif. Dengan hipotesis pada lema di atas, teorema Sinkhorn–Knopp menyatakan bahwa rencana , , konvergen ke rencana unik pada masalah [ot:eq:disc_entropic]. Vektor penskalaannya sendiri tetap mempunyai ambiguitas perkalian .
Suplemen Terbatas: Dualitas dan Reduksi Varians
Dualitas Lagrange, kondisi Slater, dan kondisi KKT
Bab ini melengkapi tulang punggung Habring dengan satu jalur terpadu dari Lagrangian ke kondisi Slater dan kondisi Karush-Kuhn-Tucker (KKT). Notasi dibuat konsisten untuk masalah minimisasi. Bagian sumber yang khusus membahas dualitas program linear tidak disertakan karena materi itu berada dalam batas kurikulum O018.
Kredit catatan donor.
Catatan donor menyatakan bahwa bagian dualitas mengikuti Bab 5 Boyd dan Vandenberghe (B&V), merujuk ke §5.3 untuk ilustrasi, dan mengaitkan interpretasi perpotongan maksimum atau titik bersama minimum dengan Bertsekas. Kredit turunan ini dipertahankan; edisi ini tidak mengimpor isi di luar rentang donor yang dibekukan.
Masalah primal dan Lagrangian
Pertimbangkan masalah dengan memuat domain bersama fungsi-fungsi tersebut. Kita memakai jika masalah tidak layak dan jika nilainya tidak terbatas ke bawah.
Lagrangian masalah [becker:eq:primal] adalah Vektor dan disebut variabel dual atau pengali Lagrange. Untuk kendala pertidaksamaan kita akan mensyaratkan komponen demi komponen.
Lagrangian bergantung pada cara masalah ditulis. Misalnya, untuk kita dapat memperkenalkan dan kendala , lalu membentuk Lagrangian terhadap kendala kesamaan itu. Pemisahan variabel seperti ini sering membuka struktur yang tidak tampak pada rumusan asal.
Fungsi dual Lagrange didefinisikan oleh Fungsi cekung terhadap , bahkan bila masalah primal tidak konveks, sebab adalah infimum titik demi titik dari fungsi-fungsi afin dalam variabel dual.
Sebagai kaidah umum yang terkait, minimisasi parsial dari fungsi konveks bersama menghasilkan fungsi konveks pada variabel yang tersisa, sedangkan supremum titik demi titik dari fungsi-fungsi konveks tetap konveks.
Masalah dual Lagrange adalah Ini merupakan masalah maksimisasi cekung, atau secara ekuivalen masalah minimisasi konveks untuk .
Untuk masalah [becker:eq:primal] selalu berlaku
Proof. Ambil titik layak . Untuk setiap dan setiap , Mengambil infimum terhadap semua titik primal yang layak memberi . Mengambil supremum terhadap semua titik dual yang layak membuktikan [becker:eq:weak-duality]. ◻
Jika , kita mengatakan bahwa dualitas kuat berlaku. Selain memberi sertifikat batas bawah, masalah dual dapat memindahkan operator linear, menyingkap kehalusan, atau menghasilkan rumusan numerik yang lebih sesuai. Untuk masalah nonkonveks sekalipun, nilai dual tetap menyediakan batas bawah yang sah, walaupun kesenjangan dualitas mungkin positif.
Kondisi Slater dan dualitas kuat
Sekarang andaikan konveks dan kendala kesamaan berbentuk . Tuliskan bagi indeks kendala pertidaksamaan yang tidak afin.
Kondisi Slater dipenuhi jika terdapat dalam interior relatif domain bersama sedemikian sehingga Jadi hanya kendala pertidaksamaan nonafin yang harus dipenuhi secara ketat.
Jika masalah primal konveks, kondisi Slater dipenuhi, dan berhingga, maka dan suatu titik dual optimum tercapai.
Kondisi Slater bersifat cukup, bukan perlu. Contoh semidefinit berikut menunjukkan salah satu gejala degenerasi. Pertimbangkan Setiap titik layak berbentuk , sehingga dan . Barisan memberi nilai objektif yang menuju nol ketika . Jadi , tetapi infimum primal tidak tercapai. Dualnya tetap mempunyai solusi optimum bernilai nol; contoh ini memperingatkan bahwa ketercapaian primal tidak mengikuti hanya dari kesamaan nilai primal dan dual.
Berikut gagasan geometri di balik teorema Slater. Definisikan himpunan nilai terganggu dan sinar terbuka Kekonveksan fungsi-fungsi kendala membuat konveks, dan . Teorema pemisahan memberi normal . Monotonisitas terhadap dan memberi dan . Kondisi Slater menyingkirkan , yaitu hiperbidang penyangga vertikal, sehingga dan normal dapat dinormalkan menjadi . Ketaksamaan pemisahan kemudian menghasilkan Dualitas lemah memberi ketaksamaan sebaliknya; karena itu dan pengali dual optimum tercapai. Interpretasi yang sama dapat dinyatakan sebagai perpotongan maksimum atau titik bersama minimum dalam geometri perturbasi.
Interpretasi titik pelana
Untuk Lagrangian [becker:eq:lagrangian], masalah primal dan dual dapat ditulis sebagai Ketaksamaan minimaks adalah bentuk titik-pelana dari dualitas lemah.
Tripel adalah titik pelana Lagrangian jika dan untuk setiap , , dan .
Sebagai contoh, pertimbangkan Lagrangiannya adalah Jika pengali optimum memenuhi , minimisasi Lagrangian terhadap ekuivalen, setelah dibagi dengan , dengan Jadi rumusan berkendala dan rumusan berpenalti berhubungan melalui pengali optimum. Hubungan ini tidak boleh diperoleh dengan membagi oleh jika pengalinya nol.
Kondisi Karush-Kuhn-Tucker
Andaikan fungsi-fungsi pada masalah [becker:eq:primal] dapat didiferensialkan. Tripel memenuhi kondisi KKT jika
stasioneritas: ; pada kasus konveks tak mulus, bentuk yang sesuai adalah ;
kelayakan primal: dan ;
kelayakan dual: ;
kekomplementeran: untuk setiap .
Andaikan optimum primal dan dual tercapai, dualitas kuat berlaku, dan memiliki syarat optimalitas Fermat yang berlaku pada . Maka pasangan optimum memenuhi kondisi KKT. Pernyataan ini tetap dapat dipakai pada masalah nonkonveks bila stasioneritas Lagrangian benar-benar mengikuti dari minimisasi globalnya dan seluruh syarat domain dipenuhi.
Jika konveks, afin, dan suatu tripel memenuhi kondisi KKT, maka optimum primal, optimum dual, dan .
Proof. Stasioneritas dan kekonveksan membuat peminimum global Lagrangian. Karena itu Dualitas lemah memberi , sehingga semua ketaksamaan adalah kesamaan. ◻
Jika masalah primal konveks memenuhi kondisi Slater dan suatu solusi primal ada dengan nilai berhingga, maka terdapat pengali sedemikian sehingga tripel tersebut memenuhi kondisi KKT.
Contoh: proyeksi pada bola
Proyeksi pada bola , dengan , menyelesaikan Kondisi KKT memberi bersama dan . Jika , maka dan . Jika , maka adalah akar unik dari Ruas kiri kontinu, menurun, dan linear sepotong-sepotong dengan titik patah ; akar dapat dicari dengan biseksi atau, lebih efisien, dengan mengurutkan titik patah. Identitas Moreau menjelaskan hubungan yang tepat:
Kekomplementeran juga mengikuti dari kesamaan primal-dual. Untuk titik pelana optimum berlaku karena kendala kesamaan lenyap. Setiap suku , sehingga jumlah nol memaksa untuk setiap .
Contoh: masalah kuadratik dengan kendala kesamaan
Pertimbangkan Kondisi KKT adalah atau sistem titik pelana Setiap solusi sistem ini adalah solusi optimum masalah konveks tersebut. Solusi tunggal hanya dijamin jika matriks KKT nonsingular; satu syarat cukup yang umum adalah berperingkat baris penuh dan definit positif pada .
Reduksi Varians untuk SAA
Pertimbangkan masalah jumlah hingga dari aproksimasi rata-rata sampel (sample average approximation, SAA) dengan bernilai hingga pada domain model. Sebagai contoh, untuk model dengan prediktor linear dan fungsi kerugian dapat dipakai dengan fungsi kerugian. Huruf menggantikan huruf pada donor agar tidak bertabrakan dengan konstanta kemulusan Lipschitz yang dipakai di bawah.
Tabel gradien dan penaksir SAGA
Pilih iterat awal dan inisialisasikan satu titik tabel untuk setiap . Simpan, pada iterasi , Dengan , tabel lengkap mempunyai kolom gradien di . Ambil indeks acak dan bentuk Pembaruan SAGA tanpa suku proksimal adalah Sesudah dihitung dari tabel lama, hanya kolom terpilih yang disegarkan: Ini menuliskan secara eksplisit inisialisasi dan urutan pembaruan yang hanya tersirat pada donor. Suku merupakan peubah kontrol (control variate). Donor juga menyebut SAG dan SVRG; keduanya adalah metode reduksi varians lain, tetapi algoritmanya tidak diimpor dari bagian di luar rentang beku.
Mengapa koreksi tabel mengurangi varians
Penghubung mandiri.
Ambil sebagai informasi sebelum ditarik, sehingga dan seluruh tabel tetap ketika ekspektasi bersyarat dihitung.
Penaksir [becker03:eq:saga-estimator] memenuhi
Proof. Keseragaman memberi ◻
Lebih tepat lagi, tuliskan dan . Maka Identitas ini memperlihatkan mekanismenya: ketika gradien tersimpan mendekati gradien komponen pada iterat sekarang, ruas kanan menyusut meskipun langkah tidak dipaksa menuju nol. Berbeda dari SAG, koreksi SAGA pada [becker03:eq:saga-estimator] membuat arah langkah takbias. SVRG mencapai gagasan serupa dengan gradien penuh pada titik acuan berkala, sehingga tidak menyimpan seluruh tabel gradien tetapi memakai evaluasi gradien tambahan.
Laju konvergensi dan iterat rata-rata
Pernyataan donor “untuk yang sesuai, metode ini konvergen secara linear” memerlukan hipotesis. Bentuk berikut adalah spesialisasi nonkomposit dari hasil SAGA oleh Defazio, Bach, dan Lacoste-Julien (2014).
Andaikan setiap konveks, terdiferensial, dan mempunyai gradien -Lipschitz. Andaikan pula pada [becker03:eq:finite-sum] -konveks kuat dan mempunyai peminimum . Jika seluruh titik tabel diinisialisasi pada dan , maka dengan
Konstanta dan laju pada teorema tersebut mengikuti hasil adaptivitas terhadap kekonveksan kuat dalam Defazio, Bach, dan Lacoste-Julien, SAGA (2014). Teorema donor tanpa hipotesis tidak dipertahankan sebagai klaim universal: tanpa kemulusan dan struktur konveks yang sesuai, laju linear tidak mengikuti hanya dari bentuk pembaruan.
Jika hanya konveks, definisikan iterat rata-rata secara tidak ambigu sebagai Di bawah asumsi konveks dan -mulus di atas, dengan , hasil yang sama memberi batas Jadi perataan bukan jaminan tanpa syarat untuk laju yang lebih baik; dalam rezim konveks yang dinyatakan, ia menyediakan jaminan sublinear untuk nilai fungsi.
Latihan dengan petunjuk dan solusi
Latihan berikut merupakan materi baru untuk edisi ini; tidak ada latihan, petunjuk, atau solusi pada rentang donor.
Dengan , buktikan Proposisi [becker03:prop:conditional-unbiasedness] dan identitas [becker03:eq:variance-identity]. Jelaskan kapan varians bersyaratnya sama dengan nol.
Petunjuk. Gunakan dan kembangkan kuadratnya.
Solusi lengkap. Keseragaman indeks memberi , sehingga selisih tersebut bermean nol. Selanjutnya, yang sama dengan ruas tengah [becker03:eq:variance-identity] dan tidak melebihi ruas kanannya. Variansnya nol tepat ketika semua sama; khususnya, nol jika untuk semua .
Ambil , , , , , dan . Hitung dua nilai mungkin bagi , ekspektasi dan variansnya, lalu bandingkan dengan gradien stokastik biasa . Untuk , hitung pula dua iterat berikutnya.
Petunjuk. , , dan .
Solusi lengkap. Pada , gradien komponen adalah dan . Oleh karena itu jika , sedangkan jika . Maka dan . Penaksir SGD biasa bernilai atau , sehingga mean-nya juga tetapi variansnya . Dengan , SAGA menghasilkan atau .
Metode Stokastik Komposit
Metode Stokastik Komposit, Cermin, dan Minibatch
Bab ini mengisi penghubung yang belum tersedia di tulang punggung Habring dan tiga modul Becker yang telah diterima. Habring telah mengembangkan operator proksimal, gradien proksimal deterministik, dan subgradien stokastik terproyeksi. Modul Becker 3 telah membuktikan ketakbiasan penaksir SAGA dan identitas varians tabelnya. Yang masih diperlukan ialah satu kerangka yang menjelaskan bagaimana operator proksimal, geometri non-Euklides, pengambilan sampel minibatch, dan reduksi varians saling terhubung.
Seluruh rumusan, bukti penghubung, latihan, petunjuk, solusi, dan laboratorium dalam bab ini ditulis secara mandiri. Catatan Habring, catatan gradien stokastik Clément W. Royer, modul Becker 3, serta rujukan penelitian pada akhir bab dipakai untuk memeriksa istilah, batas teori, dan konteks; tidak ada prosa, tata letak, gambar, atau kode mereka yang disalin.
Kita memakai norma pada ruang berdimensi hingga dan norma dual Untuk bagian proksimal dan minibatch, norma tersebut adalah norma Euklides. Filtrasi memuat seluruh informasi sebelum oracle pada iterasi dipanggil. Dengan demikian, terukur terhadap .
Masalah komposit dan oracle stokastik
Pertimbangkan masalah komposit dengan konveks, terdiferensialkan, dan mempunyai gradien -Lipschitz, sedangkan proper, konveks, dan semikontinu bawah. Andaikan himpunan peminim tidak kosong.
Oracle pada mengembalikan dan memenuhi, hampir pasti, Besaran boleh berubah sepanjang iterasi. Notasi ini sengaja memisahkan varians oracle dari konstanta kemulusan dan dari fungsi kerugian pada model statistik.
Gradien proksimal stokastik
Dengan ukuran langkah , pembaruan gradien proksimal stokastik ialah Jika adalah fungsi indikator himpunan konveks tertutup , pembaruan ini menjadi proyeksi stokastik. Jika , pembaruan ini menjadi ambang lunak setelah langkah gradien stokastik.
Algoritma 1: gradien proksimal stokastik. Pilih . Untuk , panggil oracle pada untuk memperoleh , pilih , lalu hitung [orig01:eq:spg-update]. Untuk pelaporan ergodik, simpan rerata iterat yang disebutkan dalam teorema berikut.
Ambil dan tetapkan dengan . Di bawah [orig01:eq:oracle], iterasi [orig01:eq:spg-update] memenuhi
Proof. Tuliskan , , dan . Kondisi optimalitas proks memberikan Ketaksamaan subgradien untuk , kekonveksan , dan lemma penurunan untuk yang -mulus menghasilkan Pecah suku terakhir sebagai . Karena terukur terhadap dan , suku kedua hilang dalam ekspektasi bersyarat. Untuk suku pertama, maksimisasi kuadrat atau ketaksamaan Young memberi dengan ketaksamaan terakhir menggunakan . Mengambil ekspektasi bersyarat membuktikan klaim. ◻
Andaikan untuk semua , dengan . Ambil , , dan definisikan Maka, untuk ,
Proof. Terapkan Lema [orig01:lemma:spg-one-step] dengan , ambil ekspektasi penuh, lalu jumlahkan untuk . Suku jarak meneleskop dan suku terakhir yang tidak negatif dapat dibuang. Kekonveksan memberi , yang menyelesaikan bukti. ◻
Jika , , dan batas kemulusan tidak aktif, pilihan yang menyeimbangkan kedua suku pada [orig01:eq:spg-ergodic-rate] ialah Dalam praktik, dan biasanya tidak diketahui. Rumus ini adalah penjelas skala, bukan resep penalaan tanpa diagnosis.
Minibatch: identitas varians dan biaya oracle
Ambil sampel bersyarat iid dengan rerata dan varians kuadrat paling besar . Penaksir minibatch dengan penggantian adalah
Penaksir [orig01:eq:minibatch] tak bias dan memenuhi
Proof. Setelah dikondisikan pada , simpangan setiap sampel mempunyai rerata nol dan pasangan simpangan yang berbeda saling bebas. Semua suku silang dalam kuadrat norma mempunyai ekspektasi nol. Tersisa suku diagonal yang masing-masing dikalikan . ◻
Untuk jumlah hingga , pengambilan sampel tanpa penggantian mempunyai koreksi populasi hingga yang tidak boleh disamakan dengan rumus iid.
Andaikan dan . Pada suatu , tuliskan dan . Jika dipilih seragam dari semua subhimpunan berukuran tanpa penggantian, maka
Proof. Peluang inklusi satu indeks adalah dan peluang inklusi dua indeks berbeda adalah . Kembangkan kuadrat norma. Karena , berlaku . Substitusi kedua peluang inklusi lalu penyederhanaan memberikan faktor pada [orig01:eq:finite-population]. Khusus , varians tepat nol. ◻
Minibatch menurunkan varians per iterasi, tetapi memakai evaluasi gradien komponen. Jika biaya serial yang tersedia adalah , batas tertala ideal menjadi : tidak ada percepatan kompleksitas oracle hanya dari pengelompokan. Keuntungan nyata dapat datang dari paralelisme, arsitektur perangkat, pengurangan komunikasi, atau batas langkah yang lebih baik. Pernyataan ini juga menjelaskan mengapa perbandingan hanya berdasarkan banyak iterasi dapat menyesatkan.
Penurunan cermin stokastik
Proyeksi Euklides memperlakukan semua arah dengan geometri yang sama. Pada simpleks, matriks semidefinit positif, atau ruang dengan struktur sparsitas, pilihan geometri lain dapat lebih alami.
Misalkan tak kosong, tertutup, dan konveks. Ambil fungsi pembangkit yang bernilai hingga dan kontinu pada , terdiferensialkan di setiap iterat, dan -konveks kuat terhadap . Untuk setiap dan setiap titik keterdiferensialan , Divergensi Bregman yang dibangkitkan oleh ialah Divergensi ini tidak harus simetris dan bukan metrik, tetapi .
Untuk fungsi konveks , andaikan oracle menghasilkan dengan Ambil dan andaikan masalah berikut hampir pasti mencapai peminim unik pada titik keterdiferensialan : Untuk pembanding optimum yang dipakai di bawah, andaikan pula . Asumsi eksplisit ini dapat diganti dengan syarat Legendre/interior standar yang menjamin sifat-sifat yang sama.
Algoritma 2: penurunan cermin stokastik. Pilih dalam daerah terdiferensialkan . Pada iterasi , ambil subgradien stokastik , selesaikan masalah Bregman [orig01:eq:mirror-update], dan perbarui rerata berbobot .
Untuk setiap , pembaruan [orig01:eq:mirror-update] memenuhi
Proof. Kondisi optimalitas pada himpunan memberi Identitas tiga titik Bregman mengubah bagian yang memuat menjadi Tambahkan pada kedua sisi. Gunakan , dualitas norma, dan ketaksamaan Young. Hasilnya tepat [orig01:eq:mirror-one-step]. ◻
Di bawah [orig01:eq:mirror-oracle], untuk definisikan dan Untuk setiap ,
Proof. Ambil ekspektasi bersyarat pada Lema [orig01:lemma:mirror-one-step]. Karena terukur terhadap dan , Jumlahkan sehingga divergensi Bregman meneleskop, lalu gunakan kekonveksan pada rerata berbobot. ◻
Untuk dan , gunakan . Ruas kanan kemudian menjadi Pada geometri Euklides, dan pembaruan cermin menjadi subgradien stokastik terproyeksi. Jadi metode cermin memperluas, bukan menduplikasi, teorema stokastik Habring.
Simpleks dan pembaruan eksponensial
Pada simpleks , ambil , dengan konvensi perluasan kontinu . Fungsi ini kontinu pada dan terdiferensialkan pada interior relatifnya. Mulai dari . Divergensi Bregman ialah divergensi Kullback–Leibler. Terhadap norma , fungsi ini -konveks kuat. Kondisi optimalitas memberi pembaruan tertutup Jika seragam, maka . Dengan batas , Teorema [orig01:theorem:mirror-ergodic] memberi skala setelah penalaan ideal. Ketergantungan logaritmik pada dimensi menjelaskan kegunaan geometri entropi di simpleks.
Dari SAGA ke pembaruan proksimal
Untuk masalah jumlah hingga , modul Becker 3 mendefinisikan penaksir SAGA dan membuktikan . Untuk masalah komposit, perubahan algoritmik yang benar bukan mengurangkan subgradien , melainkan memakai langkah proksimal
Andaikan asumsi masalah komposit berlaku, , dan definisikan Untuk dan , Jika dengan dan , maka
Proof. Terapkan bukti Teorema [orig01:theorem:spg-ergodic] dengan dan varians bersyarat . Untuk klaim terakhir, gunakan jumlah deret geometri hingga yang dibatasi oleh . ◻
Korolari ini menjelaskan hubungan yang hilang, tetapi sengaja tidak mengklaim bahwa varians SAGA selalu turun geometrik. Pembuktian klaim semacam itu memerlukan fungsi Lyapunov gabungan untuk galat iterat dan galat tabel. Teorema laju linear bersyarat pada modul Becker 3 menyediakan hasil khusus untuk kasus mulus dan konveks kuat; korolari di sini menunjukkan bagaimana penaksir yang sama masuk ke masalah komposit.
Laboratorium 1: regresi renggang dengan biaya oracle tetap
Laboratorium terbuka pada
labs/original-01/stochastic-composite-lab.py membangun
masalah regresi kuadrat dengan regularisasi
,
Skrip membandingkan
gradien proksimal stokastik, minibatch dengan penggantian, dan Prox-SAGA
pada anggaran evaluasi gradien komponen yang sama. Referensi numerik
dihitung oleh FISTA deterministik sampai norma pemetaan gradien
proksimal memenuhi toleransi yang dilaporkan.
Tugas laboratorium:
jalankan skrip tanpa mengubah benih acak dan verifikasikan konfigurasi beku yang dicatat pada berkas hasil;
bandingkan kesenjangan objektif terhadap evaluasi gradien komponen, bukan hanya terhadap iterasi;
periksa apakah minibatch menurunkan varians arah pada checkpoint yang sama;
ubah ukuran minibatch tetapi pertahankan anggaran oracle, lalu jelaskan perbedaan antara keuntungan statistik dan keuntungan paralel;
ganti dan ukur perubahan sparsitas serta norma pemetaan gradien proksimal;
laporkan setiap hasil yang bertentangan dengan batas teori beserta asumsi yang mungkin tidak terpenuhi.
CSV dan JSON yang dihasilkan adalah permukaan aksesibel utama. Grafik SVG hanya merupakan bantuan visual dan tidak menjadi satu-satunya pembawa informasi.
Dengan konfigurasi beku (, , , 12 epoch, dan 3.840 evaluasi gradien komponen per metode), nilai referensi FISTA adalah dengan norma pemetaan gradien proksimal . Hasil terminal deterministik adalah:
| Metode | Kesenjangan objektif | Norma pemetaan | Tak nol |
|---|---|---|---|
| Proks-SGD, | 33 | ||
| Proks-minibatch, | 10 | ||
| Prox-SAGA | 5 |
Angka tersebut adalah satu eksperimen terkontrol, bukan urutan kinerja universal. Berkas hasil JSON, CSV, dan SVG mempunyai SHA-256 berikut:
86ff701a…c447
61a6591a…5d37
87c772d9…2830.
Identitas lengkap dicatat dalam receipt QA.
Latihan, petunjuk, dan solusi lengkap
Untuk dan , tuliskan pembaruan [orig01:eq:spg-update] ketika minibatch dipakai. Tunjukkan bahwa setiap koordinat diperoleh dengan ambang lunak.
Petunjuk bertahap. (i) Hitung gradien setiap suku kuadrat. (ii) Gunakan keterpisahan norma . (iii) Selesaikan masalah proksimal skalar pada tiga kasus tanda.
Solusi lengkap. Jika , maka Tuliskan . Karena terpisah per koordinat, Rumus ini mengikuti dengan memeriksa kondisi pada , , dan .
Mulai dari [orig01:eq:spg-pathwise]. Buktikan batas yang lebih tajam untuk .
Petunjuk bertahap. (i) Maksimalkan terhadap . (ii) Ambil . (iii) Gunakan ketakbiasan hanya setelah memisahkan .
Solusi lengkap. Dualitas norma Euklides dan pelengkapan kuadrat memberikan Suku mempunyai ekspektasi bersyarat nol. Substitusi batas varians menyelesaikan klaim. Lema utama memakai hanya untuk mengganti faktor ini dengan batas sederhana .
Untuk , buktikan Proposisi [orig01:prop:finite-population] dengan peubah indikator . Periksa kasus dan .
Petunjuk bertahap. (i) Gunakan . (ii) Untuk , gunakan . (iii) Pakai .
Solusi lengkap. Karena , ekspektasi kuadrat normanya adalah Suku silang sama dengan . Koefisien akhirnya , dan penggantian memberi rumus yang diminta. Untuk faktor menjadi satu; untuk menjadi nol.
Turunkan [orig01:eq:exponentiated-update] dari [orig01:eq:mirror-update]. Jelaskan mengapa iterat yang mulai positif tetap positif dan berjumlah satu.
Petunjuk bertahap. (i) Tambahkan pengali Lagrange untuk . (ii) Diferensialkan terhadap setiap . (iii) Gunakan kendala jumlah untuk menentukan faktor normalisasi.
Solusi lengkap. Dengan konvensi dan pada simpleks, kondisi stasioner adalah Jadi . Menjumlahkan seluruh koordinat menunjukkan bahwa faktor terakhir adalah kebalikan jumlah pada penyebut [orig01:eq:exponentiated-update]. Eksponensial dan penyebut positif mempertahankan kepositifan, sedangkan normalisasi mempertahankan jumlah satu.
Andaikan batas tertala ideal adalah dan satu iterasi minibatch memakai evaluasi gradien komponen. Untuk anggaran serial , tentukan ketergantungannya pada . Sebutkan dua keadaan ketika minibatch tetap berguna.
Petunjuk bertahap. (i) Ganti dengan . (ii) Bedakan waktu dinding dari jumlah panggilan oracle. (iii) Perhatikan pengambilan sampel tanpa penggantian.
Solusi lengkap. Substitusi memberi yang bebas dari . Jadi model ideal tidak memprediksi penghematan evaluasi gradien serial. Minibatch tetap berguna jika evaluasi dapat diparalelkan atau komunikasi dapat diamortisasi; ia juga dapat membantu melalui koreksi populasi hingga tanpa penggantian, vektorisasi perangkat, atau batas langkah yang tidak tercakup dalam model sederhana.
Mulai dari [orig01:eq:prox-saga-bridge]. Jika , turunkan batas eksplisit menggunakan bilangan harmonik . Bandingkan dengan kasus geometrik.
Petunjuk bertahap. (i) Jumlahkan batas varians. (ii) Gunakan . (iii) Jangan menyimpulkan laju iterat terakhir dari batas ergodik.
Solusi lengkap. Substitusi langsung memberi Peluruhan geometrik menjadikan jumlah varians terbatas secara seragam dan menghasilkan tanpa faktor logaritmik. Kedua kesimpulan hanya berlaku untuk rerata dalam korolari ini; laju iterat terakhir memerlukan analisis tambahan.
Peta asumsi dan batas klaim
| Hasil | Asumsi penentu | Yang tidak diklaim |
|---|---|---|
| Proksimal stokastik | konveks dan -mulus; proper, tertutup, konveks; oracle tak bias; varians terbatas | laju iterat terakhir atau konvergensi nonkonveks |
| Minibatch iid | sampel bersyarat bebas dengan penggantian | koreksi populasi hingga |
| Minibatch tanpa penggantian | subhimpunan seragam berukuran dari populasi dengan | independensi antaranggota batch |
| Cermin stokastik | pembangkit -konveks kuat; pembaruan terdefinisi; ; momen dual kedua terbatas | simetri divergensi Bregman |
| Prox-SAGA penghubung | ketakbiasan SAGA dan kontrol varians yang dinyatakan | peluruhan geometrik varians tanpa Lyapunov |
Bab ini tidak membahas ketaksamaan variasional atau operator monoton maksimal; materi tersebut adalah tranche asli berikutnya. Bab ini juga tidak mengulang LP/MIP, simpleks sebagai algoritma pemrograman linear, dualitas LP, sensitivitas LP, jaringan, atau optimisasi diskret yang merupakan cakupan O018. Kata simpleks di sini hanya menunjuk himpunan probabilitas .
Rujukan matematis dan saksi verifikasi
Andreas Habring, Lecture Notes: Convex Optimization, arXiv:2607.11664v1, khususnya operator proksimal dan subgradien stokastik.
Clément W. Royer, Lecture Notes on Stochastic Gradient Methods, edisi 2023/2024, khususnya pembahasan minibatch dan biaya epoch; dipakai sebagai saksi perbandingan, bukan sumber prosa bab ini.
Lorenzo Rosasco, Silvia Villa, dan Bang Công Vũ, Convergence of Stochastic Proximal Gradient Algorithm, arXiv:1403.5074, sebagai rujukan primer bagi keluarga metode proksimal stokastik.
Amir Beck dan Marc Teboulle, Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization, Operations Research Letters 31 (2003), 167–175, DOI:10.1016/S0167-6377(02)00231-6.
Aaron Defazio, Francis Bach, dan Simon Lacoste-Julien, SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, arXiv:1407.0202v3.
Suplemen Terbatas: Douglas–Rachford
Pemisahan Douglas–Rachford
Bab ini menyajikan metode Douglas–Rachford untuk meminimumkan jumlah dua fungsi konveks melalui operator proksimal. Notasi subdiferensial dan bentuk dual dinormalkan agar persamaan konsisten dengan parameter skala yang dipakai dalam algoritma.
Kredit catatan donor.
Catatan donor menyatakan bahwa bagian ini mengikuti Bauschke dan Combettes (B&C), edisi kedua (2017), §20.3, dan mengatribusi analisis Douglas–Rachford kepada Lions dan Mercier (1979). Kredit turunan tersebut dipertahankan; edisi ini tidak mengimpor isi dari bagian yang bersebelahan.
Ambil , yaitu fungsi konveks proper dan semikontinu bawah. Seperti pada donor, andaikan terdapat titik pelana primal–dual dan aturan jumlah subdiferensial berlaku. Masalah primal adalah Dengan konjugat Fenchel , bentuk maksimisasi dual yang konsisten adalah Secara ekuivalen, titik dual yang sama meminimumkan . Tanda pada bentuk dual donor diperbaiki secara terbuka dalam edisi ini.
Untuk dan , tuliskan Pilih , parameter skala , dan parameter relaksasi tetap . Iterasi Douglas–Rachford adalah Catatan donor memperingatkan bahwa konvensi untuk pada bagian lain mungkin memakai kebalikannya. Di sini selalu memiliki arti yang ditetapkan oleh [becker:eq:dr-prox-definition].
Limit bayangan dan persamaan titik tetap
Jika barisan pada [becker:eq:dr-iteration] memenuhi dan maka adalah solusi optimal masalah [becker:eq:dr-primal].
Proof. Karena konvergen, , sehingga . Operator proksimal kontinu, maka Syarat optimalitas kedua operator proksimal memberi Menjumlahkan kedua inklusi dan memakai aturan [becker:eq:dr-sum-rule] menghasilkan , yang setara dengan optimalitas primal. ◻
Persamaan titik tetapnya dapat dilihat langsung dari syarat optimalitas. Untuk solusi primal , pilih dengan , lalu definisikan . Dengan demikian Jadi, dengan syarat solusi menjadi . Pembaruan pada [becker:eq:dr-iteration] merupakan iterasi relaksasi menuju titik tetap itu. Faktor dan pilihan subgradien ditulis eksplisit karena subdiferensial pada umumnya bernilai himpunan dan tidak dapat diperlakukan sebagai satu vektor .
Hubungan dengan ADMM
Pernyataan singkat donor bahwa ADMM merupakan kasus khusus Douglas–Rachford dipahami dalam bentuk yang lazim dan lebih presisi: ADMM dapat diperoleh sebagai pemisahan Douglas–Rachford yang diterapkan pada masalah dual yang sesuai. Bagian ADMM yang mendahului rentang beku tidak diimpor ke modul ini.
Operator Monoton dan Pemisahan
Ketaksamaan Variasional, Operator Monoton, Resolven, dan Pemisahan
Bab sebelumnya menghubungkan metode proksimal dengan oracle stokastik, minibatch, geometri Bregman, dan reduksi varians. Bab ini mengambil langkah abstraksi berikutnya: kondisi optimalitas diperlakukan sebagai pencarian nol operator bernilai himpunan. Kerangka ini menyatukan ketaksamaan variasional, subdiferensial, kerucut normal, langkah proksimal implisit, pemisahan maju–mundur, dan pemisahan Douglas–Rachford.
Seluruh uraian, bukti penghubung, latihan, solusi, dan laboratorium dalam bab ini ditulis secara mandiri. Bab Habring tentang subgradien dan metode gradien proksimal serta modul Becker tentang Douglas–Rachford dipakai sebagai prasyarat dan saksi konsistensi. Tidak ada prosa, tata letak, gambar, latihan, solusi, atau kode dari sumber tersebut yang disalin.
Untuk operator bernilai himpunan , definisikan Notasi menekankan bahwa nilai operator dapat berupa himpunan, bukan satu vektor. Masalah dasar bab ini ialah
Kemonotonan dan kemaksimalan
Operator disebut monoton jika Ia disebut -monoton kuat, dengan , jika ruas kanan dapat diganti oleh .
Operator monoton disebut monoton maksimal jika tidak ada operator monoton lain yang grafiknya memuat secara ketat. Kata maksimal merujuk pada inklusi grafik, bukan pada nilai fungsi atau ukuran norma.
Kemonotonan saja belum menjamin bahwa operator mempunyai cukup banyak nilai untuk mendefinisikan langkah implisit pada setiap titik. Sebagai contoh, operator dengan grafik tunggal monoton, tetapi tidak maksimal, karena grafik itu dapat diperluas menjadi grafik operator nol pada seluruh .
Jika proper dan konveks, maka monoton.
Proof. Ambil dan . Ketaksamaan subgradien memberi Menjumlahkan keduanya menghasilkan . ◻
Teorema Rockafellar memperkuat hasil tersebut: jika juga semikontinu bawah, maka monoton maksimal. Bab ini memakai teorema itu sebagai hasil dasar, bukan membuktikan kembali argumen pemisahan lengkapnya. Akibat pentingnya ialah kerucut normal dan operator proksimal masuk ke dalam kerangka yang sama.
Ketaksamaan variasional sebagai inklusi monoton
Untuk himpunan konveks tertutup tak kosong , kerucut normal pada didefinisikan oleh Karena , operator ini monoton maksimal.
Untuk pemetaan , masalah ialah mencari sedemikian sehingga
Suatu titik menyelesaikan jika dan hanya jika Secara ekuivalen, untuk setiap ,
Proof. Menurut [orig02:eq:normal-cone], inklusi tepat berarti dan untuk setiap . Membalik tanda menghasilkan [orig02:eq:vi]. Karakterisasi proyeksi dengan memberi ekuivalensi proyeksi. ◻
Jika untuk fungsi konveks terdiferensialkan , kondisi ini adalah kondisi optimalitas bagi . Namun, ketaksamaan variasional lebih luas: pemetaan monoton tidak harus merupakan gradien.
Jika -monoton kuat pada , maka mempunyai paling banyak satu solusi.
Proof. Andaikan dan keduanya solusi. Masukkan ke ketaksamaan untuk dan ke ketaksamaan untuk . Setelah dijumlahkan, Kemonotonan kuat memberi ruas kiri sekurang-kurangnya . Jadi . ◻
Andaikan -monoton kuat dan -Lipschitz pada , dengan . Untuk pemetaan merupakan kontraksi dengan faktor Karena itu, mempunyai tepat satu solusi , dan iterasi memenuhi .
Proof. Sifat tak ekspansif proyeksi, kemonotonan kuat, dan sifat Lipschitz memberi Rentang membuat faktor kuadrat lebih kecil dari satu. Himpunan tertutup lengkap, maka teorema titik tetap Banach memberi satu-satunya titik tetap dan konvergensi geometrik. Menurut [orig02:eq:vi-projection], titik tetap itu tepat solusi VI. ◻
Bab ini tidak memakai simpleks sebagai algoritma pemrograman linear. Proyeksi, kerucut normal, dan ketaksamaan variasional di sini berada dalam analisis konveks kontinu dan tidak mengimpor LP/MIP, dualitas atau sensitivitas LP, jaringan, maupun optimisasi diskret dari O018.
Resolven operator monoton maksimal
Untuk , definisikan resolven dan resolven terefleksi Secara apriori, invers tersebut dapat bernilai himpunan atau tidak terdefinisi pada sebagian titik. Untuk operator monoton , teorema Minty menutup kedua celah itu: di ruang Euclid, monoton maksimal jika dan hanya jika untuk setiap .
Jika monoton maksimal dan , maka bernilai tunggal pada seluruh dan Akibatnya, tak ekspansif dan tak ekspansif.
Proof. Teorema Minty memberi keberadaan pada setiap . Ambil dan . Maka dan . Kemonotonan memberi yang sama dengan [orig02:eq:firm-nonexpansive]. Jika dua nilai resolven berkorespondensi dengan yang sama, ketaksamaan itu memaksa keduanya sama, sehingga resolven bernilai tunggal. Ketaksamaan Cauchy–Schwarz memberi sifat tak ekspansif. Terakhir, ◻
Untuk setiap , Jika , maka ; jika , maka .
Proof. Ekuivalensi pertama langsung dari . Dua identitas terakhir adalah kondisi optimalitas proksimal dan proyeksi. ◻
Metode titik proksimal
Metode titik proksimal menerapkan resolven secara berulang: Ini adalah langkah implisit karena .
Andaikan monoton maksimal dan . Maka untuk setiap , iterasi [orig02:eq:ppa] memenuhi Dalam dimensi hingga, konvergen ke suatu titik dalam .
Proof. Karena , terapkan ketaksamaan [orig02:eq:firm-nonexpansive] pada dan , lalu gunakan identitas Hasilnya adalah [orig02:eq:ppa-fejer]. Jadi jarak ke setiap titik tidak membesar dan .
Barisan terbatas, sehingga mempunyai titik gugus . Sepanjang subbarisan yang menuju , berlaku dan . Grafik operator monoton maksimal tertutup; karena , diperoleh . Sifat Fejér terhadap kemudian memaksa seluruh barisan konvergen ke . ◻
Hasil ini menjelaskan kestabilan langkah implisit tanpa mengklaim bahwa selalu mudah dihitung. Pemisahan operator berguna ketika resolven bagian-bagian operator jauh lebih sederhana daripada resolven jumlahnya.
Pemisahan maju–mundur
Pemetaan tunggal disebut -kokorsif jika Kokorsivitas lebih kuat daripada gabungan kemonotonan dan kontinuitas Lipschitz. Gradien fungsi konveks dengan gradien -Lipschitz bersifat -kokorsif.
Untuk monoton maksimal dan -kokorsif, definisikan
Andaikan . Maka Untuk , iterasi konvergen di ruang berdimensi hingga ke suatu nol .
Proof. Dari definisi resolven, Selanjutnya, [orig02:eq:cocoercive] memberi Jadi langkah maju tererata untuk rentang langkah yang dinyatakan. Resolven tak ekspansif kukuh (firmly nonexpansive), dan komposisinya tererata dengan parameter . Iterasi Picard pemetaan tererata dengan himpunan titik tetap tak kosong bersifat Fejér, residunya menuju nol, dan dalam dimensi hingga konvergen ke suatu titik tetap. Gunakan ekuivalensi [orig02:eq:fb-fixed]. ◻
Dengan dan , pemetaan ini tepat menjadi langkah gradien proksimal yang telah diterjemahkan dari Habring. Nilai tambah bab ini ialah batas operatornya: langkah eksplisit memerlukan struktur seperti kokorsivitas, bukan hanya kemonotonan.
Perbaikan ekstragradien untuk operator monoton Lipschitz
Untuk VI dengan monoton dan -Lipschitz, kokorsivitas belum tentu berlaku. Langkah proyeksi tunggal dapat diganti oleh dua evaluasi berurutan:
Jika himpunan solusi tidak kosong, maka untuk setiap solusi , Dalam dimensi hingga, konvergen ke suatu solusi VI.
Proof. Karakterisasi proyeksi untuk pembaruan kedua dan sifat solusi VI, bersama kemonotonan , memberi Karakterisasi proyeksi untuk , diuji pada , memberi Substitusi, sifat Lipschitz, dan menghasilkan lalu [orig02:eq:extragradient-fejer]. Kedua selisih berurutan menuju nol. Ambil titik gugus dan lewatkan ketaksamaan proyeksi pertama ke limit; diperoleh untuk setiap . Jadi setiap titik gugus adalah solusi, dan sifat Fejér memaksa konvergensi seluruh barisan. ◻
Pemisahan Douglas–Rachford dan limit bayangan
Andaikan dan monoton maksimal. Definisikan Karena kedua resolven terefleksi tak ekspansif, komposisinya tak ekspansif dan tak ekspansif kukuh.
Andaikan . Barisan konvergen dalam dimensi hingga menuju , dan bayangannya memenuhi .
Proof. Jika titik tetap, tetapkan dan . Persamaan titik tetap dalam bentuk kedua [orig02:eq:dr-operator] memberi . Kondisi resolven lalu memberi sehingga .
Sebaliknya, jika , pilih dengan dan tetapkan . Maka dan , jadi titik tetap. Himpunan titik tetap karena itu tidak kosong. Kekukuhan tak ekspansif dan argumen Fejér yang sama dengan metode titik proksimal memberi . Kontinuitas resolven memberi , yang merupakan nol jumlah. ◻
Modul Becker 2 sudah menyediakan bentuk proksimal konkret untuk dan , berikut penormalan skala serta hubungan primal–dualnya. Bagian ini tidak mengulang materi tersebut; ia menjelaskan mengapa rumus yang sama bekerja untuk operator monoton maksimal yang tidak harus merupakan subdiferensial.
Mengapa kemonotonan saja tidak cukup untuk langkah maju
Ambil dan operator linear Karena untuk semua , operator monoton. Ia juga monoton maksimal karena invertibel untuk setiap . Namun, tidak -kokorsif untuk satu pun : ruas kiri ketaksamaan kokorsif selalu nol, sedangkan ruas kanan positif bila .
Langkah maju memenuhi sehingga menjauh dari nol untuk . Sebaliknya, langkah resolven memenuhi Contoh ini memisahkan dengan jelas tiga gagasan: monoton, Lipschitz, dan kokorsif tidak saling dapat dipertukarkan.
Laboratorium 2: inklusi linear-skew dengan regularisasi
Laboratorium pendamping mempelajari Bagian simetris membuat operator monoton kuat, sedangkan bagian skew menjaganya di luar kelas gradien fungsi konveks biasa. Operator itu -kokorsif dengan
Kode membandingkan tiga jejak: maju–mundur dengan langkah di dalam rentang , maju–mundur dengan langkah beku di luar jaminan teorema, dan Douglas–Rachford dengan resolven linear eksak serta ambang lunak. Solusi acuan unik diperoleh dengan enumerasi sembilan pola aktif tanda , bukan dengan menyembunyikan jawaban di dalam algoritma. NumPy memeriksa sistem linear, residu inklusi, dan identitas resolven. Diagnostik kedua memakai operator skew murni untuk mencocokkan faktor norma eksak langkah maju, ekstragradien, dan resolven hingga galat pembulatan.
Tugas laboratorium:
Jalankan konfigurasi beku dan cocokkan ringkasan JSON serta CSV.
Verifikasi secara numerik bahwa langkah stabil memenuhi , sedangkan langkah diagnostik berada di luar rentang itu.
Periksa bahwa residu titik tetap menuju nol bagi jejak yang diterima.
Ubah tanpa mengubah dan jelaskan pengaruhnya pada serta rentang langkah maju–mundur.
Gunakan CSV, bukan gambar saja, untuk membandingkan residu akhir dan galat terhadap solusi acuan.
Pada diagnostik skew murni, cocokkan faktor kontraksi ekstragradien dengan hasil numerik.
Latihan, petunjuk, dan solusi lengkap
Untuk dan dengan , tentukan solusi melalui inklusi kerucut normal.
Petunjuk bertahap. (i) Pisahkan kasus dan . (ii) Untuk , . (iii) Pada , .
Solusi lengkap. Jika , inklusi memberi , yang sah hanya bila . Pada , inklusi menjadi , atau . Jadi solusi tunggal adalah
Definisikan operator melalui Buktikan bahwa monoton tetapi tidak monoton maksimal.
Petunjuk bertahap. (i) Uji definisi kemonotonan pada satu pasangan yang tersedia. (ii) Cari operator monoton dengan grafik lebih besar.
Solusi lengkap. Satu-satunya pasangan grafik yang dapat dibandingkan adalah dengan dirinya sendiri, sehingga hasil kali dalam pada definisi bernilai nol. Jadi monoton. Operator nol untuk semua juga monoton dan . Karena ada perluasan monoton ketat, tidak maksimal.
Mulai dari [orig02:eq:firm-nonexpansive]. Buktikan bahwa tak ekspansif.
Petunjuk bertahap. (i) Tetapkan dan . (ii) Kembangkan kuadrat norma .
Solusi lengkap. Perluasan langsung memberi karena kekukuhan tak ekspansif menyatakan .
Untuk pada [orig02:eq:skew], hitung norma operator langkah maju , langkah ekstragradien , dan resolven .
Petunjuk bertahap. (i) Gunakan dan . (ii) Hitung kuadrat norma pada vektor sembarang.
Solusi lengkap. dan dengan normanya . Untuk ekstragradien, suku silang kembali hilang dan normanya bila . Selain itu, , sehingga norma inversnya .
Untuk dengan , buktikan bahwa pemetaan bersifat -kokorsif dengan .
Petunjuk bertahap. (i) Konstanta hilang ketika dua nilai dikurangkan. (ii) Gunakan dan .
Solusi lengkap. Untuk , Bila , kesamaan kokorsif berlaku langsung. Bila , membagi kedua identitas memberi tepat .
Andaikan dan tetapkan . Tunjukkan secara langsung bahwa .
Petunjuk bertahap. (i) Tulis . (ii) Gunakan bentuk kedua [orig02:eq:dr-operator] untuk memperoleh . (iii) Jumlahkan dua inklusi resolven.
Solusi lengkap. Persamaan titik tetap memberi , sehingga . Dari definisi resolven, Kedua unsur menjumlah menjadi nol, maka .
Peta asumsi dan batas klaim
| Hasil | Asumsi penentu | Yang tidak diklaim |
|---|---|---|
| Ekuivalensi VI | konveks tertutup tak kosong; definisi kerucut normal | keberadaan solusi tanpa asumsi tambahan |
| Resolven | monoton maksimal; | resolven jumlah mudah dihitung |
| Titik proksimal | himpunan nol tak kosong; dimensi hingga; langkah tetap positif | laju linear tanpa kemonotonan kuat |
| Maju–mundur | monoton maksimal; -kokorsif; | konvergensi untuk operator monoton Lipschitz umum |
| Ekstragradien | monoton dan -Lipschitz; konveks tertutup; | satu evaluasi operator per iterasi |
| Douglas–Rachford | monoton maksimal; nol jumlah tak kosong | setiap iterat bayangan sudah merupakan solusi |
| Laboratorium | konfigurasi linear-skew dua dimensi yang dibekukan | kinerja universal atau peringkat algoritma |
Rujukan matematis dan saksi verifikasi
Andreas Habring, Lecture Notes: Convex Optimization, arXiv:2607.11664v1, khususnya subdiferensial, operator proksimal, dan gradien proksimal; dipakai sebagai tulang punggung prasyarat.
Stephen Becker dan Mitchell Krock, catatan kelas optimisasi konveks pada commit beku
98ed693, khususnya modul Douglas–Rachford yang telah diterima; dipakai untuk menjaga notasi dan batas nonduplikasi.George J. Minty, Monotone (Nonlinear) Operators in Hilbert Space, Duke Mathematical Journal 29 (1962), 341–346, DOI:10.1215/S0012-7094-62-02933-2.
R. Tyrrell Rockafellar, On the Maximal Monotonicity of Subdifferential Mappings, Pacific Journal of Mathematics 33 (1970), 209–216, DOI:10.2140/PJM.1970.33.209.
Pierre-Louis Lions dan Bertrand Mercier, Splitting Algorithms for the Sum of Two Nonlinear Operators, SIAM Journal on Numerical Analysis 16 (1979), 964–979, DOI:10.1137/0716071.
Asesmen dan Penutupan Kursus
Asesmen, Laboratorium, dan Proyek Penutup
Bab ini menyediakan lapisan penutup kursus yang dapat dipakai untuk belajar mandiri: peta asesmen kumulatif, diagnostik prasyarat, enam set soal, rubrik pembuktian, ujian tengah dan akhir, dua laboratorium komputasi, serta satu proyek kapstone. Setiap soal mempunyai petunjuk bertahap, jawaban singkat, dan solusi acuan lengkap. Kode laboratorium dan proyek menghasilkan sertifikat deterministik yang dapat diperiksa tanpa perangkat lunak berpemilik.
Seluruh uraian, soal, solusi, rubrik, kode, dan instans sintetik dalam bab ini ditulis mandiri dan tersedia berdasarkan CC BY-SA 4.0. Bab ini tidak menyalin materi O018 tentang program linear atau bilangan bulat, simpleks, sensitivitas LP, ataupun optimisasi jaringan. Pendamping MIT OCW, Royer, dan Penn tetap merupakan karya terpisah dengan hak dan atribusinya sendiri.
Peta asesmen dan kontrak topologi
Bagian ini memetakan asesmen Original-03 tanpa mengulang bunyi soal. Seluruh teks baru pada tranche ini ditulis secara independen dan dilisensikan di bawah CC BY-SA 4.0. Notasi mengikuti spine Habring serta suplemen dan tranche yang sudah diterima, tetapi tidak ada butir donor yang disalin. Materi program linear, integer, simpleks, pemodelan riset operasi, dan wilayah O018 lainnya sengaja tidak dimasukkan.
Kontrak yang dapat diurai mesin adalah sebagai berikut. Setiap butir
induk memiliki ID *.problem.NNNN. Setiap subbutir memiliki
ID *.prompt.NNNN dan tepat satu pasangan
*.hint1.NNNN/*.hint2.NNNN, satu
*.answer.NNNN, serta satu *.solution.NNNN.
Komentar ORIG03-ASSESSMENT-MAP-ID pada peta ini hanya
merupakan rujukan nondeklaratif. Deklarasi otoritatif
ORIG03-STABLE-ID dan label LaTeX yang berpadanan berada
tepat pada butir soal di modul 01–10. Tujuh label
orig03:rubric:proof:0001 sampai
orig03:rubric:proof:0007 disediakan sebagai rujukan logis
bagi rubrik bukti yang dihimpun oleh agregator.
Lima puluh empat prompt baru
Diagnostik prasyarat: 20 prompt.
diag.prompt.0001: norma dasar dan aritmetika vektor.diag.prompt.0002: rantai ketaksamaan norma.diag.prompt.0003: proyeksi pada hiperbidang.diag.prompt.0004: karakterisasi proyeksi konveks.diag.prompt.0005: koordinat kombinasi konveks.diag.prompt.0006: kestabilan kekonveksan terhadap irisan.diag.prompt.0007: gradien dan Hessian kuadratik.diag.prompt.0008: konstanta kuat-konveks dan mulus.diag.prompt.0009: penyangga afin orde pertama.diag.prompt.0010: stasioneritas dan optimalitas global.diag.prompt.0011: subdiferensial nilai mutlak.diag.prompt.0012: ambang lunak skalar.diag.prompt.0013: ekspektasi dan varians diskret.diag.prompt.0014: rata-rata sampel independen.diag.prompt.0015: penyelesaian rekurensi kontraktif.diag.prompt.0016: kompleksitas iterasi geometrik.diag.prompt.0017: kerucut normal dan optimalitas terkendala.diag.prompt.0018: bentuk titik tetap proyeksi.diag.prompt.0019: ortogonalitas dalam Cauchy–Schwarz.diag.prompt.0020: ketaksamaan Young berbobot.
Set soal dasar konveks: 12 prompt.
ps01.prompt.0001: maksimum fungsi afin.ps01.prompt.0002: subdiferensial fungsi nilai mutlak.ps01.prompt.0003: minimisasi komposit satu dimensi.ps01.prompt.0004: spektrum kuadratik konveks.ps01.prompt.0005: kontraksi eksak langkah gradien.ps01.prompt.0006: evaluasi numerik Jensen.ps01.prompt.0007: pembuktian Jensen dua titik.ps01.prompt.0008: konjugat kuadratik.ps01.prompt.0009: bikonjugat kuadratik.ps01.prompt.0010: celah Fenchel–Young.ps01.prompt.0011: proyeksi pada kotak.ps01.prompt.0012: bukti pemotongan koordinat.
Set soal metode proksimal: 11 prompt.
ps02.prompt.0001: penurunan rumus ambang lunak.ps02.prompt.0002: proks nilai mutlak berdimensi tiga.ps02.prompt.0003: operator iterasi gradien proksimal.ps02.prompt.0004: dua iterasi dan solusi eksak.ps02.prompt.0005: lema penurunan untuk gradien Lipschitz.ps02.prompt.0006: langkah kuadratik tajam.ps02.prompt.0007: bentuk operator maju–mundur.ps02.prompt.0008: titik tetap dan minimizer.ps02.prompt.0009: kontraksi operator maju–mundur.ps02.prompt.0010: resolven operator linear monoton kuat.ps02.prompt.0011: laju titik proksimal.
Set soal dualitas dan KKT: 11 prompt.
ps03.prompt.0001: fungsi dual masalah kuadratik berekualitas.ps03.prompt.0002: sistem KKT dan celah nol.ps03.prompt.0003: pengali KKT kendala pertidaksamaan.ps03.prompt.0004: Slater dan dual skalar.ps03.prompt.0005: KKT proyeksi pada hiperbidang afin.ps03.prompt.0006: nilai primal dan dual hiperbidang.ps03.prompt.0007: keunikan dan kecukupan KKT.ps03.prompt.0008: pengali sebagai sensitivitas nilai.ps03.prompt.0009: ekspansi eksak fungsi nilai.ps03.prompt.0010: KKT proyeksi pada bola.ps03.prompt.0011: Slater dan kecukupan pada bola.
Empat belas latihan terselesaikan yang sudah diterima
Daftar berikut hanya memetakan ID dan peran kurikuler; bunyi latihan, petunjuk, dan solusi tetap berada pada modul asalnya.
d90.becker.98ed693.b03.exercise.0001: ketakbiasan dalam reduksi varians.d90.becker.98ed693.b03.exercise.0002: identitas varians dan langkah kuadratik.d90.orig.v1.tr01.exercise.0001: operator proksimal Lasso.d90.orig.v1.tr01.exercise.0002: ketaksamaan satu langkah.d90.orig.v1.tr01.exercise.0003: sampling tanpa penggantian.d90.orig.v1.tr01.exercise.0004: cermin entropi.d90.orig.v1.tr01.exercise.0005: anggaran oracle minibatch.d90.orig.v1.tr01.exercise.0006: varians Prox-SAGA.d90.orig.v1.tr02.exercise.0001: VI dan kerucut normal.d90.orig.v1.tr02.exercise.0002: maksimalitas.d90.orig.v1.tr02.exercise.0003: resolven.d90.orig.v1.tr02.exercise.0004: operator skew.d90.orig.v1.tr02.exercise.0005: rentang langkah.d90.orig.v1.tr02.exercise.0006: bayangan Douglas–Rachford.
Dengan demikian, peta awal ini merujuk 54 prompt pada modul 01–04 dan 14 latihan terselesaikan yang sudah diterima tanpa mendeklarasikan ulang ID-nya. Asesmen kumulatif lanjutan, rubrik bukti, dua laboratorium komputasi, dan proyek kapstone kini lengkap pada modul 05–13 yang mengikuti peta ini.
Diagnostik prasyarat
Sepuluh butir berikut menguji prasyarat yang dipakai di seluruh buku. Setiap subbutir merupakan prompt tersendiri dengan dua tingkat petunjuk, jawaban ringkas, dan solusi lengkap. Materi ini tidak memuat pemodelan atau algoritma yang menjadi wilayah O018.
Untuk , hitung , , dan .
Buktikan bahwa untuk setiap ,
Petunjuk tahap 1 (diag.prompt.0001). Gunakan langsung tiga definisi norma.
Petunjuk tahap 2 (diag.prompt.0001). Nilai mutlak koordinatnya adalah dan .
Jawaban ringkas (diag.prompt.0001). , , dan .
Solusi lengkap (diag.prompt.0001). Definisi memberi , , dan .
Petunjuk tahap 1 (diag.prompt.0002). Bandingkan setiap koordinat dengan jumlah kuadrat, lalu gunakan Cauchy–Schwarz untuk ketaksamaan terakhir.
Petunjuk tahap 2 (diag.prompt.0002). Kembangkan dan gunakan .
Jawaban ringkas (diag.prompt.0002). Rantai tersebut berlaku untuk semua ; konstanta tajam pada vektor yang semua koordinat mutlaknya sama.
Solusi lengkap (diag.prompt.0002). Untuk setiap , , sehingga . Selanjutnya, , sehingga . Akhirnya Cauchy–Schwarz memberi . Ini menghasilkan ketaksamaan terakhir. Jika , ketaksamaan terakhir menjadi kesamaan. Rubrik bukti: 1.9.1.
Proyeksikan pada hiperbidang .
Untuk himpunan konveks tertutup takkosong , buktikan bahwa jika dan hanya jika untuk setiap .
Petunjuk tahap 1 (diag.prompt.0003). Gunakan normal dan rumus proyeksi pada .
Petunjuk tahap 2 (diag.prompt.0003). Kurangkan dari .
Jawaban ringkas (diag.prompt.0003). .
Solusi lengkap (diag.prompt.0003). Karena dan , Jumlah koordinat hasilnya nol, sedangkan selisih sejajar normal , jadi hasil tersebut memang proyeksi ortogonal.
Petunjuk tahap 1 (diag.prompt.0004). Untuk arah maju gunakan titik ; untuk arah balik kembangkan .
Petunjuk tahap 2 (diag.prompt.0004). Minimalitas fungsi kuadrat dalam memberi turunan kanan taknegatif di .
Jawaban ringkas (diag.prompt.0004). Kondisi hasil kali dalam tersebut tepat merupakan kondisi optimalitas orde pertama bagi minimisasi jarak kuadrat pada .
Solusi lengkap (diag.prompt.0004). Jika , maka untuk dan , kekonveksan memberi . Fungsi minimum di , sehingga . Sebaliknya, bila kondisi hasil kali dalam berlaku, maka untuk setiap , Jadi meminimalkan jarak. Keunikan mengikuti kekonveksan ketat jarak kuadrat. Rubrik bukti: 1.9.4.
Tentukan sehingga .
Buktikan bahwa irisan sebarang keluarga himpunan konveks adalah konveks.
Petunjuk tahap 1 (diag.prompt.0005). Samakan koordinat pertama.
Petunjuk tahap 2 (diag.prompt.0005). Persamaan memberi kandidat tunggal; periksa koordinat kedua.
Jawaban ringkas (diag.prompt.0005). .
Solusi lengkap (diag.prompt.0005). Koordinat pertama memberi , jadi . Koordinat kedua lalu bernilai . Karena , ini kombinasi konveks yang sah.
Petunjuk tahap 1 (diag.prompt.0006). Ambil dua titik dalam irisan dan uji kombinasi konveksnya pada setiap anggota keluarga.
Petunjuk tahap 2 (diag.prompt.0006). Keanggotaan pada irisan berarti keanggotaan serentak pada semua himpunan.
Jawaban ringkas (diag.prompt.0006). Irisan tetap konveks; irisan kosong juga konveks secara vakum.
Solusi lengkap (diag.prompt.0006). Tuliskan dengan setiap konveks. Jika dan , maka untuk setiap . Karena konveks, untuk setiap , sehingga titik itu berada di . Bila kosong, implikasi dalam definisi konveks benar secara vakum. Rubrik bukti: 1.9.1.
Untuk dengan dan , hitung dan .
Tentukan konstanta kuat-konveks terbesar dan konstanta Lipschitz gradien terkecil bagi .
Petunjuk tahap 1 (diag.prompt.0007). Karena simetris, .
Petunjuk tahap 2 (diag.prompt.0007). Hitung .
Jawaban ringkas (diag.prompt.0007). dan .
Solusi lengkap (diag.prompt.0007). Diferensiasi bentuk kuadratik simetris memberi dan . Pada , , sehingga .
Petunjuk tahap 1 (diag.prompt.0008). Cari kedua nilai eigen matriks simetris .
Petunjuk tahap 2 (diag.prompt.0008). Persamaan karakteristiknya .
Jawaban ringkas (diag.prompt.0008). dan .
Solusi lengkap (diag.prompt.0008). Nilai eigen adalah akar , yaitu . Untuk kuadratik dengan Hessian konstan simetris positif definit, konstanta kuat-konveks terbesar adalah nilai eigen minimum dan konstanta Lipschitz gradien terkecil adalah nilai eigen maksimum. Jadi hasilnya dan . Rubrik bukti: 1.9.2.
Untuk , tuliskan penyangga afin orde pertama di dan verifikasi bahwa penyangga itu menyentuh di .
Buktikan bahwa jika konveks dan terdiferensialkan serta , maka adalah minimizer global.
Petunjuk tahap 1 (diag.prompt.0009). Gunakan .
Petunjuk tahap 2 (diag.prompt.0009). dan .
Jawaban ringkas (diag.prompt.0009). Penyangga afinnya , dan .
Solusi lengkap (diag.prompt.0009). Turunan , jadi . Karena itu . Selisihnya , dan selisih nol di .
Petunjuk tahap 1 (diag.prompt.0010). Gunakan ketaksamaan orde pertama bagi fungsi konveks.
Petunjuk tahap 2 (diag.prompt.0010). Substitusikan gradien nol dalam .
Jawaban ringkas (diag.prompt.0010). untuk setiap .
Solusi lengkap (diag.prompt.0010). Kekonveksan dan keterdiferensialan memberi, untuk setiap , Jadi tidak ada titik dengan nilai lebih kecil daripada . Rubrik bukti: 1.9.1.
Tentukan pada , , dan .
Hitung .
Petunjuk tahap 1 (diag.prompt.0011). Di luar nol gunakan turunan; di nol gunakan definisi subgradien.
Petunjuk tahap 2 (diag.prompt.0011). Pada nol, harus memenuhi untuk semua .
Jawaban ringkas (diag.prompt.0011). , , dan .
Solusi lengkap (diag.prompt.0011). Fungsi terdiferensialkan dengan turunan untuk dan untuk . Pada nol, syarat subgradien adalah untuk setiap . Pemilihan memberi , sedangkan memberi . Jadi subdiferensial di nol adalah .
Petunjuk tahap 1 (diag.prompt.0012). Gunakan rumus ambang lunak dengan ambang satu.
Petunjuk tahap 2 (diag.prompt.0012). .
Jawaban ringkas (diag.prompt.0012). .
Solusi lengkap (diag.prompt.0012). Operator proksimal meminimalkan . Karena minimizer negatif, turunan pada cabang adalah , yang nol pada . Titik itu konsisten dengan cabangnya dan memberi hasil yang sama dengan .
Peubah acak bernilai dengan peluang dan dengan peluang . Hitung dan .
Jika saling independen dan berdistribusi seperti , tentukan ekspektasi dan varians .
Petunjuk tahap 1 (diag.prompt.0013). Hitung momen pertama dan kedua.
Petunjuk tahap 2 (diag.prompt.0013). .
Jawaban ringkas (diag.prompt.0013). dan .
Solusi lengkap (diag.prompt.0013). Kita memperoleh dan . Maka .
Petunjuk tahap 1 (diag.prompt.0014). Gunakan linearitas ekspektasi dan aditivitas varians bagi peubah independen.
Petunjuk tahap 2 (diag.prompt.0014). Faktor dikuadratkan ketika menghitung varians.
Jawaban ringkas (diag.prompt.0014). dan .
Solusi lengkap (diag.prompt.0014). Linearitas memberi . Independensi memberi Rubrik bukti: 1.9.3.
Selesaikan dengan dan tentukan titik tetapnya.
Tentukan bilangan bulat terkecil yang menjamin .
Petunjuk tahap 1 (diag.prompt.0015). Kurangkan titik tetap dari kedua ruas.
Petunjuk tahap 2 (diag.prompt.0015). Titik tetap memenuhi .
Jawaban ringkas (diag.prompt.0015). Titik tetapnya dan .
Solusi lengkap (diag.prompt.0015). Persamaan titik tetap memberi . Dengan diperoleh dan . Jadi dan .
Petunjuk tahap 1 (diag.prompt.0016). Gunakan bentuk tertutup galat dari subbutir sebelumnya.
Petunjuk tahap 2 (diag.prompt.0016). Selesaikan dengan logaritma.
Jawaban ringkas (diag.prompt.0016). .
Solusi lengkap (diag.prompt.0016). Karena , syaratnya adalah . Karena , Bilangan bulat terkecil yang memenuhi adalah .
Minimalkan pada dan verifikasi dengan konvensi .
Verifikasi bahwa untuk setiap , solusi tersebut memenuhi .
Petunjuk tahap 1 (diag.prompt.0017). Minimizer tak terkendala berada di luar interval.
Petunjuk tahap 2 (diag.prompt.0017). Pada ujung kanan, .
Jawaban ringkas (diag.prompt.0017). , , dan .
Solusi lengkap (diag.prompt.0017). Fungsi menurun pada , jadi minimumnya tercapai di . Turunannya memberi . Dari definisi, setiap memenuhi untuk , sehingga . Memilih menghasilkan . Rubrik bukti: 1.9.4.
Petunjuk tahap 1 (diag.prompt.0018). Substitusikan dan .
Petunjuk tahap 2 (diag.prompt.0018). Argumen proyeksinya menjadi .
Jawaban ringkas (diag.prompt.0018). .
Solusi lengkap (diag.prompt.0018). Untuk , . Proyeksi setiap bilangan lebih besar daripada satu pada adalah satu. Karena itu .
Untuk dan , hitung hasil kali dalam dan kedua normanya, lalu periksa ketaksamaan Cauchy–Schwarz.
Buktikan bahwa untuk dan , , serta tentukan syarat kesamaan.
Petunjuk tahap 1 (diag.prompt.0019). Hitung sebelum normanya.
Petunjuk tahap 2 (diag.prompt.0019). Kedua norma sama dengan .
Jawaban ringkas (diag.prompt.0019). dan .
Solusi lengkap (diag.prompt.0019). , sedangkan . Jadi . Vektor-vektor tersebut ortogonal, bukan sejajar, sehingga ketaksamaan tidak menjadi kesamaan pada batas atas yang positif.
Petunjuk tahap 1 (diag.prompt.0020). Mulai dari kuadrat yang taknegatif.
Petunjuk tahap 2 (diag.prompt.0020). Kembangkan .
Jawaban ringkas (diag.prompt.0020). Ketaksamaan selalu berlaku dan kesamaan terjadi tepat ketika .
Solusi lengkap (diag.prompt.0020). Karena pemindahan suku memberi ketaksamaan yang diminta. Kuadrat itu nol tepat jika , yaitu . Rubrik bukti: 1.9.1.
Set soal I: dasar konveks
Lima masalah berikut melatih definisi konveksitas, kelengkungan kuadratik, ketaksamaan Jensen, konjugasi Fenchel, dan proyeksi. Setiap subbutir adalah prompt tersendiri dengan dua petunjuk, jawaban ringkas, dan solusi lengkap.
Untuk dan , buktikan bahwa adalah fungsi konveks.
Tentukan untuk setiap .
Tentukan peminimum dan nilai minimum serta verifikasi syarat optimalitas subgradien di titik tersebut.
Petunjuk tahap 1 (ps01.prompt.0001). Tuliskan kedua fungsi afin sebagai .
Petunjuk tahap 2 (ps01.prompt.0001). Untuk , batasi setiap dengan kombinasi maksimum di dan .
Jawaban ringkas (ps01.prompt.0001). konveks karena maksimum berhingga fungsi-fungsi afin adalah konveks.
Solusi lengkap (ps01.prompt.0001). Ambil dan . Untuk setiap , Mengambil maksimum terhadap pada ruas kiri memberi , yakni definisi konveksitas. Rubrik bukti: 1.9.1.
Petunjuk tahap 1 (ps01.prompt.0002). Di luar nol, terdiferensialkan.
Petunjuk tahap 2 (ps01.prompt.0002). Di , gunakan definisi , yaitu untuk semua .
Jawaban ringkas (ps01.prompt.0002).
Solusi lengkap (ps01.prompt.0002). Untuk dan , turunan masing-masing adalah dan ; subdiferensial fungsi konveks yang terdiferensialkan adalah singleton yang berisi turunannya. Di nol, syarat subgradien adalah untuk semua . Memilih memberi , sedangkan memberi . Sebaliknya, setiap memenuhi , sehingga interval tersebut tepat merupakan subdiferensial di nol.
Petunjuk tahap 1 (ps01.prompt.0003). Gunakan .
Petunjuk tahap 2 (ps01.prompt.0003). Uji titik dengan .
Jawaban ringkas (ps01.prompt.0003). Peminimum uniknya adalah dan nilai minimumnya .
Solusi lengkap (ps01.prompt.0003). Karena suku kuadratik bersifat konveks kuat, mempunyai paling banyak satu peminimum. Di nol, yang memuat nol. Maka syarat optimalitas perlu dan cukup untuk fungsi konveks terpenuhi, sehingga . Substitusi memberi .
Untuk jawab pertanyaan berikut.
Tentukan konstanta konveksitas kuat terbesar dan konstanta Lipschitz terkecil untuk gradien dalam norma Euclid.
Untuk langkah gradien , hitung dan buktikan . Tentukan kapan batas itu tajam.
Petunjuk tahap 1 (ps01.prompt.0004). Gunakan nilai eigen ekstrem Hessian.
Petunjuk tahap 2 (ps01.prompt.0004). Hessian mempunyai nilai eigen dan .
Jawaban ringkas (ps01.prompt.0004). dan .
Solusi lengkap (ps01.prompt.0004). Untuk kuadratik simetris, konstanta konveksitas kuat terbesar adalah dan konstanta Lipschitz gradien terkecil adalah . Karena spektrum adalah , diperoleh dan . Keduanya tajam pada masing-masing arah eigen.
Petunjuk tahap 1 (ps01.prompt.0005). Hitung .
Petunjuk tahap 2 (ps01.prompt.0005). Bandingkan dengan .
Jawaban ringkas (ps01.prompt.0005). ; faktor tajam tepat pada arah sumbu pertama (selain kasus nol, ).
Solusi lengkap (ps01.prompt.0005). Karena , Jadi Selisih ruas kanan dan kiri adalah , sehingga kesamaan terjadi jika dan hanya jika .
Ambil , titik , , dan bobot , .
Hitung kedua ruas ketaksamaan Jensen untuk data tersebut.
Buktikan ketaksamaan Jensen dua titik langsung dari definisi fungsi konveks.
Petunjuk tahap 1 (ps01.prompt.0006). Hitung dahulu rata-rata berbobot kedua titik.
Petunjuk tahap 2 (ps01.prompt.0006). .
Jawaban ringkas (ps01.prompt.0006). Ruas kiri adalah dan ruas kanan adalah , jadi .
Solusi lengkap (ps01.prompt.0006). Rata-rata berbobotnya , sehingga . Sementara itu, Karena , data tersebut memenuhi ketaksamaan Jensen.
Petunjuk tahap 1 (ps01.prompt.0007). Tuliskan definisi konveksitas dengan parameter .
Petunjuk tahap 2 (ps01.prompt.0007). Ganti dengan dan dengan .
Jawaban ringkas (ps01.prompt.0007). Untuk dan , .
Solusi lengkap (ps01.prompt.0007). Definisi konveksitas menyatakan bahwa, untuk semua dan , Setiap pasangan bobot nonnegatif dengan jumlah satu dapat ditulis sebagai dan . Substitusi memberi persis ketaksamaan Jensen dua titik. Rubrik bukti: 1.9.1.
Untuk , definisikan pada .
Hitung konjugat Fenchel .
Hitung secara langsung dan bandingkan dengan .
Nyatakan celah Fenchel–Young sebagai kuadrat dan tentukan syarat kesamaan.
Petunjuk tahap 1 (ps01.prompt.0008). Maksimalkan terhadap .
Petunjuk tahap 2 (ps01.prompt.0008). Titik stasionernya memenuhi .
Jawaban ringkas (ps01.prompt.0008). .
Solusi lengkap (ps01.prompt.0008). Menurut definisi, Fungsi di dalam supremum cekung kuat terhadap ; turunannya nol di . Substitusi menghasilkan .
Petunjuk tahap 1 (ps01.prompt.0009). Terapkan kembali definisi konjugat pada .
Petunjuk tahap 2 (ps01.prompt.0009). Maksimum tercapai di .
Jawaban ringkas (ps01.prompt.0009). .
Solusi lengkap (ps01.prompt.0009). Kita memperoleh Turunan terhadap adalah , jadi pemaksimum uniknya . Nilai supremumnya .
Petunjuk tahap 1 (ps01.prompt.0010). Samakan penyebut pada .
Petunjuk tahap 2 (ps01.prompt.0010). Kenali kuadrat dari .
Jawaban ringkas (ps01.prompt.0010). Celahnya , dan kesamaan berlaku tepat ketika .
Solusi lengkap (ps01.prompt.0010). Perhitungan langsung memberi Karena , nilai ini nonnegatif. Nilainya nol jika dan hanya jika , yakni . Rubrik bukti: 1.9.2.
Misalkan dan .
Hitung proyeksi Euclid .
Buktikan bahwa proyeksi pada kotak diperoleh dengan memotong setiap koordinat ke interval .
Petunjuk tahap 1 (ps01.prompt.0011). Potong setiap koordinat ke interval .
Petunjuk tahap 2 (ps01.prompt.0011). dipetakan ke , tetap, dan dipetakan ke .
Jawaban ringkas (ps01.prompt.0011). .
Solusi lengkap (ps01.prompt.0011). Meminimumkan pada terpisah menjadi tiga masalah skalar. Peminimum pada masing-masing adalah , , dan . Karena jumlah mencapai minimum tepat ketika setiap sukunya minimum, .
Petunjuk tahap 1 (ps01.prompt.0012). Tuliskan kuadrat jarak sebagai jumlah fungsi satu koordinat.
Petunjuk tahap 2 (ps01.prompt.0012). Peminimum skalar adalah jika , jika , dan jika .
Jawaban ringkas (ps01.prompt.0012).
Solusi lengkap (ps01.prompt.0012). Masalah proyeksi adalah Daerah layak merupakan hasil kali interval dan objektif merupakan jumlah suku yang masing-masing hanya bergantung pada satu koordinat. Karena itu, setiap koordinat dapat diminimumkan secara independen. Fungsi skalar berkurang hingga lalu meningkat; pembatasan pada menghasilkan . Menggabungkan semua koordinat membuktikan rumus tersebut. Rubrik bukti: 1.9.4.
Set soal II: metode proksimal
Lima masalah berikut menghubungkan operator proksimal, pemisahan maju–mundur, lemma penurunan, resolven monoton, dan laju titik proksimal.
Untuk , definisikan .
Buktikan bahwa untuk setiap .
Dengan penerapan per koordinat, hitung .
Petunjuk tahap 1 (ps02.prompt.0001). Tuliskan syarat optimalitas untuk .
Petunjuk tahap 2 (ps02.prompt.0001). Pisahkan kasus , , dan dalam .
Jawaban ringkas (ps02.prompt.0001).
Solusi lengkap (ps02.prompt.0001). Objektif bersifat konveks kuat, sehingga syarat menentukan peminimum unik. Jika , syaratnya , konsisten tepat ketika . Jika , diperoleh , konsisten tepat ketika . Jika , syarat menjadi , ekuivalen dengan . Ketiga kasus itu persis rumus . Rubrik bukti: 1.9.5.
Petunjuk tahap 1 (ps02.prompt.0002). Norma satu dan kuadrat jarak keduanya terpisah menurut koordinat.
Petunjuk tahap 2 (ps02.prompt.0002). Terapkan pada ketiga koordinat.
Jawaban ringkas (ps02.prompt.0002). .
Solusi lengkap (ps02.prompt.0002). Pemisahan koordinat memberi Menggabungkan ketiga peminimum skalar menghasilkan vektor yang dinyatakan.
Pertimbangkan dan langkah .
Turunkan pemetaan iterasi maju–mundur .
Dari , hitung dan , lalu tentukan peminimum eksak .
Petunjuk tahap 1 (ps02.prompt.0003). Pisahkan bagian mulus dan .
Petunjuk tahap 2 (ps02.prompt.0003). Gunakan .
Jawaban ringkas (ps02.prompt.0003). .
Solusi lengkap (ps02.prompt.0003). Karena dan , Langkah mundur adalah operator proksimal , sehingga .
Petunjuk tahap 1 (ps02.prompt.0004). Substitusikan berturut-turut dan ke .
Petunjuk tahap 2 (ps02.prompt.0004). Untuk peminimum, selesaikan .
Jawaban ringkas (ps02.prompt.0004). , , dan peminimum uniknya .
Solusi lengkap (ps02.prompt.0004). Kita memperoleh Syarat optimalitas adalah . Pada cabang , syarat itu menjadi , sehingga , yang konsisten dengan cabang. Cabang tidak menghasilkan titik yang konsisten, dan di nol interval tidak memuat nol. Konveksitas kuat suku kuadratik menjamin keunikan, jadi .
Misalkan terdiferensialkan dan gradiennya -Lipschitz.
Buktikan
Untuk pada , terapkan langkah gradien dan periksa ketajaman batas penurunan yang dihasilkan.
Petunjuk tahap 1 (ps02.prompt.0005). Integralkan gradien sepanjang ruas dari ke .
Petunjuk tahap 2 (ps02.prompt.0005). Dengan , batasi oleh .
Jawaban ringkas (ps02.prompt.0005). Batas mengikuti teorema dasar kalkulus pada dan integral .
Solusi lengkap (ps02.prompt.0005). Tetapkan . Teorema dasar kalkulus memberi Cauchy–Schwarz dan sifat Lipschitz menghasilkan Mengintegralkan batas terakhir dari nol sampai satu membuktikan klaim. Rubrik bukti: 1.9.2.
Petunjuk tahap 1 (ps02.prompt.0006). Hitung .
Petunjuk tahap 2 (ps02.prompt.0006). Bandingkan hasil dengan .
Jawaban ringkas (ps02.prompt.0006). dan ; batasnya mencapai kesamaan.
Solusi lengkap (ps02.prompt.0006). Karena , langkah berukuran memberi . Lemma penurunan dengan memberi Untuk kuadratik ini, ruas kanan sama dengan , sehingga batas tersebut tajam untuk setiap .
Pada , ambil , , dan .
Hitung secara eksplisit.
Tentukan titik tetap dan hubungkan dengan peminimum .
Buktikan bahwa adalah kontraksi dengan faktor paling besar dan simpulkan keunikan titik tetapnya.
Petunjuk tahap 1 (ps02.prompt.0007). .
Petunjuk tahap 2 (ps02.prompt.0007). Hitung .
Jawaban ringkas (ps02.prompt.0007). .
Solusi lengkap (ps02.prompt.0007). Definisi resolven dan identitas resolven subdiferensial memberi
Petunjuk tahap 1 (ps02.prompt.0008). Coba dalam rumus eksplisit .
Petunjuk tahap 2 (ps02.prompt.0008). Bandingkan persamaan titik tetap dengan .
Jawaban ringkas (ps02.prompt.0008). Titik tetapnya , yang juga merupakan peminimum unik objektif.
Solusi lengkap (ps02.prompt.0008). Rumus eksplisit memberi . Selain itu, ekuivalen dengan , lalu dengan . Ini persis syarat optimalitas untuk . Pada , syaratnya . Suku kuadratik konveks kuat, jadi peminimum tersebut unik.
Petunjuk tahap 1 (ps02.prompt.0009). Operator proksimal bersifat non-ekspansif.
Petunjuk tahap 2 (ps02.prompt.0009). Bandingkan argumen ambang lunak untuk dan .
Jawaban ringkas (ps02.prompt.0009). ; karena itu titik tetapnya tunggal.
Solusi lengkap (ps02.prompt.0009). Non-ekspansivitas menghasilkan Jadi adalah kontraksi. Jika dan keduanya titik tetap, maka , yang memaksa . Rubrik bukti: 1.9.5.
Ambil dengan dan parameter .
Hitung resolven .
Untuk iterasi titik proksimal , turunkan rumus eksak dan lajunya menuju nol.
Petunjuk tahap 1 (ps02.prompt.0010). Tetapkan .
Petunjuk tahap 2 (ps02.prompt.0010). Selesaikan terhadap .
Jawaban ringkas (ps02.prompt.0010). .
Solusi lengkap (ps02.prompt.0010). Definisi resolven menyatakan jika dan hanya jika . Karena , ini menjadi . Faktor positif, sehingga . Rubrik bukti: 1.9.5.
Petunjuk tahap 1 (ps02.prompt.0011). Substitusikan rumus resolven ke relasi iterasi.
Petunjuk tahap 2 (ps02.prompt.0011). Ulangi perkalian oleh konstanta .
Jawaban ringkas (ps02.prompt.0011). dan secara linear.
Solusi lengkap (ps02.prompt.0011). Rumus resolven memberi . Induksi terhadap menghasilkan . Karena , faktor berada dalam . Maka dan konvergensinya menuju nol bersifat linear dengan faktor eksak .
Set soal III: dualitas dan kondisi KKT
Lima masalah berikut melatih pembentukan fungsi dual, kondisi Karush–Kuhn–Tucker (KKT), kondisi Slater, dan sensitivitas nilai optimal.
Pertimbangkan masalah
Turunkan fungsi dual, lalu tentukan pengali dan nilai dual optimal.
Verifikasi semua kondisi KKT dan kesenjangan dualitas nol.
Petunjuk tahap 1 (ps03.prompt.0001). Gunakan Lagrangian .
Petunjuk tahap 2 (ps03.prompt.0001). Infimum terhadap tercapai di .
Jawaban ringkas (ps03.prompt.0001). , , dan .
Solusi lengkap (ps03.prompt.0001). Meminimumkan Lagrangian terhadap memberi syarat , jadi . Karena Lagrangian konveks kuat terhadap , titik ini memberi infimum dan Masalah dual memaksimalkan kuadratik cekung ini pada . Persamaan memberi dan . Rubrik bukti: 1.9.6.
Petunjuk tahap 1 (ps03.prompt.0002). KKT untuk kendala persamaan terdiri atas kelayakan primal dan stasioneritas.
Petunjuk tahap 2 (ps03.prompt.0002). Substitusikan dan .
Jawaban ringkas (ps03.prompt.0002). layak dan ; nilai primal dan dual sama-sama .
Solusi lengkap (ps03.prompt.0002). Kelayakan primal memberi . Stasioneritas memberi . Tidak ada syarat tanda atau kelengkapan komplementer untuk pengali persamaan. Nilai primal adalah , sedangkan hasil dual pada subbutir sebelumnya memberi . Jadi . Rubrik bukti: 1.9.6.
Pertimbangkan
Gunakan kondisi KKT untuk menentukan solusi primal dan pengali optimal.
Verifikasi kondisi Slater, turunkan fungsi dual, dan periksa nilainya di pengali optimal.
Petunjuk tahap 1 (ps03.prompt.0003). Tuliskan kendala sebagai dengan pengali .
Petunjuk tahap 2 (ps03.prompt.0003). Gunakan stasioneritas dan kelengkapan komplementer .
Jawaban ringkas (ps03.prompt.0003). dan .
Solusi lengkap (ps03.prompt.0003). Jika kendala tidak aktif, kelengkapan komplementer memberi dan stasioneritas memberi , yang tidak layak. Maka kendala aktif: . Stasioneritas kemudian memberi , sehingga . Kelayakan primal, kelayakan dual, stasioneritas, dan kelengkapan komplementer semuanya terpenuhi. Karena masalah konveks, titik KKT ini optimal. Rubrik bukti: 1.9.6.
Petunjuk tahap 1 (ps03.prompt.0004). adalah kandidat titik Slater.
Petunjuk tahap 2 (ps03.prompt.0004). Dalam , infimum terhadap tercapai di .
Jawaban ringkas (ps03.prompt.0004). Slater berlaku; untuk , dan .
Solusi lengkap (ps03.prompt.0004). Titik memenuhi , jadi kondisi Slater berlaku. Untuk , peminimum Lagrangian terhadap adalah . Substitusi memberi Kuadratik cekung ini maksimum di dengan nilai . Nilai primal di juga , sesuai dualitas kuat yang dijamin Slater. Rubrik bukti: 1.9.6.
Ambil dan , lalu pertimbangkan
Selesaikan sistem KKT untuk memperoleh dan .
Turunkan fungsi dual dan verifikasi bahwa nilai primal dan dual optimal sama.
Buktikan bahwa solusi primal itu unik dan bahwa kondisi KKT cukup untuk optimalitas pada masalah ini.
Petunjuk tahap 1 (ps03.prompt.0005). Gunakan .
Petunjuk tahap 2 (ps03.prompt.0005). Stasioneritas memberi ; substitusikan ke kendala.
Jawaban ringkas (ps03.prompt.0005).
Solusi lengkap (ps03.prompt.0005). Stasioneritas adalah , sehingga . Kelayakan persamaan lalu memberi . Karena , penyebutnya positif dan Rubrik bukti: 1.9.6.
Petunjuk tahap 1 (ps03.prompt.0006). Ambil infimum Lagrangian di .
Petunjuk tahap 2 (ps03.prompt.0006). Maksimalkan kuadratik cekung yang diperoleh terhadap .
Jawaban ringkas (ps03.prompt.0006). dan .
Solusi lengkap (ps03.prompt.0006). Substitusi ke Lagrangian memberi Turunannya nol pada , dan substitusi memberi . Di sisi primal,
Petunjuk tahap 1 (ps03.prompt.0007). Gunakan konveksitas kuat objektif untuk keunikan.
Petunjuk tahap 2 (ps03.prompt.0007). Gunakan ketaksamaan konveksitas orde pertama pada titik KKT dan hilangkan suku linear dengan kelayakan persamaan.
Jawaban ringkas (ps03.prompt.0007). Objektif konveks kuat pada himpunan layak konveks, sehingga peminimum tunggal; stasioneritas dan kelayakan KKT menjamin optimalitas global.
Solusi lengkap (ps03.prompt.0007). Fungsi bersifat konveks kuat dengan parameter satu. Pembatasannya pada hiperbidang afin tetap konveks kuat, jadi tidak mungkin mempunyai dua peminimum berbeda. Untuk kecukupan, ambil pasangan KKT . Stasioneritas memberi . Untuk setiap layak, konveksitas memberi karena . Maka titik KKT optimal global, dan konveksitas kuat membuatnya unik. Rubrik bukti: 1.9.6.
Definisikan fungsi nilai
Hitung , pengali optimal untuk kendala , dan hubungan antara dan pengali itu.
Untuk perturbasi , turunkan ekspansi eksak dan identifikasi suku sensitivitas orde pertama serta galat orde keduanya.
Petunjuk tahap 1 (ps03.prompt.0008). Kendala langsung memaksa .
Petunjuk tahap 2 (ps03.prompt.0008). Stasioneritas Lagrangian adalah .
Jawaban ringkas (ps03.prompt.0008). , , dan .
Solusi lengkap (ps03.prompt.0008). Satu-satunya titik layak adalah , sehingga . Stasioneritas memberi , jadi . Mendiferensialkan fungsi nilai menghasilkan . Tanda minus muncul karena kendala ditulis sebagai . Rubrik bukti: 1.9.7.
Petunjuk tahap 1 (ps03.prompt.0009). Kembangkan .
Petunjuk tahap 2 (ps03.prompt.0009). Ganti pada suku linear dengan .
Jawaban ringkas (ps03.prompt.0009). .
Solusi lengkap (ps03.prompt.0009). Perhitungan eksak memberi Jadi adalah perubahan linear yang diprediksi pengali, sedangkan adalah galat orde kedua yang eksak. Rubrik bukti: 1.9.7.
Ambil dan dengan . Pertimbangkan Gunakan representasi mulus .
Selesaikan kondisi KKT untuk menentukan dan pengali .
Verifikasi kondisi Slater dan buktikan bahwa pasangan KKT tersebut merupakan solusi primal-dual global yang unik pada sisi primal.
Petunjuk tahap 1 (ps03.prompt.0010). Stasioneritas adalah .
Petunjuk tahap 2 (ps03.prompt.0010). Karena berada di luar bola, kendala optimal aktif; gunakan dan .
Jawaban ringkas (ps03.prompt.0010).
Solusi lengkap (ps03.prompt.0010). Lagrangiannya dengan . Stasioneritas memberi . Jika , maka , yang tidak layak karena . Jadi , dan kelengkapan komplementer memaksa . Dari diperoleh , sehingga rumus yang dinyatakan berlaku. Rubrik bukti: 1.9.6.
Petunjuk tahap 1 (ps03.prompt.0011). memenuhi kendala secara ketat.
Petunjuk tahap 2 (ps03.prompt.0011). Gabungkan Slater, konveksitas masalah, dan konveksitas kuat objektif.
Jawaban ringkas (ps03.prompt.0011). Slater berlaku di ; KKT perlu dan cukup, dualitas kuat berlaku, dan unik karena objektif konveks kuat.
Solusi lengkap (ps03.prompt.0011). Karena , titik memenuhi , jadi kondisi Slater berlaku. Objektif dan fungsi kendala konveks serta terdiferensialkan; karena itu, di bawah Slater, kondisi KKT bersifat perlu dan cukup dan tidak ada kesenjangan dualitas. Pasangan pada subbutir sebelumnya memenuhi kelayakan primal, , stasioneritas, dan kelengkapan komplementer, sehingga optimal global. Objektif bersifat konveks kuat, maka peminimum primal pada himpunan bola yang konveks adalah unik. Rubrik bukti: 1.9.6.
Set soal IV: metode stokastik
Misalkan dan, bersyarat pada informasi masa lalu , indeks dipilih dengan peluang , . Peluang dan titik boleh -terukur.
Hitung bias penduga naif terhadap .
Tunjukkan bahwa tidak bias secara bersyarat.
Turunkan rumus eksak untuk .
Petunjuk bertahap.
Tahap 1. Tulis ekspektasi bersyarat sebagai jumlah atas semua nilai yang mungkin bagi . Tahap 2. Setelah memperoleh ketakbiasan, gunakan identitas dengan .
Jawaban singkat.
Penduga naif mempunyai bias . Sementara itu,
Solusi lengkap.
Karena dan diketahui setelah mengondisikan pada , Jadi selisihnya dari gradien penuh adalah , yang umumnya tidak nol. Untuk penduga terkoreksi, Selanjutnya, Mengurangkan kuadrat norma mean bersyarat memberi rumus varians yang dinyatakan pada jawaban singkat. Positivitas setiap penting agar koreksi terdefinisi dan tidak menghilangkan komponen mana pun.
Pada himpunan konveks tertutup , misalkan terdiferensialkan dan konveks, konveks proper semikontinu-bawah, dan Buktikan bahwa untuk setiap , Nyatakan dengan jelas kondisi optimalitas yang Anda gunakan.
Petunjuk bertahap.
Tahap 1. Pilih dan dari inklusi optimalitas. Tahap 2. Gunakan ketaksamaan subgradien dan identitas tiga titik untuk divergensi Bregman.
Jawaban singkat.
Inklusi bersama dengan memberikan hasilnya.
Solusi lengkap.
Ambil dan sehingga Karena , definisi kerucut normal memberi . Mengalikan persamaan optimalitas dengan menghasilkan Ketaksamaan subgradien menyatakan . Ruas kanan sama dengan selisih tiga divergensi Bregman pada jawaban singkat. Substitusi kedua fakta itu menyelesaikan bukti.
Pertimbangkan dan orakel stokastik , dengan dan .
Verifikasi ketakbiasan dan varians bersyarat yang seragam.
Tunjukkan bahwa tidak ada batas seragam untuk ketika menjelajahi .
Buktikan arah sebaliknya: jika dan tidak bias, maka .
Petunjuk bertahap.
Tahap 1. Pisahkan dari sendiri. Tahap 2. Untuk arah sebaliknya, terapkan ketaksamaan Jensen pada fungsi kuadrat norma.
Jawaban singkat.
tidak bias dan , tetapi , sehingga tak terbatas seragam. Sebaliknya, .
Solusi lengkap.
Gradien eksak ialah . Karena mean nol, , sedangkan . Jadi varians galat orakel selalu , tidak bergantung pada . Namun, yang menuju tak hingga saat . Dengan demikian, asumsi varians terbatas tidak boleh diam-diam diganti dengan asumsi momen kedua seragam. Untuk arah terakhir, ketakbiasan dan konveksitas kuadrat norma memberi
Dalam satu epok, ambil permutasi seragam dari . Setelah indeks terungkap, misalkan adalah himpunan indeks yang tersisa dan memuat riwayat tersebut.
Untuk titik beku , hitung .
Tunjukkan bahwa jumlah gradien selama satu epok pada titik beku tepat sama dengan .
Jelaskan mengapa bukti SGD yang mengandalkan selisih martingal tidak dapat langsung dipakai ketika titik iterasi berubah di dalam epok.
Petunjuk bertahap.
Tahap 1. Bersyarat pada riwayat, indeks berikutnya seragam hanya pada , bukan pada seluruh himpunan indeks. Tahap 2. Bedakan identitas kombinatorial pada satu titik dari jumlah pada titik-titik yang berlainan.
Jawaban singkat.
Mean bersyarat pertama umumnya bukan gradien penuh; bila berubah, identitas jumlah pada titik beku juga tidak berlaku.
Solusi lengkap.
Setelah indeks terungkap, setiap elemen mempunyai peluang untuk muncul berikutnya. Karena itu mean bersyarat adalah rata-rata gradien komponen yang tersisa. Rata-rata ini hanya sama dengan gradien penuh dalam keadaan khusus. Di sisi lain, sebuah permutasi memuat setiap indeks tepat sekali, sehingga untuk satu titik yang sama, Pada algoritme sebenarnya, suku ke- dinilai di , sehingga jumlahnya adalah dan tidak lagi dapat diganti oleh jumlah gradien pada satu titik. Selain itu, galat gradien terhadap gradien penuh umumnya mempunyai mean bersyarat tak nol. Maka argumen selisih martingal SGD dengan pengambilan sampel independen memerlukan analisis baru, bukan sekadar penggantian notasi.
Misalkan barisan tak negatif memenuhi Turunkan batas tertutup untuk , hitung limit superiornya, dan jelaskan apa yang harus diubah agar jaminan konvergensi eksak tetap masuk akal ketika .
Petunjuk bertahap.
Tahap 1. Tetapkan dan buka rekursi sebagai deret geometrik. Tahap 2. Bandingkan faktor kontraksi dengan suku paksa yang tidak lenyap.
Jawaban singkat.
Dengan , Langkah tetap dengan derau persisten hanya menjamin lingkungan solusi; langkah menurun atau reduksi varians diperlukan untuk meniadakan lantai ini.
Solusi lengkap.
Iterasi rekursi memberikan Karena , suku kedua sama dengan . Hipotesis memastikan , sehingga dan batas limit superior mengikuti. Bila tetap dan , suku paksa tidak hilang; rekursi itu sendiri tidak dapat membuktikan . Jadwal langkah yang menuju nol dengan syarat penjumlahan yang sesuai, atau penduga dengan varians yang ikut menuju nol, mengubah rekursi sehingga lantai galat dapat lenyap.
Set soal V: operator monoton dan metode pemisahan
Pada ruang Euklides berdimensi hingga, misalkan proper, semikontinu-bawah, dan -konveks kuat dengan . Misalkan konveks dan terdiferensialkan pada seluruh ruang, dengan bersifat -kokersif. Buktikan bahwa mempunyai tepat satu peminimum dan bahwa, untuk setiap , Jelaskan peran aturan penjumlahan subdiferensial dalam argumen Anda.
Petunjuk bertahap.
Tahap 1. Gunakan batas bawah kuadratik dari konveksitas kuat untuk mendapatkan kekompakan himpunan sublevel. Tahap 2. Ubah inklusi menjadi definisi resolven.
Jawaban singkat.
proper, semikontinu-bawah, koersif, dan -konveks kuat; jadi ia mempunyai peminimum tunggal. Kontinuitas memberi , dan syarat Fermat ekuivalen dengan yakni persamaan titik tetap yang diminta.
Solusi lengkap.
Konveksitas kuat memberikan batas bawah kuadratik bagi di sekitar suatu titik dalam domainnya. Fungsi konveks terdiferensialkan mempunyai batas bawah afin dari bidang singgungnya. Karena itu suku kuadratik mendominasi batas afin ketika norma membesar, sehingga koersif. Fungsi tersebut proper dan semikontinu-bawah, maka dalam dimensi hingga ia mencapai minimum. Jumlahnya tetap -konveks kuat, sehingga dua peminimum yang berbeda tidak mungkin ada.
Karena bernilai hingga dan kontinu di seluruh ruang, aturan penjumlahan berlaku tanpa syarat kualifikasi tambahan: Syarat Fermat untuk peminimum tunggal adalah . Mengalikan dengan dan menata ulang memberi . Menerapkan invers memberi persamaan titik tetap.
Misalkan maksimal monoton dan bersifat -kokersif. Untuk , definisikan dan anggap .
Tunjukkan bahwa bersifat -averaged dan bersifat -averaged.
Gunakan aturan komposisi untuk memperoleh sebagai parameter averaged bagi .
Untuk , turunkan ketaksamaan penurunan dan batas untuk residu terkecil di antara iterasi pertama.
Petunjuk bertahap.
Tahap 1. Tulis dengan . Tahap 2. Terapkan karakterisasi kuadrat operator averaged, lalu jumlahkan ketaksamaan itu dari sampai .
Jawaban singkat.
Komposisi kedua operator tersebut bersifat -averaged dengan . Untuk setiap titik tetap , dan karenanya
Solusi lengkap.
Kokersivitas menyiratkan bahwa non-ekspansif. Dengan , sehingga operator maju bersifat -averaged. Resolven operator maksimal monoton firmly non-ekspansif, yang sama dengan -averaged. Jika dua operator masing-masing - dan -averaged, komposisinya dapat diambil averaged dengan parameter Memasukkan dan menghasilkan .
Karakterisasi kuadrat operator -averaged memberi, karena , Penjumlahan meneleskopkan ruas norma dan menunjukkan Nilai minimum tidak melebihi rata-rata; mengambil akar memberikan batas pada jawaban singkat dan menunjukkan residu terbaik berorde .
Untuk , pertimbangkan operator linear Buktikan bahwa bersifat -monoton kuat, mempunyai konstanta Lipschitz , dan bersifat -kokersif. Tentukan secara eksak kapan iterasi maju merupakan kontraksi. Gunakan hasil itu untuk mendiagnosis klaim bahwa monotoni kuat saja selalu membolehkan semua .
Petunjuk bertahap.
Tahap 1. Untuk , hitung dan . Tahap 2. Hitung norma faktor , dengan rotasi seperempat putaran.
Jawaban singkat.
Untuk setiap , dan . Faktor kontraksinya adalah sehingga kontraksi terjadi tepat ketika .
Solusi lengkap.
Bagian simetris adalah identitas. Karena itu , yang membuktikan monotoni kuat dengan modulus satu. Perkalian langsung memberi ; jadi norma operatornya dan yakni kokersivitas yang dinyatakan.
Matriks iterasi mempunyai bagian skalar dan bagian rotasi , sehingga norma setiap vektor dikalikan dengan . Syarat ekuivalen dengan Jadi interval tidak seragam terhadap bagian antisimetri. Monotoni kuat tanpa kontrol Lipschitz atau kokersivitas tidak cukup untuk membenarkan klaim langkah tersebut.
Pada , minimalkan dengan dan . Ambil dan konvensi Tentukan peminimum, lalu verifikasi secara langsung bahwa adalah titik tetap dan bahwa bayangannya sama dengan peminimum.
Petunjuk bertahap.
Tahap 1. Gunakan penyusutan lunak untuk dan proyeksi untuk . Tahap 2. Ikuti urutan tanpa menukar konvensi komposisi.
Jawaban singkat.
Peminimumnya . Selain itu, , , , dan . Maka dan bayangan .
Solusi lengkap.
Kendala efektif memaksa . Pada himpunan itu , sehingga nilai terkecil dicapai secara tunggal di . Proksimal dengan parameter satu adalah penyusutan lunak; akibatnya dan . Proksimal indikator adalah proyeksi ke , sehingga dan . Oleh sebab itu Variabel titik tetap tidak harus sama dengan solusi primal; pada konvensi ini solusi diperoleh dari bayangan proksimalnya, yang memang bernilai satu.
Misalkan maksimal monoton pada ruang Euklides berdimensi hingga, , dan . Pertimbangkan Buktikan bahwa konvergen ke suatu titik di . Dalam bukti Anda, tunjukkan juga bahwa .
Petunjuk bertahap.
Tahap 1. Tetapkan dan gunakan firm non-ekspansivitas terhadap . Tahap 2. Jumlahkan galat kuadrat yang dihasilkan; lalu gunakan ketertutupan graf operator maksimal monoton pada subsekuens konvergen.
Jawaban singkat.
Firm non-ekspansivitas memberi Perturbasi yang normanya dapat dijumlahkan membuat barisan kuasi-Fejér, dan penjumlahan ketaksamaan memperlihatkan . Semua titik klaster adalah nol ; dalam dimensi hingga sifat kuasi-Fejér lalu memberi konvergensi seluruh barisan.
Solusi lengkap.
Ambil . Maka . Dengan , firm non-ekspansivitas menghasilkan Karena , . Jumlah norma galat hingga, sehingga dan terbatas dan jarak terhadap setiap nol mempunyai limit.
Mengembangkan kuadrat lalu memakai (1) memberi Karena terbatas dan galat dapat dijumlahkan, kedua suku galat di ruas kanan dapat dijumlahkan. Penjumlahan ketaksamaan menunjukkan , jadi residu itu menuju nol.
Setiap subsekuens konvergen juga memenuhi . Dari definisi resolven, , dan ruas kiri menuju nol. Graf operator maksimal monoton tertutup, sehingga . Jadi semua titik klaster berada di . Barisan terbatas dalam dimensi hingga mempunyai titik klaster, dan sifat kuasi-Fejér beserta fakta bahwa semua titik klasternya adalah nol memaksa seluruh barisan konvergen ke satu nol .
Set soal VI: transportasi optimal dan sintesis
Misalkan adalah himpunan kopling probabilitas dan dua fungsi biaya memenuhi . Tuliskan dan untuk nilai optimal dengan biaya dan .
Buktikan .
Jika optimal untuk biaya , buktikan bahwa ia paling jauh -suboptimal untuk biaya .
Petunjuk bertahap.
Tahap 1. Integralkan batas titik demi titik terhadap sembarang kopling probabilitas. Tahap 2. Sisipkan nilai di antara biaya pada dan nilai .
Jawaban singkat.
Untuk setiap , . Mengambil infimum memberi , dan
Solusi lengkap.
Karena massa total setiap kopling adalah satu, Jadi untuk setiap . Mengambil infimum memberi . Menukar peran kedua biaya memberi , sehingga batas nilai optimal terbukti. Selanjutnya, karena . Batas kedua memuat dua sumber galat: evaluasi rencana dan pergeseran nilai optimal.
Pada , ambil biaya . Misalkan mempunyai momen pertama hingga dan untuk suatu .
Hitung biaya kopling deterministik .
Buktikan bahwa dan layak untuk masalah dual Kantorovich.
Gunakan kesetaraan primal–dual untuk menyimpulkan optimalitas kopling translasi tersebut.
Petunjuk bertahap.
Tahap 1. Kurangi dari dan lengkapi kuadrat dalam . Tahap 2. Gunakan identitas .
Jawaban singkat.
Biaya kopling translasi adalah , dan Nilai dual kedua potensial juga , sehingga kopling dan potensial itu optimal.
Solusi lengkap.
Pada kopling , biaya bernilai konstan , sehingga integralnya . Untuk semua , Maka , dengan kesetaraan tepat pada graf translasi. Momen pertama menjamin integral potensial terdefinisi, dan Dual lemah menyatakan bahwa nilai ini tidak dapat melebihi biaya kopling mana pun. Karena kopling translasi mencapai nilai yang sama, celah dualnya nol dan kopling itu optimal.
Untuk marginal positif dan , definisikan dengan . Tuliskan dan .
Turunkan pembaruan baris dan kolom dalam bentuk log-sum-exp.
Buktikan bahwa , tidak mengubah .
Jelaskan secara matematis mengapa pemusatan dan dengan pergeseran yang berlawanan dapat mencegah luapan numerik tanpa mengubah kopling.
Petunjuk bertahap.
Tahap 1. Selesaikan persamaan terhadap setiap , lalu ambil logaritma; lakukan hal yang sama untuk kolom. Tahap 2. Tambahkan konstanta pada semua dan kurangkan dari semua .
Jawaban singkat.
Transformasi membiarkan setiap jumlah tetap, sehingga tidak berubah.
Solusi lengkap.
Kendala baris adalah , jadi Logaritma jumlah eksponensial adalah fungsi . Dengan cara yang sama, kendala kolom menghasilkan rumus untuk pada jawaban singkat. Jika , maka Dalam koordinat log, ini tepat sama dengan menambahkan pada dan mengurangkannya dari . Karena entri bergantung pada , semua entri tetap sama. Kita boleh memilih , misalnya untuk memusatkan rentang nilai log, agar eksponensial perantara tidak terlalu besar atau kecil. Operasi itu mengubah representasi, bukan kopling atau marginalnya.
Pada tabel kopling probabilitas berukuran , definisikan dengan konvensi . Misalkan meminimalkan dan meminimalkan pada himpunan kopling yang sama. Buktikan
Petunjuk bertahap.
Tahap 1. Bandingkan nilai objektif teratur pada dan . Tahap 2. Gunakan untuk setiap distribusi pada sel.
Jawaban singkat.
Optimalitas kedua rencana memberi batas bawah nol dan
Solusi lengkap.
Karena optimal untuk biaya tanpa regularisasi, . Di sisi lain, optimalitas untuk objektif teratur menyatakan Menata ulang memberi ketaksamaan pertama pada jawaban singkat. Entropi distribusi dengan paling banyak atom berada di antara nol dan . Maka , yang menyelesaikan batas atas. Batas ini mengukur bias biaya tak teratur, bukan jarak antara kedua rencana.
Pertimbangkan fungsi dual dan tuliskan .
Hitung gradien terhadap dan .
Hitung bentuk kuadratik Hessian pada arah dan buktikan kekonkafan.
Identifikasi arah gauge. Jika graf bipartit dukungan positif terhubung, buktikan bahwa hanya arah gauge yang mempunyai kelengkungan nol.
Petunjuk bertahap.
Tahap 1. Diferensiasikan satu eksponensial dan kelompokkan jumlah baris serta kolom. Tahap 2. Bentuk kuadratik dapat ditulis sebagai jumlah berbobot dari .
Jawaban singkat.
dan Arah adalah arah gauge; bila dukungan terhubung, semua arah nol berbentuk demikian.
Solusi lengkap.
Diferensiasi terhadap menghasilkan , sedangkan diferensiasi terhadap menghasilkan . Diferensiasi kedua pada lintasan memberi Bobotnya nonnegatif, sehingga konkaf. Bentuk kuadratik nol tepat bila pada setiap sisi dukungan positif. Pada graf bipartit yang terhubung, kondisi ini memaksa semua sama dengan satu konstanta dan semua . Itulah transformasi yang tidak mengubah . Jadi dual bersifat konkaf ketat setelah satu gauge dipatok, meskipun tidak konkaf ketat pada representasi yang belum dinormalisasi.
Rubrik analitik untuk pembuktian
Setiap kriteria di bawah dinilai dengan skala yang sama: 0 tidak ada atau tidak sah; 1 fragmen relevan dengan galat mayor; 2 arah sebagian benar tetapi masih ada celah substantif; 3 benar dengan satu kekurangan minor yang tidak mengubah kesimpulan; dan 4 lengkap, tepat, dan seluruh dependensi logis dinyatakan. Setiap rubrik mempunyai empat kriteria, jadi skor maksimumnya adalah 16. Keanggunan gaya tidak boleh menutupi galat matematika, dan notasi alternatif yang ekuivalen harus dinilai berdasarkan isinya.
Rubrik proof.0001: hipotesis, tipe, dan kuantor
Kriteria (masing-masing 0–4).
Menyatakan objek, ruang, domain, dan kodomain secara konsisten.
Menempatkan semua kuantor dan dependensi parameter pada lingkup yang benar, termasuk perbedaan antara pernyataan titik demi titik dan seragam.
Menggunakan tepat hipotesis ketertutupan, konveksitas, keterbatasan, atau keterukuran pada langkah yang memerlukannya.
Menutup semua kasus tepi dan memastikan bahwa kesimpulan mempunyai tipe logis yang sama dengan klaim semula.
Kegagalan umum.
Menganggap domain sama dengan seluruh ruang; menukar “untuk setiap” dengan “terdapat”; memakai konstanta yang diam-diam bergantung pada iterasi; membagi dengan besaran yang belum dibuktikan positif; atau menyatakan limit tanpa menentukan topologi.
Rubrik proof.0002: keberadaan dan argumen topologis
Kriteria (masing-masing 0–4).
Mengidentifikasi himpunan sublevel atau barisan peminimum yang tepat dan membuktikan keterbatasan atau kekompakannya.
Menggunakan semikontinuitas-bawah, ketertutupan, atau kekompakan dengan arah ketaksamaan dan topologi yang benar.
Membedakan dengan tegas keberadaan, ketunggalan, dan kestabilan, serta memberi hipotesis tersendiri bagi masing-masing klaim.
Menangani fungsi bernilai-diperluas, domain efektif, dan nilai tak hingga tanpa operasi aljabar yang tidak sah.
Kegagalan umum.
Mengatakan “kontinu maka minimum ada” pada himpunan tak kompak; menganggap konveksitas memberi ketunggalan; menyimpulkan koersivitas hanya dari keterbatasan-bawah; mengabaikan domain kosong; atau mengambil limit dalam domain yang belum dibuktikan tertutup.
Rubrik proof.0003: penurunan, teleskop, dan laju
Kriteria (masing-masing 0–4).
Menurunkan ketaksamaan satu-langkah dari asumsi yang dinyatakan, dengan tanda, faktor, dan norma yang benar.
Menentukan besaran potensial nonnegatif dan meneleskopkan indeks tanpa kehilangan suku batas.
Memilih langkah atau parameter dalam rentang yang benar dan melacak semua konstanta hingga batas akhir.
Membedakan laju nilai fungsi, jarak iterasi, dan residu, termasuk apakah klaim berlaku untuk iterasi terakhir, terbaik, atau rata-rata.
Kegagalan umum.
Menghapus suku bertanda tak diketahui; kesalahan indeks awal/akhir; memilih langkah setelah melihat kuantitas acak masa depan; mengubah batas menjadi dengan menguadratkan sepihak; atau menyembunyikan konstanta yang bergantung pada dimensi.
Rubrik proof.0004: dualitas, kualifikasi, dan KKT
Kriteria (masing-masing 0–4).
Membentuk Lagrangian dengan tanda, ruang dual, dan domain yang benar.
Menyatakan kondisi kualifikasi yang benar-benar cukup sebelum menggunakan dualitas kuat atau keberadaan pengali.
Menurunkan kelayakan primal, kelayakan dual, stasioneritas, dan kelonggaran komplementer tanpa melewatkan inklusi subdiferensial.
Membuktikan kebutuhan atau kecukupan kondisi KKT sesuai kelas masalah, serta menghubungkannya dengan titik pelana atau nilai dual.
Kegagalan umum.
Menyatakan KKT tanpa kualifikasi; memberi pengali bertanda salah; mengganti inklusi dengan persamaan gradien saat fungsi tak mulus; menyamakan dualitas lemah dengan kuat; atau memakai kelonggaran komplementer untuk menyimpulkan kelayakan yang belum dibuktikan.
Rubrik proof.0005: filtrasi dan argumen stokastik
Kriteria (masing-masing 0–4).
Mendefinisikan filtrasi dan menyatakan dengan benar besaran yang terukur sebelum pengambilan sampel berikutnya.
Menghitung ekspektasi bersyarat, ketakbiasan, dan bias tanpa mengasumsikan independensi yang tidak tersedia.
Membedakan batas varians dari batas momen kedua dan menggunakan hukum varians total atau Jensen secara sah.
Menukar ekspektasi, penjumlahan, limit, atau subdiferensial hanya jika syarat integrabilitas dan teorema yang dibutuhkan telah dipenuhi.
Kegagalan umum.
Mengondisikan pada informasi yang sudah memuat sampel baru; menyebut galat sebagai selisih martingal padahal mean bersyaratnya tidak nol; mengganti dengan varians; memakai sampel tanpa pengembalian seolah-olah independen; atau mengambil ekspektasi dari kuantitas tak terintegralkan.
Rubrik proof.0006: operator monoton dan resolven
Kriteria (masing-masing 0–4).
Menyatakan domain operator bernilai-himpunan dan membedakan monotoni, monotoni maksimal, monotoni kuat, serta kokersivitas.
Mengubah inklusi menjadi persamaan resolven atau titik tetap dengan urutan komposisi dan parameter yang benar.
Menggunakan firm non-ekspansivitas, keaveragan, atau kontraksi dengan konstanta yang dibuktikan, bukan diasumsikan.
Menghubungkan residu atau titik klaster dengan nol operator melalui ketertutupan graf dan argumen konvergensi yang lengkap.
Kegagalan umum.
Menganggap semua operator monoton maksimal; memperlakukan resolven sebagai invers biasa; menukar dengan ; mengabaikan domain pada aturan jumlah; atau menyimpulkan konvergensi iterasi hanya dari residu yang menuju nol tanpa kontrol titik klaster.
Rubrik proof.0007: contoh penyangkal dan sertifikat komputasional
Kriteria (masing-masing 0–4).
Menargetkan tepat satu hipotesis atau kesimpulan dan memastikan contoh memenuhi semua asumsi lain yang dipertahankan.
Menghitung objek kunci secara eksak atau dengan batas galat yang tersertifikasi, termasuk kasus tepi yang relevan.
Memisahkan bukti matematis dari ilustrasi numerik serta menyatakan presisi, toleransi, dan residu bila komputasi dipakai.
Menjelaskan secara eksplisit bagaimana hasil contoh membatalkan klaim universal atau bagaimana sertifikat memverifikasi klaim yang terbatas.
Kegagalan umum.
Contoh melanggar asumsi lain; satu plot diperlakukan sebagai bukti universal; residu kecil disamakan dengan galat solusi tanpa batas kondisi; pembulatan mengubah tanda; atau program menguji hanya satu parameter sementara klaimnya untuk semua parameter.
Ujian tengah kumulatif
Untuk , , dan , pertimbangkan Buktikan bahwa selalu mempunyai peminimum. Apakah peminimum itu selalu tunggal? Berikan satu kondisi sederhana pada yang menjamin ketunggalan.
Petunjuk bertahap.
Tahap 1. Bandingkan dengan ketika . Tahap 2. Untuk ketunggalan, cari kondisi yang membuat suku kuadrat konveks ketat; untuk menyangkal ketunggalan umum, izinkan memiliki kernel.
Jawaban singkat.
kontinu dan koersif karena , sehingga minimum dicapai. Ketunggalan tidak selalu berlaku; misalnya dan sebenarnya memberi minimum tunggal, tetapi matriks dengan kolom identik dapat menghasilkan banyak representasi dengan nilai sama. Kondisi sederhana yang cukup adalah berperingkat kolom penuh.
Solusi lengkap.
Kedua suku kontinu dan tak negatif. Karena , Jadi semua himpunan sublevel tak kosong yang relevan kompak, dan teorema Weierstrass memberi keberadaan peminimum.
Ketunggalan dapat gagal. Sebagai contoh, ambil , , dan . Untuk dengan , objektif hanya bergantung pada : . Nilai minimumnya dicapai pada , dan setiap pembagian nonnegatif dari memberi peminimum berbeda. Jika berperingkat kolom penuh, maka konveks ketat. Jumlah fungsi konveks ketat dengan fungsi konveks tetap konveks ketat, sehingga peminimum yang sudah terbukti ada harus tunggal.
Untuk dan , definisikan Hitung secara langsung dari definisi, verifikasi , dan tentukan konstanta Lipschitz terkecil dari .
Petunjuk bertahap.
Tahap 1. Maksimalkan kuadrat konkaf dalam definisi . Tahap 2. Terapkan perhitungan yang sama pada atau substitusikan gradien inversnya.
Jawaban singkat.
Karena itu , dan konstanta Lipschitz terkecil gradien adalah .
Solusi lengkap.
Definisi konjugat memberi Titik stasionernya , dan substitusi menghasilkan . Selanjutnya, Peminimum negatif kuadrat, atau kondisi stasioner, memberi . Nilainya . Akhirnya, Kesetaraan berlaku untuk setiap pasangan berbeda, jadi bukan hanya batas yang cukup, melainkan konstanta terkecil.
Misalkan konveks dengan gradien -Lipschitz dan konveks proper semikontinu-bawah. Untuk , definisikan Buktikan bahwa untuk setiap , Kemudian turunkan batas untuk nilai fungsi iterasi gradien proksimal bila peminimum ada.
Petunjuk bertahap.
Tahap 1. Gabungkan lemma penurunan untuk dengan inklusi optimalitas proksimal dan ketaksamaan subgradien untuk . Tahap 2. Gunakan identitas tiga norma, tetapkan , lalu jumlahkan dan manfaatkan monotoni nilai objektif.
Jawaban singkat.
Suku tambahan yang muncul adalah , sehingga ketaksamaan yang diminta berlaku. Untuk iterasi yang sama,
Solusi lengkap.
Inklusi proksimal menyediakan dengan Lemma penurunan, konveksitas , dan ketaksamaan subgradien memberi Koefisien terakhir nonnegatif karena , sehingga suku negatif itu dapat dibuang. Dengan , penjumlahan untuk meneleskopkan jarak dan memberi Ketaksamaan yang sama dengan menunjukkan nilai tidak naik. Karena itu suku terakhir tidak melebihi rata-rata suku, yang menghasilkan batas pada jawaban singkat.
Misalkan Dari titik sembarang , tentukan arah Newton , buktikan bahwa adalah peminimum eksak, dan tunjukkan bahwa uji Armijo menerima langkah penuh untuk setiap .
Petunjuk bertahap.
Tahap 1. Selesaikan dan hitung gradien di . Tahap 2. Gunakan ekspansi kuadrat eksak sepanjang serta .
Jawaban singkat.
dan . Selain itu, sehingga Armijo berlaku tepat bila (atau trivial bila ).
Solusi lengkap.
Gradiennya dan Hessiannya . Persamaan Newton memberi , sehingga titik baru adalah . Karena definit positif, titik stasioner ini peminimum tunggal. Ekspansi eksak memberi Ruas kanan uji Armijo adalah . Untuk , definit positifnya membuat uji ekuivalen dengan . Jika , titik sudah optimal dan kedua ruas sama untuk semua .
Ambil dan dengan . Selesaikan Verifikasi kondisi Slater, tulis seluruh kondisi KKT, dan hitung pasangan primal–dual optimal secara eksplisit.
Petunjuk bertahap.
Tahap 1. Titik nol adalah titik Slater; karena di luar bola, kendala pada solusi harus aktif. Tahap 2. Stasioneritas memberi .
Jawaban singkat.
KKT terdiri dari Solusinya
Solusi lengkap.
Karena , Slater berlaku. Masalah konveks dan objektifnya konveks ketat, sehingga KKT perlu dan cukup serta solusi primal tunggal. Lagrangiannya Stasioneritas dan tiga kondisi lainnya tercantum pada jawaban singkat. Solusi tanpa kendala tidak layak, maka kendala aktif dan . Dari diperoleh bahwa searah dengan . Menormakan persamaan itu menghasilkan , sehingga pasangan yang dinyatakan mengikuti. Pengalinya positif, maka semua kondisi KKT terpenuhi.
Pertimbangkan masalah konveks skalar Tentukan solusi, tunjukkan bahwa Slater gagal, dan buktikan bahwa tidak ada pengali yang memenuhi kondisi KKT pada solusi. Jelaskan mengapa contoh ini tidak menyangkal teorema KKT dengan kualifikasi.
Petunjuk bertahap.
Tahap 1. Tentukan seluruh himpunan layak dari ketaksamaan kuadrat. Tahap 2. Diferensiasikan di titik layak.
Jawaban singkat.
Satu-satunya titik layak dan optimal ialah . Tidak ada titik dengan , jadi Slater gagal. Stasioneritas KKT menuntut , yakni , mustahil untuk setiap .
Solusi lengkap.
Karena kuadrat selalu nonnegatif, syarat ekuivalen dengan . Maka adalah satu-satunya titik layak dan otomatis peminimum. Slater memerlukan titik dengan , yang tidak ada. Untuk pengali , Lagrangian adalah dan kondisi stasioneritas pada ialah sebuah kontradiksi. Teorema KKT yang menjamin keberadaan pengali memakai kondisi kualifikasi seperti Slater. Hipotesis itu gagal di sini, sehingga ketiadaan pengali justru menunjukkan mengapa kualifikasi tidak boleh dihilangkan.
Ujian akhir kumulatif
Misalkan konveks, kontinu, dan tak negatif; proper, semikontinu-bawah, konveks, dan tak negatif; linear; serta . Buktikan bahwa mempunyai tepat satu peminimum. Nyatakan bagian argumen yang membuktikan keberadaan dan bagian yang membuktikan ketunggalan.
Petunjuk bertahap.
Tahap 1. Gunakan ketaknegatifan dua suku pertama untuk membatasi himpunan sublevel. Tahap 2. Periksa apa yang terjadi pada modulus konveksitas kuat ketika fungsi konveks ditambahkan pada kuadrat .
Jawaban singkat.
proper, semikontinu-bawah, dan , sehingga ia koersif dan mencapai minimum. Selain itu, bersifat -konveks kuat, sehingga peminimumnya tunggal.
Solusi lengkap.
Karena proper, terdapat dengan ; fungsi bernilai hingga, jadi dan proper. Komposisi kontinu dan konveks, sementara semikontinu-bawah. Maka semikontinu-bawah. Dari ketaknegatifan, Jadi sebuah barisan peminimum berada dalam himpunan terbatas; dalam dimensi hingga kita dapat mengambil subsekuens konvergen, dan semikontinuitas-bawah menunjukkan bahwa limitnya mencapai infimum. Ini membuktikan keberadaan.
Fungsi kuadrat adalah -konveks kuat. Penambahan dua fungsi konveks mempertahankan modulus itu, jadi juga -konveks kuat. Jika ada dua peminimum berbeda, ketaksamaan konveksitas kuat pada titik tengah akan memberi nilai yang lebih kecil secara ketat daripada nilai minimum, kontradiksi. Maka peminimum tunggal.
Misalkan konveks dengan gradien -Lipschitz, proper semikontinu-bawah dan konveks, serta . Untuk , definisikan Algoritme menggandakan sampai uji majorisasi terpenuhi. Buktikan bahwa pencarian berhenti secara hingga, lalu buktikan sertifikat penurunan Nyatakan residu gradien proksimal yang dapat dihitung dari langkah ini.
Petunjuk bertahap.
Tahap 1. Lemma penurunan menjamin (A) untuk semua . Tahap 2. Model yang diminimalkan bersifat -konveks kuat dan nilainya di sama dengan .
Jawaban singkat.
Penggandaan akhirnya menghasilkan , sehingga (A) berlaku. Konveksitas kuat model memberi nilai model di paling besar ; (A) memindahkan batas itu ke objektif sebenarnya. Residu yang lazim adalah .
Solusi lengkap.
Lemma penurunan menyatakan untuk semua , Jadi begitu urutan penggandaan mencapai , uji (A) pasti diterima; jumlah penggandaan hingga.
Tuliskan model di dalam kurung sebagai . Ia -konveks kuat dan adalah peminimumnya. Dengan memakai dalam ketaksamaan konveksitas kuat, Karena dan uji (A) memberi , kedua ketaksamaan menghasilkan sertifikat yang diminta. Vektor dapat dihitung dari langkah. Ia nol tepat bila , yang melalui kondisi optimalitas ekuivalen dengan .
Untuk dan , pertimbangkan Anggap terdapat dengan . Turunkan sistem KKT lengkap. Tuliskan subgradien norma Euclidean baik ketika maupun ketika , dan jelaskan mengapa sistem KKT cukup untuk optimalitas global.
Petunjuk bertahap.
Tahap 1. Gunakan pengali untuk fungsi kendala . Tahap 2. Terapkan aturan rantai subdiferensial pada norma dan pisahkan kasus argumen nol.
Jawaban singkat.
Terdapat , , dan sehingga Jika , ; jika , subdiferensialnya adalah bola satuan. Slater membuat KKT perlu dan, karena masalah konveks, juga cukup.
Solusi lengkap.
Lagrangian adalah Kondisi Slater yang diberikan menjamin keberadaan pengali optimal dan aturan KKT tanpa celah dual. Stasioneritas adalah inklusi Memilih dan dari kedua subdiferensial mengubahnya menjadi persamaan pada jawaban singkat. Secara koordinat, jika dan jika . Untuk norma Euclidean, saat , sedangkan sembarang dengan sah saat .
Sistem dilengkapi oleh kelayakan primal, kelayakan dual , dan kelonggaran komplementer. Objektif dan fungsi kendala konveks; maka setiap pasangan yang memenuhi sistem membentuk sertifikat titik pelana Lagrangian dan memberi peminimum global.
Misalkan adalah vektor tak nol yang diketahui. Untuk peluang , , ambil dan . Di antara semua distribusi , tentukan distribusi yang meminimalkan , hitung nilai minimumnya, dan tulis varians minimum terhadap mean .
Petunjuk bertahap.
Tahap 1. Masalah skalar yang harus diminimalkan adalah pada simpleks. Tahap 2. Gunakan pengali Lagrange atau Cauchy–Schwarz, lalu kurangi dari momen kedua.
Jawaban singkat.
Varians minimumnya adalah nilai terakhir dikurangi .
Solusi lengkap.
Ketakbiasan mengikuti dari . Momen keduanya ialah Cauchy–Schwarz memberi Kesetaraan terjadi tepat ketika sebanding dengan , yakni . Karena semua vektor tak nol, distribusi itu strictly positif dan layak. Substitusi memberi nilai minimum. Identitas memberi varians yang diminta.
Misalkan konveks, terdiferensialkan dan -konveks kuat terhadap norma , serta konveks pada . Dengan filtrasi , anggap Iterasi diberikan oleh Jika meminimalkan dan , buktikan untuk dan bahwa
Petunjuk bertahap.
Tahap 1. Dari ketaksamaan tiga titik dan konveksitas kuat , turunkan batas satu langkah dengan suku . Tahap 2. Ambil ekspektasi bersyarat, jumlahkan, gunakan Jensen pada , lalu optimalkan langkah konstan.
Jawaban singkat.
Ketaksamaan dasar memberi Setelah dijumlahkan dan dibagi , batasnya ; pilihan langkah yang diberikan membuatnya .
Solusi lengkap.
Optimalitas langkah cermin dan identitas tiga titik menghasilkan, untuk , Tambahkan pada kedua ruas. Karena , Young memberi Ambil dan ekspektasi bersyarat. Karena terukur terhadap , ketakbiasan memberi . Maka ketaksamaan pada jawaban singkat berlaku.
Menjumlahkan untuk meneleskopkan divergensi dan memberi Konveksitas dan Jensen membatasi ruas kiri dari bawah oleh . Substitusi membuat kedua suku kanan sama dengan , sehingga hasil mengikuti.
Misalkan maksimal monoton dan -monoton kuat dengan . Buktikan bahwa untuk setiap , Simpulkan bahwa mempunyai paling banyak satu nol dan, jika nol ada, iterasi konvergen linear kepadanya.
Petunjuk bertahap.
Tahap 1. Tetapkan , , lalu tulis anggota dan dari definisi resolven. Tahap 2. Terapkan monotoni kuat dan Cauchy–Schwarz; kemudian ambil .
Jawaban singkat.
Monotoni kuat memberi yang bersama Cauchy–Schwarz menghasilkan kontraksi. Karena ,
Solusi lengkap.
Dari definisi resolven, Monotoni kuat memberikan Setelah dikalikan dan ditata ulang, ini menjadi ketaksamaan pada jawaban singkat. Jika , Cauchy–Schwarz dan pembagian oleh memberi batas Lipschitz; bila batasnya trivial.
Jika dan keduanya nol , monotoni kuat memberi , sehingga . Untuk nol yang ada, . Penerapan berulang faktor kontraksi memberi batas linear yang dinyatakan.
Misalkan dan total massanya sama. Untuk , tinjau Buktikan bahwa, dengan tetap, pemaksimal unik terhadap setiap adalah dan turunkan pembaruan analog untuk . Simpulkan bahwa penskalaan Sinkhorn adalah maksimisasi koordinat blok eksak dan nilai dual tidak menurun pada setiap setengah langkah. Jelaskan ketidaktunggalan bersama akibat gauge.
Petunjuk bertahap.
Tahap 1. Nolkan turunan parsial terhadap satu dan periksa tanda turunan keduanya. Tahap 2. Ulangi untuk dan amati transformasi .
Jawaban singkat.
Persamaan stasioner blok ialah yang memberi rumus pada soal; rumus blok diperoleh dengan menukar baris dan kolom. Setiap turunan kedua blok negatif, jadi pembaruan adalah maksimum unik dan tidak menurunkan . Pasangan bersama hanya unik hingga penambahan konstanta pada dan pengurangan konstanta yang sama pada .
Solusi lengkap.
Untuk tetap, Menetapkannya nol dan mengeluarkan faktor memberi rumus eksplisit pada soal. Turunan kedua adalah dan tidak ada suku silang antara yang berlainan ketika tetap. Jadi rumus itu adalah pemaksimal blok unik. Secara simetris, Mengganti satu blok dengan pemaksimal eksaknya tidak dapat menurunkan nilai fungsi dual. Dalam variabel skala eksponensial, kedua rumus adalah pembaruan baris dan kolom Sinkhorn.
Jika ditambah dan dikurangi , semua jumlah tetap. Suku linear juga tetap karena total massa dan sama. Jadi nilai dual dan kopling tidak berubah; inilah kebebasan gauge yang membuat pemaksimal pasangan tidak tunggal sebelum normalisasi.
Pertimbangkan dengan , , dan konveks terdiferensialkan. Tuliskan inklusi optimalitas primal dan sistem primal–dual dengan variabel untuk suku . Bandingkan kapan gradien proksimal stokastik langsung layak dipakai dan kapan pemisahan primal–dual lebih sesuai. Berikan sepasang residu KKT dan asumsi orakel minimum yang diperlukan untuk klaim konvergensi stokastik.
Petunjuk bertahap.
Tahap 1. Gabungkan dengan kerucut normal , lalu gunakan aturan rantai melalui . Tahap 2. Bandingkan proksimal gabungan dengan proyeksi ke dan proksimal konjugat norma yang dapat dihitung secara terpisah.
Jawaban singkat.
Optimalitas ekuivalen dengan keberadaan sehingga Gradien proksimal langsung sesuai bila mudah; pemisahan primal–dual sesuai bila hanya proyeksi ke dan proyeksi dual ke bola yang mudah. Residu dapat berupa jarak kedua inklusi ke nol. Orakel harus tidak bias secara bersyarat, bermomen kedua terkendali, dan langkah harus memenuhi syarat penjumlahan yang sesuai.
Solusi lengkap.
Dengan aturan rantai konveks, Karena kendala ditulis sebagai indikator , syarat Fermat adalah Memperkenalkan menghasilkan sistem pada jawaban singkat. Secara ekuivalen, , dan fungsi konjugat itu adalah indikator bola .
Jika proksimal gabungan tersedia dalam bentuk tertutup atau dapat dihitung murah, langkah gradien proksimal stokastik memisahkan bagian halus secara langsung. Untuk umum, proksimal gabungan biasanya tidak terurai menjadi penyusutan lunak lalu proyeksi. Metode primal–dual menjaga sebagai operator linear dan hanya membutuhkan proyeksi ke bola serta proyeksi ke bola berjari-jari ; karena itu ia lebih sesuai pada keadaan tersebut.
Satu pasangan residu matematis adalah dengan nilai tak hingga bila berada di luar domain konjugat. Keduanya nol tepat pada pasangan KKT. Untuk analisis stokastik, penduga gradien sekurang-kurangnya harus memenuhi dan batas momen kedua atau varians yang sesuai. Pada skema Robbins–Monro dasar, langkah positif lazimnya memenuhi dan ; klaim laju dengan langkah tetap memerlukan asumsi tambahan seperti reduksi varians atau menerima lantai galat. Norma operator juga harus masuk ke batas langkah primal–dual, bukan diabaikan.
Laboratorium 3: kegagalan lokal dan globalisasi Newton
Laboratorium ini memperlihatkan bahwa arah yang tampak “orde dua” belum tentu aman secara global. Kita memakai fungsi konveks mulus Minimum uniknya adalah dengan nilai nol. Walaupun Hessian selalu positif, kelengkungan pada arah sangat kecil ketika besar. Karena itu, langkah Newton penuh dari titik awal yang disediakan dapat melompat ke daerah dengan nilai objektif jauh lebih tinggi. Contoh ini memisahkan dua persoalan: pemilihan arah dan pemilihan panjang langkah.
Kode tetap berada di
labs/original-03/globalisasi-newton.py. Dengan seed dan
konfigurasi yang dibekukan, kode membandingkan empat metode:
gradien dengan langkah tetap yang sengaja terlalu besar;
gradien dengan pencarian balik Armijo;
Newton murni dengan langkah penuh;
Newton teredam dengan Hessian terkoreksi , dengan .
Jejak lengkap ditulis ke CSV, ringkasan dan sertifikat ditulis ke JSON, dan SVG hanya memvisualkan data yang sama. Tidak ada kesimpulan numerik yang bergantung pada grafik.
Prompt
Jalankan skrip sekali dan kerjakan hal-hal berikut.
Turunkan langkah Newton murni pada koordinat dan jelaskan mengapa menghasilkan lompatan besar walaupun fungsi konveks.
Dari jejak CSV, temukan kenaikan objektif pertama bagi Newton murni dan kegagalan metode gradien berlangkah tetap.
Buktikan bahwa syarat Armijo menghasilkan penurunan ketat bila adalah arah turun.
Buktikan bahwa koreksi membuat menjadi arah turun selama gradien tidak nol.
Cocokkan bukti Anda dengan seluruh boolean sertifikat dalam JSON dan jelaskan mengapa “gagal” di sini merupakan bukti terkontrol, bukan galat program.
Petunjuk bertahap
Gunakan dan tulis .
Bandingkan kolom
objectivepada dua baris berturutan; jangan menyimpulkan kegagalan hanya dari gambar.Pada ruas kanan Armijo, tanda adalah fakta penentu.
Gunakan untuk menunjukkan .
Periksa juga bahwa semua langkah metode teredam diterima oleh Armijo dan nilai objektifnya monoton menurun.
Jawaban singkat
Newton murni gagal karena invers kelengkungan sangat besar. Langkah gradien tetap gagal karena faktor koordinat kuadratiknya adalah . Pencarian balik memendekkan langkah sampai memenuhi penurunan cukup. Koreksi Hessian menjamin arah turun, sedangkan Armijo mengglobalisasi panjang langkah; kombinasi keduanya mencapai toleransi gradien yang dibekukan.
Solusi acuan lengkap
Pada koordinat pertama, Newton murni memberi Untuk , suku berorde , sehingga iterasi melompat melintasi minimizer dan menaikkan . Pada iterasi berikutnya mendekati nol pada presisi mesin; skrip berhenti sebelum pembagian hampir singular merusak jejak. Untuk gradien tetap pada koordinat kedua berlaku , jadi magnitudonya tumbuh geometrik.
Untuk arah gradien , kita memiliki . Karena diferensiabel, terdapat sehingga setiap memenuhi Armijo; pencarian balik dengan faktor dalam karena itu berhenti dalam banyak langkah berhingga. Untuk arah Newton terkoreksi, konstruksi memberi Maka argumen pencarian balik yang sama berlaku. Sertifikat program memeriksa langsung batas eigenvalue, tanda turunan arah, semua penerimaan Armijo, monotonisitas objektif, dan norma gradien akhir. Sebaliknya, metode yang tidak diglobalisasi diwajibkan memperlihatkan kenaikan atau ledakan yang telah ditentukan; dengan demikian jalur gagal merupakan bagian dari eksperimen.
Hak dan firewall O018.
Teks, soal, solusi, dan kode laboratorium ini ditulis mandiri untuk lapisan Original-03 dan tersedia berdasarkan CC BY-SA 4.0. Tidak ada prosa, soal, solusi, kode, atau susunan pedagogis O018 yang disalin atau diadaptasi; O018 tetap merupakan korpus terpisah.
Laboratorium 4: Sinkhorn log-domain dan sertifikat transportasi
Diberikan histogram positif
,
dengan
dan matriks biaya
,
masalah transportasi teratur-entropi yang dipakai di sini adalah
Representasi langsung
rentan underflow. Skrip
labs/original-03/transportasi-entropik.py menyimpan
potensial dual
dan melakukan pembaruan dengan logsumexp. Kopling dibentuk
hanya dari
Eksperimen utama memakai titik dan massa yang dihasilkan oleh seed tetap. Dua eksperimen ekuivalen kemudian dijalankan: (i) dan dikalikan faktor positif yang sama; (ii) konstanta besar ditambahkan ke semua entri . Transformasi pertama mempertahankan rasio biaya-entropi, sedangkan transformasi kedua menambah konstanta pada nilai objektif tanpa mengubah minimizer. Kasus kedua memaksa seluruh kernel naif menjadi nol, tetapi pembaruan log-domain tetap menghasilkan kopling yang sama.
Prompt
Turunkan pembaruan bergantian bagi dan dari kendala marginal.
Buktikan bentuk dual dan identitas celah primal-dual yang diperiksa skrip.
Verifikasi dari CSV bahwa setiap entri kopling utama positif dan bahwa jumlah baris serta kolom cocok dengan dan dalam toleransi.
Buktikan invariansi kopling ketika diganti dengan , .
Jelaskan mengapa tidak mengubah kopling, lalu cocokkan dengan uji underflow terkontrol.
Petunjuk bertahap
Ambil log dari persamaan dan selesaikan satu potensial ketika potensial lain dibekukan.
Gunakan konjugat dari , yaitu .
Jangan menjumlahkan kernel naif pada uji stres; periksa penghitung nol dan residual hasil log-domain secara terpisah.
Untuk penskalaan, pilih potensial baru .
Untuk penambahan konstanta, serap ke salah satu potensial.
Jawaban singkat
Pembaruan log-domain menormalkan satu marginal pada satu waktu tanpa pernah membentuk kernel kecil. Dualnya adalah CSV dan JSON membuktikan residual marginal, positivitas numerik, kesepakatan primal-dual, invariansi penskalaan, invariansi pergeseran biaya, dan pemulihan dari kasus ketika kernel naif seluruhnya underflow.
Solusi acuan lengkap
Untuk tetap, kendala baris memberi Rumus bagi analog dari kendala kolom. Konjugasi entropi menghasilkan dual pada jawaban singkat. Jika dibentuk dari potensial, nilai primal dan nilai dual berimpit pada optimum; program memeriksa .
Jika dan , potensial , memberi log-kopling yang persis sama. Jika , pilih dan ; sekali lagi log-kopling tidak berubah. Namun kernel naif memuat faktor dan dapat menjadi nol pada aritmetika floating point. Potensial log-domain menyerap konstanta sebelum eksponensiasi akhir, sehingga residual marginal, positivitas kopling utama, dan kesepakatan dengan dua masalah ekuivalen tetap dapat diperiksa.
Hak dan firewall O018.
Teks, soal, solusi, dan kode ini merupakan material baru CC BY-SA 4.0. Tidak ada byte, prosa, latihan, solusi, kode, atau struktur instruksional O018 yang digunakan; peran laboratorium ini terbatas pada penutupan komputasional Original-03.
Proyek kapstone: masalah invers komposit yang tahan pencilan
Proyek ini menyatukan pemodelan konveks, gradien Lipschitz, operator
proksimal, formulasi dual, pemisahan primal-dual, anggaran oracle, dan
sertifikat a posteriori. Instans tetap dibentuk oleh
labs/original-03/kapstone-invers-komposit.py: matriks
,
sinyal renggang
,
derau kecil, dan delapan pencilan besar. Modelnya
FISTA dengan restart
gradien dan PDHG dijalankan untuk jumlah iterasi yang sama. Setiap
iterasi inti masing-masing memakai satu aplikasi
dan satu aplikasi
,
sehingga perbandingan memakai anggaran operator yang sama. Jejak CSV
mencatat objektif, batas bawah dual layak, celah tersertifikasi, dan
galat rekonstruksi. SVG hanya merupakan visualisasi jejak tersebut.
Prompt
Selesaikan tujuh tonggak berikut dan serahkan uraian matematis bersama JSON, CSV, serta SVG yang dihasilkan tanpa perubahan konfigurasi.
Instans dan pencilan. Rekonstruksi instans dari seed, verifikasi ukuran, support sinyal, dan delapan indeks pencilan.
Model konveks. Buktikan kekonveksan [orig03:eq:capstone-model] dan jelaskan mengapa Huber lebih tahan pencilan daripada kuadrat murni.
Bagian mulus. Turunkan gradien dan batas Lipschitz .
Langkah proksimal. Turunkan soft-threshold bagi dan tulis iterasi FISTA yang dipakai.
Dual dan PDHG. Turunkan konjugat Huber, kendala dual, serta pembaruan PDHG; buktikan .
Anggaran sepadan. Bandingkan kedua metode pada jumlah perkalian matriks-vektor yang sama, bukan pada waktu dinding.
Sertifikat dan interpretasi. Verifikasi kelayakan dual, celah primal-dual, pemetaan gradien proksimal, dan perbaikan terhadap least squares; nyatakan juga apa yang tidak dibuktikan eksperimen ini.
Petunjuk bertahap
Hash matriks dan data dalam JSON adalah identitas instans, bukan pengganti pemeriksaan ukuran dan seed.
Turunan Huber adalah proyeksi skalar ke dan bersifat satu-Lipschitz.
Komposisi dengan mengalikan konstanta Lipschitz oleh .
Gunakan .
Konjugat Huber adalah ; konjugat norma satu menghasilkan kendala .
Kolom
matrix_vector_productsadalah sumbu perbandingan yang benar.Skala kandidat dual bila perlu untuk memperoleh batas bawah yang benar-benar layak sebelum menghitung celah.
Jawaban singkat
Model adalah jumlah fungsi konveks. Bagian Huber mulus memiliki gradien -Lipschitz dengan , dan bagian norma satu memiliki proksimal soft-threshold. Dualnya memaksimalkan FISTA dan PDHG mencapai objektif yang cocok pada anggaran operator sama; batas dual layak memberi celah terukur, dan kedua rekonstruksi mengungguli least squares pada instans berpencilan yang dibekukan.
Solusi acuan lengkap
Karena dan norma satu konveks, komposisi afin dan penjumlahan mempertahankan kekonveksan. Turunan Huber adalah . Proyeksi ini satu-Lipschitz, sehingga Langkah yang dibekukan karena itu sah. Optimalisasi proksimal skalar memberi soft-threshold, lalu ekstrapolasi Nesterov menghasilkan FISTA; restart gradien memakai vektor yang sudah tersedia tanpa mengubah dua aplikasi operator inti per iterasi.
Dari dan , dual yang tertulis pada jawaban singkat mengikuti melalui Fenchel–Rockafellar. Proksimal adalah pembagian oleh diikuti kliping ke ; proksimal primal tetap soft-threshold. Pilihan memberi .
Pada iterasi berhingga, kandidat dual dapat melanggar kendala kedua sedikit. Penskalaan mempertahankan kendala kotak dan memastikan kelayakan. Nilai dual menjadi batas bawah rigor bagi objektif primal. Program menguji kelayakan, celah terhadap batas terbaik, norma pemetaan gradien proksimal FISTA, kesamaan anggaran, kedekatan kedua objektif, dan galat rekonstruksi terhadap baseline least squares. Bukti ini berlaku untuk instans dan toleransi yang dinyatakan; ia tidak mengklaim bahwa parameter yang sama optimal bagi semua masalah invers atau semua pola pencilan.
Hak dan firewall O018.
Proyek, bukti, soal, solusi, kode, dan instans sintetik ini ditulis mandiri dan tersedia berdasarkan CC BY-SA 4.0. Tidak ada materi O018 yang disalin, diadaptasi, atau dijadikan templat tersembunyi; O018 tetap terpisah dari lapisan penutupan Original-03.
Secara tepat, fungsi-fungsi diidentifikasi apabila sama hampir di mana-mana. Norma adalah supremum esensial, . Rincian teori ukuran ini tidak diperlukan dalam kuliah ini.↩︎
dan disebut eksponen konjugat Hölder.↩︎
Secara informal: keduanya mempunyai struktur yang sama.↩︎
Asumsi dimensi hingga menyediakan kekompakan sekuensial yang dipakai bukti ini. Generalisasi ke dimensi tak hingga memerlukan hipotesis tambahan, misalnya refleksivitas dan semikontinuitas bawah lemah; ketiga asumsi yang ditampilkan saja tidak cukup.↩︎
Sebagai latihan: mengapa barisan seperti ini selalu ada?↩︎
Pracitra terdefinisi dengan baik juga untuk pemetaan yang tidak invertibel.↩︎
yakni batas ↩︎
Tanda minus pada dipilih untuk memudahkan perhitungan.↩︎
Formulasi ini memakai yang terdefinisi pada seluruh , termasuk di luar .↩︎
Artinya, memenuhi definisi ruang vektor.↩︎
Batas ini dikenakan pada subgradien yang benar-benar dipilih oleh algoritma; batas tersebut tidak disimpulkan hanya dari sifat Lipschitz relatif pada .↩︎
Di sini kekonveksan telah ditunjukkan secara langsung. Rincian untuk lsc ditinggalkan sebagai latihan.↩︎
Ketika topologi dibutuhkan, keduanya akan diasumsikan sebagai ruang Polish dengan aljabar- Borel; yaitu, ruang topologis separabel yang topologinya dibangkitkan oleh suatu metrik lengkap.↩︎
Secara khusus, memuat himpunan kosong serta tertutup terhadap komplemen dan gabungan terhitung.↩︎
Hal ini khususnya menyiratkan bahwa tidak mempunyai massa titik.↩︎