Belajar Lagrange Multipliers


Setelah lebih kurang 1 minggu menikmati liburan di Wellington dan melupakan sejenak kegiatan PhD, hari ini saya iseng untuk mulai kembali kegiatan riset. Namun, berhubung saya baru saja menyelesaikan draft proposal riset, agak bingung juga apa yang mesti dikerjakan. Akhirnya saya memutuskan untuk mulai dengan belajar Support Vector Machines (SVM), salah satu teknik machine learning yang diklaim ampuh, yang mungkin akan saya manfaatkan untuk tema riset selanjutnya. Berhubung saya pun baru mulai belajar dan belum sepenuhnya paham, tulisan ini tidak membahas tentang SVM (sorry ^_^), tetapi akan membahas salah satu tools yang digunakan di SVM yaitu Lagrange multipliers.

Sebenarnya selama ini saya sudah beberapa kali mengimplementasi program SVM untuk sekadar menyelesaikan toy problems. Jika menggunakan platform MATLAB, toolbox favorit saya adalah libsvm. Namun saya belum benar-benar paham bagaimana prinsip dasarnya. Well, saya terkadang masih menganut paradigma practical programmer, i.e., “give me the problem specification or the math formula, then I can always develop the program code for it without truly understand the underlying fundamental principle“. Setelah mengikuti setengah jalan online course oleh Prof. Yaser Abu-Mostafa, saya pikir Lagrange multipliers merupakan konsep yang penting di SVM dan deserves to be well understood.

Oke sekarang kita bermain-main dengan Lagrange multipliers. Saya akan mulai pembahasannya dengan sebuah contoh optimisasi sederhana dalam ruang Euclidean 2 dimensi yang dapat diselesaikan dengan Lagrange multipliers.

ellipse_rect

Seperti yang diilustrasikan gambar di atas, problemnya adalah sbb: “diberikan sebuah elips dengan persamaan x^2 + 4y^2 = 4, tentukan sebuah persegi panjang di dalam elips yang memiliki keliling terbesar“.

Sebelum memikirkan solusinya, marilah kita formulasikan lebih detil problem tersebut, dimulai dengan menentukan persamaan persegi panjang dalam bentuk x dan y. Asumsikan sebuah titik (x,y) di kuadran I pada gambar (kanan atas) dimana persegi panjang (warna merah) dan elips (warna biru) beririsan. Maka x adalah setengah dari panjang dan y adalah setengah dari lebar, obviously. Maka persegi panjang tersebut dapat kita tulis dalam sebuah fungsi  f(x,y) = 4x + 4y. Dengan demikian, berikut ini merupakan formulasi masalah dari mencari persegi panjang dengan keliling terbesar:

\displaystyle \max_{x,y} 4x + 4y \text{ subject to } x^2+4y^2 = 4\quad \quad \quad(1)

Dalam kalimat deskriptif, tentukan nilai x dan y yang memberikan f(x,y) maksimum, namun masih dalam batasan {x^2}+4{y^2}=4. Masalah seperti ini biasa dikenal dengan istilah constrained optimization.

Metode Lagrange Multipliers merupakan salah satu alat untuk menyelesaikan constrained optimization dalam hal mencari minimum/maksimum lokal, dimana fungsi batasan dalam bentuk persamaan (equality constraint). Dengan metode ini, formulasi (1) dapat ditulis kembali dengan memanfaatkan sebuah variabel \lambda yang disebut sebagai Lagrange multiplier dalam bentuk fungsi Lagrange sbb:

\displaystyle \max_{x,y} \mathcal{L}(x,y,\lambda) \quad \quad \quad (2)

dimana \displaystyle \mathcal{L}(x,y,\lambda)=f(x,y) - \lambda g(x,y)…(3) merupakan fungsi Lagrange, dan

\displaystyle f(x,y) = 4x + 4y \quad \quad \quad (4),

\displaystyle g(x,y) = x^2 + 4y^2 -4 \quad \quad \quad (5).

Untuk menyelesaikan problem (2), kita dapat menggunakan turunan parsial dari \mathcal{L} yang dinyatakan dengan vektor \nabla_{\{x,y,\lambda\}} \mathcal{L} (karena memiliki lebih dari 1 variabel, silakan baca ini jika belum familiar/lupa dengan turunan parsial) untuk mencari titik stasioner, i.e., (x_0, y_0, \lambda_0) yang menghasilkan \nabla_{\{x_0, y_0, \lambda_0\}} \mathcal{L}= \mathbf{0}. Perlu diperhatikan bahwa \nabla_{\{x,y,\lambda\}} \mathcal{L} = (\frac{\partial \mathcal{L} }{\partial x},\frac{\partial \mathcal{L} }{\partial y},\frac{\partial \mathcal{L} }{\partial \lambda} ).

Sekarang kita coba analisis lebih lanjut \frac{\partial \mathcal{L} }{\partial x} dan \frac{\partial \mathcal{L} }{\partial y} sebagai berikut:

\frac{\partial \mathcal{L} }{\partial x} = 0 \Rightarrow 4 - \lambda_1 (2x) = 0 … (6)

\frac{\partial \mathcal{L} }{\partial y} = 0 \Rightarrow 4 - \lambda_2 (8y) = 0 … (7)

Dalam hal ini, (6) dan (7) membentuk sebuah sistem persamaan linear. Dengan mengasumsikan \lambda_1 = \lambda_2, maka didapatkan x = 4y.

Dengan mensubstitusi x pada persamaan (5) dengan 4y, kita dapatkan

\displaystyle {(4y)^2} + 4{y^2} = 4 \Rightarrow 20{y^2}=4 \Rightarrow y = \pm \frac{1}{\sqrt{5}}.

Maka,

  • Untuk \displaystyle y = \frac{1}{\sqrt{5}}, x = \frac{4}{\sqrt{5}}
  • Untuk \displaystyle y = -\frac{1}{\sqrt{5}}, x = -\frac{4}{\sqrt{5}}

Dengan demikian, ada dua solusi yaitu (\frac{4}{\sqrt{5}}, \frac{1}{\sqrt{5}}) dan (-\frac{4}{\sqrt{5}}, -\frac{1}{\sqrt{5}}), dimana paling tidak salah satunya memberikan nilai maksimum untuk f(x,y). Jika kita cek dengan cara mensubstitusi masing-masing solusi tersebut ke f(x,y), maka (\frac{4}{\sqrt{5}}, \frac{1}{\sqrt{5}})-lah yang memberikan nilai maksimum.

Menjawab pertanyaan di awal, jadi persegi panjang yang dimaksud adalah persegi panjang dengan keliling \displaystyle f(\frac{4}{\sqrt{5}}, \frac{1}{\sqrt{5}}) = 4 (\frac{4}{\sqrt{5}}) + 4 (\frac{1}{\sqrt{5}}) = \frac{20}{\sqrt{5}} (selesai !)

Kalau kita coba analisis lebih lanjut persamaan (6) dan (7), kita akan menyadari bahwa sebenarnya masing-masing itu adalah \frac{\partial f}{\partial x}= \lambda \frac{\partial g}{\partial x} dan \frac{\partial f}{\partial y} = \lambda \frac{\partial g}{\partial y}, sehingga \nabla_{\{x,y\}} f = \lambda \nabla_{\{x,y\}} g. Secara intuitif, ini berarti nilai maksimum dapat ditemukan jika gradien dari f(x,y) paralel dengan gradien dari g(x,y)Konstanta \lambda tetap dibutuhkan karena panjang vector gradien antara gradien f dan g biasanya berbeda.

Kebetulan contoh di atas menghasilkan sistem persamaan linear yang mudah untuk diselesaikan. Selain itu, penambahan dimensi dari ruang solusi juga biasanya menambah kompleksitas, seperti contoh permasalahan berikut ini untuk kasus di ruang Euclidean 3 dimensi:

\displaystyle \max_{\{x,y,z\}} {x^2} + x + 2{y^2} + 3{z^2} \text{ subject to } x^2 + y^2 + z^2 = 1.

Silakan coba selesaikan sendiri🙂

10 thoughts on “Belajar Lagrange Multipliers

  1. artikel yang menarik mas, saya juga tertarik untuk belajar SVM. untuk ulasan artikel diatas saya masih belum paham cara mencari fungsi persegi panjang f(x,y) = 4x + 4y, mohon petunjuknya mas soalnya matematika saya sangat lemah

    1. Sorry mgkn penjelasan saya di atas memang belum cukup jelas. Kalau saya jelaskan seperti ini mudah2an lebih gampang dimengerti:

      Dari gambar koordinat cartesius di atas, dapat dilihat bahwa persegi panjang besar bergaris merah dapat dibagi menjadi 4 buah persegi panjang kecil, hasil perpotongan dengan sumbu koordinat. Perhatikan salah satu persegi panjang yg kecil, i.e., yang kanan atas. Panjang dan lebar dari persegi panjang kecil tsb adalah x dan y.

      Sekarang perhatikan persegi panjang besar. Dapat dilihat bahwa total length garis atas dan bawah (“panjang”) sama dengan 4x, dan total length garis kiri dan kanan (“lebar”) sama dengan 4y. Jadi, keliling persegi panjang tsb 4x + 4y.

      Semoga bisa dipahami.

      1. Ok berarti konteksnya utk landasan teori di TA ya. Hmm.. kalau boleh kasih saran, karena Lagrange multiplier ini udah cukup tua dan well known, sebaiknya sebisa mungkin hindari untuk mengutip dari blog (termasuk tulisan saya ini), wiki atau sejenisnya, kecuali kalau benar-benar terpaksa, karena itu bisa mengurangi ‘tingkat keilmiahan’ TA nya.

        Instead, kutiplah dari referensi sekredibel mungkin yang bisa ditemui, e.g., textbook, conference/journal paper, lecture notes. Salah satu cara untuk mencarinya bisa browse daftar referensi yang ada di wikipedia https://en.wikipedia.org/wiki/Lagrange_multiplier (tapi hindari untuk langsung mengutip wiki page nya).

        Good luck 🙂

  2. Permisi..boleh bantu selesain soal ini?
    Z=XY subject to X+Y=G dengan cara interpretasi lagrange multiplier

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s