Optimasi 2

Dosen : Prof. Dr. Suhartono, M.Kom

Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Fakultas : Sains dan Teknologi

Jurusan : Teknik Informatika

Optimasi Grafis

Solusi grafis yang diberikan pada masalah ketapel sepenuhnya memuaskan. Apakah solusi tersebut akan memenangkan kontes bergantung pada apakah model yang kita buat untuk fungsi tujuan sudah benar. Kita telah mengabaikan, misalnya, hambatan udara, yang mungkin penting.

Penyelesaian masalah optimasi telah mempersiapkan kami untuk menguji hasilnya di lapangan. Mungkin kita akan menemukan bahwa sudut optimal dunia nyata agak lebih curam atau lebih dangkal dibandingkan $\theta ={45}^{\circ }$ .

Selain argmax, besaran penting lainnya yang perlu dibaca dari grafik pada Gambar 1 adalah presisi argmax. Dalam istilah matematika yang ketat, argmax untuk soal bola tenis tepat pada titik 45 derajat $\cos (\theta )\sin (\theta )=0.5$ . Namun, misalkan bola diluncurkan hanya pada sudut 40 derajat. Perbedaan lima derajat terlihat jelas oleh mata, namun hasilnya pada dasarnya sama dengan 45 derajat: $\cos (\theta )\sin (\theta )=0.492$ . Hal yang sama juga berlaku untuk sudut peluncuran 50 derajat. Untuk kedua sudut peluncuran “sub-optimal”, outputnya berada dalam 2 persen dari hasil 45 derajat. Sangat mudah untuk membayangkan bahwa faktor di luar cakupan model sederhana—angin, misalnya—dapat mengubah hasil sebesar atau lebih dari 2 persen, sehingga laporan praktis dari argmax seharusnya adalah “40 hingga 50 derajat” daripada “tepat 45 derajat”.

Kontes dimenangkan atau dikalahkan dengan margin kurang dari 1%, jadi Anda tidak boleh menyimpang begitu saja dari argmax. Di samping itu, ${45}^{\circ }$ adalah argmax model . Realitas mungkin menyimpang dari model. Misalnya, hambatan udara atau angin mungkin mempengaruhi jarak sebesar 1%. Itu adalah. hasil sebenarnya mungkin menyimpang sebanyak 1% dari nilai model. Jika demikian, kita seharusnya tidak mengharapkan argmax di dunia nyata mendekati 45 dibandingkan ; di mana pun dalam interval domain tersebut menghasilkan keluaran yang berada dalam 1% dari keluaran maksimum untuk model.

Derivatif dan optimasi

Kita sekarang akan menyusun ulang pencarian argmax dan interpretasinya dalam bentuk turunan fungsi tujuan sehubungan dengan kuantitas keputusan ( $\theta$ dalam soal ketapel). Untuk fungsi dengan satu masukan, ini tidak akan menjadi perbaikan dari teknik melihat grafik untuk mencari argmax. Namun, alasan sebenarnya menggunakan turunan adalah untuk mempersiapkan kita di masa depan untuk memecahkan masalah dengan lebih dari satu masukan, yang sulit untuk menggambar atau menafsirkan grafik. Selain itu, mendeskripsikan fungsi dalam bahasa turunan dapat membantu kita berpikir lebih jernih tentang aspek masalah, seperti ketepatan argmax.

Dengan grafik seperti Gambar 1 , mudah untuk mencari argmax; akal sehat membawa hari ini. Jadi pada awalnya tidak jelas mengapa kami mengambil pendekatan berikut:

Mari kita nyatakan argmax dari fungsi tujuan $f(x)$ oleh $x^{\star }$ . Mari kita lihat turunannya ${\partial }_{x}f(x)$ di lingkungan $x^{\star }$ . Mengacu pada Gambar 1 , dimana $x^{\star }={45}^{\circ }$ , Anda mungkin dapat melihatnya ${\partial }_{x}f(x^{\star })$ adalah nol; garis singgung grafik fungsi di $x^{\star }$ adalah horisontal.

Dilihat dari sisi lain, kemiringan $f(x)$ di sebelah kiri $x^{\star }$ positif. Bergerak sedikit ke kanan (yaitu bertambah $x$ dengan jumlah yang sangat kecil) meningkatkan output $f(x)$ . Di sisi lain, tepat di sebelah kanan $x^{\star }$ , kemiringan $f(x)$ negatif; saat Anda mencapai puncak bukit dan melanjutkan perjalanan, Anda akan menuruni bukit. Jadi turunan fungsi tersebut positif pada salah satu sisinya $x^{\star }$ dan negatif di sisi lain, menunjukkan bahwa ia melewati nol pada argmax.

Akal sehatnya benar: Berjalan menanjak untuk mencapai puncak, berjalan menurun untuk menjauh dari puncak. Di puncak bukit yang mulus, medannya datar. (Karena fungsi pemodelan kita mulus, bukit-bukit yang kita gunakan untuk memvisualisasikan fungsinya juga harus demikian.)

masukan $x^{\star }$ seperti yang ${\partial }_{x}f(x^{\star })=0$ disebut titik kritis . Mengapa tidak menyebutnya sebagai argmax saja? Karena kemiringannya juga akan menjadi nol pada suatu argumen. Dan bahkan dimungkinkan untuk memiliki kemiringan nol pada titik yang bukan merupakan argmin atau argmax.

Pada titik ini, kita mengetahui nilai-nilai itu $x^{\star }$ itu memberi ${\partial }_{x}f(x^{\star })=0$ adalah “titik kritis”, namun kita belum menjelaskan cara mengetahui apakah titik kritis tertentu merupakan argmax, argmin, atau bukan keduanya. Di sinilah perilakunya ${\partial }_{x}f(x)$ di dekat $x=x^{\star }$ penting. Jika $x^{\star }$ adalah argmax, kalau begitu ${\partial }_{x}f(x)$ akan positif di sebelah kiri $x^{\star }$ dan negatif di sebelah kanan $x^{\star }$ ; berjalan ke atas bukit untuk sampai ke sana $x^{\star }$ , di puncak bukitnya datar, dan setelah melewati puncak bukit tersebut kemiringannya negatif.

Untuk argumen, berubah $x$ dari kurang dari $x^{\star }$ menjadi lebih besar dari $x^{\star }$ ; Anda akan berjalan turun ke lembah, lalu meratakan diri di bagian paling bawah $x=x^{\star }$ , lalu kembali ke sisi lain lembah setelah Anda melewatinya $x=x^{\star }$ . Gambar 3 menunjukkan situasinya.

Gambar 3: Baris atas: Fungsi objektif di dekat argmax (kiri) dan argmin (kanan). Baris terbawah: Turunan dari fungsi tujuan. Garis horizontal (oranye) menandai nol pada sumbu vertikal.

Baris bawah grafik pada Gambar 3 menunjukkan turunan fungsi tujuan $f(x)$ , itu adalah, ${\partial }_{x}f(x)$ . Anda dapat melihatnya untuk argmax $f(x)$ , turunannya ${\partial }_{x}f(x)$ positif ke kiri dan negatif ke kanan. Demikian pula, di dekat argumen $f(x)$ , turunannya ${\partial }_{x}f(x)$ negatif ke kiri dan positif ke kanan.

Dengan kata lain, turunan ${\partial }_{x}f(x)$ memiliki kemiringan negatif di sebelah kiri argmin dan kemiringan positif di sebelah kiri argmax.

Turunan kedua dari fungsi tujuan $f(x)$ pada titik kritis $x^{\star }$ adalah apa yang memberitahu kita apakah titik kritisnya adalah argmax, argmin, atau bukan keduanya.

Titik kritis $x^{\star }$__________${\partial }_{x}f(x^{\star })$__________${\partial }_{xx}f(x^{\star })$

argmax_______________0_________________negatif

argumen______________0_________________positif

juga tidak_____________0__________________0

---

TAKE NOTE !

Sepanjang Blok 2, kami telah menerjemahkan ciri-ciri fungsi yang terlihat pada grafik ke dalam bahasa turunan:

1. Kemiringan suatu fungsi $f(x)$ pada masukan apa pun $x$ adalah nilai fungsi turunan ${\partial }_{x}f(x)$ pada saat yang sama $x$ .

2. Kecekungan suatu fungsi $f(x)$ pada masukan apa pun adalah kemiringan fungsi turunan, yaitu,${\partial }_{xx}f(x)$ .

3. Dengan menggabungkan (i) dan (ii), kita mendapatkan kecekungan suatu fungsi $f(x)$ pada masukan apa pun $x$ adalah nilai fungsi turunan kedua , yaitu, ${\partial }_{xx}f(x)$ .

4. Pada argmax $x^{\star }$ dari $f(x)$ , nilai fungsi turunan ${\partial }_{x}f(x^{\star })$ adalah nol dan nilai fungsi turunan kedua ${\partial }_{x}f(x^{\star })$ negatif . _ Situasi di argmin sejalan, turunan fungsi tujuan adalah nol dan turunan keduanya positif .

---

---

SEE HOW IT`S DONE.

Apa titik kritisnya?

Anda sudah familiar dengan polinomial kuadrat:

$$g(x)=a_0+a_{1}x+a_2{x}^2$$

Grafik polinomial kuadrat adalah parabola yang cekung ke atas atau cekung ke bawah. Parabola hanya mempunyai satu titik kritis, yang dapat berupa argmin atau argmax.

Mari kita temukan titik kritisnya. Kita tahu bahwa titik kritisnya adalah $x^{\star }$ seperti yang ${\partial }_{x}g(x^{\star })=0$ . Karena kita tahu cara membedakan hukum pangkat, kita bisa melihatnya

$${\partial }_{x}g(x)=a_1+2a_{2}x$$

dan, lebih khusus lagi, pada titik kritis $x^{\star }$ turunannya akan menjadi

$$a_1+2a_2{x}^{\star }=0$$

Di atas adalah persamaan, bukan definisi. Dikatakan bahwa terserah $x^{\star }$ kebetulan, jumlahnya $a_1+2a_2{x}^{\star }$ harus nol. Dengan menggunakan aljabar lama, kita dapat mencari lokasi titik kritis

$$x^{\star }=-\frac{a_1}{2a_2}$$

---