FAKTORISASI MATRIK NON NEGATIF SKALA BESAR

FAKTORISASI MATRIK NON NEGATIF SKALA BESAR

TESIS

Oleh

PASUKAT SEMBIRING 067021007/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

FAKTORISASI MATRIK NON NEGATIF SKALA BESAR

TESIS

Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

PASUKAT SEMBIRING 067021007/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: FAKTORISASI MATRIK NON NEGATIF SKALA BESAR : Pasukat Sembiring : 067021007 : Matematika

Menyetujui, Komisi Pembimbing

(Drs. Opim Salim S.,M.Ikom,PhD) Ketua

(Dr. Saib Suwilo, M.Sc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 15 Juli 2008


Telah diuji pada Tanggal 15 Juli 2008

PANITIA PENGUJI TESIS Ketua

:

Drs. Opim Salim Sitompul,M.Ikom,PhD

Anggota

:

Dr. Saib Suwilo, M.Sc Prof. Dr. Herman Mawengkang Drs. Marwan Harahap, M.Eng


ABSTRAK Faktorisasi matrik non negatif dapat digunakan untuk memperoleh data representatif yang non negatif. Oleh karena itu faktorisasi ini dapat diformulasikan sebagai problema meminimumkan dengan batas kendala. Metode projected gradien sebagai salah satu teknik yang ada untuk mengoptimisasi batas kendala digunakan untuk faktorisasi non negatif. Metode yang diusulkan memperlihatkan sifat-sifat optimisasi yang terkuat. Kata kunci : Faktorisasi matrik, Matrik non negatif

i Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

ABSTRACT Non negative matrix factorization can be used for finding representations of nonnegative data. Therefore this factorization can be formulated as a minimization problem with bound constraints. The projected gradient method as one of the existing technique for bound-constrained optimization is used for the non-negative factorization. The proposed methods exhibit strong optimization properties. Keywords : Matrix factorization, Non negative matrix

ii Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

KATA PENGANTAR Tuhan itu sangat baik dan luar biasa kuasaNya. pertolonganNya sangatlah nyata. Banyak hal yang tidak terduga terjadi selama menyusun tesis ini. Atas kemurahanNya tesis ini dapat diselesaikan tepat pada waktu yang telah ditetapkan. Terima kasih buat anakku tercinta: Perananta Sembiring, SKM; Mariamagdalena Sembiring, S.Farm.Apt.; David Immanuel Sembiring, SP. dan Emiaginta Sembiring, yang telah menjadi sahabat dalam suka dan duka serta penolong dan pendorong untuk tetap tabah dan tegar. Penulis juga mengucapkan terima kasih kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.Ak selaku Rektor Universitas Sumatera Utara Medan. Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Prof.

Dr.

Herman Mawengkang selaku ketua Program Studi Magister

Matematika SPs Universitas Sumatera Utara, yang selalu memberi motivasi kepada penulis. Drs. Opim Salim S., MIkom, Phd selaku pembimbing I yang telah banyak membantu dalam penulisan tesis ini.

iii Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

Dr. Saib Suwilo, M.Sc selaku pembimbing II yang telah banyak memberikan masukan-masukan dalam penulisan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan. Seluruh pihak yang ikut membantu dalam penulisan tesis ini. Rekan-rekan mahasiswa reguler stambuk 2006, semoga sukses selalu.

Tuhan

menyertai kita. Amin.

Medan, September 2008 Penulis,

Pasukat Sembiring

iv Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

RIWAYAT HIDUP

A. Data Pribadi. Nama

: Pasukat Sembiring

Tempat/Tanggal Lahir : Dairi/ 13 November 1953 Jenis Kelamin

: Laki-Laki

Agama

: Katholik

Status Perkawinan

: Menikah

Alamat Rumah

: Jln. Pinangmas II Block C No.15 Perumahan Villa Palem Kencana Medan.

B. Riwayat Pendidikan. 1. SR Negeri Tigalingga (1961-1967) 2. SMP Negeri Tigalingga (1967-1970) 3. SMA Negeri Kabanjahe (1970-1973) 4. FMIPA USU Medan (1974-1984)

C. Pengalaman Kerja. 1. Staf Pengajar SMA Dharma Putra Medan (1975-1979) 2. Staf Pengajar SMA Nasional Khalsa Medan (1980-1985) 3. Staf Pengajar FMIPA USU Medan (1985-sekarang)

v Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

v

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

viii

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

3

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

4

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

4

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

5

2.1 Metode yang Ada dan Sifat-sifat Baru . . . . . . . . . . .

5

2.1.1 Metode Multiplicative Update . . . . . . . . . . . .

5

2.1.2 Alternatif Non Negatif Least Square . . . . . . . . .

7

2.1.3 Gradient Approaches . . . . . . . . . . . . . . . .

8

2.1.4 Projected Gradient Method Untuk Optimisasi Batas Kendala . . . . . . . . . . . . . . . . . . . . . .

9

2.1.5 Alternatif Non Negatif Least Squares Menggunakan Projected Gradient Methods . . . . . . . . . . . . . .

11

2.2 Dasar-dasar Algoritma

. . . . . . . . . . . . . . . . . . vi


14

2.3 Algoritma Update Multiplicative

. . . . . . . . . . . . .

14

2.3.1 Algoritma Descent Gradient . . . . . . . . . . . . .

17

2.3.2 Algoritma Least Square . . . . . . . . . . . . . . .

19

BAB 3 MATRIKS TAK NEGATIF . . . . . . . . . . . . . . . . . .

21

3.1 Aplikasi 1 : Model Terbuka . . . . . . . . . . . . . . . .

24

3.2 Aplikasi 2 : Model Tertutup . . . . . . . . . . . . . . . .

30

BAB 4 PROGRAM NON LINIER

. . . . . . . . . . . . . . . . . .

32

4.1 Set Konvek Konstrain . . . . . . . . . . . . . . . . . . .

33

4.2 Kondisi Kuhn-Tucker . . . . . . . . . . . . . . . . . . .

36

4.3 Metode Gradient Tereduksi . . . . . . . . . . . . . . . .

40

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . .

47

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .

47

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

48

vii Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Ilustrasi pendekatan FMN . . . . . . . . . . . . . . . . . .

22

4.1

a. Kurva Konvek Terbuka Kebawah; b. Kurva Konvek Terbuka Keatas; c. Irisan Kurva Konvek . . . . . . . . . . . . . . .

34

a. Kurva tidak set konvek; b. Kurva set konvek

36

4.2

viii Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

. . . . . . .

BAB 1 PENDAHULUAN

1.1 Latar Belakang Umumnya matriks dapat digunakan di dalam kehidupan sehari-hari misalnya dalam bidang industri, pertanian, teknik dan lain-lain. Matriks yang digunakan dalam hal ini adalah matriks yang berskala besar. Untuk memproses matriks berskala besar memerlukan ketelitian yang sangat rumit dan waktu yang lama. Untuk menghindari hal ini diperlukan suatu cara menyederhanakan sehingga lebih efesien. Faktorisasi matriks non negatif (FMN) berguna untuk memperoleh gambaran dari data non-negatif. Dengan adanya n×m data matriks V integer dengan Vij > 0 dan bilangan bulat positif r < min(n, m), faktorisasi matriks non negatif memperoleh 2 (dua) matriks non-negatif W ∈ Rr×n dan H ∈ Rr×m seperti: V ≈ WH Jika setiap kolom V representatif pada suatu objek, faktorisasi matriks non negatif memperkirakannya dengan kombinasi linier dari r basis dalam kolom W . Faktorisasi matriks non negatif telah digunakan dalam banyak bidang. Pendekatan konvensional untuk mendapatkan W dan H dengan memeperkecil perbedaan antara V dan W H: 1 XX (Vij − (W H)ij )2 min f(W, H) = W,H 2 i=1 j=1 n

m

(1.1)

Subject to Wia ≥ 0, Wbj ≥ 0, ∀ i, a, b, j 1 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

2 Ketidaksamaan seperti variabel atas dan bawah adalah mengacu kepada batas kendala. Karena itu, (1.1) adalah satu masalah optimisasi batas kendala yang standar. Dapat dicatat bahwa: m n X X i=1 j=1

(Vij − (W H)ij )2 = V − W H 2F

dimana k · k adalah norm Frobenius Pendekatan yang paling populer untuk menyelesaikan (1.1) adalah algoritma nultiplicative. (Lee dan Seung, 2001). Hal tersebut mudah untuk dilakukan dan sering memberikan hasil yang baik. Setiap iterasi metode ini, elemen W dan H dikalikan dengan faktor-faktor tertentu. Sebagaimana elemen nol tidak update, semua komponen dari W dan H adalah positif untuk semua iterasi. Tipe strategi ini berlawanan dengan metode tradisional optimisasi batas kendala, yang biasanya membolehkan iterasi untuk mendapatkan elemen tertentu. (Contohnya dalam hal ini elemen nol). Hingga kini, ada penelitian secara formal dengan menggunakan teknik optimisasi batas kendala faktorisasi matriks non negatif. Dalam hal ini akan dibahas beberapa metode secara detail tentang studi faktorisasi matriks non negatif, sebelumnya memerlukan kolom Ws dijumlahkan menjadi ∀a = 1, . . . , r. Nilai fungsi tidak berubah karena f(W D, D − 1H) = f (W, H) untuk setiap r × r diagonal matrik D positif. Konstrain dengan masuknya pembatas tambahan, (1.1) tidak lagi menjadi masalah. Sebagaimana pembatas-pembatas ini dapat melengkapi prosedur optimisasi, dalam hal ini tidak dipertimbangkan masalah modefikasi. Diantara teknik optimisasi batas kendala yang ada, metode projected gradient adalah sederhana dan efektif, dalam hal ini secara komprehensif dalam meng-


3 gunakan projected gradient method untuk faktorisasi matriks non negatif. Beberapa modifikasi yang bermanfaat menghasilkan efisiensi dalam hal pelaksanaannya. Sementara metode multiplicative update masih menghasilkan yang kurang konvergen, metode yang dihasilkan menunjukkan sifat optimisasi yang kuat. Dengan eksperimen, menunjukkan bahwa satu dari metode yang diusulkan konvergen lebih cepat daripada metode multiplicative update. Metode ini merupakan pendekatan yang menarik. Secara seksama, formula ini bukan masalah batas kendala, yang memerlukan fungsi yang tepat untuk mendefinisikan dengan baik pada setiap titik dalam daerah terbatas. Fungsi log tidak didefinisikan dengan baik jika Vij = 0 atau (W H)ij = 0, karena itu formulasi ini tidak disarankan pada kasus ini.

1.2 Perumusan Masalah Faktorisasi matriks non negatif dapat digunakan pada pengendalian tingkat dimana gambaran (representatif) data menggunakan matriks jarang. Dalam banyak penerapan dibutuhkan pengendalian terhadap sifat-sifat dari data yang representatif tersebut. Dalam hal ini harus diminimumkan kesalahan sehingga data yang diperoleh lebih representatif.

1.3 Tujuan Penelitian Tujuan penelitian ini adalah mendeskripsikan ide dasar dari faktorisasi matriks non negatif, menunjukkan bagaimana kaitannya dalam matriks jarang dan mencari galat yang lebih kecil dalam perkalian matriks V ≈ W H.


4 1.4 Kontribusi Penelitian Kontribusi penelitian adalah menambah wawasan pengetahuan dalam penelitian di bidang matematika, khususnya yang berkaitan dengan menggunakan faktorisasi matriks non negatif.

1.5 Metodologi Penelitian Penelitian ini diawali dengan konsep-konsep faktorisasi matriks non negatif yang meliputi:

1. Multiplicative Update 2. Alternatif Non Negatif Least Square 3. Gradient Approaches 4. Projectif Gradient untuk Optimisasi Kendala 5. Alternatif Non Negatif Least Square Menggunakan Projected Gradient Methods

Selanjutnya dibahas mengenai algoritma update multiplicative, algoritma descent gradient dan algoritma least square untuk memfaktorisasi matriks non negatif yang berskala besar.


BAB 2 TINJAUAN PUSTAKA

2.1 Metode yang Ada dan Sifat-sifat Baru Banyak metode untuk faktorisasi matriks non negatif. Beberapa diskusi dalam membahas batas kendala tidak dilakukan dengan tepat. (Paatero, 1999). Dibutuhkan sifat-sifat tertentu dalam masalah faktorisasi matriks non negatif. Gradien fungsi (W H) terdiri dari dua bagian: ∇W f(W, H) = (W H − V )HT dan ∇H f (W, H) = W T (W H − V )

(2.1)

yang berturut-turut diturunkan secara parsial kepada elemen dalam W dan H. Dari Karush-Kuhn-Tucker (KKT) kondisi optimal (W, H) adalah satu titik tetap jika dan hanya jika: Wia ≥ 0, Hbj ≥ 0 ∇W f(W, H)ia ≥ 0, ∇H f (W, H)bj ≥ 0

(2.2)

Wia .∇W f(W, H)ia = 0, dan Hbj .∇H f (W, H)bj ≥ 0, ∀i, a, b, j Metode optimisasi untuk faktorisasi matriks non negatif menghasilkan satu barisan W k , H k k=1 dari iterasi. Problema (1.1) adalah tidak konveks dan bisa memiliki daerah fisibel.

2.1.1 Metode Multiplicative Update Pendekatan yang paling banyak untuk meminimalkan (1.1) adalah metode perkalian yang sederhana. Algoritma 1 Multiplicative Update: 5 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

6 1. Permulaan Wiak+1 > 0, ∀i, a, b, j 2. Untuk k = 1, 2, . . . Wiak+1 = Wiak k+1 k Hbj = Hbj

(V (H k )T )ia , ∀i, a (W k H k (H k )T )ia

((W k+1 )T V )bj , ∀b, j (W k+1 )T W k+1 H k )bj

Algoritma ini adalah metode tipe titik tertentu jika (Wk Hk (Hk )T )ia 6= 0 dan Wiak+1 = Wiak > 0, lalu (V (Hk )T )ia = (Wk Hk (Hk )T )ia menunjukkan bahwa ∇W f (Wk , Hk )ia = 0, yang merupakan bagian dari kondisi KKT telah menunjukkan bahwa nilai fungsi tidak bertambah setelah diperbaharui. (Lee dan Seung, 2001). f(Wk+1 , Hk ) ≤ f(Wk , Hk ) dan f(Wk+1 , Hk+1 ) ≤ f (Wk+1 , Hk )

(2.3)

Diklaim bahwa limit dari barisan (W k , H k )k=1 adalah titik yang tidak berubah. Titik yang sesuai dengan kondisi KKT, mengindikasikan bahwa pernyataan ini adalah salah karena tidak menunjukkan konvergensi. Oleh karena itu, metode multiplicative update ini masih tidak memiliki sifat optimisasi. (Gonzales dan Zhang, 2005). Untuk menjadikan algoritma 1 terdefinisi dengan baik, harus dipastikan bahwa denominator adalah positif. Selain itu, jika Wiak = 0 pada iterasi, Wia = 0 k > 0. pada semua iterasi yang berikutnya. Jadi, harus dijaga Wia1 > 0 dan Hbj

Teorema berikut dibahas ketika sifat ini ada. Algoritma 1 jika V mempunyai k > 0, ∀ i, a, b, j lalu kolom dan baris nol, dan Wia1 > 0 dan Hbj

k Wiak = 0 dan Hbj > 0, ∀ i, a, b, j, ∀ k ≥ 1


(2.4)

7 2.1.2 Alternatif Non Negatif Least Square Dari sifat (2.3), algoritma 1 adalah hal khusus dari sebuah kerangka umum, yang tidak menentukan satu matriks dan meningkatkan yang lain: Temukan Wk+1 seperti f(Wk+1 , Hk ) ≤ f (Wk , Hk ), dan Temukan Hk+1 seperti f (Wk+1 , Hk+1 ) ≤ f (Wk+1 , Hk ), Keadaan ekstrim untuk memperoleh titik terbaik. (Paatero, 1999 ; Chu et al, 2004). Algoritma 2 alternatif non negatif least square.

1 > 0, ∀ i, a, b, j 1. Permulaan Wia1 > 0, Hbj

2. Untuk k = 1, 2, . . . W k=1 = arg min f (W, H k )

(2.5)

H +1 = arg min f (W k+1 , H)

(2.6)

W ≥0

H≥0

Pendekatan algoritma ini adalah metode penurunan blok koordinat dalam optimisasi batas kendala, dimana berturut-turut satu blok variabel diperkecil dibawah pembatas yang sesuai dan sisa blok sudah tertentu. Untuk Faktorisasi matriks non negatif, hal yang paling sederhana dari dua blok variabel W dan H. (Bertsekas, 1999). Pokok persoalan yang lain adalah apabila rangkaian (Wk , Hk ) mempunyai setidaknya satu batas titik (ada setidaknya satu sub rangkaian konvergen), dalam analisis optimisasi, sifat ini kemungkinan sering berasal dari daerah yang tak terbatas, tetapi daerah pembatas Wia ≥ 0 dan Hbj ≥ 0 adalah tidak terbatas.


8 Dapat dengan mudah menambah batas atas yang luas untuk semua variabel dalam (1.1). Sebagaimana modifikasi masih menyebabkan masalah batas kendala, algoritma 2 dapat digunakan. Didalam perbedaan itu, adalah belum jelas bagaimana dengan mudah mengubah aturan multiplicative update jika ada batas atas dalam (1.1). Sebagai kesimpulan, berbeda dengan algoritma 1, yang masih kurang memberi hasil konvergen, memiliki sifat optimisasi yang baik.

2.1.3 Gradient Approaches Mendiskusikan secara singkat metode yang memilih ukuran langkah sepanjang arah gradient negatif. Didefinisikan: 2 dan Hbj = Fbj2 Wia = Eia

Dirumuskan kembali (1.1) sebagai sebuah masalah optimisasi tanpa pembatasan dari variabel Eia dan Fbj , kemudian metode gradient standard dapat digunakan. (Chu et al, 2004). Pengarang yang sama juga menyebutkan bahwa W k+1 = max(0, W k − αk∇W f (W k , H k )) H k+1 = max(0, H k − αk∇H f (W k , H k )) dimana αk adalah stepwise. Pendekatan ini sudah merupakan projected gradient method. (Shepherd, 2004).


9 2.1.4 Projected Gradient Method Untuk Optimisasi Batas Kendala Bentuk standar masalah optimisasi batas kendala min f (x)

x∈Rn

(2.7)

Subject to li ≤ xi ≤ ui , i = 1, . . . , n dimana f(x) : Rn → R adalah fungsi turunan tak terhingga , l dan u adalah batas bawah dan atas, berurutan. Anggap k adalah indeks iterasi projected gradient method, memperbarui pemecahan terakhir xk ke xk+1 dengan aturan berikut

Dimana P [xi ] =

(

xi ui li

xk+1 = P [xk − αk ∇f (xk )] jika li < xi < ui jika xi > ui jika x i ≤ li

memetakan sebuah titik ke daerah batas yang fisibel. Variasi projected gradient method berbeda dalam memilih step wise. Mengemukakan aturan yang sederhana dan efektif yang disebut aturan Armijo sepanjang pancaran proyeksi. (Bersekas, 1999). Prosedurnya diilustrasikan dalam algoritma Projected Gradient Method untuk Optimisasi Batas Kendala

1. Diberikan 0 < β < 1, 0 < σ < 1. Permulaan setiap x1 yang fisibel. 2. Untuk k = 1, 2, . . . xk+1 = P [xk − αk ∇f (xk )] dimana αk = βkt dan tk adalah bilangan non negatif yang mana f (xk+1 ) − f(xk ) ≤ α∇f (xk )T (xk+1 − xk )


(2.8)

10 Kondisi (2.8) digunakan untuk banyak bukti metode gradient, memastikan kesesuaian penurunan nilai fungsi per iterasi. Dengan mencoba stepwise 1, β1 , β2, . . . , βn telah membuktikan bahwa αk > 0 sesuai dengan (2.8) selalu ada dan setiap titik batas merupakan limit poin (stasionari) dari (2.7). Pilihan yang biasa dari σ adalah 0,01 dan menganggap β = 1/10. Bertsekas (1976). Mencari αk adalah operasi yang paling memakan waktu dalam algoritma 2, jadi harus menguji berapa stepwise sebaik mungkin. Karena αk−1 dan αk dapat saja sama, satu cara dalam menggunakan αk−1 sebagai perkiraan awal dan kemudian meningkatkan atau menurunkan untuk mendapatkan βtk terbesar yang sesuai dengan (2.8). (Lin dan Mor’e, 1999). Kadang-kadang, langkah yang lebih besar lebih efektif memproyeksikan variabel-variabel untuk membatasi pada satu pengulangan. Algoritma 3 Metode Projected Multiplicative

1. Diberikan 0 < β < 1, 0 < σ < 1. Permulaan dengan semua x1 yang fisibel membuat α0 = 1. 2. Untuk k = 1, 2, . . . a. Menetapkan αk ← αk−1 b. Jika αk fisibel dengan (2.8) berulang-ulang meningkatkan dengan αk ← αk /β sampai αk fisibel dengan (2.8) juga x(αk /β) = x(αk ) kemudian berulang-ulang diturunkan dengan αk ← αk β sampai αk fisibel dengan (2.8) c. Menetapkan xk+1 = p[xk − αk ∇f (xk )]


11 Hasil yang konvergen telah dibuktikan sebagai contoh, dapat mengira bahwa mendapatkan α dengan reduksi fungsi terbesar membuat konvergen lebih cepat: αk = arg min f (P [xk − α∇f (xk )]) a≥0

Pemilihan konvergen seperti αk dapat dibuktikan. (McCormick dan Tapia, 1972). Hambatan yang besar untuk meminimumkan masalah batas adalah mengidentifikasi komponen-komponen bebas (misalnya, li < xi < ui) dan komponenkomponen aktif (misalnya, xi = li atau ui ) pada titik tetap konvergen. Projected gradient method diperkirakan efektif untuk melakukannya karena metode tersebut dapat menambah beberapa variabel aktif pada satu iterasi tunggal. Bagaimanapun, ketika ketetapan ini telah diidentifikasi, masalah dalam iterasi yang tak terbatas dan konvergen lambat dalam metode gradient. Akan dijelaskan dalam bagian ini dimana persoalan ini tidak serius untuk masalah faktorisasi matriks non negatif.

2.1.5 Alternatif Non Negatif Least Squares Menggunakan Projected Gradient Methods Bagian ini mengidindikasikan bahwa algoritma 2 berdasarkan pada efisiensi dalam pemecahan sub-masalah (2.5) dan (2.6), yang masing-masing merupakan masalah batas kendala menyusun penggunaan untuk menyelesaikannya. Sub masalah (2.6) terdiri atas masalah least square non negatif independent (2.8), jadi dapat menyelesaikan secara terpisah, situasi yang cocok untuk lingkungan paralel. Bagaimanapun, dalam seting serial, mencobanya bersamaan lebih baik karena alasan-alasan berikut:


12 1. Permasalahan-permasalahan least square non-negatif ini berhubungan erat sebagaimana hal-hal tersrebut berbagi matriks konstan yang sama yaitu V dan Wk+1 . 2. Melakukannya dalam H secara keseluruhan, bukan dalam kolom individual menjadikan semua operasi basis matriks. Karena kode aljabar linier numerik telah disetel dengan baik memiliki kecepatan yang lebih baik pada matriks dari pada operasi vektor, maka dapat menghemat waktu perhitungan.

Untuk deskripsi metode yeng lebih mudah, (2.6) dapat dituliskan kembali sebagi berikut: 1 min f¯(H) ≡ kV − W Hk2F H 2

(2.9)

Subject to Hbj ≥ 0, ∀ b, j V dan W keduanya merupakan matriks konstan dalam (2.9). Jika merekai kolom-kolom Hs kepada vector Vec (H0 ), kemudian.   T W W 1 1 ..  vec(H)+(H)0s linear terms f¯(H) = kV −W Hk2F − vec(H)T  . 2 2 WTW Matriks Hessian (misalnya, turunan kedua) dari f(H) adalah blokdiagonal dan setiap blok W T W merupakan matriks semi-definet positif r × r. Karena W ∈ Rn × r dan r n, W T W dan semua matriks Hessian cendrung dikondisikan dengan baik, suatu sifat yang bagus untuk algoritma optimasi. Biaya yang tinggi dalam menyelesaikan sub-masalah (2.5) dan (2.6) pada setiap pengulangan menjadi perhatian, sehingga hal ini penting untuk menganalisa kompleksitas waktu dan mencari efisiensi pelaksanaan tiap sub-masalah memerlukan suatu prosedur iterasi, yang mana iterasi berhubungan dengan sub-iterasi


13 ketika menggunakan Algoritma 4 untuk menyelesaikan (2.9), harus memperhatikan (2.9), gradient: ∀ f f¯(H) = W T (W H − V ) dalam setiap sub-iterasi. Mengikuti pembahasan harus memperhitungkan dengan (W T W )H − W T V matriks konstan W T W dan W T V dapat dihitung berturut-turut dalam operasi O(nr2) dan O(nmr) sebelum menjalankan subiterasi. Tujuan utama perhitungan per sub-iterasi adalah mendapatkan stepwise a ¯ adalah seperti kesesuaian kondisi penurunan (2.8) telah memenuhi. Anggap H ¯H ˜ ≡ P [H ¯ − α∀f( ¯ )] memenuhi (2.8), persolusi mutahir. Untuk memeriksa jika H ˜ menggunakan operasi O(nmr) jika ada percobaan, biaya perhihitungan f¯(H) tungan O(tmnr) menjadi penghalang digunakan strategi untuk mengurangi biaya suatu fungsi kuadrat f (x) dan semua vektor d, 1 f(x + d) = f (x) + ∇f (x)T d + dT ∇2f (x)d 2 ˜ dan X, ¯ (2.8) dapat ditulis Karena itu, untuk dua integrasi berurutan X sebagai berikut: 1 x − x)T ∇2f (x)(˜ x − x) + (˜ x − x) ≤ 0 (1 − σ)∇f (x)T (˜ 2 ¯ diartikan dalam (2.9) adalah sebagai kuadrat, jadi (2.8) menjadi: Sekarang H D E E D ˜ − H, (W T W )(H ˜ −H + 1 H ˜ − H) ≤ 0 (1 − σ) ∇f(H, H 2 ˜ −H ¯ ), yang mengdimana (.., ) adalah jumlah produk matriks (W T W ).(H gunakan O(mr2). Jadi, biaya O(mnr) dalam pemeriksaan (2.8) dikurangi secara signifikan menjadi O(mr2).


14 Dapat menggunakan prosedur yang sama untuk memperoleh Wk+1 dengan menulis nilai (2.6) sebagai suatu bentuk yang sama dengan (2.9): O(nmr) + #sub-iterasi × O(tmr2), dimana V T dan HT matriks konstan. Biaya keseluruhan selesaikan (1.1) adalah #iterasi × O(nmr) + #sub-iterasi× O(tmr2 + tnr2)f(W ) = 12 kV T − H T W T k2F , pada setiap interasi ada dua operasi O(nmr) : V (Hk)T dan (Wk+1 )T V , sama seperti dalam metode multiplicative update, jika t dan # sub iterasi kecil, metode ini efisien. Untuk mengurangi jumlah iterasi, suatu teknik sederhana namun bermanfaat adalah dengan warna start solution procedure pada setiap sub-masalah. Pada iterasi terakhir (Wk , Hk ) semuanya sama jika Wk adalah suatu titik permulaan yang efektif untuk penyelesaian (2.5).

2.2 Dasar-dasar Algoritma Skema klasifikasi dasar yang ditujukan terhadap algoritma FMN yang sudah dibicarakan sebelumnya. Algoritma ini dapat memperlihatkan lebih dari satu kelas, secara umum dapat dibagi menjadi 3 kelas, algoritma multiplicative update, algoritma gradient descent dan algoritma alternatif kuadrat terkecil. Dapat dicatat bahwa telah terbentuk library centre (FMN LAB) dari MATLAB yang rutin untuk tiap-tiap kelas dari algoritma FMN. (Chichocki dan Zdunek, 2006)

2.3 Algoritma Update Multiplicative Algoritma update multiplicative dengan rata-rata kuadrat kesalahan fungsi objektif (dengan menggunakan notasi operator susunan MATLAB) diberikan se-


15 bagai algoritma update multiplicative. Faktorisasi Matriks Non Negatif. (Lee dan Seung, 2001) W = rad(m, k); % awalnya W sebagai matrik acak padat H = rand(k, n); % awalnya H sebagai matrik acak padat Untuk i = 1: maxiter (MU )H = H. ∗ (W T A)./(W T W H + 10−9 ); (MU )W = W. ∗ (AHT )./(W HH T + 10−9 ); 10−9 dalam hukum update ditambahkan untuk mencegah pembagian dari nol. Menggunakan gradient dan sifat-sifat kontinu untuk mengklaim bahwa algoritma convergen terhadap suatu minimum lokal yang kemudian memperlihatkan tidak benar. Pembuktian memperlihatkan sifat-sifat kontinu yang tidak sesuai penjelasannya terhadap titik pelana. Untuk memahami kenapa salah satu yang harus diperhatikan dua dasar observasi yang meliputi kondisi optimal KarushKhun-Tucker. Pertama : Matriks awal W dan H positif dan kemudian matrik ini positif melalui iterasi. Pernyataan ini mudah diverivikasi dengan membandingkan terhadap bentuk hukum multiplicative update. Kedua : Jika urutan iterasi (W, H) konvergen terhadap (W ∗ , H ∗ ) dan W ∗ > 0 dan H ∗ > 0, (∂f/∂W )(W ∗, H ∗ ) = 0 dan (∂f /∂H)(W ∗, H ∗ ) = 0, point kedua ini dapat diverifikasi terhadap H dengan menggunakan bentuk bahan tambahan dari hukum update. H = H + [H./W T W H]. ∗ [W T (A − W H)] Perhatikan elemen (i, j) dari H. Anggap titik limit untuk H dicapai sehingga


16 Hij > 0 kemudian cari Hij Hij T [W W H]

([W T A]ij − [W T W H]ij ) = 0 ij

Karena Hij > 0 mengimplikasikan [W T A]ij = (W T W Hij )ij yang mengimplikasikan [∂f/∂H]ij = 0. Bila mana dua point ini digabung untuk mencapai kondisi optimum. Hal ini hanya berlaku untuk titik limit (W ∗, H ∗ ) yang tidak mempunyai suatu elemen sama dengan nol. (Bertsekas, 1999). W ≥0 H ≥0 (W H − A)H T ≥ 0 W T (W H − A) ≥ 0 (W H − A)H T .∗W = 0 dan W T (W H − A).∗H = 0 Disamping kenyataan ini sebagai contoh Hij > 0 untuk semua iterasi, elemen-elemen ini dapat konvergen (menyebar) terhadap nilai limit dari 0 dengan (∂f /∂H)ij ≥ 0 terhadap (W ∗, H ∗ ) bahkan Hij = 0. Jadi mungkin bahwa Hij = 0 dimana satu harus memberikan kondisi kelambanan dan mencari yang sebanding sehingga (∂f/∂H)(W ∗ , H ∗) ≥ 0 dan ini tidak muncul bagaimana menggunakan hukum update multiplicative. Jadi didalam kesimpulan hanya dapat membuat pernyataan berikut mengenai konvergensi dari algoritma multiplicative. (Lee dan Seung, 2001). Bila algoritma konvergen terhadap titik limit di dalam interior dari daerah fisibel titik ini adalah suatu titik tetap. Titik stasionari ini dapat atau tidak dapat berupa suatu lokasi minimum. Bila titik limit berada pada batas dari


17 daerah fisibel maka titik tetapnya tidak dapat ditentukan. Dalam kaitannya dengan statusnya sebagai algoritma Faktorisasi Matriks Nonnegatif pertama yang sudah dikenal, algoritma update multiplicative merupakan suatu basis terhadap algoritma yang lebih baru sebagai pembanding telah berulang bahwa algoritma ini konvergen. Hal ini memerlukan banyak iterasi dibandingkan dengan alternatif penurunan gradient dan algoritma Least Square yang dibicarakan dibawah ini. Kerja per iterasi adalah tinggi karena masingmasing iterasi memerlukan kerja O(mnk). Untuk mencegah beberapa hal ini periset telah mengusulkan modifikasi terhadap algoritma tersebut. Sebagai contoh membentuk suatu modifikasi tetapi kejelekannya masih mempunyai problem konvergensi yang sama. (Gonzalez dan Zhang, 2005). Algoritma yang dimodifikasi adalah menjamin terhadap konvergen suatu algoritma titik stationer. Disamping itu, untuk menurunkan hukum update yang tidak sama terhadap kepentingan-kepentingan dari elemen-elemen di dalam pendekatannya. (Dhillon dan Sra, 2005).

2.3.1 Algoritma Descent Gradient Algoritma Faktorisasi Matriks Nonnegatif dari kelas kedua didasarkan pada metode penurunan gradient. Algoritma dari kelas ini berulang-ulang menggunakan hukum update dari bentuk yang diperlihatkan dibawah ini. Algoritma penurunan gradient dasar untuk Faktorisasi Matriks Nonnegatif. W = rand(m, k); % initialize W H = rand(k, n); % initialize H


18 Untuk i = 1: maxiter ∂f H = H − εH ∂H ∂f W = W − εW ∂W

Setiap langkah ukuran parameter εH dan εW berubah tergantung pada algoritma turunan parsialnya. Algoritma ini selalu mengambil suatu langkah didalam arah gradient negatif dari penurunan yang paling tajam. Usaha-usaha umumnya di dalam pemilihan nilai untuk ukuran εH, εW . Beberapa algoritma pada awalnya diatur nilai-nilai tahap ukurannya terhadap 1. Kemudian dikalikan dengan

1 2

pada masing-masing urutan iterasi. Ini adalah sederhana tetapi

tidak ideal karena tidak ada hambatan yang menyebabkan elemen dari matrik update W dan H dari pendekatannya menjadi negatif. Penggunaan yang praktis kebanyakan algoritma penurunan gradien adalah suatu langkah proyeksi yang sederhana. (Shahnaz et al., 2006; Hoyer, 2004; Chu et al., 2004; Pauce et al., 2006). Jadi setelah tiap hukum update, matrik update diproyeksikan terhadap elemen-elemen negatif mendekati nilai-nilai non negatif 0. Tanpa pemilihan yang hati-hati untuk εH dan εW hanya sedikit yang dapat dikatakan mengenai konfergensi penurunan gradient. Selanjutnya, penambahan proyeksi non negatif membuat analisa lebih sulit. Metode penurunan gradient yang menggunakan suatu hukum geometri sederhana untuk ukuran langkah seperti kekuatan dari fraksi atau prosedur melalui suatu fraksi pada masingmasing iterasi sering menghasilkan suatu faktorisasi yang jarang digunakan. Dalam hal ini metode sangat sensitif terhadap W dan H. Dengan suatu inisialisasi acak metode ini konvergen terhadap suatu faktorisasi yang tidak berapa jauh dari matriks awal. Metode penurunan gradient seperti algoritma Seung dan Lee, penggunaan matriks yang baik untuk stepwise menghasilkan suatu faktorisasi


19 yang lebih baik, tetapi seperti disebutkan diatas, sangat lambat terhadap konvergen. Seperti didiskusikan dalam matriks shepherd adalah suatu teknik penurunan gradient yang diusulkan merupakan konvergensi dengan menggunakan pemilihan pada stepwise. Keburukan teori konvergensi untuk mendukung pendekatan ini adalah kurang tepat. (Chu et al, 2004).

2.3.2 Algoritma Least Square Kelas terakhir dari algoritma Faktorisasi Matriks Nonnegatif adalah kelas Algoritma Least Square. Di dalam algoritma ini langkah kuadrat terkecil diberi oleh langkah kuadrad terkecil yang lain di dalam suatu penampilan alternatif, jadi menaikkan terhadap nama Algoritma Least Square. Algoritma Least Square pertama sekali digunakan oleh Paatero, 1999. Algoritma Least Square mengeksploitasi kenyataan bahwa problem optimasi tidak konvek terhadap W dan H, maka hal ini konvek dalam W dan H, jadi akan memberikan suatu matriks dan matriks yang lain dapat ditemui dengan suatu perhitungan kuadrat terkecil yang sederhana. Suatu elemen algoritma least square mengikuti: Basik Algoritma Least Square untuk Faktorisasi Matriks Nonnegatif W = rand(m, k); % initialize W as random dense matrik untuk i = 1: maxiter (LS)

Solver untuk H pada matrik equation W T W H = W T A

(NONNEG) Set all negative elements H to 0 (LS)

Solve for W in matrix equation HH T W T = HAT

(NONNEG) Set all negative elements W to 0 Dalam pseudocode diatas memiliki metode yang telah sederhana untuk me-


20 mastikan non negativity, tahap proyeksi yang mengatur semua elemen negatif yang dihasilkan dari kuadrat terkecil hingga 0. Teknik sederhana ini yang mempunyai keuntungan tambahan.

Sudah barang tentu bantuan matriks jarang.

Terlebih-lebih hal tersebut memberikan iterasi beberapa fleksibility tambahan tidak tersedia di dalam algoritma yang lain, terutama sekali terhadap kelas multiplicative update. Selalu yang dapat ditemukan dari multiplicative adalah bahwa salah satu elemen dalam W dan H menjadi nol dan harus berada pada 0. Hal ini menetapkan elemen 0 membatasi, berarti bahwa algoritma memulai menurun tajam terhadap titik tertentu bahkan hal ini merupakan titik tertentu yang jarang dan harus kontinu dan vein. Algoritma Least Square adalah lebih fleksibel menuruti proses iterasi untuk keluar dari bagian yang jarang. Tergantung pada implementasi algoritma least square dapat lebih cepat. Implementasi memperlihatkan pemahaman yang signifikan diatas kurang bekerja dibandingkan dengan algoritma Faktorisasi Matriks Nonnegatif. Perbaikan-perbaikan terhadap dasar algoritma least square muncul. (Paatero, 1999, Langville et al., 2006).


BAB 3 MATRIKS TAK NEGATIF

Pendekatan Faktorisasi Matriks Non Negative dapat diformulasikan sebagai berikut: Suatu cover image C tertentu dengan ukuran m × m, dapat memfaktorisasi C ke dalam dua matrik non negative B dan H dengan ukuran masing-masing m × r dan r × m dimana C = B × H dimana r ≤ m. Matrik non negatif B mengandung vektor basis, F MN dan matrik H berbobot non negative, mempunyai koefisien assosiasi (bobot non negative). Untuk mengukur kualitas dari faktorisasi pendekatan C = BH, fungsi biaya antara C dan BH perlu untuk mengoptimalisasikan subjek terhadap konstrains non-negative pada B dan H. Hal ini dikerjakan dengan meminimumkan Z informasi divergen yang diberikan oleh: Z(C||BH) = Σ(Cij Log ij

Cij − Cij + (BH)ij ) (BH)ij

yang akan menghasilkan hukum multiplicative update. Hkj ← Hkj

Σi Bik Cik /(BH)ij Σi Bik

Bjk ← Bjk

Σj Hkj Cij /(BH)ij Σj Bkj

dimana matriks B dan H adalah awal dari matrik random non negative dan update dikerjakan secara alternative sehingga setelah diupdate satu baris H, perlu mengupdate kolom yang sesuai dengan B. Dengan perkataan lain tidak harus mengupdate matriks H pertama disertai oleh update dari matriks B. Algoritma 21 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

22 Faktorisasi Matriks Nonnegatif adalah suatu algoritma optimisasi iterasi. Dimana modifikasi pada tiap-tiap iterasi fungsi basis non negatif dan pengkodean (Hkj ) sampai konvergen.

Gambar 3.1 : Ilustrasi pendekatan FMN

Poin-poin yang keluar yang berkaitan dengan bayangan digital watermaking, syarat tertutup terhadap kompresi bayangan. Prinsip Componen Analisis (PCA) secara tradisi adalah salah satu metode yang digunakan secara umum untuk mereduksi analisa data fisinalisasi dan analisa Chester. Hasil sebelumnya memperlihatkan bahwa PCA tampaknya tidak sesuai untuk mereduksi dimensi dalam pernyataan gen cluster selanjutnya. Dewasa ini Faktorisasi Matriks Nonnegatif telah diusulkan untuk analisa data non negatif. Contoh : Non negativity membuat hasil dari bayangan muka awal secara fisial dan kemampuan menginterprestasikan secara rasional. Sekarang Faktorisasi Matriks Nonnegatif mulai banyak di gunakan dalam analisa data. Contoh untuk informasi yang lebih banyak dan referensinya. Dalam bidang bio informatika, Faktorisasi Matriks Nonnegatif juga telah merupakan suatu metode yang kuat untuk analisa data microarray dan analisa urutan protein. Bahkan Faktorisasi Matriks Nonnegatif digunakan untuk gen cluster dan dalam algoritma yang dimodifikasi yang didasarkan pada Faktorisasi Matriks Nonnegatif, yang di-


23 gunakan untuk keperluan yang sama. Faktorisasi Matriks Nonnegatif digunakan untuk menganalisa urutan protein. Faktorisasi Matriks Nonnegatif hanya digunakan secara langsung untuk mengcluster sampel yang dinyatakan gen dengan dibandingkan terhadap cluster secara hirarki dan pemetaan orgonisasi sendiri, Faktorisasi Matriks Nonnegatif digunakan untuk bioclustering dari data yang dinyatakan gen. Disini memperkenalkan lebih tajam ide dasar dari Faktorisasi Matriks Nonnegatif, dengan memberikan suatu set data dalam bentuk matrik yang terdiri dari m sampel dalam ruang n dimensi, dimana masingχ ∈ Rm×n + masing entri adalah non negative (contoh χij ≥ 0 untuk semua i, j), Faktorisasi Matriks Nonnegatif adalah untuk menentukan suatu pendekatan X ≈ BH, dimana B adalah suatu matrik n × d dan H suatu matrik d × m dan kedua B, H adalah juga non negative. Masing-masing kolom B dapat dipandang sebagai basis vektor dan masing-masing kolom H dapat dipandang merupakan suatu gambar vektor baru yang sebanding dengan data sesungguhnya. Lebih jelasnya pada dasarnya ada terdapat 2 algoritma untuk menyempurnakan dekomposisi melalui implementasi update multiplicative sebagai berikut: bik ← bik

(XH T )ik (BHH T )ik

hkj

(B T X)kj (B T BH)kj

χ

bik ←

ij Σj hkj (BH) ij

Σj hkj

dan χ

hkj ← hkj

ij Σj bik (BH) ij

Σi bik

Hukum update multiplicative dapat mengikuti non negative dengan initialization non negatif. Dalam banyak jenis sistem linear yang muncul dalam penerapan, elemenelemen dari matriks koefisien menunjukkan besaran tak negatif. Ini berkaitan dengan pengetahuan tentang matriks-matriks yang demikian serta sifat-sifatnya.


24 Definisi suatu matriks A berorde n × n dengan entri bilangan real disebut tak negatif jika αij ≥ 0 untuk setiap i dan j, dan disebut positif jika αij > 0 untuk setiap i dan j. Hal yang serupa, suatu vektor x = (x1, . . . , xn )T disebut tak negatif jika setiap xi ≥ 0 dan dikatakan positif jika setiap xi > 0.

3.1 Aplikasi 1 : Model Terbuka Misalkan ada sejumlah n industri yang memproduksi sejumlah n produk yang berbeda.

Masing-masing industri memerlukan masukan (input) produk

dari industri lain dan kemungkinan bahkan dari produknya sendiri. Pada model terbuka, diasumsikan bahwa ada kebutuhan (demand) tambahan untuk masingmasing produk yang berasal dari sektor luar. Masalahnya adalah menentukan keluaran (output) dari masing-masing industri yang diperlukan sesuai dengan kebutuhan total (total demand). Dapat dilihat bahwa masalah ini dapat dijelaskan dengan suatu sistem persamaan linear dan bahwa sistem tersebut mempunyai suatu penyelesaian tak negatif tunggal. Misalkan αij melambangkan jumlah masukan dari industri ke-i yang diperlukan untuk memproduksi satu unit keluaran di industri ke-j. Satu unit masukan atau keluaran produk tersebut dihargai sebesar satu dolar. Jadi dengan memproduksi produk ke-j seharga satu dollar akan dihabiskan sebanyak Pn i=1 αij dolar. Jelasnya, memproduksi produk ke-j tidak akan menguntungkan P kecuali ni=1 αij < 1. Misalkan di melambangkan kebutuhan dari sektor terbuka untuk produk ke-i. Selanjutnya, misalkan xi adalah jumlah keluaran dari pro-


25 duk ke-i yang diperlukan untuk mencukupi kebutuhan total. Jika industri ke-j ingin mempunyai keluaran sebanyak xj , maka akan diperlukan suatu masukan sebanyak αij xj unit dari industri ke-i. Jadi kebutuhan total untuk produk ke-i akan menjadi αi1 x1 + αi2 x2 + · · · + αin xn + di dan karenanya dibutuhkan syarat xi = αi1 x1 + αi2 x2 + · · · + αin xn + di untuk i = 1 . . . n. Hal ini menjadikan sistem (1 − α11)x1 + (−α12)x2 + · · · + (−α1n)xn + d1 .. . (1 − α21)x1 + (−α22)x2 + · · · + (−α2n)xn + dn yang dapat dituliskan dalam bentuk (I − A)x = d

(3.1)

Elemen-elemen dari A memiliki dua sifat penting:

(i) αij ≥ 0 untuk masing-masing i dan j (ii)

n P

αij < 1

i=1

Vektor x seharusnya bukan hanya merupakan suatu penyelesaian dari (3.1), tapi juga harus tak negatif (tidak ada artinya jika hanya memiliki keluaran negatif). Untuk memperlihatkan bahwa sistem tersebut mempunyai penyelesaian tak negatif tunggal, perlu membiasakan menggunakan suatu norma matriks baru,


26 yang disebut norma-satu (one-norm) dan dilambangkan dengan tanda k · k. Akan dilihat bahwa untuk sembarang matriks B berorde m × n. ! m X |bij | kBk1 = max 1≤j≤n

(3.2)

i=1

Juga akan ditunjukkan bahwa matriks norma-satu memenuhi sifat-sifat perkalian berikut di bawah ini: kBCk1 ≤ kBk1 kCk1

untuk sembarang matriks C ∈ Rn×r (3.3)

kBxk1 ≤ kBk1 kxk1

n

untuk sembarang matriks x ∈ R

Khususnya jika A adalah matriks berorde n × n yang memenuhi syarat (i) dan (ii), maka dari persamaan (3.2) didapatkan kAk1 < 1. Selanjutnya, jika λ adalah sembarang nilai eigen dari A dan x adalah suatu vektor eigen dari λ, maka kλkkxk1 = kλxk1 = kAxk1 ≤ kAxk1kxk1 dan oleh karena itu |λ| ≤ kAk1 < 1 Jadi 1 bukanlah nilai eigen dari A. Hal ini mengakibatkan I − A tak singular dan karena itu sistem (3.1) mempunyai penyelesaian yang tunggal X = (I − A)−1d Akan dilihat bahwa penyelesaian ini pasti tak negatif. Untuk melakukan hal ini, akan ditunjukkan bahwa (I − A)−1 adalah tak negatif. Catatan pertama adalah sebagai konsekuensi dari sifat perkalian (3.3), mendapatkan: kAmk1 ≤ kAkm1 Karena |Ak1 < 1, maka kAmk1 → 0 jika m →∼


27

dan karena itu Am mendekati matriks nol jika m →∼ karena : (I − A)(1 + A + · · · + Am ) = I − Am+1 menyebabkan: I − A + · · · + Am = (I − A)−1 − (I − A)−1Am+1 Pada m →∼, maka (I − A)−1 (I − A)−1 Am+1 → (I − A)−1 dan karena deret 1 + A + · · · + Am konvergen ke (I − A)−1 pada m →∼. Dengan syarat (i) I + A + · · · + Am adalah tak negatif untuk masing-masing m, dan dengan demikian maka (I − A)−1 pastilah tak negatif. Karena d tak negatif, maka penyelesaian x menjadi tak negatif. Oleh karena itu dapat dilihat bahwa syarat-syarat (i) dan (ii) menjadi sistem (3.1) akan mempunyai penyelesaian tak negatif x yang tunggal. Sebagaimana yang mungkin sudah di duga, terdapat suatu versi tertutup dari model masukan dan keluaran. Pada versi tertutup, diasumsikan bahwa masing-masing industri harus memproduksi keluaran yang cukup untuk mencukupi kebutuhan masukan industri lain atau dirinya sendiri. Sektor terbuka diabaikan. Jadi, sebagai pengganti dari sistem (3.1) diperoleh: (I − A)x = 0 dan membutuhkan penyelesaian positif untuk x. Keberadaan dari x yang demikian pada kasus ini adalah suatu hasil yang lebih mendalam dibandingkan dengan yang ada pada versi terbuka dan memerlukan beberapa teorema yang lebih tinggi.


28 Teorema Perron jika A adalah matriks positif berorde n×n, maka A memiliki nilai eigen real positif r dengan sifat-sifat sebagai berikut:

a. r adalah akar sederhana dari persamaan karakteristik b. r memiliki vektor eigen positif x c. Jika λ adalah sembarang nilai eigen lainnya dari A, maka |λ| < r

Teorema Perron dapat dianggap sebagai suatu khusus dari teorema yang lebih umum menurut Frobenius. Teorema Frobenius berlaku pada matriks-matriks tak negatif yang tak tereduksi (irreducible). Definisi matriks tak negatif A dikatakan sebagai matriks yang tereduksi (reducible) jika terdapat suatu partisi dari himpunan indeks {1, 2, . . . , n} ke dalam himpunan-himpunan tak kosong yang saling lepas (disjoint) I1 dan I2 sehingga αij = 0 apabila i ∈ I1 dan j ∈ I2. Jika tidak demikian. A disebut sebagai matriks yang tak tereduksi (irreducible). Contoh 1. Misalkan A adalah  x  x  x  x x

matriks berbentuk  x 0 0 x x 0 0 x  x x x x   x x x x x 0 0 x

Misalkan I1 = {1, 2, 5} dan I2 = {3, 4}. Maka I1 ∪ I2 = {1, 2, 3, 4, 5} dan αij = 0 kalau i ∈ I1 dan j ∈ I2 . Oleh karena itu A tereduksi. Perhatikanlah bahwa jika P adalah matriks permutasi yang dibentuk dengan mempertukarkan


29 baris ketiga dan kelima dari matriks identitas I,  x x 0 0  x x 0 0 PA =   x x 0 0 x x x x x x x x

maka  x x  x   x x

Secara umum dapat dilihat bahwa suatu matriks A berorde n × n tereduksi jika dan hanya jika terdapat sebuah matriks permutasi P sedemikian rupa sehingga P AP T adalah matriks berbentuk:

B X

O C

di mana B dan C adalah matriks-matriks bujur sangkar : Teorema Frobenius jika A adalah matriks tak negatif yang tak tereduksi (irreducible), maka A memiliki nilai eigen real positif r dengan sifat-sifat sebagai berikut:

1. r memiliki vektor eigen positif x 2. Jika λ adalah sembarang nilai eigen lain dari A, maka |λ| ≤ r, nilai-nilai eigen dari modulus r semuanya adalah akar sederhana dari persamaan karakteristik.


30 Sebenarnya jika terdapat m nilai-nilai eigen dan modulus r, maka nilai-nilai eigen tersebut akan berbentuk

λk = r exp

2kπi m

k = 1, 0, 1, . . . , m − 1

3.2 Aplikasi 2 : Model Tertutup Pada model masukan-masukan Leontief tertutup, diasumsikan tidak ada kebutuhan pada sektor terbuka dan dapat diharapkan mendapatkan keluarankeluaran untuk memenuhi kebutuhan semua industri. Jadi, dengan mendefinisikan semua xi dan semua αij sebagaimana dalam model terbuka. xi = αi1 x1 + αi2x2 + · · · + ain xn untuk i = 1, . . . , n. Sistem yang dihasilkan dapat dituliskan dalam bentuk (A − I)x = 0

(3.4)

Seperti sebelumnya. (i) αij ≥ 0 Oleh karena tidak ada sektor terbuka, jumlah keluaran dari industri ke-j seharusnya sama dengan masukan total untuk industri tersebut. Jadi xj =

n X

αij xj

i=1

dan karenanya memiliki syarat kedua (ii)

n P

αij = 1 j = 1, . . . , n

i=1

Syarat (ii) mengakibatkan A − 1 singular karena jumlah vektor barisnya adalah 0. Oleh karena itu nilai 1 adalah nilai eigen dari A dan karena kAk1,


31 maka semua nilai eigen dari A memiliki modulus kurang dari atau sama dengan 1. Diasumsikan bahwa cukup banyak koefisien A yang tak nol sehingga A menjadi tak tereduksi (irreducible). Kemudian berdasarkan Teorema Frobenius untuk λ = 1 memiliki vektor eigen positif x. Jadi sembarang kelipatan positif dari x akan merupakan penyelesaian positif.


BAB 4 PROGRAM NON LINIER

Didalam bab ini ditemukan prosedur optimasi tertentu untuk memaksimisasi atau meminimisasi suatu fungsi dari n variabel. Kejelekannya seperti yang telah dicatat sebelumnya prosedur ini tidak dapat digunakan untuk menyelesaikan soal yang melebihi variabelnya sangat banyak. Disini akan disajikan beberapa metode fisibel secara komputasi untuk menyelesaikan tipe-tipe tertentu dari problema pemograman non linier. Suatu problema pemograman non liner adalah suatu problema dimana harus memaksimumkan atau meminimumkan suatu fungsi f (¯ x), kendala suatu set konstrain persamaan atau ketidaksamaan. Dimana f (¯ x) atau paling sedikit satu dari fungsi yang muncul dalam set konstrain atau keduanya adalah suatu fungsi non linier. Problema pemograman non linier secara umum dapat dinyatakan sebagai berikut: Maximize Z = f(¯ x) Subject to gi (¯ x){≤, =, ≥}bi

(4.1) i = 1, 2, . . . , m

(4.2)

Dimana satu dari tiga relasi {≤, =, ≥} adalah dirancang terhadap masingmasing dari m konstrain (4.2). Fungsi f(¯ x) dalam persamaan (4.1) disebut fungsi objektif. Sehubungan dengan itu konstrain non negatifitas (xj ≥ 0) pada beberapa atau semua dari variabel dinyatakan secara terpisah atau dapat dianggap termasuk dalam konstrain (4.2). Tidak ada diketahui metoda dari penentuan maximum global terhadap problema pemograman non linier secara umum. Bahkan jika fungsi objektif dan konstrain sesuai dengan sifat-sifat tertentu maximum global kadang-kadang dapat diterima. Sebagai contoh membuktikan bahwa 32 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

33 maximum global dari suatu fungsi konfek terhadap suatu set konfek dibatasi dan pada suatu titik extrim dari set konfek. Disini akan diturunkan ”Kondisi Kuhn-Tucker” suatu set dari kondisi yang diperlukan untuk memaximumkan suatu problema non linier. Kondisi ini didalam hal tertentu juga menghasilkan maksimum global. Kondisi Kuhn-Tucker sesungguhnya sangat berguna didalam menurunkan metode untuk menyelesaikan beberapa jenis problema non linier. Dapat dilihat bagaimana penggunaan kondisi Kuhn-Tucker hingga mengembangkan suatu algoritma dengan menggunakan metode simplek untuk menyelesaikan program kuadratik. Didalam suatu problema program kuadrat fungsi objektif adalah kuadratik dan konstrainnya adalah linier.

4.1 Set Konvek Konstrain Untuk mengetahui ”Kuhn-Tucker Kondisi” pertama ditentukan sifat-sifat x) harus beda dalam bentuknya sehingga set konstrain (4.2) adalah dari fungsi gi (¯ suatu set konvek.

x/g(¯ x) ≤ Teorema 1 Jika g(¯ x) adalah suatu fungsi konvek, kemudian set C1 = {¯ b} adalah konvek set, jika suatu fungsi adalah konkav.

Kemudian set C2 =

{¯ x/h(¯ x) ≤ b} adalah konvek set.

ˆ¯ = λ¯ ¯2 ∈ C, titik x x1 + (1 − Bukti : Perlu diperlihatkan bahwa setiap 2 titik x ¯1 , x ˆ x2 adalah di C1, karena g(x) adalah konvek maka akan menuruti bahwa: λ)¯ ˆ¯) ≤ λg(¯ g(x x1 ) + (1 − λ)g(¯ x2 )


(4.3)

34 x1) ≤ b dan g(¯ x2 ) ≤ b substitusi ketidaksamaan ke dalam Karena : x1 , x2 ∈ C1 , g(¯ (4.3) sehingga dihasilkan: ˆ¯1) ≤ λb + (1 − λ)b = b g(x

(4.4)

ˆ¯) ≤ b dan juga x ˆ¯ ∈ C1 Jadi g(x Terbukti bahwa C2 adalah konvek set adalah analog. Dua contoh dari C1 dan C2 diperlihatkan dalam gambar (4.1a). Daerah bayangan C1 dalam gambar (4.1a) menyatakan set dari titik-titik yang sesuai dengan fungsi konvek. Dalam gambar (4.1b) daerah bayangan C2 mewakili set dari titik yang sesuai g(x1, x2 ) = x21 + x2 ≤ 4. h(x1 , x2) = x2 − 2x21 ≥ 1 h(x1 , x2) adalah fungsi konvek dan C2 adalah suatu konvek set. Irisan dari C1 dan C2 , convek set C1 diperlihatkan dalam gambar (4.1c).

Gambar 4.1 : a. Kurva Konvek Terbuka Kebawah; b. Kurva Konvek Terbuka Keatas; c. Irisan Kurva Konvek

Penggabungan dari hasil teorema (4.1) dengan kenyataan bahwa irisan dari konvek set adalah suatu konvek set, dilihat bahwa set konstrain (4.2) adalah


35 x) adalah sumerupakan suatu set konvek jika tanda ”≤” digunakan bilamana gi (¯ x) adalah suatu fungsi atu fungsi konvek dari tanda ”≥” digunakan bilamana gi (¯ konkav. Tidak dapat disebutkan sesuatu mengenai hal dimana tanda yang sama akan menjelaskan beberapa konstrain dalam (4.2). Pada gambar (4.1.a) dilihat bahwa jika konstrain x21 + x22 = 4 dan x2 − 2x21 = 1, kemudian set yang dihasilkan merupakan batas dari C1 dan C2 kecenderungan set ini adalah konvek. Secara umum kesamaan konstrain : g(¯ x) = b, akan menghasilkan suatu konvekset. Jika g(¯ x) adalah linier, yakni g(¯ x) = a ¯x ¯ = b (suatu hyperplane). Kemudian uraikan suatu set dari kondisi yang sesuai untuk set konstrain (4.2) yang konvek. Penambahan konstrain non negatif tidak mempengaruhi soal berikutnya dan kondisi untuk suatu set konstrain konvek tidak diperlukan. Hal ini untuk irisan dari beberapa set non konvek untuk menghasilkan suatu set konvek. Perhatikan dua konstrain: x2 − x31 + 2x21 + x1 ≤ 2

(4.5)

x2 − x1 ≥ 1

(4.6)

Daerah yang diarsir dalam gambar (4.1.a) menunjukkan set dari titik yang sesuai (4.5). Jelas ini tidak suatu set konvek, bahkan set dari titik-titik yang berada dalam irisan (4.5) dan (4.6) diperlihatkan dalam gambar (4.1.b) adalah suatu set konvek.


36

Gambar 4.2 : a. Kurva tidak set konvek; b. Kurva set konvek

4.2 Kondisi Kuhn-Tucker Dalam mengembangkan algoritma untuk problem non linier maka berguna untuk memiliki beberapa informasi dengan karakteristik dari optimasi. Suatu set dari relasi akan diperoleh dimana suatu penyelesaian optimum harus sesuai untuk suatu problem optimisasi konstrain dimana konstrain semua sama. Bahkan juga diperlukan untuk memperhatikan hal-hal dari konstrain yang juga tidak sama. Dalam hal-hal tertentu perlu diperhatikan kondisi optimisasi dari konstrain non negatif terhadap variabel. Perhatikan problem non linier berikut: Maximize z = f (¯ x) ≡ f (x1 , x2, . . . , xn )

(4.7)

Subject to gi (x) ≤ bi , i = 1, 2,

(4.8)

g(x) ≥ bi , i = p + 1, . . . , m xi ≥ 0, j = 1, 2, . . . , n

(4.9) (4.10)

Selanjutnya anggaplah untuk penyederhanaan bahwa fungsi-fungsi di dalam


37 konstrain (4.8) adalah konvek dan fungsi dalam (4.9) adalah konvek sehingga dari penyelesaian yang fisibel adalah satu set konvek. Disimpulkan bahwa sex), i = 1, 2, . . . , m tertentu. mua turunan partial pertama dari fungsi f (¯ x) dan gi (¯ Sekarang diperhatikan fungsi Lagrangian berikut: F (¯ x, λ, µ ¯) = f (¯ x) +

n X

ti {bi − λi (¯ x)} +

i=1

m X

µi (bi − gi (¯ x)

(4.11)

i=p+1

Anggap x ¯0 adalah suatu relatif maximum terhadap problem non linier yang diuraikan pada (4.7) disambung pada persamaan (4.10). Konstrain dari bentuk x0) = bi dan tidak ak(4.8) atau (4.9) dikatakan aktif pada x ¯0. Contohnya gi (¯ tif pada x0 jika terjadi ketidaksamaan. Sekarang anggap bahwa meminimumkan ¯ µ f (¯ x, λ, µ ¯ ) terhadap batas atas atau konvergen batas bawah pada variabel x ¯, λ, ¯. Ingin menentukan batas atas dan batas bawah memperlihatkan bahwa maximum ¯0, µ ¯0 ) diperoleh, juga akan menghasilkan maximum x0 terhadap problem (¯ x0 , λ program non linier. Sesungguhnya harus memerlukan x ≥ ¯0

(4.12)

x) ≥ 0 bi = gi (¯

(4.13)

Juga untuk konstrain (4.8)

Jadi di dalam memaximumkan f (¯ x, λ, µ ¯ ) memerlukan masing-masing istilah dan jumlah p X

xi [bi − gi (¯ x)] adalah non negatif dan ini terjadi (4.14)

i=1

Jika λi ≥ 0, i = 1, 2, . . . , p Dengan cara yang sama juga diinginkan: m X µi [hi − gi (¯ x)] adalah non negatif i=p+1

Bahkan untuk i = p + 1, . . . , m bi − gi (xi ) ≤ 0


(4.15)

38 oleh karena itu jika memerlukan: µi ≤ 0; i = p + 1, . . . , m

(4.16)

kemudian masing-masing µi [bi − gi (¯ x)] akan nonnegatif. ¯ µ Jadi dalam memaximumkan subjek f (¯ x, λ, ¯) terhadap konstrain (4.12), (4.14) dan (4.16) sambil mengabaikan konstrain (4.8) dan (4.9) terhadap problem non linier dipilih bahwa jika suatu dari konstrain terakhir ini melanggar ¯ µ nilai dari f (¯ x, λ, ¯ ) akan lebih kecil dari pada itu jika konstrain sesuai. ¯ µ Jadi suatu kondisi yang diperlukan untuk memaksimumkan f (¯ x, λ, ¯ ) sub¯ ≥ ¯0, ≤ ¯0 adalah merupakan masing-masing konstrain (4.8) dan jek to x ¯ ≥ ¯0; λ (4.9) yang sesuai. Sekarang terlihat bahwa suatu kondisi yang diperlukan untuk perluasan dari suatu maximum terhadap fungsi yang tidak mempunyai kendala ¯ µ f(¯ x, λ, ¯ ) adalah: ∂F = 0; j = 1, 2, . . . , n ∂xj ∂F = 0; j = 1, 2, . . . , p ∂λj ∂F = 0; i = p + 1, 2, . . . , m ∂µi

(4.17) (4.18) (4.19)

¯ µ Bahkan kondisi ini harus dimodifikasi bilamana, f (¯ x, λ, ¯ ) adalah maximum, sub¯ ≥ ¯0, ≤ ¯0. jek to x ¯ ≥ ¯0; λ

Modifikasinya adalah sebagai berikut : anggap

¯0, µ ¯ µ ¯ ≥ o¯, ≤ o¯, ¯0 ) adalah suatu titik maximum dari f (¯ x, λ, ¯ ) subjek to x¯ ≥ o¯; λ (¯ x0 , λ ¯ 0 = [λ ¯ 01 , λ ¯ 02, . . . , λ ¯ 0n ] dan µ ¯ = [µ0,p+1, . . . , µ0m ]. dimana x ¯0 = [x01, x02, . . . , x0n ), λ


39 Kemudian kondisi berikut haruslah sesuai Jika : xoj > 0 Jika : λoj = 0 Jika : µoi > 0

∂F =0 ∂xj ∂F =0 ∂xj ∂F =0 ∂λj

(4.20) (4.21) (4.22)

Persamaan (4.20) ; (4.21) dan (4.22) berikut apabila xoi ; λoi dan µoi tidak nol. Kemudian konstrain (xoi ≥ 0; λoi ≥ 0; µoi ≤ 0) tidak mempunyai evek memaxi¯ µ mumkan F (¯ x, λ, ¯ ). Bahkan jika suatu dari variabel ini nol, kemudian penyelesaian optimum terjadi pada batas-batas sebagai contoh xoi = 0, kemudian ¯0, µ harus berada pada [¯ x0, λ ¯0 ] dalam hal ini µoi = 0

∂F ∂µj

∂F ∂xj

≥ 0 harus berada pada

¯0, µ [¯ x0 , λ ¯0 ]. x); i = Sekarang diperlihatkan persamaan (4.20) ke (4.22) dalam F (¯ x) dan gi (¯ 1, 2, . . . , m. Dari persamaan (4.21) dilihat λoj adalah maximum. Untuk problem ¯0, µ ¯0 . non linier (4.7) hingga (4.10) hanya jika terdapat vektor λ Apabila : x ¯0 ≥ 0 p

X ∂F ∂F ∂gi ∂gi − = λoi − − Σµ = 0 pada x ¯=x ¯o ∂xi ∂xj ∂xj ∂xj i=1

(4.23)

Apabila : x ¯oi ≥ 0 p

X ∂gi ∂F ∂F ∂gi − = λoi − − Σµoi ≤ 0 pada x ¯=x ¯o ∂xj ∂xj ∂xj ∂xj i=1

(4.24)

¯ oi > 0 Apabila : λ ∂F ≡ bi − gi(¯ x) = 0 pada x ¯=x ¯o ∂λi

(4.25)

∂F ≡ bi − gi(x) ≤ 0 pada x ¯=x ¯o ∂λi

(4.26)

¯ oi = 0 Apabila : λ


40 Apabila : µ ¯ oi < 0 ∂F ≡ bi − gi(¯ x) ≤ 0 pada x ¯=x ¯o ∂µi

(4.27)

∂F ≡ bi − gi ≥ 0 pada x ¯=x ¯o ∂µi

(4.28)

Apabila : µ ¯ oi = 0

Kondisi ini disebut kondisi Kuhn-Tucker, salah satu hubungan (4.24) dan (4.25) harus berada untuk masing-masing i, i = 1, 2, . . . , p; sehingga relasi (4.26) dan (4.27) harus berada untuk masing-masing i, i = p + 1, . . . , m. Keempat relasi ini memastikan bahwa x ¯o akan sesuai dengan konstrain (4.8) dan (4.9) membentuk suatu set konvek.

4.3 Metode Gradient Tereduksi Prosedur ini adalah suatu teknik yang disebut gradient tereduksi atau metode penggeneralisasian gradient yang didasarkan pada metode perluasan untuk batasan linier terhadap penggunaan pada batasan non linier. Metode ini mengatur variabelvariabel sehingga hambatan aktif kontinu dan sesuai bilamana prosedur-prosedur bergerak dari suatu titik ke titik yang lain. Ide untuk algoritma ini digunakan oleh Wilde dan Beighler dengan menggunakan nama constrain derivatives, oleh Wolfe menggunakan nama metode reduced gradien dan diperluas oleh Abadie dan Carpenter menggunakan nama generalisasi reduced gradient. Menurut Avriel, jika model ekonomi dan konstrain adalah linier, prosedur ini adalah metode ekonomi dan konstrain adalah linier, prosedur ini adalah metode linier program simpleks dan jika tidak terdapat konstrain disebut gradien search. Pengembangan dari prosedur dimulai dengan problem optimisasi non linier yang ditulis dengan kon-


41 strain yang sama. Slack yang diperoleh dan variabel surflus telah ditambahkan xs atau x2s sehingga terhadap setiap konstrain yang tidak sama problemnya adalah: obtimasi : y(x) (4.29) Subject to

fi (x) = 0 untuk i = 1, 2, . . . , m

Disamping itu ada m konstrain dan n variabel independen dengan n > m. Juga walaupun tidak ditulis secara spesifik variabel dapat mempunyai batas atas dan batas bawah dan prosedur seperti yang diuraikan disini akan memastikan batas atas dan batas bawah dan prosedur seperti yang diuraikan disini akan memastikan bahwa variabel positip atau nol. Pandangan dari penggeneralisasian gradient tereduksi adalah untuk mengubah problema konstrain menjadi suatu problem unconstraint dengan menggunakan substitusi langsung. Jika substitusi adalah mungkin maka hal ini akan mengurangi jika variabel independent menjadi (n − m) dan mengeliminasi persamaan konstrain. Bagaimanapun, konstrain non linier hal ini tidak fisibel untuk menyelesaikan konstrain m, dan variabel independen dalam istilah sisa (n−m) variabel dan kemudian disubstitusi terhadap persamaan ini menjadi model ekonomi. Karenanya prosedur dari fariasi konstrain dan multipel Lagrange di dalam teori klasik dari maximum dan minimum adalah diperlukan. Disini model ekonomi dan persamaan konstrain di ekspansikan dalam deret Taylor dan hanya istilah order pertama yang digunakan. Kemudian melalui persamaan linier ini persamaan konstrain dapat digunakan untuk menurunkan jumlah variabel independen. Hal ini akan digunakan terhadap Jacobian determinan dari metode variasi konstrain dan definisi dari multipel Lagrange. Pengembangan dari penggeneralisasian metode gradien tereduksi akan mengikuti variasi konstrain. Dalam hal dua variabel independen dan satu persamaan konstrain akan digunakan konsep demonstrate. Dan


42 kemudian hal-hal yang umum akan diuraikan. Perhatikan masalah dibawah ini Obtimasi : y(x1, x2) (4.30) Subject to : f (x1 , x2) = 0 Ekspansikan di dalam deret Taylor, titik fisibel xk (x1k , x2k ) memberikan: ∂y (xk )(x1 − x1k ) + ∂x1 ∂y (xk )(x1 − x1k ) + 0 = y(xk ) + ∂x1

y(x) = y(xk ) +

∂y (xk )(x2 − x2k ) ∂x2 ∂y (xk )(x2 − x2k ) ∂x2

(4.31) (4.32)

Substitusi persamaan (4.29) ke persamaan (4.30) untuk mengeliminasi x2 yang diberikan, setelah penyusunan: −1 ∂f ∂y (xk ) (xk ) f (xk ) y(x) =y(xk) − ∂x2 ∂x2 −1 ∂f ∂y ∂f ∂y ∂f (xk ) (xk ) (xk ) − (xk ) (xk ) (x1 − x1k ) + ∂x2 ∂x1 ∂x2 ∂x2 ∂x1 (4.33) Dalam persamaan (4.33) kedua istilah diketahui konstrain dievaluasi pada titik xk dan koefisien dari (x1 − x1k ) juga sebagai konstanta dan memberikan x1 arah terhadap suatu gradien. Jadi untuk menghitung suatu titik stationeri persamaan dan hasilnya adalah seperti variasi konstrain yang dituliskan dalam persamaan (4.33) dari persamaan ini diselesaikan secara bersama untuk titik stationeri. Bahkan dapat dipandang sebagai pemberian arah terhadap gerakan dari xk untuk mendapatkan nilai yang diperbaiki dari model ekonomi dan sesuai terhadap persamaan (4.29). Penggeneralisasian metode generalisasi tereduksi menggunakan pendekatan yang sama seperti diuraikan untuk dua variabel independen. Untuk meneliti arah


43 yang diperlukan untuk moedel ekonomi dan juga untuk mempergunakan persamaan konstrain, hal ini akan memberikan suatu ekspansi untuk gradien yang tereduksi dari persamaan (4.29). Untuk menggambarkan metode ini variabel independen menjadi basis dan non basis. Ada m variabel basis xb dan (n − m) variabel non basis xnb . Dalam teori m persamaan konstrain dapat diselesaikan untuk m variabel basis dan (n−m) variabel non basis. Sebagai contoh persamaan (4.29) memperlihatkan penyelesaian: Fi (x) = fi (xb , xnb ) = 0 untuk i = 1, 2, . . . , m

(4.34)

Memperlihatkan penyelesaian xb didalam syarat-syarat xnb dari persamaan (4.34) akan memberikan: Xi,b = fi (xnb ) untuk i = 1, 2, . . . , m

(4.35)

Nama variabel basik dan non basik adalah dari program linier. Dalam program linier variabel basik semuanya persamaan dan variabel non basik semuanya nol. Bahkan dalam program non linier, variabel-variabel non basik digunakan untuk menghitung nilai dari variabel basik dan dimanipulasi untuk mendapatkan optimum dari model ekonomi. Model ekonomi dapat dipandang sebagai suatu fungsi, hanya variabel non basik sehingga hanya persamaan konstrain (4.35) untuk mengeliminasi variabel basik. Sebagai contoh: y(x) = y(xb , xnb ) = y[∼ fi (xnb ), xnb ] = y(xnb )

(4.36)

Bila diekspansikan persamaan diatas ke dalam deret Taylor mengenai xk


44 dan hanya melibatkan order pertama akan diperoleh: m n n X X X ∂y ∂y ∂y (xk )dxj,b + (xk )dxj,nb = (xk )dxj.nb ∂xj,b ∂xj,nb ∂xj,nb j=1 j=m+1 j=m+1

(4.37)

Didalam persamaan (4.37) notasi matrik dapat ditulis: ∇T Y (xk )dxnb = ∇T yb (xk )dxb + ∇T Ynb (xk )dxnb

(4.38)

Persamaan ini dapat dibandingkan dengan persamaan (4.31) ekspansi Taylor series dan persamaan konstrain (4.34) akan menghasilkan suatu persamaan yang dapat disubstitusi ke dalam persamaan (4.38). Untuk mengeliminasi variabel basis m n X X ∂fi ∂fi (xk )dxjib + (xk )dxj,nb = 0 untuk i = 1, 2, . . . , m ∂xj ∂xj j=1 j=m+1

     

(4.39)

Atau di dalam persamaan (4.39) bentuk matrik adalah:    δf (x ) δf1 (xk ) δf1 (xk ) δf1 (xk ) 1 k     . . . . δxn δx1 δxm  dxib  dxm+1  δxm+1 . . . .  .    .     . . . . +  =0    . . . . . .  dx   dxn mb δfm (xk ) δfm (xk ) δfm (xk ) m (xk ) . . δfδx . . ∂x1 ∂x δx m m m+1 (4.40) Persamaan berikut mendefenisikan Bb sebagai matrik dari turunan parsial

pertama dari fi yang digabung dengan variabel basis dan Bnb sebagai matrik yang bergabung dengan variabel non basis. Bb dxb + Bnb dxnb = 0

(4.41)

Ini adalah suatu titik yang sesuai dengan persamaan (4.37) yang dapat digunakan untuk mengeliminasi: Dxb = −Bb−1 Bnb dxnb


(4.42)

45 Substitusi persamaan (4.42) ke persamaan (4.40) akan memberikan: T ∇T Y (xk ) dxnb = −∇T yb (xk )Bx−1 b Bnb dxnb + ∇ Ynb (xk )dxnb

(4.43)

Eliminasi dxnb dari persamaan (4.43) persamaan untuk metode tereduksi Y (Xk ) diperoleh: ∇T Y (xk ) = ∇T ynb (xk ) − ∇T Yb (xk )Bb−1Bnb

(4.44)

Dengan mengetahui nilai dari turunan partial pertama dari model ekonomi dan persamaan konstrain pada suatu titik fisibel gradien tereduksi dapat dihitung melalui persamaan (4.44). Hal ini akan mencocokkan model ekonomi persamaan konstrain. Penggeneralisasian metode gradient tereduksi menggunakan gradient tereduksi untuk memastikan nilai yang lebih baik dari model ekonomi dengan cara yang sama dengan pemahaman gradient untuk sistem yang telah digunakan. Contoh: Xnb = xk,nb + α∇Y (xk )

(4.45)

Dimana parameter dari garis sepanjang gradient tereduksi. Garis yang dipilih untuk digunakan menentukan optimum dari Y (xnb ) sepanjang garis gradient tereduksi dari xk . Didalam mengambil langkah-langkah percobaan bilamana α adalah bervariasi sepanjang penggeneralisasian garis gradient tereduksi matrik Bb dan Bnb harus dievaluasi dengan gradient ∇Yb (xb ) dan ∇Ynb (xk ). Hal ini memerlukan pengetahuan xnb dan xb pada setiap langkah. Nilai xnb diperoleh dari persamaan (4.45). Bahkan persamaan (4.44) harus diselesaikan dan seterusnya, ini harus dilakukan secara numerik dengan metode Newton-Raphson. Seperti yang dijelaskan oleh Reklaitis. Kebanyakan dari usaha komputasi dapat terlihat


46 dalam penggunaan metode Newton-Raphson untuk mengevaluasi nilai dari variabel basik juga variabel non basik dapat dihitung dari persamaan (4.46). Algoritma Newton-Raphson untuk prosedur pemberian nama dibicarakan pada persamaan berikut ini: Xi+1,b = xi,b − Bb−1 f (xi,b , xnb )

(4.46)

dimana nilai dari akar persamaan konstrain (4.44) akan diselesaikan untuk xb , dan digunakan untuk menghitung xnb dari persamaan (4.47). Jadi turunan yang dihitung untuk penggenerelisasian gradient tereduksi matrik Bb dapat digunakan prosedur penyelesaian akar dalam algoritma Newton-Raphson. Contoh berikut mengilustrasikan penggenerelisasian algoritma gradient tereduksi. Ini merupakan suatu modifikasi dan perluasan dari suatu contoh yang diberikan oleh Reklaitis.


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Dari hasil penelitian ini dapat disimpulkan bahwa Faktorisasi Matriks Nonnegatif dapat diformulasikan untuk meminimumkan kesalahan dengan batas kendala bilangan non negatif, sehingga V ≈ W H.

5.2 Saran Perlu dikaji beberapa metode untuk memahami faktorisasi matrik non negatif, sehingga dengan demikian dapat digunakan dalam program linier dan program non linier.

47 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

DAFTAR PUSTAKA

Bertsekas, D., 1999, Nonlinear Programming, Athena Scientific, Belmont, MA. Catral, M. L. Han; Neumann, M. and Plemmons, R., 2004, On Reduced Rank Non-Negative Matrix Factorization for Symmetric Non-Negative Matrices, Linear Algebra Appl., Vol. 393(1); 107-126. Chu, M. F. Diele; Plemmons, R. and Ragni S., 2004, Optimality Computation, and Interpretation of Non-Negative Matrix Factorization, Unpublished Preprint. Cichocki, A. R. Zdunek, NMFLAB MATLAB Toolbox for Non-negative Matrix Factorization. URL: www.bsp.brain.riken.jp/ICALAB/nmflab.html/ Donoho, D. V. Stodden, When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts, Adv. Neural Inf. Process. Syst., Vol.17. Golub, G. C. V. Loan, 1996, Matrix Computation, third ed., The Johns Hopkins University Press, Baltimore. Hoyer, P., 2004, Non-Negative Sparse Coding, in: Proceedings of the IEEE Workshop on Neural Network for Signal Processing, Martigny, Switzerland, 557565. Hoyer, P., 2004, Non-Negative Matrix Factorization with Sparsenessconstraints, J. Mach. Learn. Res., Vol. 5; 1457-1469. Lee, D. D. H. S. Seung, 1999, Learning the Parts of Objects by Non-Negative Matrix Factorization, Nature, vol. 401; 788-791. Lee, D. D. H. S. Seung, 2001, Algorithms for Non-Negative Matrix Factorization, Adv. Neural Inf. Process. Syst., Vol. 13: 556-562 Paatero, P. U. Tapper, 1994, Positive Matrix Factorization: A Non-Negative Factor Model with Optimal Utilization of Error Estimates of Data Value, Environmetrics, Vol. 5;111-126. Wild, S., 2003, Seeding Non-Negative Matrix Factorization with the Spherical KMeans Clustering, Master Thesis, University of Colorado, Department of Applied Mathematics. Zhang, D. S. Chen and Zhou, Z. H., 2005, Two-dimensional Non-Negative Matrix Factorization for Face Representation and Recognition, in: Proceedings of the ICCV’05 Workshop on Analysis and Modeling of Faces and Gestures (AMFG’05), Lecture Notes in Computer Science, Springer, Berlin, Vol. 3723; 350-363.

48 Pasukat Sembiring: Faktorisasi Matrik Non Negatif Skala Besar, 2008. USU e-Repository © 2008

FAKTORISASI MATRIK NON NEGATIF SKALA BESAR

Recommend Documents