Konvergensi Global Metode Spectral Conjugate Descent yang Baru Menggunakan Pencarian Garis Armijo yang Termodifikasi

42

ISSN 2302-7290 Vol. 2 No. 2, April 2014

Konvergensi Global Metode Spectral Conjugate Descent yang Baru Menggunakan Pencarian Garis Armijo yang Termodifikasi Global Convergence of the New Spectral Conjugate Descent Method with the Modified Armijo-type Line Search Dahliatul Hasanah Fakultas MIPA Universitas Negeri Malang Jalan Semarang 5, Malang 65145

abstrak

Metode nonlinear spectral conjugate descent yang baru merupakan gabungan dari metode conjugate descent dan metode spectral conjugate gradient. Metode ini menghasilkan yang berorientasi menurun (descent direction). Dengan menggunakan pencarian garis strong Wolfe Rule, metode ini telah dibuktikan konvergen global. Tulisan ini menganalisis tentang konvergensi global metode tersebut dengan menggunakan pencarian garis Armijo yang termodifikasi. Analisis ini menunjukkan bahwa menggunakan pencarian garis Armijo yang termodifikasi, metode nonlinear spectral conjugate descent yang baru konvergen global. Kata kunci: metode nonlinear spectral conjugate descent, konvergen global, pencarian garis Armijo yang termodifikasi abstract

The new nonlinear spectral conjugate descent method is constructed by combining the spectral conjugate gradient method and conjugate descent method. This method generates descent direction dk. Under the strong Wolfe rule this method is globally convergent. This paper analyzed global convergence of this method using the modified Armijo line search. The result shows that the new nonlinear spectral conjugate descent method is globally convergent under the modified Armijo line search. Key words: nonlinear spectral conjugate descent method, global convergence, modified Armijo line search

pendahuluan

Beberapa tahun terakhir banyak bermunculan metode-metode baru dan yang merupakan modifikasi dari metode-metode lama untuk menyelesaikan masalah optimasi tanpa kendala. Hal ini dikarenakan masalah optimasi tanpa kendala banyak digunakan di berbagai bidang seperti transportasi, eksplorasi bahan bakar minyak, aerospace, dan sebagainya (Liu et al., 2012). Semakin besar skala atau variabel yang terlibat dalam masalah optimasi tanpa kendala, maka semakin besar pula kebutuhan akan adanya suatu metode yang mampu menyelesaikan masalah optimasi tanpa kendala dalam skala besar.

Alamat Korespondensi: e-mail: [email protected]

Masalah optimasi nonlinier tanpa kendala merupakan pencarian nilai minimum dari fungsi bernilai f(x) yaitu min f(x), x ∈ Rn. ........................................................ (1.1) f adalah fungsi nonlinier yang kontinu dan terdiferensialkan dengan gradien g(x) = ∇f(x). Masalah tersebut dapat diselesaikan secara numerik, yaitu dengan cara iteratif. Iterasi yang dijalankan dinotasikan dengan xk, k=1,2,.... Setiap iterasi diberikan oleh xk+1=xk + akdk............................................................. (1.2)

dalam mencari nilai lokal walaupun membutuhkan perhitungan yang lebih banyak et.alminimum (2008) yang menunjukkan bahwa pencarian garis Armijo yang termodifikasi lebih efisien dalam dalammencari mencarinilai nilaiminimum minimumlokal lokalwalaupun walaupunmembutuhkan membutuhkanperhitungan perhitunganyang yanglebih lebihbanyak banyak dalam garis mencari nilai minimum lokal walaupun membutuhkan perhitungan yang lebih banyak dibandingkan pencarian lainnya. METODE PENELITIAN dibandingkan pencarian garis lainnya. dibandingkan pencarian garis lainnya. dibandingkan pencarian garis lainnya.

Kekonvergenan metode spectral conjugate descent dengan menggunakan pencarian

Hasanah: Konvergensi Global Metode Spectral Conjugate Descent

43 METODE PENELITIAN Armijo yang termodifikasi akan dianalisis dengan menggunakan pendekatan secara numeri METODE PENELITIAN METODE PENELITIAN METODE PENELITIAN Kekonvergenan metodeConjugate spectral conjugate descent dengan menggunakan pencarian garis Metode Conjugate Gradient menggunakan Metode Gradient ak adalah panjang langkah (step length) yang ditentukan Kekonvergenan metode spectral conjugate dengan menggunakan pencarian garis Kekonvergenan metode spectral conjugate descent dengan menggunakan pencarian garis Kekonvergenan metode spectraldescent conjugate descent dengan pencarian garis Pada umumnya metode conjugate gradient oleh suatu pencarian garis, dk adalah arah pencarian dan dengan menggunakan pendekatan secara numeric. Armijo yang termodifikasi akan dianalisis Pada umumnya metode conjugate gradient dideskripsikan olehnumeric. iterasi berikut ini: Armijo yangakan termodifikasi akan dianalisis dengan menggunakan pendekatan secara dideskripsikan oleh iterasi berikut ini: Armijo yang termodifikasi dianalisis dengan menggunakan pendekatan secara numeric. Armijo yang termodifikasi akan dianalisis dengan menggunakan pendekatan secara numeric. x1 adalah titik awal. Metode Conjugate Gradient Salah satu metode yang terkenal Metode Conjugateuntuk Gradient Metode Conjugate Gradient Metode Conjugate Gradient menyelesaikan masalah ini adalah metode conjugate umumnya metode conjugate gradient dideskripsikan oleh iterasioleh berikut Padamemori umumnya metode conjugate gradient dideskripsikan iterasiini: berikut ini: gradient. MetodePada iniPada membutuhkan yang adalah panjang langkah (steplength) yang ditentukan oleh suatu Pada umumnya metode conjugate gradient dideskripsikan oleh iterasi berikut ini: umumnya metode conjugate gradient dideskripsikan oleh iterasi berikut ini: pencarian garis,

sedikit dan mempunyai sifat kekonvergenan lokal ak>0 adalah panjang langkah (steplength) yang finisikan oleh yang maupun global. Namun arah pencarian ditentukan oleh suatu pencarian garis, dk didefinisikan adalah panjang langkaholeh: (steplength) yang ditentukan oleh suatu pencarian garis, dihasilkan dari metode ini tidak dijamin arah yang adalah panjang langkah (steplength) yang ditentukan oleh suatu pencarian garis, dide- didepanjang langkah (steplength) yang ditentukan suatu pencarian garis, adalah panjang langkah (steplength) yang ditentukan oleh suatu pencarian garis, didedidemenurun. Di lain adalah pihak, metode spectral gradient { oleh ( finisikan oleh finisikan oleh gradien sebagai arahnya di menggunakan hanya finisikan oleh finisikan oleh . .......................... (2.1) (2.1) setiap pencarian garisnya. Metode ini mempunyai { dengan adalah gradient dari f di titik , adalah parameter yang jika digu performa yang lebih bagus daripada metode conjugate { (2.1) { { (2.1) (2.1) gradient dalam berbagai masalah (Birgin & Martinez, dengan adalah gradient dari f di titik yang , adalah parameter yang arah jika digunakan untuk meminimumkan fungsi kuadratik convex ketat maka pencarian dan dengan gk=g(xk) adalah gradien dari f di titik xk, 2001). dengan adalah gradient dari f diberdasarkan titik , parameter adalah parameter jika digunakan untuk meminimumkan fungsi convex ketat maka arah pencarian dan adalah yang jikayang digunakan untuk Birgindengan &dengan Martinez (2001) mengembangkan merupakan konjugat dari fungsi objektif (Zhang et.al,2006). Da kdi adalah gradient dari f dibfkuadratik titik adalah parameter yang jika digunakan adalah gradient dari titik ,yang ,Hessian adalah parameter yang jika digunakan meminimumkan fungsi kuadratik yang konveks ketat, metode suntuk pectralmeminimumkan conjugate gradient yang merupakan merupakan konjugat berdasarkan Hessianketat dari maka fungsi arah objektif (Zhang et.al,2006). Dai, et.al fungsi kuadratik yang convex pencarian dan menyatakan bahwa jika fungsi objektifnya fungsi kuadratik yang convex maka arah pencarian dk dan dk-1adalah merupakan konjugat meminimumkan fungsi yang convex ketat maka arah pencarian dan untuk meminimumkan fungsi kuadratik yang convex ketat maka arah pencarian dan gabunganuntuk dari metode spectral (2004) gradient dankuadratik metode (2004) menyatakan bahwa jika fungsi objektifnya fungsi kuadratik yang ketat berdasarkan Hessianadalah dari fungsi objektif (Zhang al., conjugatemerupakan gradient. Metode ini terbukti sangat efektif konjugat berdasarkan Hessian dari fungsi objektif (Zhang et.al,2006). Dai,etconvex et.al dan menggunakan pencarian garis eksak maka metode conjugate gradient merupakan konjugat berdasarkan Hessian dari objektif (Zhang et.al,2006). Dai, merupakan konjugat berdasarkan Hessian darifungsi fungsi objektif (Zhang et.al,2006). Dai,et.al et.al mengha 2006). Dai et al. (2004) menyatakan bahwa jika fungsi untuk menyelesaikan masalah optimasi tanpa kendala dan menggunakan pencarian garis eksak maka metode conjugate gradient menghasilkan (2004) menyatakan bahwa jika pencarian fungsi objektifnya adalah fungsi kuadratik yang convex ketat formula un objektifnya adalah fungsi kuadratik yang konveks nonlinier. Akan tetapi metode ini menghasilkan arah arah-arah yang konjugat satu dengan lainnya. Terdapat banyak (2004) menyatakan bahwa jika fungsi objektifnya adalah fungsi kuadratik yang convex ketat (2004) menyatakan bahwa jika fungsi objektifnya adalah fungsi kuadratik yang convex ketat lainnya. Terdapat banyak ketat satu dan dengan menggunakan pencarian garisformula eksak,untuk yang belum tentu menurun.arah-arah pencarian yang konjugat dan menggunakan pencarian garis diantaranya eksak maka metodeFletcher-Reeves conjugate gradient maka metode conjugate gradient menghasilkan arahyang terkenal, adalah (FR),menghasilkan Polak-Ribiere-Polyak (PRP Metodedan lain terkenalyang adalah metode conjugate menggunakan pencarian garis maka metode conjugate gradient menghasilkan danyang menggunakan pencarian gariseksak eksak maka metode conjugate gradient menghasilkan terkenal, diantaranya adalah Fletcher-Reeves (FR), Polak-Ribiere-Polyak (PRP) dan arah pencarian yang konjugat satu dengan lainnya. descent dengan menggunakan pencarian garis strong arah-arah pencarian yang konjugat satu(CD). dengan lainnya. Terdapat banyak formula untukini: conjugate descent Formula-formula tersebut diberikan berikut conjugate descent (CD). Formula-formula tersebut diberikan berikut ini: arah-arah pencarian yang konjugat satu lainnya. Terdapat banyak formula untuk arah-arah pencarian yang konjugat satudengan dengan lainnya. Terdapat banyak formula untuk Terdapat banyak formula untuk bk yang terkenal, di Wolfe. Metode ini dikembangkan oleh Fletcher (1987). antaranya adalah (FR), Polak-Ribiereyang diantaranya Fletcher-Reeves (FR), Fletcher-Reeves Polak-Ribiere-Polyak (PRP) dan Salah satu sifatterkenal, penting dari metode iniadalah adalah arah ‖ ‖ ‖ ‖ yang (FR), Polak-Ribiere-Polyak (PRP) yangterkenal, terkenal,diantaranya diantaranyaadalah adalahFletcher-Reeves Fletcher-Reeves (FR), Polak-Ribiere-Polyak (PRP)dan dan (2.2) Polyak (PRP) dan conjugate descent (CD). Formulapencarian yang dihasilkan merupakan arah pencarian ( ‖ ‖ ‖ ‖ conjugate descent (CD). Formula-formula tersebut diberikan berikut ini: formula tersebut diberikan berikut ini: yang menurun (descent direction). conjugate descent (CD). Formula-formula tersebut diberikan berikut ini: conjugate descent (CD). Formula-formula tersebut diberikan berikut ini: (2.3) Termotivasi oleh Birgin & Martinez, Liu et al. (2012) ‖ ‖ ‖ ‖ ( (2.2) ‖ ‖ ‖ ....................................................... ‖ ‖ ‖ mengembangkan metode yang menggabungkan (2.2) ‖ ‖ (2.2) (2.2) ‖ ‖ ‖ ‖ metode conjugate descent dandan metode spectral conjugate dan gradient yang disebut dengan metode spectral conjugate ‖ ‖ (2.3) .................................................... (2.3) (2.4) ‖ ‖ (2.3) (2.3) descent. Metode ini menghasilkan arah pencarian yang ‖ ‖ ‖ ‖ ‖ ‖ (2 menurun. Liu et al. (2012) telah menunjukkan bahwa dan metode ini konvergen global menggunakan pencarian dan dan dan garis strong Wolfe. Di lain pihak, untuk pencarian ‖ ‖ ‖ ‖‖ ‖ (2.4) garis yang lain belum ditunjukkan kekonvergenan ............................................. (2.4) (2.4) (2.4) globalnya. Dalam makalah ini dibahas kekonvergenan global ‖ ‖‖menyatakan di mana dan Euclidean norm. ‖ menyatakan dengan dan menyatakan di mana dan Euclidean norm. metode spectral conjugate descent dengan menggunakan Euclidean norm. pencarian garis Armijo yang termodifikasi. Hal ini di mana dan ‖ ‖Conjugate menyatakan Euclidean norm. Metode Spectral Gradient termotivasi oleh Kim et al. (2008) yang menunjukkan Metode Spectral Conjugate Gradient Metode Spectral Conjugate Gradient bahwa pencarian garis Armijo yang termodifikasi Metode spectral gradient awalnya dikembangkan Metode spectral gradient awalnya dikembangkan oleholeh Barzilai dandan Bor Metode spectral gradient awalnya dikembangkan Barzilai lebih efisien dalam mencari nilai minimum lokal oleh Barzilai dan Borwein pada tahun 1988, kemudian Metode Spectral Conjugate GradientRaydan mengembangkan metode ini lebih jauh untuk menyel 1988, kemudian 1988, kemudian Raydan mengembangkan metodejauh ini lebih jauh untuk men walaupun membutuhkan perhitungan yang lebih Raydan mengembangkan metode ini lebih gradient awalnya dikembangkan oleh Barzilai dan Borwein padamengemb tahun banyak dibandingkan pencarian garis lainnya. Metode spectral untuk menyelesaikan masalah optimasi tanpa optimasi tanpa kendala dalam skala besar. Birgin dan Martinez (2001) optimasi tanpa kendala dalam skala besar. Birgin dan Martinez (2001) menge kendala dalam skala besar. Birgin & Martinez 1988, kemudian Raydan mengembangkan metode ini lebih jauh untuk gabungan menyelesaikan masalahspec metode spectral conjugate gradient yang merupakan daridari metode spectral conjugate merupakan gabungan metode s (2001)metode mengembangkan tigagradient macamyang metode spectral optimasi tanpa kendala dalam skala besar. Birgin dan Martinez (2001) mengembangkan 3 macam metode conjugate gradient. Arah pencarian diberikan oleh metode conjugate gradient. Arah pencarian diberikan oleh metode penelitian conjugate gradient yang merupakan gabungan dari metode spectral conjugate gradientgradient yang merupakan gabungan dari metode spectral gradient dan metode spectral dan metode conjugate gradient. Kekonvergenan metode spectral conjugate descent pencarian diberikan oleh:oleh metodeyang conjugateArah gradient. Arah pencarian diberikan dengan menggunakan pencarian garis Armijo di mana dandan parameter oleholeh di mana parameter ditentukan ditentukan termodifikasi dianalisis dengan menggunakan pendekatan secara numerik. di mana dan parameter ditentukan oleh

dandan dan Sedangkan spectral gradient yang dapat ditentukan oleholeh Sedangkan adalah adalah spectral gradient yang dapat ditentukan

mana dan ‖ ‖ menyatakan Euclidean norm. ‖ menyatakan dan ‖ di Euclidean norm.

Metode Spectral Conjugate Gradient 1988,Birgin kemudian Raydan mengembangkan metode ini lebih jauh3 untuk menyelesaikan masalah Metode Spectral Conjugate Descent m skala besar. dan Martinez (2001) mengembangkan Metode Conjugate Gradient Untuk mendapatkan arah macam pencarian yang menurun, Liu et.al (2012) mengkombinasi Metode Spectral Spectralmetode Conjugate Gradientconjugate spectral gradient yang merupakan gabungan dari metode spectral gradient dan optimasi tanpa kendala dalam skala besar. Birgin dan Martinez (2001) mengembangkan 3 macam de SpectralMetode Conjugate Gradient Metode spectral gradient awalnya dikembangkan oleh Barzilai dan Borwein pada tahun Untuk mendapatkan arah pencarian yang menurun, Liu et.al (2012) mengkombinasi spectral gradient gradient awalnya dikembangkan oleh Barzilai Barzilai dan Borwein Borwein pada tahun tahun Metode spectral awalnya dikembangkan oleh dan pada radient yang merupakan gabungan dari metode spectral gradient dan metode spectral conjugate gradient dan metode conjugate descent. Arah pencarian dari metode Metodeconjugate Spectralgradient Conjugate Gradient metode conjugate gradient. Arah pencarian diberikan oleh Conjugate Gradient metode spectral yang merupakan gabungan dari metode spectral gradient dan Metode spectral gradient awalnya dikembangkan oleh Barzilai dan Borwein pada tahun metode spectral conjugate gradient dan metode conjugate descent. Arah pencarian dari metode 1988, kemudian Raydan mengembangkan metode ini lebih jauh untuk menyelesaikan masalah 1988, kemudian kemudian Raydan Raydan mengembangkan mengembangkan metode metode ini ini lebih lebih jauh jauh untuk untuk menyelesaikan menyelesaikan masalah masalah 1988, 5 conjugate gradient descent diberikan oleh Arah pencarian diberikan oleh spectral Metode gradient awalnya dikembangkan oleh Barzilai dan Borwein pada tahun metodeawalnya conjugate gradient. Arah pencarian diberikan pectral gradient dikembangkan oleh Barzilai dan oleh Borwein pada tahun

conjugate gradient descent diberikan oleh 44 Sains & Mat, Vol. 2 No. 2, April 2014: 42–48 kemudian mengembangkan metode inidan lebih jauh(2001) untuk menyelesaikan masalah optimasi tanpa dalam skala besar. Birgin Martinez mengembangkan 3 macam optimasi tanpa dalam skala besar. Birgin dan Martinez mengembangkan 3 Conjugate macam Metode Spectral Descent optimasi Raydan tanpa kendala kendala dalam skalakendala besar. Birgin dan Martinez (2001) mengembangkan 3(2001) macam Metode Spectral Conjugate Descent 1988, kemudian Raydan mengembangkan metode ini lebih jauh untuk menyelesaikan masalah (2.6) 5 { Conjugate Metode Conjugate Descent Raydan mengembangkan metode lebih jauh untuk menyelesaikan masalah metode spectral conjugate gradient yang merupakan gabungan dari metode spectral gradient dan Untuk mendapatkan arah et.al pencarian menurun asi tanpa kendala skala besar.ini Birgin dan Martinez (2001) mengembangkan macam (2.6) Metode Spectral Descent metode spectral conjugate gradient yang merupakan gabungan metode spectral gradient dan Liu metode spectraldalam conjugate gradient yang merupakan gabungan dari metode spectral gradient dan { 3dari di mana danSpectral parameter ditentukan oleh Untuk mendapatkan arah pencarian yang menurun, (2012)yang mengkombin di mana dan parameter ditentukan oleh optimasi tanpa kendala dalam skala besar. Birgin dan Martinez (2001) mengembangkan 3 macam dan parameter b ditentukan oleh: b adalah Untuk mendapatkan arahmendapatkan pencarian yang menurun, Liu et.al (2012)gradient mengkombinasi k k metode conjugate gradient. Arah pencarian diberikan oleh spectral conjugate dan(2012) metodemengkombin conjugate endala dalam skala besar. Birgin dan Martinez (2001) mengembangkan 3 Descent macam dan parameter ditentukan oleh arahmetode pencarian yang menurun, Liu et.al metode conjugate gradient. Arah pencarian diberikan oleh e spectral conjugate gradient yang merupakan gabungan dari metode spectral gradient dan metode conjugate gradient. Arah pencarian diberikan oleh metodeUntuk spectral conjugate gradient dan metode conjugate descent. Arah pencarian dari metod Metode Spectral Conjugate adalah adalah metode spectral conjugate gradient dandari metode conjugate descent. Arah pencarian dari metode metode spectral conjugate gradient yang merupakan gabungan metode spectral gradient dan conjugate gradient descent diberikan oleh metode spectral conjugate dan descent. Arah pencarian dari meto conjugate gradient yang merupakan gradient e conjugate gradient. Arah pencariangabungan diberikandari olehmetode conjugate gradient descent gradient diberikan olehmetode Untukspectral mendapatkan arahdan pencarian yang menurun, Liu conjugate et.al (2012) mengkombinasi (2.7) (2.7) conjugate gradientdiberikan descent diberikan oleh { { metode conjugate gradient. Arah pencarian oleh di mana dan parameter ditentukan oleh conjugategradient gradientdan descent diberikan oleh descent. di mana Arah pencarian diberikan dan parameter ditentukan oleh conjugate e gradient. oleh { metode spectral metode conjugate Arah pencarian dari metode ....................................... (2.7) di mana dan parameter ditentukan oleh (2.6 {

(2.6) (2.6 { (2.8) adalah (2.8) . .................................................(2.8) (2.6) { Armijo yang termodifikasi Dengan menggunakanadalah pencarian garis akan ditunjukkan bahwa { Dengan menggunakan pencarian garis Armijo (2.7 Dengan menggunakan pencarian garis Armijo yang termodifikasi akan ditunjukkan bahwa { dan (2.7) metode ini konvergen global serta menghasilkan arah pencarian yang menurun. { yang termodifikasi akan ditunjukkan bahwa metode (2.7 adalah { metode ini konvergen global serta menghasilkan arah pencarian yang menurun. ini konvergen global serta menghasilkan arah dan (2.8 dan dan (2.7) pencarian { yang menurun. (2.8) (2.8 Pencarian Garis Armijo Yang Termodifikasi dan menggunakan pencarian garis yang term Dengan menggunakan pencarianDengan garis Armijo yang termodifikasi akanArmijo ditunjukkan bah Sedangkan adalah spectral gradientDengan yang dapat ditentukan oleh Pencarian Garis Armijo Yang Termodifikasi Pencarian Garis Armijo Yang Termodifikasi Pencarian garis merupakan salah satu bagian yang penting dalam metode optimisasi. Termenggunakan pencarian garis Armijo yang termodifikasi akan ditunjukkan bahwa (2.8) metode ini konvergen global serta menghasilkan arah pencari Dengan menggunakan pencarian garismerupakan Armijoarah yang termodifikasi akan ditunjukkan bah metode ini konvergenPencarian global sertagaris menghasilkan pencarian menurun. salah satuyang bagian yang dan dapat duaini jenis pencarian garis, yakni pencarian garis eksak dan tidak eksak. Namun dalam prakmetode konvergen global serta menghasilkan arah pencarian yang menurun. Pencarian garis merupakan salah satu bagian yang penting dalam metode optimisasi. Terpenting dalam metode optimisasi. Terdapat jenis (2.5) metodepencarian ini konvergen global serta menghasilkan arah akan pencarian yang dua menurun. Dengan menggunakan garis Armijo yang termodifikasi ditunjukkan bahwa Sedangkan adalah spectral gradient yang dapat ditentukan oleh pencarian garis, yakni pencarian garis eksak dan tidak sedangkan adalah spectral gradient yang dapat teknya, pencarian garis yang tidak eksak lebih dipilih daripada pencarian garis yang eksak karena Sedangkan adalah spectral gradient yang dapat ditentukan oleh dapat dua jenis pencarian garis, yakni pencarian garis eksak dan tidak dalam prakPencarian Gariseksak. ArmijoNamun Yang Termodifikasi Sedangkan adalah spectral gradient yang dapat ditentukan oleh . Secara numerik metode inikonvergen sangat efisien, tetapi arah pencarian Pencarian Garismenghasilkan Armijo Yang Termodifikasi metode ini global akan serta arah pencarian yang menurun. eksak. Namun dalam praktiknya, pencarian garis yang oleh: al gradient yangditentukan dapat ditentukan olehsifat pencarian garisPencarian eksak yang terlalu mahal dan tidak efisien. Di lain pihak, bagi sebagian Pencarian Garis Armijo Yang Termodifikasi Pencarian garis merupakan salahbesar satu bagian yang pe Garislebih Armijo Yangdaripada Termodifikasi yang dihasilkan belum tentu arahspectral yang menurun (descent teknya, pencarian garis yangdirection). tidak eksak dipilih pencarian garis yang eksak karena tidak eksak lebih daripada pencarian garis Pencarian garis(2.5) merupakan salahdipilih satu bagian yang penting dalam metode optimisasi. T Sedangkan adalah gradient yang dapat ditentukan oleh (2.5) (2.5) metode-metode optimisasi, sebagai contoh metode Newton dan metode Quasi-Newton, kekonPencarian garis merupakan salah satu bagian yang penting dalam metode optimisasi. Teryang eksak karena sifat pencarian garis eksak yang optimisasi. dapat dua jenis pencarian garis, yakni pencarian garis eksak Pencarian garis merupakan salah satu bagian yang penting dalam metode T .................................................. (2.5) Berdasarkan metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi sifat pencarian garisGaris eksak yang terlalu mahal dangaris, tidakyakni efisien. Di lain pihak, sebagian dapat dua jenisTermodifikasi pencarian pencarian garis eksakbagi dan tidak eksak.besar Namun dalam prad Pencarian Yang .. Secara numerik metode ini sangat efisien, akan tetapi arah pencarian gkan adalah spectral gradient yang dapat ditentukan oleh Armijo (2.5) Secara numerik metode ini sangat efisien, akan tetapi arah pencarian terlalu mahal dan tidak efisien. DiNamun lain pihak, bagi vergenan metodenya tidak bergantung pada pencarian garis eksak yang digunakan. dapat dua jenis pencarian garis, yakni pencarian garis eksak dan tidak eksak. dalam prakteknya, pencarian garis yang lebih dipilih daripad . arah Secara numerik metode inipencarian sangat efisien, akan tetapi arah pencarian (2.5) dapat dua jenis garis, yakni pencarian garis eksak dantidak tidakeksak eksak. Namun dalam pra metode belum Flethcer-Reeves sehingga pencarian yang dihasilkan adalah araholeh pencarian yang Sedangkan spectral gradient yang dapat ditentukan teknya, pencarian garis yang tidak eksak lebih dipilih daripada pencarian garis yang eksak kare Pencarian garis merupakan salah satu bagian yang penting dalam metode optimisasi. Teryang dihasilkan tentudapat arahadalah yang menurun (descent direction). sebagian besar metode-metode optimisasi, sebagai metode-metode optimisasi, sebagai contoh metode Newton dan metode Quasi-Newton, kekonalahyang spectral gradient ditentukan oleh dihasilkan belumyang tentu arah yang menurun (descent direction). Secara umum, pencarian garis tidak eksak mencari panjang langkah (steplength) yang teknya, pencarian garis yang tidak eksak lebih dipilih daripada pencarian garis yang eksak karena numerikmenurun. metodeMetode ini sangat efisien, akan tetapi arah pencarian sifat pencarian garis eksak yang mahal dansebagian tidak teknya, pencarian garis yang tidak eksak lebih dipilih daripada pencarian garis yang eksakefisie kare (2.5) Fletcher-Reeves yang termodifikasi diberikan oleh contoh metode Newton dan metode Quasi-Newton, . Secara Secara numerik metode ini sangat efisien, akan tetapi arah pencarian sifat pencarian garis eksak yang terlalu mahal dan tidak efisien. Diterlalu lain pihak, be numerik metode ini sangat dapat dua jenis pencarian garis, yakni pencarian garis eksak danyang tidak eksak. Namun dalam prak-bagi yangmetode dihasilkan belum tentu arah yang menurun (descent direction). Berdasarkan spectral conjugate gradient, Zhang et.al (2006) memodifikasi vergenan metodenya tidak bergantung pada pencarian garis eksak digunakan. Berdasarkan metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi (2.5) sesuai sehingga fungsi objektif merupakan fungsi yang menurun di setiap iterasinya. Salah satu sifat pencarian garis eksak yang terlalu mahal dan tidak efisien. Di lain pihak, bagi sebagian besar kekonvergenan metodenya tidak bergantung pada metode-metode optimisasi, sebagai contoh metode Newton efisien, akan tetapi arah pencarian yang dihasilkan sifat pencarian garis eksak yang terlalu mahalmetode dan tidak efisien. Dimetode lain pihak, bagi sebagiankeko be (2.5) u arah yang menurun (descent direction). metode-metode optimisasi, sebagai contoh Newton dan Quasi-Newton, . Secara metode ini sangat efisien, akan tetapi arah pencarian teknya, pencarian garis yang tidak eksak lebih dipilih daripada pencarian garis yang eksak karena yangnumerik dihasilkan belum arah yang menurun (descent direction). metode sehingga arah pencarian yang dihasilkan adalah arah pencarian yang {tentu metode Flethcer-Reeves Flethcer-Reeves sehingga arah pencarian yang dihasilkan adalah arah pencarian yang pencarian garis eksak yang digunakan. Berdasarkan metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi Secara umum, pencarian garis tidak eksak mencari panjang langkah (steplength) yang belum tentu arah yang menurun (descent direction). pencarian metode-metode garismetode yang optimisasi, tidak eksak sebagai adalah contoh pencarian metode garis Newton Armijo dan yang metode dideskripsikan Quasi-Newton, sebagai kekonberi. Secara numerik ini sangat efisien, akan tetapi arah pencarian vergenan metodenya tidak bergantung pada pencarian garis e metode-metode optimisasi, sebagai contoh metode Newton dan metode Quasi-Newton, keko .menurun. Secarabelum numerik metode ini menurun sangat efisien, akan tetapi arah pencarian vergenan metodenya tidak bergantung pada memodifikasi pencarian garis eksak yangmencari digunakan. Secara umum, pencarian garis tidak eksak sifat pencarian garis eksak yang terlalu mahal dan tidak efisien. Di lain pihak, bagi sebagian besar Metode Fletcher-Reeves yang termodifikasi diberikan oleh tentu arah yang (descent direction). Berdasarkan metode spectral conjugate gradient, Berdasarkan metode spectral conjugate gradient, Zhang et.al (2006) edihasilkan spectral conjugate gradient, Zhang et.al (2006) memodifikasi menurun. Metode Fletcher-Reeves yang termodifikasi diberikan oleh vergenan metodenya tidak bergantung pada pencarian garis eksak digunakan. sesuai tentu sehingga fungsi objektif merupakan fungsi yang bilangan menurun diyang setiap iterasinya. Salah satu diberikan oleh (2.2). ( )yang metode sehingga arah pencarian dihasilkan adalah arah pencarian yang Secara umum, pencarian garis tidak eksak mencari kut: diberikan , terdapat bulat nonnegative paling kecil panjang langkah (steplength) yang sesuai sehingga fungsi vergenan metodenya tidak bergantung pada pencarian garis eksak yang digunakan. yangmenurun dihasilkan belum arah yang menurun (descent direction). Zhang etFlethcer-Reeves al. (2006) memodifikasi metode FlethcerSecara umum, pencarian garis tidak eksak mencari panjang langkah (steplength) ya metode-metode optimisasi, sebagai contoh metode Newton dan metode Quasi-Newton, kekonbelum tentu arah yang (descent direction). Berdasarkan metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi metode Flethcer-Reeves sehingga arah pencarian yang dihasilkan adalah arah pencarian yang objektif merupakan fungsi yang menurun di setiap Secara umum, pencarian garis tidak eksak mencari panjang langkah (steplength) yang hingga arah pencarian yang dihasilkan adalah arah pencarian yang Reeves Berdasarkan sehingga arah pencarian yang dihasilkan {{ pencarian garis yang tidak eksak adalah pencarian garis Armijo yang dideskripsikan sebagai berisesuai sehingga fungsi objektif merupakan fungsi yang men Secara umum, pencarian garis tidak eksak mencari panjang langkah (steplength) ya sedemikian sehingga metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi menurun. Metode Fletcher-Reeves yang termodifikasi diberikan oleheksak sesuai sehingga fungsi objektif merupakan fungsi yang menurun setiap iterasinya. Salah s vergenan metodenya tidak bergantung pada pencarian garis yang digunakan. iterasinya. Salah satu pencarian garis yang di tidak eksak kan metode spectral conjugate gradient, Zhang et.al (2006) memodifikasi adalah arah yang menurun. Metode e Flethcer-Reeves sehingga arahpencarian pencarian yang adalah arah pencarian yang menurun. Metode Fletcher-Reeves yang termodifikasi diberikan oleh sesuaidihasilkan sehingga fungsi objektif merupakan fungsimerupakan yang menurun diyang setiap iterasinya. Salah satu pencarian garis tidak eksak adalah pencarian garis Arm sesuai sehingga fungsi objektif fungsi yang menurun di setiap iterasinya. Salah sa Reevesdiberikan yang termodifikasi diberikan oleh diberikan oleh (2.2). Flethcer-Reeves adalah pencarian garis Armijo yang dideskripsikan pencarian garis yang eksak adalah pencarian garis Armijo yang dideskripsikan sebagai be Secara umum, garis tidak eksak mencari panjang langkah (steplength) yang (pencarian ) yang metode sehingga arah pencarian yang dihasilkan adalah arah pencarian yang kut:dihasilkan diberikan , tidak terdapat bilangan bulat nonnegative paling kecil Fletcher-Reeves yang termodifikasi diberikan oleh: oleh (2.2). -Reeves sehingga arah pencarian adalah arah pencarian run. Metode Fletcher-Reeves yangyang termodifikasi diberikan oleh pencarian garis yang tidak eksak adalah pencarian garis Armijo yang dideskripsikan sebagai beriJika pencarian garis yang digunakan adalah pencarian garis eksak, maka metode ini kembali ke { fungsi sebagai berikut: diberikan pencarian garis yang tidak eksak adalah pencarian Armijo yang sebagai be ( Salah )dideskripsikan kut: diberikan ,, terdapat pencarian garismerupakan Armijo berdasarkan {yang sesuai Modifikasi sehingga objektif fungsi menurun di garis setiap iterasinya. satu ( yang )fungsi menurun. Metodesedemikian Fletcher-Reeves termodifikasi diberikan oleh kut: diberikan , terdapat bilangan bulat nonnegative palingbilanga kecil sehingga e Fletcher-Reeves yang termodifikasi diberikan oleh yang standard. kut: diberikan { metode Fletcer-Reeves bilangan bulatbulat nonnegatif paling kecil ( )terdapat , terdapat bilangan nonnegative paling kecil ( garis ) kut:tidak diberikan , terdapat bilangan bulat nonnegative paling kecil { pencarian garis yang eksak adalah pencarian Armijo yang dideskripsikan sebagai berisedemikian sehingga sedemikian sehingga sedemikian sehingga diberikan oleh (2.2). diberikan oleh (2.2). { sehingga Jika pencarian pencarian garis garis yang digunakan adalah pencarian garis eksak, maka maka metode metode ini ini kembali kembali ke ke sedemikian { yang Jika digunakan adalah pencarian garis eksak, sedemikian sehingga ( ) kut: diberikan , terdapat bilangan bulat nonnegative paling kecil adalah matriks simetris dan definit positif yangfungsi dikembangkan oleh Wei et.al (2000). Uniberikan oleh (2.2). Modifikasi pencarian garis Armijo berdasarkan metode Fletcer-Reeves yang standard. metode Fletcer-Reevesdiberikan yang standard. Modifikasi pencarian Armijo berdasarkan fungs oleh(2.2). (2.2). sedemikian sehingga diberikan oleh Modifikasi pencarian garis berdasarkan fungsi garis Modifikasi pencarian garis mengubah Armijo berdasarkan eh (2.2). tuk memudahkan penggunaan, modifikasi ini dapat Armijo digunakan dengan menjadi Modifikasi pencarian garis Armijo berdasarkan fungsi Modifikasifungsi pencarian garis Armijo berdasarkan fungsi untuk adalah . Untuk metodegaris conjugate garis Armijokeyang termodifikasi Jika pencarian garis yang digunakan pencarian eksak,descent, maka pencarian metode ini kembali Modifikasi pencarian garis Armijo berdasarkan Jika pencarian garisadalah yang digunakan adalah pencarian garis eksak,fungsi maka metode ini et.al kembali ke matriks simetris dan definit positif yang oleh Wei (2000). Unadalah matriks dan, definit yang dikemb dideskripsikan sebagai berikut: diberikan , positif , simetris dan encarian garis yangmetode digunakan adalah pencarian garis eksak, maka metode ini kembali kedikembangkan Fletcer-Reeves yang standard. adalah matriks simetris dan definit yang dikembangkan oleh positif Wei et.al (2000). U gunakan adalah Jika pencarian garis eksak, maka metode ini kembali ke pencarian garis yang digunakan adalah pencarian garis eksak, maka metode ini kembali ke adalah matriks simetris dan definit positif yang dikembangkan oleh Wei et.al (2000). Unmetode Fletcer-Reeves yang standard. B adalah matriks simetris dan definit positif tuk memudahkan penggunaan, modifikasi ini dapat diguna aris yang digunakan adalah pencariantuk garis eksak, metode kembali kepenggunaan, adalah matriks dandigunakan definit positif yang oleh Wei et.al (2000). Jika pencarian garis yangmaka digunakan adalah ksimetris memudahkan penggunaan, modifikasi ini dapat dengan mengubahdengan menjadi e Fletcer-Reeves yang standard. tukini memudahkan modifikasi ini dapatdikembangkan digunakan mengubah menjU yang dikembangkan olehdengan Wei mengubah et al. (2000). menjadi Untuk tuk memudahkan penggunaan, modifikasi ini dapat digunakan pencarian garis eksak,yang maka metode ini kembali ke standard. metode Fletcer-Reeves standard. untuk garis . Untuk metode conjugate descent, pencari tuk memudahkan penggunaan, modifikasi ini dapat digunakan dengan mengubah menja eeves yang standard. adalah matriks simetris dan definit positif yang dikembangkan oleh Wei et.al (2000). Ununtuk . Untuk metode conjugate descent, pencarian garis Armijo yang termodifik untuk . Untuk metode conjugate descent, pencarian Armijo yang termodifikasi memudahkan penggunaan, modifikasi ini dapat metode Fletcer-Reeves yang standar. untuk . Untuk metode conjugate descent, pencarian garis Armijo yang termodifikasi untuk . Untuk metode conjugate descent, garis Armijo yang termodifik digunakan dengan mengubah Bpencarian mI untuk m>0. dideskripsikan sebagai ,d k menjadi tuk memudahkan dideskripsikan penggunaan, modifikasi ini dapat digunakan dengan mengubah menjadi diberikan , berikut:, diberikan , 5sebagai berikut: dideskripsikan sebagai berikut: diberikan , , pencarian dan , Untuk metode conjugate descent, garis Armijo dideskripsikan sebagai berikut: sebagai diberikan , , , dan dideskripsikan berikut: , , d untuk . Untuk metode conjugate descent, diberikan pencarian garis Armijo, yang termodifikasi Metode Spectral Conjugate Descent yang termodifikasi dideskripsikan sebagai berikut: pectral Conjugate Descent Untuk mendapatkandideskripsikan arah pencarian diberikan dan sebagai yang berikut: diberikan , , , dan menurun, et al. (2012) Liu mengkombinasi metode ntuk mendapatkan arah pencarianLiu yang menurun, et.al (2012) mengkombinasi , misal didefinisikan ,, pencarian Armijo misal didefinisikan pencarian , misal didefinisikan , pencarian garisgaris Armijo yangyat spectral conjugate gradient dan metode conjugate descent. Armijo yang termodifikasi adalah mencari a pectral conjugate gradient dan metode conjugate descent. Arah pencarian dari metode garis k mencaridi mana di manaadalah adalah bilangan nonnegative paling mencari bilangan bulatbulat nonnegative paling kecilkecil seh Arah pencarian dari metode conjugate gradient descent di mana jk adalah bilangan bulat nonnegatif paling , misal didefinisikan , pencarian garis Armijo yang termodifikasi adalah , misal didefinisikan , pencarian garis Armijo yang termodifikasi adalah gradient descent diberikan oleh oleh: diberikan kecil sehingga ( ( ) ) ( () ‖ mana bilangan adalahbulat bilangan bulat nonnegative paling kecil sehingga mencari mencari di mana diadalah nonnegative paling kecil sehingga (2.6) ......................... (2.6) { dan dan

na

{

conjugate dan parameter ditentukan olehgradient descent diberikan oleh di mana ditentukan oleh danadalah parameter adalah ditentukan oleh dan parameter dan

(

(

)

)

(

(

(

) ‖( ‖

)

)

) ‖

‖(2.9)

(2.9)

(2.11)

(2.11)

dan bilangan riil yang sangat (2.7) MisalMisal ( dan dan )bilangan riil yang sangat kecil,kecil, makamaka yangy { ( ) (2.10) (2.10) ...................... (2.10) tukantukan oleh oleh Misal dan bilangan riil yang sangat kecil, yang maka paling yang paling sesuai ditenMisal dan bilangan riil yang sangat kecil, maka sesuai diten(2.8) tukan olehtukan oleh { { menggunakan pencarian garis Armijo yang termodifikasi akan ditunjukkan bahwa dan

dan

i konvergen global serta menghasilkan arah pencarian yang menurun.

n Garis Armijo Yang Termodifikasi

dengan

dengan dengan

dengan

ncarian garis merupakan salah satu bagian yang penting dalam metode optimisasi. Ter-

{

{

HASIL PEMBAHASAN HASIL DANDAN PEMBAHASAN

HASIL DAN PEMBAHASAN HASIL DAN PEMBAHASAN

, misal didefinisikan , pencarian garis Armijo yang termodifikasi adalah , pencarian garis Armijo yang termodifikasi adalah , misal didefinisikan pencarian garis Armijo yang termodifikasi adalah , misal didefinisikan , pencarian garis ,Armijo yang termodifikasi adalah mencari di mana yang adalah bilangan bulat nonnegative paling kecil sehingga , pencarian garis Armijo termodifikasi adalah , pencarian Armijo termodifikasi adalah mencari diyang mana adalah bilangan bulatgaris nonnegative paling kecil sehingga adalah bilangan bulatgaris paling kecil sehingga , nonnegative misal didefinisikan , pencarian Armijo yang termodifikasi adalah , pencarian garis Armijo yang termodifikasi adalah , pencarian garis Armijo yang termodifikasi adalah Bukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan benar. Untu mencari di mana adalahdibilangan nonnegative paling kecil sehingga mencari mana bulat adalah bilangan bulat nonnegative paling kecil sehingga 7 , nonnegative misal didefinisikan , pencarian garis Armijo yang termodifikasi adalah bilangan bulat nonnegative paling kecil sehingga langan bulat paling kecil sehingga definisikan , pencarian garis Armijo yang termodifikasi adalah ‖ ‖ ( ) ( ) ‖ ‖ ‖ ‖ ( ) ( ) ) ( ) mencari di mana adalah bilangan bulat nonnegative paling kecil sehingga (2.9) hh bilangan nonnegative paling sehingga bilangan bulat bulat nonnegative paling kecil kecil sehingga , sehingga berlaku (2.9) ‖ ‖ Sehingga (3.2) benar unt (2.9) berlaku ‖ ‖ ‖ ‖Dengan ( bulatkecil ) paling kecil ( menggunakan )(2.9) ( adalah )paling ( sehingga )Bukti. di mana bilangan nonnegative (2.9) 7 benar. induksi, kita akan tunjukkan bahwa kesimp na adalah bilangan bulat nonnegative sehingga Bukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan Untuk ‖ ‖ ‖ ‖ ( ) ) ) mencari ( ) dan (2.9) (2.9) ‖ ‖ bena Bukti. Dengan menggunakan kita akan , tunjukkan bahwa kesimpulan .Descent Kita asumsikan dan yaitu . Ji , Hasanah: pencarian garis Armijo yang))Metode termodifikasi adalah ‖ ‖untuk induksi, dan ( ((Global ( ) benar ‖‖ ) ‖‖ Spectral )) Konvergensi Conjugate 45 (2.9) (2.9) 7 (2.9) ‖ ‖ berlaku , sehingga berlaku Sehingga dan dan ‖ ‖ berlaku , sehingga berlaku Sehingga (3.2) benar untuk ‖ ‖ ( ) ( ) berlaku (bilangan )nonnegative ( ) ‖ ) ‖ kesimpulan ‖ ‖ Sehingga (3.2) ben (2.9) , sehingga berlaku , maka . Dari (2.4), (2.6) dan (2.8) didapatkan hBukti. paling kecil sehingga Dengan menggunakan induksi, kita akan Untuk ( tunjukkan ( bulat ) (2.10) ( bahwa ) (2.9)benar. dan (2.10) (2.10) dan 7 untuk . Kita asumsikan benar ‖ ‖ Kita asumsikan benar untuk , yaitu . untuk Jika ) kita (bilangan ) (‖ dan Bukti. Dengan menggunakan induksi, akan tunjukkan bahwa kesimpulan benar. Untuk ,7 yaitu , yaitu Misal . h>0 dan e>0 riil yang sangat kecil, ‖ (2.10) (2.10) .benar Kita asumsikan benar dan dan ‖sesuai berlaku , sehingga berlaku Sehingga (3.2) untuk ) )riil Misal dan bilangan riil yang sangat kecil, maka yang paling sesuai diten‖ ‖ (2.10) ) ( ) (2.10) bilangan yang sangat kecil, maka yang paling ditenMisalpaling sesuai dan ( ditentukan bilangan riil yang sangat kecil, maka paling diten‖ ‖ ( ) ‖sesuai (2.9) )(2.10) (( )) maka jk yang oleh , yang maka .‖Dari (2.4), (2.6) ‖dan ‖(2.8) didapatkan (2.10) (2.10) , maka . Dari (2.4), (2.6) dan (2.8) didapatkan ‖ ‖ berlaku , sehingga berlaku Sehingga (3.2) benar untuk Bukti.dan Dengan menggunakan kita akan tunjukkan bahwa benar. Misal dan bilangan riil yang sangat kecil, yang paling sesuai diten, Jika makasesuai .Untuk Dari (2.4), (2.6) dan Misal riil induksi, yang kecil, maka paling diten7 (2.8) didapatkan ‖ yang ‖kesimpulan . Kita benar untuk dan ,sangat yaitu .maka (bilangan ) sesuai (asumsikan )maka (2.10) tukankecil, oleh ganriilriil yang sangat kecil, maka yang paling sesuai diten-induksi,(2.10) an yang sangat yang paling ditenBukti. Dengan menggunakan kita akan tunjukkan bahwa kesimpulan benar. Untuk tukan oleh Misal dan bilangan riil yang sangat kecil, maka yang paling sesuai ditenangan yang sangat kecil, maka yang paling sesuai ditenangan riil riil yang sangat kecil, maka yang paling sesuai diten‖ (2.6), ‖ (2.8) . Kita asumsikan benar untuk , yaitu . )Jika ‖ Sehingga Jika ‖ dan . Sehingga dari , sehingga berlaku benar untuk tukan, oleh tukan oleh(2.4), ‖ dan ‖ asumsi bahwa ‖ 7 7‖ ( makadan berlaku . Dari (2.6) dan sangat (2.8) ‖ , sehingga ‖ paling ‖ , maka ‖ (3.2) ( riil ) ‖didapatkan ‖‖ (diten‖ kesimpulan bilangan yang kecil, maka yang sesuai berlaku berlaku Sehingga benar. (3.2) ‖ untuk ‖ ‖ ‖ ‖ n Misal bilangan riil oleh yang sangat kecil, maka yang paling sesuai diten) ‖ benar Bukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa Untuk tukan ) , maka . Dari{didapatkan (2.4), (2.6) dan (2.8) didapatkan (2.10) ‖ ‖ . Jika , yaitu {dan { . Kita asumsikan benar untuk 7 (2.11)benar (2.11) ‖. Sehingga ‖ . Jika Kita asumsikan benar untuk danJika ‖ , ‖yaitu tukan olehJika ( (2.11) , dari sehingga Sehingga (3.2) untuk ,,akan maka dari (2.6), (2.8) dan asumsi bah ‖ . Sehingga ‖(2.6), ‖ berlaku ‖dan ‖asumsi ) ‖. ..................................... { Jika maka b =0. Dengan demikian , makaberlaku (2.8) bahwa { k Bukti. Dengan menggunakan induksi, kita tunjukkan bahwa kesimpulan benar. Untuk Bukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan benar. Untuk (2.11) ngan riil yang sangat kecil, maka yang paling sesuai diten, maka (2.11) . Sehingga dari (2.6), (2.8) dan asumsi bahwa , maka . Dari (2.4), (2.6) dan (2.8)Jika didapatkan (2.11) {{ ‖ ‖‖ bahwa ‖ ‖ ( (2.8) ‖ dari ‖ (2.6), ‖dan) ‖ ‖asumsi ‖ ‖‖ .‖Jikadidapatkan‖ ‖ ((2.11) ) (2.8) {(2.11) , maka . Dari (2.4), (2.6) dan didapatkan {{ didapatkan . Kita asumsikan benar untuk dan , yaitu didapatkan Bukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan benar.untuk Untuk (2.11) (2.11) (2.11) ‖ ‖ ‖ ‖ berlaku , sehingga berlaku Sehingga (3.2)benar benar untuk berlakubahwa , sehingga berlaku Sehingga (3.2) didapatkan dengan dengan { ika , maka dengan . Sehingga dari (2.6), (2.8) dan asumsi 0‖ Dengan { (2.11) ‖ berlaku ‖ (2.8) ‖, sehingga ‖ Bukti. menggunakan induksi, kita akan tunjukkan bahwa kes ) ‖ . Dari (2.11) (2.4), (2.6)dari dan didapatkan ‖ Sehingga dengan Jika ( , maka , maka dengan berlaku (3.2) benar untuk Jadi kesimpulan benar untuk . dan Dengan demikian ‖‖. .Jika . Sehingga (2.6), (2.8) . Kita asumsikan benar untuk yaitu Jikaconjuga ‖ ‖ ‖dan‖ bahwa ‖ ‖‖)terbukti . Kita asumsikan benar untuk , ,yaitu ( ) ‖ ‖ bahwa ‖ metode ‖‖7‖ spectral ‖ ‖ ( ‖ ‖ ‖ ‖ ( dan ‖ asumsi ‖ ( )‖ ‖ didapatkan dengan ‖ , ‖sehingga ‖ tunjukkan bahwa ‖‖ kesimpulan ‖‖ Sehin ‖ )induksi, berlaku berlaku Bukti.benar Dengan menggunakan kita ‖akan ‖ ‖ { Jika ‖ ‖ . Kita asumsikan untuk dan , yaitu . Jika descent menghasilkan arah pencarian yang menurun, yaitu untuk seti ,maka maka Dari(2.4), (2.4), (2.6)dan dan (2.8) didapatkan ,didapatkan makapembahasan . Sehingga dari (2.6),, ) (2.8) bahwa (2.11) dengan HASIL DAN ‖ dan ‖ asumsi. .Dari ‖ ‖(2.6) ‖ (2.8) ‖ didapatkan ( AHASAN hasil dan PEMBAHASAN HASIL maka dari (2.8) dan asumsi bahwa. berlaku ‖ ‖ bahwa . Kita asumsikan untuk demikian dan ,Sehingga yaitu metode Jadi kesimpulan benar untuk Dengan terbukti berlaku ,bahwa sehingga (3.2)s 7 ‖Jika ‖PEMBAHASAN ‖ Dengan ‖ ,demikian ‖. Sehingga ‖,bahwa ‖metode ‖(2.6), ( kesimpulan )DAN Jadi benar untuk . Dengan terbukti spectral conjugate iterasinya. Bukti. menggunakan induksi, kita akan tunjukkan kesimpulan benar. Untuk maka .benar Dari (2.4), (2.6) danbenar (2.8) didapatkan Jadi kesimpulan untuk . Dengan demikian terbukti bahwa metode spectral c didapatkan HASIL DAN PEMBAHASAN HASIL DAN PEMBAHASAN algoritma metode spectral conjugate descent dengan menggunakan penBerikut adalah algoritma metode conjugate ‖dengan ‖‖menggunakan ‖untuk ‖ . Dari ‖induksi, ( spectral ) ‖ ‖ conjugate Berikut adalah algoritma metode spectral conjugate descent penN Bukti. Dengan menggunakan kita tunjukkan bahwa‖‖k ‖ ‖yaitu ‖‖‖, benar ‖bahwa ‖dan ‖‖ menurun, ‖,akan ‖‖yaitu (‖descent didapatkan ))pencarian Berikut adalah algoritma metode spectral dengan penmenghasilkan pencarian yang . Kita asumsikan maka (2.4), (2.6) dan (2.8) didapatkan ‖descent ‖ menggunakan Jika , berlaku maka . Sehingga dari ( (2.6), (2.8) dan asumsi descent arah pencarian yang menurun, yaitu untuk setiap HASILmenghasilkan DAN PEMBAHASAN ‖arah AN Dengan menggunakan garis Armijo yang termodifikasi, , sehingga berlaku Sehingga (3.2) benar untuk AN ‖ ‖ adal descent menghasilkan arah pencarian yang menurun, yaitu unt descent dengan menggunakan pencarian garis Armijo adi kesimpulan benar untuk . Dengan demikian terbukti bahwa metode spectral conjugate Berikut adalah algoritma metode spectral conjugate descent dengan menggunakan penBerikut adalah algoritma metode spectral conjugate descent dengan menggunakan penBukti. Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan benar. Untuk ‖ berlaku ‖ ‖ ‖ ng termodifikasi. (iterasinya. ‖ ‖ Seh carian garis Armijo termodifikasi. HASIL DAN PEMBAHASAN ‖ ‖ ‖ ‖, maka ‖) ‖‖ ‖ . Dari (2.4), berlaku , sehingga ametode metode spectral conjugate descent dengan menggunakan penspectral conjugate descent dengan menggunakan (yang ) ‖ ‖ penMBAHASAN carian garis Armijo yang termodifikasi. (2.6) dan (2.8) didapatkan iterasinya. didapatkan yang termodifikasi. barisan menurun. ini mengakibatkan yang oleh Algoritma SCD-M ‖dihasilkan ‖bahwa Berikut adalah algoritma metode spectral conjugate descent menggunakan penJadidengan kesimpulan benar untuk k.dan Dengan demikian . benar Kita asumsikan benar untuk dan , yaitu ma metode spectral conjugate descent dengan menggunakan penJadiyang kesimpulan untuk . Dengan demikian metode spectral conjugate tma metode spectral conjugate descent dengan menggunakan pen‖maka ‖‖. Hal ‖(2.6), ‖((2.8) ‖dan ‖asumsi (yaitu )‖‖iterasinya. Jika ,maka .Sehingga Sehingga dari(2.6), (2.8) Jika ,yang dari asumsi ‖ ‖ . Jika ‖ ‖ ‖ ‖bahwa )bahwa descent menghasilkan arahcarian pencarian menurun, untuk‖terbukti setiap berlaku , sehingga berlaku Sehingga (3.2) benar untuk Armijo yang termodifikasi. carian garis Armijo yanggaris termodifikasi. . Kita asumsikan benar untukgaris descent dan yang , termodifikas yaitu Berikut adalah algoritma metode spectral conjugate descent dengan menggunakan penAlgoritma SCD-MA difikasi. fikasi. terbukti bahwa metode spectral conjugate Dengan menggunakan pencarian Armijo alah algoritma metode spectral conjugate descent dengan menggunakan penAlgoritma SCD-MA Dengan menggunakan pencarian garis Armijo yang termodifikasi, adalah termuat di . Akibatnya terdapat suatu konstan sedemikian sehingga ‖ ‖ Jika , maka . Sehingga dari (2.6), (2.8) dan asumsi bahwa carian garis Armijo yang termodifikasi. descent menghasilkan arah pencarian yang menurun, yaitu untuk setiap , maka . Dari (2.4), (2.6) dan (2.8) didapatkan odifikasi. modifikasi. menggunakan pencarian garis Armijo yang termodifikasi, Jadi kesimpulan benar untuk .(Dengan demikian bahwa spectral conjugate didapatkan Algoritma SCD-MA didapatkan AN ‖ dan ‖ Dengan ‖metode ‖pencarian ‖ ‖‖)menurun, ‖ ‖yang ‖Jika ‖ ‖ ‖ ‖ terasinya. ) ‖terbukti ( metode . Kita asumsikan benar untuk ,terbukti yaitu .conjugate Algoritma SCD-MA Algoritma SCD-MA menghasilkan arah yaitu kesimpulan benar . Dengan demikian bahwa spectral , barisan , yang , Jadi . Pilih titik awaluntuk , maka . Dari (2.4),dari (2.6) dan (2.8) didapatkan carian garis Armijo termodifikasi. barisan yang menurun. Hal ini mengakibatkan yang dihasilkan Al Jika , maka Sehingga (2.6), danoleh asums o yang termodifikasi. yang menurun. Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA Langkah 1 : diberikan , , , . Pilih titik awal didapatkan iterasinya. Langkah 1 : diberikan , , , . Pilih titik awal Algoritma SCD-MA ‖ ‖ Hal Langkah 1 menghasilkan : diberikan (3.3)S barisan yang menurun. ini mengakibatkan yang dihasilkan oleh Algoritma descent arah yang termodifikasi, menurun, yaitu untuk setiap ma metode spectral conjugate descent dengan menggunakan penuntuk setiap iterasinya. Dengan menggunakan pencarian garispencarian Armijo yang adalah , maka . Dari (2.4), (2.6) dan (2.8) didapatkan ‖ ‖ ‖ ‖ ‖ ‖ ( ) ‖ ‖ ‖. Akibatnya ‖ titik ‖awal ‖spectral ‖ ‖‖(2.8) ‖ ‖asumsi ‖ sehingga ‖maka ‖‖. Sehingga ‖(2.6), ‖dan descent pencarian untukkonstan setiap ) 1kesimpulan : terdapat diberikan , . Dengan , (. (yang , awal .‖Pilih Langkah 1 ,:maka diberikan , menghasilkan ,untukarah , Pilih titik )yaitu Jadi benar demikian terbukti bahwa metode conjugate termuat di terdapat suatu sedemikian Algoritma didapatkan Jikamenurun, ,termodifikasi, dari bahwa ‖ ‖ MA di, Langkah konstan sedemikian sehingga stop. Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga , SCD-MA ,. Akibatnya . Pilih titik awal , ., Jika , termuat . ,Pilih Pilih titik awal titik awal 0. Set pencarian garis yang adalah ‖suatu Set Hal .Dengan Jika termuat di . Akibatnya suatu konstan sedemikian ‖unt‖ ‖, maka ‖, stop. .: Set ,titik .‖Jikadihasilkan , maka Langkah 1 ini ,menggunakan , stop. .Armijo Pilih titik awal barisan yang oleh Algoritma SCD-MA odifikasi. ,, yang menurun. ,.,iterasinya. ,diberikan .iterasinya. awal ,mengakibatkan . Pilih Pilih titik awal ‖ terdapat ‖ ‖ ‖( ‖) ‖ ‖ ‖sehingga ‖ ‖ ( ) Dengan menggunakan pencarian garis Armijo yang ‖ ‖ arah pencarian yang menurun, yaitu setiap ‖Jadi ‖,kesimpulan ‖,Jikamenurun. didapatkan ‖benar ‖ untuk ‖ (2.8) ‖(3.3) ‖terbukti ‖untuk . Jika ,semua maka stop. . Set(2.11) , . Setdescent , ,maka stop. (dan ) .menggunakan Jikamemenuhi maka stop. berlaku pada dan cari yang (2.9) (2.10). 1 Langkah :, diberikan ,‖menghasilkan . yang Pilih titik awal maka . memenuhi Sehingga (2.6), dan asumsi bahwa barisan Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA untuk .Dengan Dengan demikian terbukti bahwa spectral conjugate ikan , yang .pencarian Pilih titik awal Jadi kesimpulan benar .dari metode Dengan garis Armijo yang termodifikasi, adalah ‖kan ‖ ‖Langkah ‖metode ‖ spectral ‖ ‖conjugate ‖ 2 : , menentukan pada (2.11) dan cari (2.9) dandemikian (2.10). (dan , maka stop. , maka stop. di ., Akibatnya terdapat suatu sedemikian sehingga 2 : konstan menentukan pada (2.11) dan cari yang memenuhi (2.9) (2.10).bahwa termodifikasi, {f(x )}termodifikasi, adalah barisan yang).menurun. Hal ‖ ‖ . Set , . Jika , maka stop. k aermuat stop. Dengan menggunakan pencarian garis Armijo yang adalah Langkah 2Langkah : menentukan j pada (2.11) dan cari a a ‖‖ ‖‖Langkah , maka maka stop. Jika , maka Sehingga dari (2.6),conjugate (2.8) dan asum (3.4) k k cari iterasinya. Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemik ‖ ‖ Jadi kesimpulan benar untuk . Dengan demikian terbukti bahwa metode spectral Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga untuk Langkah 2 : menentukan pada (2.11) dan yang memenuhi (2.9) dan (2.10). 2 : menentukan pada (2.11) dan cari yang memenuhi (2.9) dan (2.10). dan .(2.9) maka stop. didapatkan termuat di(2.10). Akibatnya terdapat suatu sedemikian sehingga descent menghasilkan arah pencarian yang menurun, untuk setiap descent arah pencarian yang yaitu setiap ini mengakibatkan {xkSCD-MA }menurun, yang dihasilkan olehkonstan Algoritma barisan yang menurun. Hal ini mengakibatkan yang konstan dihasilkan oleh Algoritma Asumsi SCD-MA juga mengakibatkan terdapat sedemikian ‖Jika ‖ ‖suatu ‖ ‖‖‖ ‖‖ untuk ‖ ‖sehing . Set ,yang .memenuhi Jika ,. dan maka stop. (maka )yaitu Langkah 3 :,memenuhi misal dan . Jika stop. ‖cari ada(2.11) dan cari (2.9) (2.10). da dan dan (2.10). yang memenuhi (2.9) dan . Jika ,yang maka stop. Jika , maka .menghasilkan Sehingga dari (2.6), (2.8) dan asumsi bahwa Langkah 3.‖barisan :Pilih misal dan .(2.9) Jika maka stop. (3.3) ,(2.11) , ‖cari titik awal yang menurun. Halpencarian ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA Langkah 2 : menentukan pada (2.11) dan cari yang memenuhi dan (2.10). pada (2.11) dan yang memenuhi (2.9) dan (2.10). Jadi kesimpulan benar untuk . Dengan demikian terbukti bahwa didapatkan pada (2.11) dan cari yang memenuhi (2.9) dan (2.10). Dengan menggunakan garis Armijo yang termodifikasi, adalah semua berlaku SCD-MA termuat di W. Akibatnya terdapat suatu ‖ ‖ semua Lemma 3.2.sehingga Misalkan SCD-MA berlaku. Maka descentdan menghasilkan arah maka pencarian yang menurun, yaitu untuk setiap met Langkah 3 i:tentukan . Asumsi Jikastop. maka stop. Langkah 3termuat :gmisal dan Jika n kmengakibatkan aberlaku h4di :maka m smisal a(2.11) loleh d a.maka nsemua oleh (2.7) dan oleh (2.8), oleh (2.6). iterasinya. iterasinya. .Jika terdapat suatu konstan sedemikian berlaku (3.3) ‖ ‖ Langkah 2LLangkah :ajuga menentukan pada dan cari yang memenuhi (2.9) dan (2.10). Asumsi SCD-MA terdapat suatu konstan sedemikian sehingga untuk : 3tentukan (2.7) dan oleh (2.8), tentukan oleh (2.6). dan pada .Akibatnya Jika maka stop. didapatkan dan . cari maka stop. entukan (2.11) dan yang memenuhi (2.9) dan (2.10). ‖ ‖ ‖ ‖ ‖ ‖ ( ) Langkah 4 : tentukan oleh (2.7) dan oleh (2.8), maka tentukan oleh (2.6). konstan f* sedemikian sehingga termuat di . Akibatnya terdapat suatu konstan sedemikian sehingga (3.5) Langkah 3 : misal dan . Jika maka stop. descent menghasilkan pencarian yang yaitu Jadi kesimpulan benar untuk . arah Dengan demikian terbukti metode spect .. Jika maka stop. ‖ ‖ dan ‖ menurun, ‖ bahwa dan Jika maka stop. barisan yang menurun. Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA , maka stop. maka stop. ‖(3.4) ‖Armijo ‖dan ‖ tentukan iterasinya. dan Langkah 4 : tentukan (2.7) oleh (2.8),suatu maka tentukan oleh (2.6). Asumsi SCD-MA juga mengakibatkan terdapat konstan sedemikian sehingga Langkah 4langkah : tentukan oleh (2.7) dan oleh (2.8), maka oleh (2.6). Dengan menggunakan pencarian garis garis Armijo yang termodifikasi, termodifikasi, adalah ‖ ‖ adalah , kembali ke 2. Dengan menggunakan pencarian yang ( )‖‖ ‖ ‖untuk emua (3.3) Langkah 3Langkah : (2.8), misal dan . Jika maka stop. Langkah 5 : set , kembali ke langkah 2. danberlaku oleh maka tentukan oleh (2.6). 7) dan oleh (2.8), maka tentukan oleh (2.6). l2.7) dan . Jika maka stop. : tentukan tentukan bkoleh oleh (2.7) dan jkoleh (2.8), 5 : set , kembali ke langkah 2.tentukan ‖ ‖ iterasinya. descent menghasilkan arah yang menurun, yaitu Langkah 44Langkah :Misalkan (2.7) dan oleh (2.8), maka oleh (2.6). ‖ konstan ‖ Dari ‖ sedemikian ‖demikian ‖ bahwa ‖pencarian ‖ yang ‖spectral ((2.6). )Dengan (3.3) termuat di .Jadi Akibatnya terdapat suatu hhpada (2.7)(2.11) dan oleh (2.8), maka tentukan oleh Lemma 3.2.sehingga Misalkan Asumsi SCD-MA berlaku. Maka dan oleh maka tentukan oleh (2.6). .................................................... (3.3) dan cari yang memenuhi (2.9) dan (2.10). Bukti. (3.3) kita dapatkan pencarian garis Armijo termodifikasi, adalah Lemma 3.2. SCD-MA Maka kesimpulan benar untuk .menggunakan Dengan terbukti metode conjugate semua berlaku barisan yang menurun. Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA barisan yang menurun. Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA (3.4) Langkah : set , berlaku. kembali ke langkah 2. n (2.7) global Algoritma SCD-MA akan dibuktikan dengan Langkah 5Asumsi :(2.8), set ,5Asumsi kembali ke langkah 2.menggunakan Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. Maka SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga untuk maka tentukan d oleh (2.6). ‖ ‖ k Langkah 4 : tentukan oleh (2.7) dan oleh (2.8), maka tentukan oleh (2.6). Kekonvergenan global Algoritma SCD-MA akan dibuktikan dengan menggunakan mbali ke langkah 2. bali ke langkah 2. kan oleh (2.7) dan 5oleh maka,tentukan oleh (2.6). Jadi kesimpulan benar untuk . Dengan demikian terbukti m Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga Kekonvergenan global Algoritma SCD-MA akan dibuktikan dengan menggunakan (3.5) Dengan menggunakan pencarian garis Armijo yang bahwa termodi iterasinya. ‖dihasilkan ‖(3.4) dan Langkah set(2.8), kembali ke langkah ‖ maka ke langkah 2. ‖(3.3) ‖ untuk kembali kedan langkah 2. 5berlaku barisan menurun. Hal mengakibatkan oleh Algoritma SCD-MA dan descent menghasilkan arah pencarian yang yaitu untuk setiap . global Jika stop. Langkah :: set k=k+1, kembali ke‖global langkah 2. ‖Asumsi ‖inimenurun, termuat diyang Akibatnya terdapat suatu konstan sedemikian sehingga termuat di2. . .Akibatnya terdapat suatu konstan sedemikian sehingga ‖spectral ‖yang conjugate t.embali 3.2. dan semua Kekonvergenan Algoritma SCD-MA akan dibuktikan dengan menggunakan Kekonvergenan Algoritma SCD-MA akan dibuktikan dengan menggunakan Jadi kesimpulan benar untuk . Dengan demikian terbukti bahwa metode SCD-MA juga mengakibatkan terdapat Lemma Misalkan Asumsi SCD-MA berlaku. Maka ∑( )pencarian ∑( )termodifikasi, Langkah 5 asumsi-asumsi : set , kembali ke langkah 2. SCD-MA akan berikut. Algoritma SCD-MA akan dibuktikan dengan menggunakan Algoritma SCD-MA akan dibuktikan dengan menggunakan descent menghasilkan pencarian yang menurun, yaitu , kembali keDari langkah 2. semua berlaku asumsi-asumsi berikut. barisan yang menurun. Halarah ini mengakibatkan dihasilkan ole Dengan menggunakan garis Armijo yangyang Kekonvergenan global Algoritma Bukti. Dari (3.3) kita dapatkan Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga untuk Kekonvergenan global Algoritma SCD-MA dibuktikan dengan menggunakan Bukti. (3.3) kita dapatkan termuat .akan Akibatnya terdapat suatu konstan sedemikian sehingga al(2.7) Algoritma SCD-MA akan dibuktikan dengan menggunakan iterasinya. (3.4) bal Algoritma SCD-MA akantentukan dibuktikan dengan menggunakan suatu konstan M>0 sedemikian sehingga untuk semua dan oleh (2.8), maka oleh (2.6). Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. Maka (3.5) ‖ di‖ yang Bukti. Dari (3.3) kita dapatkan ‖ ‖ asumsi-asumsi berikut. asumsi-asumsi berikut. descent menghasilkan arah pencarian menurun, yaitu untuk setiap (3.3) ‖ ‖ (3.3) dan (3.4) dibuktikan dengan menggunakan asumsi-asumsi Kekonvergenan global Algoritma SCD-MA akanmenggunakan dibuktikanbarisan iterasinya. ‖ yang ‖menggunakan Asumsi SCD-MA genan global Algoritma SCD-MA akan dibuktikan dengan termuat di . yang Akibatnya terdapat (3.5) suatu konstan sedemikian menurun. Hal initermodifikasi, mengakibatkan yang dihasilkan olehsehingga Algorit k dengan berlaku Asumsi SCD-MA semua berlaku asumsi-asumsi berikut. Dengan menggunakan pencarian garis Armijo adalah ‖ ‖ juga dan embaliDari ke langkah 2.dapatkan (3.3) Asumsi SCD-MA juga mengakibatkan terdapatsuatu suatu konstan sedemikian sehinggauntuk untuk ( ) sehingga Asumsi SCD-MA mengakibatkan terdapat konstan sedemikian berikut. Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. Maka terbatas di mana adalah titik awal. iterasinya. Asumsi SCD-MA Asumsi SCD-MA Bukti. (3.3) kita ∑( ) ∑( ) ∑( ) ∑( ) Dengan menggunakan pencarian garis Armijo yang (3.4) Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. asumsi-asumsi berikut. 1. Level terbatas dimengakibatkan mana adalah titik awal. termuat di .................................................................. Akibatnya terdapat suatu konstan∑( sedemikian sehingga rikut. ‖ mengakibatkan ‖ Maka ∑( )untuktermo 1.set LevelBukti. set di mana adalah titik awal. (3.5) Asumsi SCD-MA juga terdapat suatu konstan sedemikian (3.4) sehingga barisan yang menurun. Hal ini terbatas yang dihasilkan oleh) Algoritma SCD-MA Asumsi SCD-MA Dari (3.3) kita dapatkan semua berlaku semua berlaku ‖ ‖ al Algoritma SCD-MA akan dibuktikan dengan menggunakan dan Dengan menggunakan pencarian garis Armijo yang termodifikasi, adalah ngsi objektif memenuhi kondisi Lipschitz, yaitu terdapat L > 0 Asumsi 1. Level set dititik mana titik awal.Hal ini mengakibatkan 1. Level set SCD-MA terbatas di mana adalah awal. adalah (3.5) ‖ berlaku. ‖terbatas barisan yang menurun. yang dihasilkan dan 2. Gradient dari fungsi objektif memenuhi kondisi Lipschitz, yaitu terdapat L > 0 L > 0 terdapat suatu konstan Asumsi SCD-MA juga mengakibatkan sedo terbatas mana adalah titik awal. terbatas didi mana adalah awal. A Asumsi SCD-MA Lemma 3.2. Misalkan Asumsi SCD-MA Maka 2. Gradient dari fungsi objektif memenuhi kondisi Lipschitz, yaitu terdapat (3.4)) (3.4) semua berlaku ∑( ) titik ∑( )di mana termuat di . Akibatnya terdapat suatu konstan sedemikian sehingga 1. Level set terbatas adalah titik awal. ‖ ‖ 1. Level set terbatas; ( ‖ ‖ terbatas di mana adalah titik awal. terbatas di mana adalah titik awal. Bukti. Dari (3.3) kita dapatkan ( ) barisan yang menurun. Hal ini mengakibatkan yang dihasilkan oleh Algoritma SCD-MA gga untuk ∑ Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. ( ) Dengan demikian . Sedangkan dari (2.9) didapatkan Gradient dari fungsi objektif memenuhi kondisi Lipschitz, yaitu terdapat L > 0 2. semua Gradient dari2.berlaku fungsi objektif memenuhi kondisi Lipschitz, yaitu terdapat L > 0 ( ) (3.5) suatu termuatjuga di mengakibatkan . Akibatnya terdapat Bukti. Dariterdapat (3.3) kita ∑(Ldapatkan )berlaku ) semua berlaku (3.4) sehing Asumsi SCD-MA terdapat suatukonstan konstan sedemikian sedemikian s Level set kondisi terbatas adalah titik∑( awal. ‖ sehingga untuk semua ektif1.memenuhi memenuhi kondisi Lipschitz, yaitu terdapat L>di>awal. 0berlaku ktif 0‖mana x1sedemikian adalahLipschitz, titik awal. dan terbatas diyaitu mana adalah titik sedemikian sehingga untuk semua Maka Lemma 3.2. Misalkan Asumsi SCD-MA berlaku.Maka Maka 2. Gradient dari fungsi objektif memenuhi kondisi Lipschitz, yaitusehingga terdapat L‖ >‖ 0 Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. (3.3) bjektif memenuhi kondisi Lipschitz, yaitu terdapat LL >>suatu 0(3.1) objektif memenuhi kondisi Lipschitz, yaitu terdapat 0 termuat di . Akibatnya terdapat konstan sedemikian ‖2. ‖ ‖ ‖ sedemikian sehingga untuk semua berlaku sedemikian sehingga untuk semua Gradien dari fungsi objektif ∑ ‖> ‖0 ) (3.1) ∑ ( ( berlaku ( kitamemenuhi )kondisi ‖ ) ‖ (3.5) semua berlaku ‖SCD-MA ‖3.2. ∑( )Lemma ∑( )suatu 2. Gradient dari fungsi objektif memenuhi kondisi Lipschitz, Bukti. Dari Lipschitz, (3.3) dapatkan semua berlaku berlaku (3.5) iemua fungsi objektif memenuhi kondisi yaitu terdapat L‖ >‖yaitu 0 ‖Asumsi Misalkan berlaku. ‖juga ‖ terdapat Asumsi mengakibatkan terdapat sedemikian (3.1)sehingga. ..untuk ‖‖ ‖‖Lkonstan ‖SCD-MA dan ( Maka dan dan (3.5) sedemikian sehingga untuk semua berlaku Lipschitz, yaitu terdapat L > 0 sedemikian uk semua berlaku ∑( ) ∑( ) uk semuayangDengan berlaku terbatas di mana adalah titik awal. ∑ ( ) ) teorema menunjukkan bahwa Algoritma SCD-MA menghasilkan Dengan demikian . Sedangkan dari (2.9) dida (3.3) ) ‖ ‖. Sedangkan demikian ∑ ( dari didapatkan ‖ (2.9) ‖ ‖ ‖ ‖ Ini mengakibatkan ‖Dengan (3.1) (3.1) Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan (3.5) ‖ berlaku. ‖ dari ∑ Misalkan demikian . Sedangkan (2.9) didapatkan ∑Lemma ‖dan Asumsi ∑) SCD-MA dan . Maka Berdasarkan (3.2), keds ‖sehingga ‖ semua untuk semua berlaku ‖ ‖ sedemikian ‖sehingga ‖ ‖ untuk ‖berlaku ‖ 3.2. ‖(‖ SCD-MA Berikut adalah teorema yang menunjukkan bahwa Algoritma SCD-MA menghasilkan (3.1) (3.1) berlaku hingga untuk semua semua berlaku Berikut adalah teorema yang menunjukkan bahwa Algoritma menghasilkan Bukti. Dari (3.3) kita dapatkan Bukti. Dari (3.3) kita dapatkan ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ (3.1) Asumsi SCD-MA juga mengakibatkan terdapat suatu konstan sedemikian sehingga untuk ‖ ‖ ‖ ‖ (3.1) (3.1) bjektif memenuhi kondisi yaitu terdapat Lbahwa >menunjukkan 0 Algoritma menurun. ) ∑( ) )∑ )Dari ‖ ‖ berlaku. Bukti. (3.3) kita dapatkan adalahLipschitz, teorema SCD-MA menghasilkan (semua )‖ ∑ ( (3.4) ) berlaku Berikut‖yang adalah bahwa Algoritma SCD-MA menghasilkan ‖ Maka ∑Berikut ‖ menunjukkan ‖ teorema ∑‖ yang (pencarian )∑( ( ‖ ((2.9) dan Lemma Misalkan Asumsi deret tersebut adalah sehingga adalah deret )yang menuru ∑ ( arah )yang ‖didapatkan ( 3.2.deret ) ‖ ‖SCD-MA Dengan demikian dari Bukti. Dari (3.3) kita ‖ nonnegative ‖(3.1) ∑ arah yang ( dapatkan ) ∑ deret ( tersebut yangmenunjukkan menunjukkan bahwa Algoritma SCD-MA menghasilkan yang Algoritma SCD-MA menghasilkan ‖ bahwa ‖ menurun. ‖berlaku ‖. Sedangkan (3.1) pencarian menurun. semua Berikut adalah teorema yang menunjukkan bahwa Algoritma SCD-MA menghasilkan . ............................ (3.1) ma yang menunjukkan bahwa Algoritma SCD-MA masemua yang menunjukkan bahwa Algoritma SCD-MA menghasilkan uk berlaku danarah dihasilkan oleh Algoritma SCD-MA, maka ∑menghasilkan ( ∑ )∑( demikian Sedangkan dari didapatkan arahmenurun. pencarian yang pencarian yang ‖ ‖ ‖ ‖ dan dan ∑ Bukti. Dari kita dapatkan ‖ )(3.3) ‖∑kedua ∑( )(2.9) ∑( ∑( )) . ‖ ‖ Dengan demikian dan mengakibatkan . Berda ∑Dengan ‖( menurun. ‖ menunjukkan Ini mengakibatkan dan ..Ini Berdasarkan Lemma 3.2. Misalkan Asumsi SCD-MA Maka Berikut adalah teorema yang menunjukkan bahwa Algoritma SCD-MA menghasilkan Teorema 3.1. Misal dan dihasilkan oleh Algoritma maka Berikut adalah teorema yang bahwa (3.4) (Algoritma ) maka dalah teorema yang menunjukkan bahwa Algoritma SCD-MA menghasilkan ∑ ‖ ‖ ∑ ( ) ) Ini ∑ (3.2), ‖ ‖ ∑ Teorema 3.1. Misal dan dihasilkan oleh SCD-MA, mengakibatkan dan . Berdasarkan (3. ‖SCD-MA, ‖berlaku. arah pencarian yang menurun. n. n. ‖ Teorema ‖ ‖ ‖ ‖ ‖ (3.2) (3.1) ∑( ) ∑( ) Lemma 3.2. Misalkan Asumsi SCD-MA berlaku. Maka ∑ (3.5) Teorema 3.1. Misal dan dihasilkan oleh Algoritma SCD-MA, maka ( ) Bukti. Dari (3.3) kita dapatkan 3.1. Misal dan dihasilkan oleh Algoritma SCD-MA, maka Algoritma SCD-MA menghasilkan arah pencarian Dengan demikian . Sedangkan (2.9)deret didapatkan tersebut deret nonnegative sehingga deret tersebut adalah der ∑ deret ‖deret ‖ )tersebut ∑‖ ‖dari ( maka (‖ deret ) (3.2) deret tersebut adalah nonnegative yangadalah menurun. dan ‖ arah pencarian yang menurun. dihasilkan oleh Algoritma SCD-MA, maka dihasilkan oleh Algoritma SCD-MA, ngmengakibatkan menurun. ∑sehingga ( SCD-MA )adalah deret tersebut nonnegative sehingga adalah deret yang ‖. Sedangkan ‖adalah Dengan demikian dari (2.9) didapatkan (3.2)))deret)tersebut ∑( Lemma 3.2. Misalkan Asumsi berlaku. Maka ∑ ‖SCD-MA, ∑ dan . Berdasarkan (3.2), kedua (( ∑( Teorema 3.1.‖ Misal dan oleh Algoritma SCD-MA, makaderet yang menurun. nni yang dihasilkan oleh Algoritma maka an dihasilkan oleh Algoritma SCD-MA, maka dihasilkan ‖ ‖ ma menunjukkan bahwa Algoritma SCD-MA menghasilkan dan ‖ ‖ ‖ ‖ (3.2) ‖ ‖ (3.2) Dengan demikian dan . ‖ Dengan demikian dan . ∑ ‖ ‖ ∑ (‖ ‖ ‖ oleh (‖‖dapatkan ) Bukti. Dari kita (3.5)kedua ∑) (3.3) ‖ ∑demikian mengakibatkan dan .‖Berdasarkan 3.1. dihasilkan Misal dihasilkan Algoritma maka ‖ danIni (3.2) (3.2) . (‖)(3.2)dan(3.2), ) ∑( sal Teorema dan adalah maka dan ∑ oleh ∑((3.3) ) ) deret tersebut deret nonnegative sehingga deret adalah yang (tersebut )Dengan dariDari (2.9) didapatkan ∑ demikian ‖ ‖SCD-MA, ‖deret ∑ ( SCD-MA, )‖ (menurun. ‖ . Sedangkan ‖‖ Dengan ‖‖ Algoritma (3.2) (3.2) Bukti. kita dapatkan n. Teorema 3.1. Misal {g } dan {d } dihasilkan oleh ( ) k k deret tersebut adalah deret nonnegative sehingga deret tersebut adalah deret yang menurun. ‖ ‖ ∑ dan ‖ dapatkan (3.2) Ini mengakibatkan dan ∑ . . Berdasarkan (3.2), kedua ‖ (3.3) ‖ ‖ kita (3.2) Dari ‖ ∑ ‖Bukti. Dengan demikian ‖ ∑( ‖‖demikian ∑()) ) . .Berdasarkan ) dari (maka ) ‖ ∑ ∑∑( dan Algoritma SCD-MA, ∑Dengan Ini mengakibatkan (3.2), kedua (( ∑ ) n dihasilkan oleh Algoritma SCD-MA, maka Dengan .Sedangkan Sedangkan dari(2.9) (2.9) didapatkan demikian didapatkan

nisikan

( ) ‖ ‖deret dan Dengan demikian . deret tersebut adalah deret nonnegative sehingga tersebut deret yang menurun. ∑( ) ∑( ∑ adalah ( deret tersebut adalah ) Dengan demikian sehingga . deret Sedangkan dari (2.9) didapatkan deret tersebut ∑adalah deret nonnegative yang menurun. ‖ Ini ‖ mengakibatkan (3.2) ‖ ‖ ∑ . Berdasarkan (3.2), kedua )) ∑∑ (( ‖‖ ‖‖)) ∑∑ (() (3.2))dan D e n∑( ‖ ‖ ∑( dan Dengan demikian . ................................................... (d e mdemikian ) g. a n i k i a7n ∑ ) ( , Dengan .. Sedangkan dari (2.9) 7 ‖ ‖ Dengan demikian dan . ∑ ‖ ‖ ∑ ( ) ( ) 7 deret tersebut adalah deret nonnegative sehingga deret tersebut adalah deret yang menurun. ( (3.2), ) sedangkan dari (2.9) didapatkan ‖ ‖ ∑ ‖ ‖ ∑ Inimengakibatkan mengakibatkan∑∑Dengan dan . Berdasarkan (3.2), kedua Ini dan . Berdasarkan kedua 7demikian dari (2.9) didapatk ∑ ‖ )‖ ) . Sedangkan ∑ ( Bukti. Dengan menggunakan induksi, kita akan ( ∑) ( ( 7 ‖ mengakibatkan ‖ menggunakan Dengan demikian dan kesimpulan .tunjukkan Bukti. Dengan menggunakan induksi, kita akanderet tunjukkan bahwa Untuk ‖benar. ‖akan Ini dan ∑deret . Berdasarkan (3.2), kedua Bukti. Dengan induksi, kita bahwa kesimpulan benar. Untuk deret tersebut adalah∑deret deret nonnegative sehingga deret tersebut adalah deretyang yang menurun. tersebut adalah nonnegative sehingga tersebut adalah deret menurun. tunjukkan bahwa kesimpulan benar. Untuk k=1 Bukti. Dengan menggunakan induksi, kita akan tunjukkan Untuk ∑ ‖ (2.9) ‖ )didapatkan ∑‖ ( ∑ ( bahwa kesimpulan ( ) Inibenar. ) Dengan demikian . Sedangkan dari ∑ ‖ ∑ mengakibatkan dan .B ‖ ‖ Dengan menggunakan induksi, kita akan tunjukkan bahwa kesimpulan benar. Untuk berlaku , sehingga berlaku Sehingga (3.2) benar untuk berlaku d 1=g 1, benar. sehingga . adalah deret demikian tersebut deret‖‖berlaku nonnegative sehingga tersebut .adalah yang menurun. ‖∑ deret ‖ ( Sehingga berlaku , sehingga (3.2) benar ‖benardan n tunjukkan bahwa kesimpulan Untukberlaku Dengan demikian dan . )deret untuk demikian . Sedangkan dari (2. ‖ ‖ Sehingga berlaku , sehingga berlaku Dengan (3.2)‖Dengan untuk demikian, untuk k=1. Kita ‖ deret ‖ )nonnegative tersebut tersebut adalah ∑benar ‖)benar ‖Ini).untuk ∑ deret (∑ mengakibatkan dan ∑ . sehingga . Berdasarka ‖ dan ‖( Sehingga berlaku ‖ ‖Dengan , sehingga berlaku (3.2) benar ‖∑ Dengan demikian Sedangkan dari didapatkan . Kita asumsikan benar(3.2) untuk , yaitu .(2.9) Jikaadalah ‖‖ ( ‖dan Dengan demikian dan ‖ ‖ .deret untuk , yaitu Jika (3.2) benar untuk ‖∑ . Sehingga Kita asumsikan benar untukk-1 dan dan. Kita asumsikan ,, yaitu ‖ ‖ ) ∑ ( asumsikan benar untuk yaitu (‖ . Jika ‖ sehingga ‖ Dengan demikian dan deret tersebut adalah deret nonnegative deret tersebut adalah deret. y Kita asumsikan benar ,untuk , yaitu maka ‖∑ dan Dari (2.6) dan ‖ (2.8) didapatkan ∑,, maka ∑ (2.6) mengakibatkan . Berdasarkan (3.2), kedua ‖maka ) ‖∑‖ ‖ (‖ . Jikadan ) ‖( .. Jika (2.4), dan (2.8) didapatkan , yaitu J iIni k (2.4), a(2.4), , maka . Dari (2.6) dan (2.8) didapatkan . Dari ‖ ‖ ∑ Ini demikian mengakibatkan dan Ini mengakibatkan‖ ∑ ‖ dan . Dengan dan . , maka (2.8) didapatkan Dari(2.4), (2.4),(2.6) (2.6)dan dan (2.8) didapatkan deret tersebut adalah sehingga deret tersebut adalah deret yang menurun. dan (2.8) didapatkan . Dari ‖ ‖deret nonnegative ∑ Ini dan . Berdasarkan (3.2), kedua Berdasarkan (3.2), kedua deret ‖ ‖ ‖ ‖ ( mengakibatkan)∑‖ ‖ ‖ ‖ nonnegative ‖ ‖ ‖sehingga deret tersebut ada ( deret adalah deret ‖ ‖ ‖) ‖ tersebut ( ‖‖ ‖ ‖tersebut Dengan) demikian dan‖ adalah . deretderet nonnegatif sehingga deret deret tersebut adalah deret nonnegative sehingga deret tersebut adalah yang menurun. ‖ ‖ ‖ ‖ ‖ ‖ ( ) ‖ ‖ ‖, maka ‖ Dengan demikian dan . Jika ‖ ‖ . Sehingga (2.6), (2.8), dan asumsi bahwa Jikadari . Sehingga dari (2.6), (2.8) dan asumsi bahwa ‖ ‖(2.8) maka Dengan demikian danasumsi bahwa . Jika , maka . Sehingga dari (2.6), dan , maka . Sehingga dari (2.6), (2.8)didapatkan dan asumsi bahwa (2.6), (2.8)didapatkan dan asumsi bahwa didapatkan patkan ‖ ‖ ‖ ‖) ‖ ‖‖ ‖ ‖ ‖ ( )‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ( ‖ ‖ ‖ ‖ ( )‖ ‖ ‖ ‖ ‖ ‖ ( ) ‖ ‖‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖benar Jadi kesimpulan untuk . Dengan Jadi demikian terbuktibenar bahwa metode spectral conjugate kesimpulan untuk . Dengan demikian terbukti bahwa metode spectral conjugate Jadi kesimpulan benar untuk . Dengan demikian terbukti bahwa metode spectral conjugate esimpulan benar untuk . Dengan demikian terbukti bahwa metode spectral conjugate ‖ ‖ descent menghasilkan arah pencarian yang menurun, yaitu untuk setiap ‖ ‖ untuk setiap descent menghasilkan menurun, an terbuktidescent bahwa menghasilkan metode spectral conjugate ‖ ‖ yang arah pencarian yang menurun, yaitu arah pencarian untuk setiap yaitu

Dengan Dengandemikian demikian∑∑ (( ∑∑

((

46

Ini Inimengakibatkan mengakibatkan∑∑

))

‖‖ ‖‖ )) ∑∑ (( ‖‖ ‖‖

‖

. .Sedangkan Sedangkandari dari(2.9) (2.9)didapatkan didapatkan

dan dan∑∑

Kita )) definisikan

‖ kedua ‖kedua ‖ {‖(3.2), . .Berdasarkan Berdasarkan (3.2),

‖

Sains & Mat, Vol. 2 No. 2, April 2014: 42–48

‖

‖

}. Maka dapat kita simpulkan bahwa

deret deret nonnegative sehingga deret adalah deret yang deret tersebut tersebut adalah adalah deret nonnegative sehingga deret tersebut tersebut deret yang menurun. untuk semua .menurun. tersebut adalah deret yang menurun. Denganadalah demikian Lemma 3.4. Misal asumsi SCD-MA berlaku, {xk} ‖‖ ‖‖ Dengan dan . .. dan {gk} dihasilkan oleh algoritma SCD-MA. Oleh Dengandemikian demikian dan dan Lemma 3.4. Misal asumsi SCD-MA berlaku, dan dihasilkan oleh alg karena itu, terdapat suatu konstan M2>0 sedemikian MA. Maka terdapat suatu konstan sedemikian sehingga untuk semua b sehingga untuk semua k berlaku Kedua sifat ini sangat penting untuk menunjukkan kekonvergenan global Algoritma Kedua SCD-MA. ‖ ‖ sifat ini sangat penting untuk menunjukkan kekonvergenan global Algoritma SCD-MA. (3.7) .......................................................... (3.7) ng untuk menunjukkan kekonvergenan global Algoritma kekonvergenan SCD-MA. Kedua sifat ini sangat penting untuk menunjukkan global Algoritma SCD-MA. ‖ ‖ Lemma 3.3. Misal Asumsi SCD-MA berlaku. Jika ada suatu konstan sedemikian sehingga nunjukkan kekonvergenan global Algoritma SCD-MA. Lemma 3.3.untuk Misal Asumsi SCD-MA berlaku. Jika ada Kedua sifat ini sangat penting menunjukkan kekonvergenan global Algoritma SCD-MA. SCD-MA berlaku. Jika ada suatu konstan sedemikian Lemma 3.3. Misal Asumsi SCD-MA berlaku. Jika ada sehingga suatu konstan sedemikian sehingga suatu konstansedemikian e>0 sedemikian sehingga untuk semua ‖ untukkonstan semua berlaku ‖ sehingga , maka terdapat suatu konstan sedemikian seerlaku. Jika ada suatu konstan 3.3. Misalterdapat Asumsisuatu SCD-MA berlaku.sehingga Jika sedemikian ada suatu sedemikian ‖Lemma ‖ ku , maka se-konstan 9 Bukti. (3.7) ‖ global enting menunjukkan kekonvergenan Algoritma SCD-MA. untuk semua berlaku ‖konstan maka terdapat suatu sedemikian se- dapat dibuktikan pada beberapa kasus k>1 berlaku , maka terdapat suatu konstan untuk semua berlaku , Kedua maka terdapat suatu penting konstan sedemikian se- hingga sifat ini sangat untuk menunjukkan kekonvergenan global Algoritma SCD-MA. ‖ ‖ untuk semua berlaku , maka terdapat suatu konstan sedemikian seberikut. MJika sedemikian sehingga untuk semua k berlaku lakuSCD-MA 1>0 ada msi berlaku. suatu sehingga hingga untuk semua berlaku Kedua sifat inikonstan sangat penting sedemikian untuk menunjukkan global Algoritma SCD-MA. ‖ ‖ Bukti. Kitakekonvergenan akansedemikian membuktikan (3.7) dengan memperhatikan berikut ini.beberapa Kita akan membuktikan (3.7)beberapa dengan kasus memperhatikan (3.6) 9 kasus b Lemma 3.3. Misal Asumsi SCD-MA berlaku. Jika ada suatu konstan sehingga hingga untuk semua berlaku sifat ini sangat penting kekonvergenan global SCD-MA.Bukti. ‖ untuk ‖ menunjukkan (3.6)Algoritma ‖ ‖ rlaku ‖ ‖ , maka terdapat suatu konstan sedemikian se................................................................. (3.6) (3.6) Kasus 1. a =1. Berdasarkan (3.2) kita peroleh Lemma 3.3.ini Misal Asumsi SCD-MA berlaku. Jika kekonvergenan ada suatu konstan sehingga(3.2) ksedemikian Kedua sifat penting menunjukkan global Algoritma SCD-MA. ‖ ‖kita‖peroleh ‖. Untuk Kasus 1. . Berdasarkan (3.2) kita peroleh Kasus 1.se. Berdasarkan Bukti. Untuk kita peroleh sehingga , jika ‖ ‖Asumsi SCD-MA ‖berlaku. ‖ sangat semua berlaku , k=1 terdapat sedemikian (3.6) ‖ untuk ‖ suatu (3.6) mauntuk 3.3. Misal ada konstan sedemikian sehingga Bukti. Untuk peroleh d,konstan =g sehingga ‖peroleh ‖ Jika ‖maka ‖kita peroleh sehingga . suatu Untuk 1jika 1akan Bukti. Kita membuktikan (3.7) dengan memperhatikan beberapa kasus berikut ini. ‖ ‖ ‖ ‖ berlaku Bukti. kita sehingga . Untuk , jika sangat pentingUntuk untuk menunjukkan kekonvergenan global Algoritma SCD-MA. ‖ ‖ untuk semua berlaku , maka terdapat suatu konstan sedemikian seLemma 3.3. Misal Asumsi SCD-MA berlaku. Jika ada suatu konstan sedemikian sehingga Kedua sifat sangat k>2, penting untuk menunjukkan kekonvergenan Algoritma SCD-MA. Bukti. Kita akan be ‖ global ‖ , jika |akan ‖ ‖‖ ‖(3.7) ‖ (2.6), ‖|membuktikan | dengan | memperhatikan ‖ ‖‖ ‖ bebe ini sangatuntuk penting untuk menunjukkan kekonvergenan global Algoritma maka dengan menggunakan (2.4), (2.8) dan(3.7) ketaksamaan segitiga Bukti. Kita membuktikan dengan memperhatikan ‖ ‖ berlaku ‖kita sehingga .. ini Untuk , jika jika hingga semua Untuk maka ‖ ‖ SCD-MA. ‖,, sedemikian ‖. Untuk Bukti. Untuk sehingga ‖ ‖ peroleh semua berlaku , ‖maka terdapat suatu konstan se-(3.2) ngan menggunakan (2.4), (2.8) dan konstan ketaksamaan segitiga ‖ ‖(2.6), Kasus 1.(3.6) . Berdasarkan kita peroleh ,dengan maka dengan menggunakan (2.4), (2.6), (2.8) dan ketaksamaan segitiga Misal Asumsi SCD-MA berlaku. Jika ada suatu sedemikian sehingga hingga untuk semua berlaku menggunakan (2.4), (2.6), (2.8) dan ‖ ‖ untuk semua berlaku ,berlaku. maka terdapat konstan seLemma Misal Asumsi SCD-MA Jika suatu sedemikian Kasus .‖Berdasarkan (3.2) kita ‖ ada ‖ suatu ‖ konstan ‖sehingga ‖ mengakibatkan ‖ (3.2) ‖ kita ‖peroleh ‖sedemikian ‖sehingga ‖ ‖ ‖. Dengan ‖ ‖ 3.unakan Misal Asumsi SCD-MA berlaku. Jika ada suatu sedemikian sehingga didapatkan sehingga . Hal ini‖Kasus mengakibatkan sehingga . .Hal ini 1.‖1. Berdasarkan peroleh menunjukkan kekonvergenan global Algoritma ‖konstan ‖ (2.6), (2.4), untuk (2.6), (2.8) dan 3.3. ketaksamaan segitiga (3.6) , maka dengan menggunakan (2.4), (2.8)SCD-MA. dan ketaksamaan segitiga asangat untuk penting semua berlaku Bukti. beberapa kasus berikut ini. ‖Kita‖akan membuktikan | (3.7) dengan | ‖ memperhatikan ‖‖ ‖ ‖segitiga ‖ suatu ‖ didapatkan ‖. Untuk kita peroleh sehingga , jika didapatkan berlaku ‖ ‖‖ ketaksamaan , maka terdapat konstan sedemikian se‖ ‖ ‖ ‖ ‖suatu ‖ sedemikian ‖ ‖‖ (3.6)‖ se- ‖ ‖ ‖ ‖ ‖ ‖ ‖sedemikian untuk semua berlaku untuk semua berlaku , ‖maka terdapat konstan aBukti. berlaku , maka konstan sedemikian se| | | | ‖‖ ‖untuk ‖ ,‖‖ Misal Asumsi SCD-MA‖hingga berlaku. Jikaterdapat ada suatu sehingga ‖ Bukti. ‖. Kasus Untuk kita peroleh sehingga Untuk jika demikian .‖akan‖(3.7) demikian untukkita .dengan ‖ suatu ‖konstan 1. .Kita Berdasarkan (3.2) peroleh akan membuktikan memperhatikan beberapa kasusDengan berikut ini. Bukti. (3.7) beberapa kasus b 9 ‖ memperhatikan ‖didapatkan ‖‖menggunakan ‖ ‖ ‖‖(2.6), ‖‖(2.4), ‖‖Kita ‖ ‖(3.6) ‖membuktikan ‖ dengan ‖ ‖ ‖ ‖ ‖ ‖ ‖ sehingga . Hal mengakibatkan dengan (2.8) dan ketaksamaan segitiga ‖ ‖ ‖‖ ‖ ‖ ‖ ‖‖ semua berlaku Hal ini mengakibatkan . ‖ ‖ ‖ ‖ Bukti. Untuk kitaberlaku peroleh . sehingga Untuk , ‖‖jika ‖ sehingga ‖ketaksamaan ‖(3.6) ‖ ‖‖‖ ‖‖. ‖‖.Hal hingga untuk semua sehingga‖‖ Halini inimengakibatkan mengakibatkan‖ ‖ ‖ ‖ uk semua ‖ ‖, kita ‖ ‖‖ ‖ , maka terdapat suatu konstan sedemikian se‖Untuk ‖‖ peroleh ‖ berlaku ‖‖berlaku maka dengan menggunakan (2.4), (2.6), (2.8) dan segitiga 9 ‖ ‖ ‖ ‖‖ ‖ ‖ ‖‖ ‖‖ ‖ ‖ Kasus ‖ ‖. 2.Untuk ‖ (3.2) ‖adalah |nonnegatif. |adalah ‖Berdasarkan ‖‖ ‖ nonnegatif. sehingga Kasus . Berdasarkan kita peroleh Kasus 1. . .Berdasarkan (3.2) peroleh ‖ 1. . ‖Jika, jika maka bilangan definisi ‖ ‖‖ ‖‖ ‖ ‖‖ ‖‖‖ ‖ ‖‖ Kasus 2. Jika makakita bilangan B ‖‖demikian ‖ dengan ‖ (2.4), ‖‖ ‖‖(3.6) ‖ ‖ ‖‖ menggunakan (2.6), dan untuk(2.8) ‖ beberapa ‖ . ‖‖ketaksamaan ‖ segitiga ‖ . ‖jika Bukti. Untuk kita peroleh sehingga . kasus Untuk , (3.6) ‖, maka ‖akan dengan Bukti. Kita membuktikan (3.7) memperhatikan berikut ini. ‖ ‖ ‖(3.6) ‖ semua berlaku didapatkan ‖‖ ‖ ‖ ‖ ‖ ‖ demikian untuk Dengan demikian untuk ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ demikian untuk . ‖ ‖ | | ‖ ‖‖ ‖ 9 Bukti. Kita akan membuktikan (3.7) dengan memperhatikan beberapa kasus berikut ini. ‖‖ ‖‖(2.4), ‖‖ ‖ ‖ ‖ ‖ ‖ , ‖maka dengan (2.6), (2.8) dan ketaksamaan segitiga sehingga . Hal ini mengakibatkan ‖ menggunakan ‖ ‖ ‖ | | ‖ ‖‖ ‖ ‖ ‖ ‖ akan ‖ dengan ‖ akan ‖ ini. ‖ dalam pencarian garismembuktikan Armijo yang termodofikasi, tidakkasus mungkin dalam pencarian garis memperhatikan Armijo yang termodofikasi, tida. ‖ ‖membuktikan ‖ ‖ ‖. Untuk ‖ ‖ kita ‖‖ peroleh ‖ ‖ didapatkan ‖ sehingga Bukti. Kita (3.7) dengan beberapa berikutmemenini. ‖‖ , memperhatikan jika Bukti. Kita (3.7) beberapa kasus berikut ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ Karena memenuhi kondisi Lipschitz dan , maka maka dengan menggunakan (2.4), (2.6), (2.8) dan ketaksamaan segitiga Untuk kita peroleh sehingga . Untuk , jika Kasus . Berdasarkan (3.2) kita peroleh ‖kita peroleh ‖ Bukti. ‖1.,‖sehingga uk . Untuk , jika ‖ Kasus 2. . Jika maka adalah bilangan nonnegatif. Berdasarkan definisi ‖ ‖ ‖ ‖ 9 (3.6) ‖ ‖ ‖ ‖‖ ‖ ‖ ‖‖ ‖ . Berdasarkan ‖‖ ‖‖.‖untuk ‖ maka ‖maka‖ ‖‖ adalah ‖ ‖. De Kasus 1. ‖ sehingga atkan ‖ ‖ ‖dan ‖, maka sehingga Hal ini mengakibatkan isi Lipschitz dan ‖ ‖ (3.2) ‖ ‖ ‖ ‖bilangan ‖bilangan Kasus 2.kita . Jika adalah Hal ini mengakibatkan ‖ (3.2) kita ‖ Kasus 2. . Jika no demikian . peroleh kondisi Lipschitz Kasus 1.‖‖, maka .beberapa Berdasarkan (3.2) kita peroleh makaKarena menggunakan (2.4), ketaksamaan segitiga ‖ dengan ‖‖ memenuhi ‖‖ ‖Kasus ‖ akan ‖maka ‖membuktikan 1.(2.6), . ‖‖Berdasarkan peroleh Bukti. Kita akan membuktikan (3.7) dengan memperhatikan beberapa kas ‖dan ‖dan ‖(2.6), ‖(2.8) ‖ dan ‖‖ ‖ uhi (2.9) (2.10) secara bersamaan. Bukti. Kita (3.7) dengan memperhatikan kasus berikut ini. uhi (2.9) (2.10) secara bersamaan. ‖ dan ‖‖ ‖ ‖‖ ‖ ‖ ‖ | | ‖ ‖‖ ‖ didapatkan , dengan menggunakan (2.4), (2.6), (2.8) ketaksamaan segitiga ‖ kitadengan ‖ ‖ ‖ ,Karena maka menggunakan (2.4), (2.8) dan ketaksamaan segitiga z dan , maka ‖ ‖ ‖ ‖ peroleh sehingga . Untuk , jika ‖ ‖, maka pencarian garis Armijo termodofikasi, tidak mungkin memenmemenuhi kondisi dan ‖ ‖‖‖ ‖ ‖ dalam ‖ ‖ yang ‖ ‖Lipschitz ‖‖ ‖ ‖ ‖ ‖ ‖ ‖ | | ‖ ‖‖ ‖ ‖ ‖‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖‖ ‖ ‖‖ Kasus 2. a <1. Jika a <1 maka j -1 adalah bilangan ‖‖ k‖ dalam k ‖ ‖ ‖ ‖‖ dalam pencarian garis Armijo yang termodofikasi, ‖ ‖‖ |ini. ‖bilangan ‖‖ ‖nonnegatif. demikian untuk pencarian yang termodofikasi, Bukti. akan membuktikan (3.7)peroleh dengan memperhatikan kasus berikut demikian . |kArmijo ‖‖‖ ‖ kita ‖maka ‖ ‖ ‖ ‖ ..‖untuk ‖ ‖ ‖ ‖‖‖Kita 9garis Bukti. dengan memperhatikan beberapa kasus berikut ini. Berdasarkan (3.2) kita peroleh .beberapa Jika maka adalah Berdasarka Kasus 1. (3.2) ‖membuktikan ‖‖|Kita ‖2.‖akan ‖‖|‖‖Kasus ‖1. ‖Berdasarkan tidak (2.9), Jika tidak memenuhi maka memenuhi dan ‖ g ‖(2.4), ‖Jika ‖‖‖ ‖Kasus ‖ (3.7) ‖ ‖(2.9), ‖‖.‖Berdasarkan ‖(2.8) ‖‖dan didapatkan ‖‖ sehingga . ‖‖ Hal ini ‖‖mengakibatkan . definisi Dengan ‖Lipschitz ‖memenuhi nonnegatif. a dalam pencarian ‖ ‖‖ (2.6), ‖‖ ‖‖ ‖kondisi ‖‖ dengan menggunakan ‖ Karena ,‖‖maka ketaksamaan segitiga k ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ sehingga . Hal ini mengakibatkan . D ‖ ‖‖ ‖‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ uhi (2.9) dan (2.10) secara bersamaan. ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ondisi‖Lipschitz Hal ini mengakibatkan maka ‖‖2..‖‖‖garis Kasus Berdasarkan kita ‖‖ ‖ ‖ sehingga ‖ ‖‖‖ ‖‖‖‖,. maka ‖‖ ‖‖ ‖‖‖ ‖ uhi ‖Armijo ‖ ‖adalah ‖ ‖‖ ‖peroleh ‖secara | bilangan |Berdasarkan ‖ .mungkin ‖‖Denga ‖deB .‖‖‖Hal‖ (3.2) ini‖ sehingga mengakibatkan .maka Dengan dan (2.10) bersamaan. Kasus 1.‖‖|‖ Kasus .‖‖ Berdasarkan (3.2) kita ‖ ‖‖ ‖ ‖ dan |peroleh ‖‖‖. ‖Jika Kasus 2.dalam maka bilangan nonnegatif. uhi (2.9) dan (2.10) secara bersamaan. pencarian yang termodofikasi, tidak ‖ ‖‖ 1. .(2.9) Jika adalah nonnegatif. garis Armijo yang termodofikasi, ‖ ‖‖ ‖ ‖ ‖ ‖‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖memenuhi Karena kondisi Lipschitz dan , maka ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ demikian untuk . ‖ ‖ Bukti. Kita akan membuktikan (3.7) dengan memperhatikan beberapa kasus berikut ini. ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖‖ ‖ Jika tidak memenuhi (2.9), maka ‖ ) ‖ ‖ ‖ ( ‖) ‖‖ ‖Karena‖ memenuhi ‖ ‖‖‖ ‖ kondisi (‖ | ( ‖‖|)sehingga )‖, ‖maka ) | ini (mengakibatkan untuk . ‖‖( ‖). Hal ‖ ‖mengakibatkan ‖‖ ‖ . ‖demikian ‖Hal‖‖ ‖ini ‖Jika | )maka ‖‖ ( ‖‖ ‖ ‖‖ ‖ ‖‖ ‖ ‖‖Lipschitz ‖ untuk ‖‖ ‖ ‖ dan ‖ ‖(.‖memenuhi ‖‖ ‖tidak ‖ ‖untuk ‖demikian ‖ ‖‖tidak ‖pencarian tidak memenuhi (2.9), .Armijo Dengan mungkin (2.9) dan (2.10) secara ‖‖‖ ‖ demikian dalam yang termodofikasi, tidak mungkintidak me Jika memenuhi (2.9), maka ‖‖‖‖‖‖‖‖‖‖‖‖ garis yang termodofikasi, ‖‖ ‖‖ ‖ pencarian ‖garis ‖Armijo ‖‖ ‖ ‖ ‖kita ‖‖ peroleh ‖ ‖‖‖ ‖ ‖kondisi ‖‖ sehingga ‖ ‖‖‖‖ ‖‖ ‖ ‖‖.‖‖ uhi (2.9) dan‖‖dalam (2.10) secara bersamaan. ‖ 1. ‖ ‖‖‖‖‖ Lipschitz ‖ a memenuhi dan , maka Kasus . Berdasarkan (3.2) ‖ ‖ ‖ ‖ ‖ ‖ ‖ Kasussehingga 2. . Jika maka adalah bilangan nonnegatif. Berdasarkan definisi ‖ ‖ Dari (3.4) dan untuk semua maka ‖ ‖ ‖ ‖ ‖ bersamaan. ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖‖ ‖ . Hal ini mengakibatkan . Dengan ‖‖ kondisi ‖‖ ‖ Lipschitz ‖ turunan, ‖nonnegatif. ‖ terdapat ‖ Berdasarkan ‖ definis ‖ .de . maka Hal ini mengakibatkan Kasus .‖Jika ‖, maka maka adalah bilangan ‖‖ ‖ Kasus ‖2. ( ‖Nilai ‖Rata-rata ‖‖dan ‖sehingga ‖)Berdasarkan ‖terhadap memenuhi ‖ Teorema turunan, terdapat sehingTeorema Nilai Rata-rata untuk semua maka Karena .‖Jika adalah bilangan Berdasarkan untuk . ) ‖nonnegatif. untuk . maka ‖ sedemikian ‖2. ‖‖ nonnegatif. ) secara (Berdasarkan (terhadap Dari‖(3.4) untuk uhi (2.10) ‖‖ ‖‖‖semua ‖2.‖ ‖ ‖‖‖ maka ‖‖ ‖ Berdasarkan Jika memenuhi (2.9),‖secara maka Kasus .‖Jika adalah bilangan definisi uhi (2.9) danbersamaan. (2.10) ‖‖ | ((2.9) | dan‖tidak ‖‖demikian ‖‖dan ‖‖‖ ‖‖demikian ‖ ) bersamaan. ( ( ) ) ( ) ‖ ‖ ‖ ‖ dalam pencarian garis Armijo yang termodofikasi, tidak mungkin memen( ( ) ) ( ) ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ menuhi kondisi Lipschitz dan , maka maka ‖‖ ‖ ‖ ‖ dan ‖‖ demikian ‖ ‖‖ maka Dari (3.4) dan ‖Lipschitz semua ‖memenuhi ‖‖ ‖.termodofikasi, ‖ ‖ pencarian ‖‖untuk Lipschitz dan‖‖. ,Armijo maka dalampencarian garis yang termodofikasi, mungkin me ga ga ‖‖‖garis memenuhi kondisi , maka ‖ untuk ‖‖ ‖‖‖‖kondisi dalam Armijo yang tidaktidak mungkin memen ‖ ‖Karena ‖ ‖‖ demikian untuk ‖ ‖garis Jika tidak memenuhi (2.9), maka ‖ ini ‖ yangJika tidak (2.9), ‖ ‖ ‖ memenuhi ‖nonnegatif. ‖‖‖tidak ‖ ‖‖ ‖‖ 2. ‖‖dalam ‖.‖‖‖ Hal ‖‖Kasus ‖maka ‖. Jika 2. memenuhi maka adalah bilangan pencarian Armijo termodofikasi, tidak memensehingga mengakibatkan . mungkin Dengan Jika (2.9), maka . Jika maka adalah bilangan Berdasarkan definisi ‖ ‖ ‖ ‖ ‖ Berdasarkan Teorema Nilai Rata-rata terhadap turunan, terdapat sedemikian sehing-nonnegati ‖ ‖‖ Kasus ‖ ‖ ‖ ‖ uhi (2.9) dan (2.10) secara bersamaan. ‖ ‖ ‖ ‖‖ ‖ ( ( ) ) ( ) ( ) Berdasarkan Teorema Nilai Rata-rata terhadap turunan, terdap ‖uhi (2.9) ‖ adalah ‖ (2.10) ‖ ) secara ‖ ‖ Lipschitz ‖ ‖ ‖‖‖‖ ‖ ‖‖Kasus ‖ Berdasarkan Rata-rata turunan, terdapat ‖‖, maka menuhi ‖ ‖‖2.‖‖‖ ‖‖ ‖‖.‖‖Jika ‖‖‖‖ ‖ untukkondisi semua dan bersamaan. ( 2. ( Teorema (Nilai (termodofikasi, )(terhadap ) (maka () memen)Armijo ) definisi ( Berdasarkan ( ) t maka Berdasarkan uhi (2.9) ‖ dan (2.10) bersamaan. ‖(bilangan ‖secara ‖)nonnegatif. ‖yang Kasus . Jika adalah bilangan nonnegatif. ‖ ‖ ‖maka dan ‖dalam dalam pencarian garis yang ‖maka ‖ secara ‖Armijo ‖ .bersamaan. pencarian garis termodofikasi, tidak mungkin ga ‖ ‖ untuk uhi (2.9) dan (2.10) ‖ ‖ ‖ ‖ Dari (3.4) dan ‖ ‖ demikian untuk semua ‖ ‖ ‖ ‖ memenuhi ‖ ( ga)ga () ) (2.9), maka ( terhadap ) ) ( turunan, ( ( ) ) ‖ ‖ sedemikia ( ) ‖ ‖ Jika ‖ ‖‖ ‖ ‖ tidak ‖Jikatermodofikasi, ‖tidak ‖ memenuhi ‖ (Teorema ‖ Armijo tidak memenuhi (2.9), maka Jika (2.9), maka Berdasarkan Nilai Rata-rata yang tidak mungkin memen- terdapat ‖ pencarian ‖ Dari ‖ (3.4) Dari (3.4)dan dan ‖dalam untuk dalam pencarian garis Armijo yang termodofikasi, tidak mungkin m untuk k,‖ maka ‖garis ‖‖maka ‖tidak ‖secara ‖ semua ‖semua ‖ ‖ ‖ ‖‖ ‖‖uhi ‖ Sehingga Sehingga ‖ uhi (2.9) dan (2.10) secara bersamaan. Jika memenuhi (2.9), maka ‖ ‖ (2.9) dan (2.10) bersamaan. ‖ ‖‖ ‖ ) ‖maka ) terdapat ( ) konstan ( ( ) dan) bilangan bulat ‖ ‖‖ ‖maka 2. adalah bilangan Berdasarkan definisi ‖ ‖ ‖(‖ nonnegatif. 3.4) dan ‖ ‖ ‖ untukKasus semua suatu ‖‖ ‖. Jika ‖Karena ‖ (ga ‖ dan ‖ bilangan ‖ maka ( (terhadap ( terdapat ) ( ) ) ( (se ‖ konstan ( turunan, ) ) )turunan, ( sedemikian Teorema Nilai Rata-rata terhadap maka terdapat‖ suatu bulat Berdasarkan Teorema Nilai Rata-rata terdapat ‖(2.9)‖ dan ‖)‖ konstan ‖maka Berdasarkan ‖ ‖ ‖ dan (3.4) untuk semua ‖ Dari ‖ ‖ Karena maka terdapat suatu dan bilangan bulat ( ( ) ( ) ( ) uhi (2.10) secara bersamaan. uhi (2.9) dan (2.10) secara bersamaan. ‖ ‖ ‖ Jika tidak memenuhi (2.9), maka Jika tidak memenuhi (2.9), maka ‖ ‖ ‖ ( ( ) ) ( ) ( ) ‖ ‖ ( ) ‖ ( ( ) ( ) sedemikian sehingga untuk semua , dalam pencarian garis Armijo yang termodofikasi, tidak mungkin memen‖ ‖ ( ) ( ( ) ) ( ) ( ) ( ( ( ) ) ( ) erdapat konstan ‖‖‖ Karena maka terdapat ‖ ‖‖‖ bulat ‖semua ‖ suatu ‖ bilangan semua maka ‖dan ‖suatu ‖) (‖untuk konstan (Sehingga ) )makaga dan bilangan ( ga ) bulat( (Sehingga ) ‖ ,untuk ‖ sedemikian ‖ untuk Dari (3.4) dan ‖‖ tidak semua ( ) ( ) ( ( ) ) sehingga semua , memenuhi dan maka Jika (2.9), maka ‖ semua ‖ untuk Sehingga memenuhi (2.9), makaNilai Rata-rata ‖‖ Rata-rata ‖ ‖ ‖ Jika ‖ tidak Berdasarkan Teorema terhadap turunan, Berdasarkan Teorema Nilai terhadap turunan, terdapat sedemikian sehing-terdapat , sedemikian sehingga uhi untuk semua , secara (2.9) dan (2.10) bersamaan. Berdasarkan Teorema Nilai Rata-rata terhadap turunan, sedemikian sehing ‖ ‖ Berdasarkan Teorema Nilai Rata-rata terhadap turunan, terdapat sedemikian ( ( ) ) ( ) ( )se ‖ ‖ ‖ ‖ ( ( ) ) ( ) ( ) ‖‖ ‖ maka Kedua dengan Kedua terdapat konstan dan bilangan bulatruas( dibagi ‖ semua ‖ ‖ Teorema (kemudian ()sehing)( dikurangkan ( ‖ ( ‖ ) (dengan )( ) ( ruas )( dibagi )dikurangkan (sedemikian )didapatkan ‖‖‖ suatu ‖ maka sedemikian sehingga ()dengan () (dengan )kemudian (didapa ) untuk Berdasarkan Nilai turunan, terdapat ‖ ‖ ‖Rata-rata terhadap ‖)Sehingga ‖( terdapat ‖‖konstan ‖terdapat ‖‖ suatu ) ( ( ) ) ( ) ‖ ‖Jika ‖ ga maka ( ) ( ( ) ) ( ) Karena‖ dan bilangan bulat gaga ‖ ‖ ( ( ) ) ( ) ( ) tidak memenuhi (2.9), maka ‖ ‖ ‖ ( ( ) ) ( ) ( ) ‖ Sehingga tuk semua , ‖konstan ‖ untuk semua berlaku ‖ ‖ ‖Nilai ga Karena maka terdapat suatu dan) bilangan Berdasarkan Nilai Rata-rata terhadap Berdasarkan Teorema Rata-rata terhadap turunan, terdapat sedemikian Sehingga ‖ ‖ terdapat ( ) berlaku (( ()bulat (Teorema ()) bulat (sehing) ) didapatkan )( )turunan, ‖‖ ‖untuk ‖berlaku Sehingga sehingga semua ,‖ ‖ konstan dengan kemudian ‖ untuk Sehingga semua ( ( Kedua ) ) ruas (( (( ))( (dikurangkan a sedemikian maka terdapat dandibagi bilangan ‖ suatu ‖ dengan ‖ ()) ) ruas (dengan ) (dengan )() ) ((kemudian ) ) ( Kedua ruas dibagi dengan kemudian dikurangkan dengan Kedua dibagi ( ( ) ( () ( )) ) )sedemikian ‖ ‖ ‖‖untuk ‖ semua Berdasarkan Nilai Rata-rata terhadap terdapat sedemikian sehing-terdapat dikurangkan sehingga , ) suatu Teorema Nilai terhadap turunan, ga Sehingga untuk semua berlaku ga‖ Karena konstan bulat ‖sedemikian ‖‖ bilangan ‖(‖Rata-rata ( ‖Teorema ( ( ), maka )( terdapat (Berdasarkan ) (turunan, (( ) dan Karena maka terdapat suatu ) ) ) ) ikian sehingga untuk semua , ‖ ‖( () )) ‖ (((Karena ( ( ()() )‖( ‖)(‖ ))( ) (( )()) ())‖) )‖ ‖ ‖ ‖ konstan ‖ ‖ ‖ bulat (‖( ‖, ‖ ‖ ‖ maka ((bulat (Kedua ))) ))dengan () )maka ( ‖bilangan terdapat suatu danKarena bilangan Sehingga q∈(0,1) dan sedemikian ga Sehingga ‖konstan Sehingga ga ruas dibagi kemudian ‖‖ ‖ semua sedemikian sehingga untuk , Kbilangan ‖ ‖ Karena maka terdapat suatu konstan dan bilangan bulat maka terdapat suatu konstan dan bulat (dikurangkan () ) ( (dengan ) ) )( )) )didapatkan Sehingga ( ( ) ( ( ( ‖ ‖ ‖ ‖ berlaku ( ( ) ) ( ) ( ( ) ) ‖ ‖ Kitaterhadap definisikan Berdasarkan Teorema turunan, terdapat sedemikian sehingSehingga sehingga untuk semua k>K, Rata-rata ‖ ‖Nilai hingga untukdefinisikan semuasemua , Sehingga untuk berlaku Kedua ruas dibagi dengan kemudian dikurangkan dengan didapatkan Kita sedemikian sehingga untuk semua , ( ( ) ) ( ) ( ( ) ) sehingga untuk semua , Kedua ruas dibagi dengan kemudian dikurangkan dengan didapat ‖ ‖ ( ) ( Karena ( )‖( ()bulat ( ( )(() )( ) ( ()(() ‖))( ‖)‖) (()() ‖ ‖ ‖( ‖ ‖() ( ‖))‖) ‖ ‖ ‖ maka terdapat suatu konstan dan bilangan ()(((()()))))‖) )(‖ (‖, ()maka ( ( ) )( ()() kita ga Sehingga )‖( ( ( Karena untuk semua berlaku ‖‖ ‖ ‖ (‖ Sehingga ‖ ‖( ( Kita definisikan simpulkan ‖‖ ‖ ‖ Sehingga ( ( ) ) ) ) bahwa ) ) ‖‖)‖ ‖ Karena ‖ ( bahwa ) ( ‖ ( {‖) ) ( ) (}. Maka ) ‖ (dapat ‖ ‖ ‖ gga untuk semua berlaku }. Maka dapat kita simpulkan ‖ ‖ hingga untuk semua ‖ ‖ ‖‖ ‖ }. Maka dapat kita simpulkan ‖( ‖ {‖ ‖ ‖ , ‖ bahwa ‖ ‖ ‖ ‖ ‖ ( ) Sehingga ( ( ) ) ) ( ) ( )( dengan ) ) Sehingga dibagi kemudian dikurangkan Kedua kemudian didapatkan semua ‖( berlaku ( ‖ dengan ) )untuk (. Sehingga ) ruas (dengan ( ( )didapatkan )( )((‖ ) dikurangkan }. Maka dapat simpulkan bahwa ()dibagi ( Sehingga ‖Sehingga ‖ Kedua ‖untuk ‖ruas ‖( dengan {‖ ‖kita ‖kita ‖)simpulkan () ‖ )(‖(‖dengan () ))) ) ) ‖,(mak ) ruas dibagi ( }. ) Maka ( dapat ( semua )Kedua (bahwa ( )) (‖kemudian (‖dengan ) ) ) dikurangkan ‖( )‖( ) ( ( )(didapatkan Karena ( ( ) ) ( kKita semua berlaku dibagisemua dengan kemudian dikurangkan dengan didapatkan ‖ untuk ‖‖ ruas untuk semua . Sehingga ‖Kedua definisikan Dengan demikian, untuk k>K berlaku semua berlaku ntuk semua berlaku ‖‖ ) ( )‖ ‖)3.4. ( Karena )) )asumsi ( ) ‖‖ dan Misal dihasilkan ‖ oleh ‖ algoritma SCD- ‖ ‖ (() ) (berlaku, ( ((SCD-MA (Karena untuk .}. Maka Sehingga ( oleh (( bahwa (Lemma (((() ( )())‖ )) (‖() ))) ‖ ))‖ ‖( (() )() ‖ ) ‖‖(‖ ‖() (())‖) ‖‖( (‖,‖)maka ) ) Sehingga ‖i SCD-MA ‖Lemma ‖semua ‖ SCD‖ dikurangkan Kita definisikan dapatSCD-MA kita simpulkan berlaku, dan dihasilkan algoritma Kedua ruas dibagi dengan kemudian dikurangkan did ( ( ( ) ) ) ) ‖‖ ‖ 3.4. Misal asumsi berlaku, dan dihasilkan oleh algoritma SCDKedua ruas dibagi dengan kemudian dengan didapatkan ( ( ( ) ) ) ( )(‖dengan Sehingga Kedua ruas dibagi dengan kemudian dikurangkan Sehingga efinisikan ‖ ‖ ‖dihasilkan ‖ ‖oleh algoritma ‖konstan ‖ {‖dan }. Maka ‖ ‖ dapat kita simpulkan bahwa uk semua berlaku MA. Maka terdapat suatu sedemikian sehingga untuk semua berlaku ‖ ‖ ( ( ( ) ) ) ( ) berlaku, SCDLemma 3.4. Misal asumsi SCD-MA berlaku, dan dihasilkan oleh algoritma SCD‖ ‖ ‖ ‖ Kita konstan sehingga untuk semua berlaku Kedua ruas‖ dibagi dikurangkan dengan dengan didapatkan Kitasuatu definisikan ‖ dengan {‖ }.dapatkan ruas ‖‖ ‖, ‖ (( ) ) ‖) didapatkan Maka dapat simpulkan ‖(( ))‖didapatkan )kemudian ( (())‖ )dengan MA. Makasedemikian terdapat konstan untuk berlaku (‖ (sedemikian ( Kita )kemudian )) Karena ( ‖semua ) kita (dapatkan ‖ ‖, maka ()‖‖ )‖(dikurangkan )‖ ‖ ( ‖( dibagi ()() )bahwa ‖( ‖Kedua (‖)berlaku ( dapat ( ‖ )simpulkan )sehingga (dengan Karena ‖) ‖maka ‖ ‖ terdapat ‖suatu ‖ ‖ ‖ ‖‖ ((berlaku {‖semua }. Maka Sehingga ( ‖( (maka ) () ) ) ( ))( ( ) ‖) ‖( ‖ ‖, ( sedemikian untuk semua kita bahwa ‖ .‖sehingga ( ( ( ) ) ) ( ) ( ( ) ) ) ‖ ( ‖‖ Karena Kita definisikan MA. Maka konstan sedemikian sehingga untuk semua (3.7) an ‖ untuk ‖ ‖ ‖ ‖ ‖ ‖ Kita definisikan sikan ‖ ‖kita ( oleh ( ) }. )SCD) dapat ‖ simpulkan ( ( bahwa ) ) ‖ ‖ ‖, maka msi SCD-MA(3.7) berlaku,untuk semua danKarena ‖ ( ‖(3.7) ‖ ‖algoritma {‖ . ‖dihasilkan Maka ‖ ‖ ‖ ( ( ( ) ) ) ( ) Kita dapatkan ( (SCD(() ‖( Kita ‖ ‖‖ ruas ‖ Kedua dibagi dengan (kemudian dikurangkan dengan didapatkan Lemma berlaku, dan dihasilkan algoritma () ))) ‖) (‖) )) ‖ ‖ ( ) ‖ (‖‖ ) ‖‖( ‖) ‖ ‖ semua (3.7) ‖ ((dapatkan ( bahwa ( ‖)Sehingga )oleh ) Sehingga dapatkan ‖ ‖ ‖. 3.4.‖Misal ‖ asumsi}.SCD-MA Kita Maka kita‖semua simpulkan atu sehingga (algoritma ( ‖,‖(maka ( ) Karena ‖‖‖ dan ‖‖dapat an ( dapat (asumsi (simpulkan ) Maka ‖ ( kita ( )(oleh )(bahwa ‖untuk ‖(3.7) ‖ ) berlaku ‖ )berlaku, ‖)( ) ) ) ( ) (‖ ))‖‖‖ ‖( ‖ Karena ‖ }. {‖dapat }. ‖‖ ‖ ‖ sedemikian ‖Lemma simpulkan {‖ konstan Maka kitaSCD-MA bahwa 3.4. Misal dihasilkan SCDuntuk semua . (dihasilkan ( ( algoritma ) ) berlaku ) ( )‖ ‖ MA. Maka terdapat suatu konstan sedemikian sehingga untuk semua ma 3.4. Misal asumsi SCD-MA berlaku, dan oleh SCD‖ ‖ ‖ ‖ ( ) ( ) ‖ ‖ ‖ ‖ ‖. ‖ ‖ dapatkan ‖ ‖(Dari ( (konstan ) ) Sehingga ) Kita (( (3.2) ()( ‖)) berlaku ‖, Karena ‖ )) (3.2) diperoleh ( (suatu ( ) ( Dari )) sedemikian ( diperoleh ‖ ‖ ‖ (( ) ) maka ( ) ) ( )‖, maka MA. terdapat sehingga untuk semua ‖‖ ‖ ‖ (3.7) ‖ Oleh ‖Karena }.Sehingga Maka dapat kita simpulkan bahwa ‖ Sehingga Lemma 3.4. Misal SCD-MA berlaku, dan dihasilkan oleh algoritma SCDsemua . asumsi karena itu, dapat disimpulkan bahwa ‖ ‖ ua ( ) ‖untuk ‖Maka ‖ ‖. ‖ ( ( ( ) ) ( () ( ( untuk(semua ) ) berlaku ) ( )‖ ‖ Maka terdapat suatu konstan sedemikian (3.7) sehingga ) ‖)(‖ ‖)‖ Sehingga ‖ ‖semua Misal asumsi SCD-MA berlaku, dan suatu olehberlaku, algoritma ‖ dihasilkan ‖ untuk k.Misal Kita)SCDdapatkan ( ‖SCD) ‖‖ ‖ ( ) ‖ ‖‖ ‖ Kita dapatkan MA. Maka terdapat konstan sedemikian sehingga untuk semua berlaku Lemma 3.4. asumsi SCD-MA dan dihasilkan oleh algoritma ‖ ‖ ‖ ‖ 4.. Misal asumsi SCD-MA berlaku, dan dihasilkan oleh algoritma SCD( ( ) (3.7) ‖ ‖ ( ( ( ) ) ) ( ) ‖ ‖‖ ( ‖ ‖ ( ( )Dari (3.2) ) diperoleh ( ) ) ( ( ‖, maka( ( ) ) ‖) ‖ ) Karena ‖ ‖( ) ( ( ) ‖) ‖ ‖ ‖ (3.7) sehingga diperoleh Sehingga ) ‖ (‖ Sehingga Dari diperoleh dapat suatu konstan sedemikian semua berlaku )(‖ ‖ ) ‖ ‖ ‖ ‖ ((3.2) ‖(3.2) ( ) ‖sehingga ( semua )Dari ‖ ‖ ‖ ‖ untuk MA. Maka terdapat suatu konstan sedemikian untuk berlaku terdapat suatu konstan sedemikian sehingga untuk semua berlaku Kita dapatkan Misal asumsi SCD-MA berlaku, dan dihasilkan oleh(3.7) algoritma SCD‖ ‖ Kita dapatkan Sehingga ‖ (‖ ( ‖ ‖ Sehingga ‖ (‖ ‖ )‖‖ ( ) () Kita ) ‖ (3.2)(diperoleh ) ‖ ) ‖‖ ‖ dapatkan ( ) ‖ (‖ ( ) )‖‖ ‖‖ ‖ ‖ ‖ ‖ ‖ ) ( (3.7) Dari dapat suatu sedemikian sehingga untuk semua (3.7) berlaku ‖ ‖ Kita dapatkan ‖ ‖konstan ( ) (3.7) ‖ ‖ ‖ ‖ ‖ ‖ ‖ ( )‖ ‖ ( )) ‖‖ ‖‖ ‖ ‖ ( ()(‖ ‖ ) ‖) ‖ Dari ((3.2)) ‖diperoleh ‖ ‖ ( DariKita (3.2)dapatkan diperoleh Sehingga Kita dapatkan (3.7) ‖ ‖ ( ) ‖ ‖ ( ( )‖‖ )‖‖‖ ‖ ‖ ‖ Kita dapatkan ( (3.2) ) ‖( ‖) ‖ ‖ diperoleh ‖ Kita ‖ dapatkan ( )Dari Dari (3.2) diperoleh ( Dari (3.2) diperoleh ) ‖ ) ‖‖ ‖ ‖ ) ‖‖ (‖ ( ( )‖ ‖ Dari (3.2) diperoleh ‖ ‖ Kita dapatkan ‖ ‖ ( ( )‖ ‖ ( ) ‖ )‖‖ ‖ Dari (3.2) diperoleh ( ) ‖ ‖‖ ‖Dari (3.2) diperoleh ( )‖ ‖ Dari (3.2) diperoleh ‖ ‖ ( (3.2) ‖ ‖ Dari ‖ )‖diperoleh

ma NilaiTeorema Rata-rataNilai terhadap turunan, terdapat sedemikian sehingsarkan Rata-rata terhadap turunan, terdapat sedemikianSehingga sehingSehingga Sehingga ( ) ‖‖ ‖‖ ma )NilaiSehingga Rata-rata( terhadap sedemikian sehing- ( ) ‖ ‖ ‖ ‖ ) (turunan, terdapat ( ) )

‖ ‖ ‖ }

‖ ‖ ‖ ‖ ‖‖ ‖‖ ‖‖ ‖‖

‖ { ‖ ‖ ‖ ‖ ) ( ) (( ) ‖ ‖( ) ( ) Didefinisikan ‖ )‖ ( ) ) ( ) ( ( ) ) ‖ ‖ ‖ ‖ gga( ) ) Hasanah: ‖ ‖ Didefinisikan Global Metode Spectral Conjugate Descent 47 Didefinisikan { } ‖ ‖ Didefinisikan ( ) Konvergensi ) gga Kedua ruas dibagi dengan (kemudian dikurangkan dengan didapatkan maka didapatkan . ‖( ‖ ‖{ )‖ ‖ ‖ } }{ { } ) ‖ ( ) ( )( ) (( )) ) ( () ) ‖ ‖ ( ) ‖ ( ) ( ( ‖ ‖ ( ) ( ( ) ) ( ) ( ) emudian dikurangkan didapatkan Didefinisikan ‖ 3.5. ) Misalkan ( (Teorema )Didefinisikan ) 3.5. ) Misalkan Asumsi ( Teorema )(‖ berlaku, Karena(dengan Asumsidihasilkan {xk} dan oleh algoritma ‖ ‖ SCD-MA }} { } SCD-MA{{berlaku, ( ( ) ) ( ) maka didapatkan ( ) ‖ ‖ . dan {g } dihasilkan oleh algoritma SCD-MA. Maka ‖ ‖ ‖ ‖ ( ) k ‖ ‖ ( ) ) a ruas dibagi dengandikurangkan kemudian dikurangkan dengan didapatkan SCD-MA. dengan kemudian didapatkan maka didapatkan . ‖ ‖ maka .( a)ruas)dibagi dengan kemudiandengan dikurangkan didapatkan ‖Maka ) ‖ ) dengan ‖ ‖ ‖ ‖ ‖didapatkan ‖‖, maka ( ( ( maka ) ()didapatkan ( ( ) ) ‖ { Karena) . }‖ dihasilkan oleh algoritma { } ‖ Asumsi ‖ dengan kemudian dikurangkan dengan Teoremadidapatkan 3.5. Misalkan SCD-MA berlaku, dan ‖ ‖ ‖ ‖( ‖ )berlaku,Asumsi ( ( ( ) ) )maka didapatkan ( Misalkan ) ‖‖ ‖‖ maka didapatkan ..SCD-MAdihasilkan ( ) Misalkan maka didapatkan Teorema 3.5. berlaku, oleh dan ( ) ‖ ‖ 3.5. Teorema SCD-MA algoritma di )) ( ) ‖‖ ‖‖. Asumsi ‖‖ ‖‖ dan ) )(( ‖)( ‖)‖ (( ) ) ()(Teorema ‖, maka ‖ ‖ Asumsi SCD-MA berlaku, dan dihasilkan oleh algoritma ( ) SCD-MA. (3.5. ) Misalkan ) ) ( ) Maka ‖ ‖ ( ) ) ) ( ) ‖ Maka ‖ ‖ ‖ Bukti.‖ Andaikan tidak benar Maka terdapat suatu konstan SCD-MA. ‖ )‖ bahwa SCD-MA. Maka Teorema Asumsi SCD-MA berlaku, di Teorema 3.5. Misalkan Asumsi SCD-MAoleh berlaku, dan d ( ) ) )( ‖ ‖ didapatkan (‖, )maka na (( )(( ) maka SCD-MA berlaku, dihasilkan algoritma dan maka . Bukti. SCD-MA. )(( 3.5. ) Misalkan didapatkan . ‖ ‖, Andaikan tidak dan benar bahwa ‖3.5. ‖ Misalkan ) ‖ ‖Teorema ( ) ‖ )‖Asumsi ‖,‖maka na maka ‖ ‖(‖Maka (Sehingga ) ) ())) ‖ ) ‖(‖maka ‖ ‖ untuk setiap SCD-MA. berlaku Maka lemma 3.3, ‖ terdapat ‖ ‖ ( ) ) ) ‖ ‖ ‖ ( sedemikian ( ) sehingga ) ‖, maka SCD-MA. Maka ‖. Berdasarkan SCD-MA. Maka ‖ ‖berlaku, ‖ ‖ Teorema 3.5. Misalkan Asumsi SCD-MA dan dihasilkan oleh algoritma ( ( ( ) ) ) ( ) Teorema 3.5. Misalkan Asumsi SCD-MA berlaku, dan dihasilkan oleh algoritma ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ( ) ( ) Bukti. Andaikan tidak benar bahwa Maka terdapat suatu konstan ( ( (( )( ) ( ) )konstan ) ( )) ( sedemikian )‖ ‖ sehingga untuk ‖semua berlaku ‖ ‖ . Di lain pihak, ‖‖‖suatu ‖ ‖‖ konstan ‖ ‖ ‖ Bukti. Andaikan tidak benar bahwa Maka terda Bukti. Andaikan tidak benar bahwa Maka terdapat ( ( ( ) ) ) ( Maka ) ‖ ‖tidak SCD-MA. Maka ‖ ‖ Maka terdapat suatu konstan e>0 sedemikian sehingga Bukti. Andaikan benar bahwa Maka terdapat suatu konstan SCD-MA. ‖ ‖ sedemikian sehingga untuk setiap berlaku . Berdasarkan lemma 3.3, terdapat gga Kita( dapatkan ‖ ‖ ‖ ‖ ‖ ‖ ) ( ) Sehingga gga untuk suatu konstanuntuk .setiap Sehingga kita dapatkan ‖untuk ‖ terdapat sedemikian setiap berlaku . Maka Berdasarka sehingga setiap berlaku Berdasarkan lemma terdapat untuk berlaku . Berdasarkan lemma ‖‖‖ ‖‖‖ 3.3, Bukti. Andaikan benar bahwa terda ‖ sedemikian ‖ ‖ksehingga Bukti. Andaikan tidak benar bahwa Maka terda Bukti. Andaikan tidak benar bahwa Maka konstan ‖‖. tidak ‖ ‖ ‖ ‖ sedemikian sehingga untuk setiap berlaku Berdasarkan lemma 3.3, terdapat ‖sedemikian ‖ suatu konstan sedemikian sehingga untuk semua berlaku . sehingga Di lain pihak, ‖ ‖ ‖ ‖ ( ) ( ) 3.3, terdapat konstan M >0 ‖ ( )‖ ‖ ( ) ‖ ‖ ( ) ‖( ‖ ) ‖ konstan 1 ‖ ‖untuk ‖3.3,semua konstan sedemikian sehingga berlaku sedemikian sehingga untuk berlaku .‖‖Di lain pihak, ‖‖ terdapat sedemikian untuk berlaku .. Berdasarka ‖sehingga ‖berlaku sedemikian sehingga untuk setiap berlaku Berdasark sedemikian untuk setiap berlaku .semua Berdasarkan lemma ‖ ‖setiap ‖ ‖‖sehingga untuk semua k . Di lain pihak, konstan sedemikian sehingga untuk semua berlaku Di lain pihak, ‖ ‖ ( ) ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ ( ) ( ) Bukti. Andaikan tidak benar bahwa Maka terdapat suatu konstan ‖ ‖ tidak benar bahwa Maka terdapat suatu konstan untuk konstan . Sehingga kita dapatkan Kita dapatkan Bukti. Andaikan dapatkan ‖ ‖ ‖ suatu ‖ ‖ ‖ dapatkan ‖‖ konstan sedemikian untuk semua untuk suatu konstan konstan ‖sehingga ‖ M2>0. konstan sedemikian sehingga untuk semua berlaku suatu . Sehingga kitaberlaku dapatkan konstan sedemikian sehingga untuk semua berlaku . Di lain pihak, ‖ ‖ untuk suatu konstan . Sehingga kita dapatkan ‖Berdasarkan Dari ‖‖ ‖‖ ‖ konstan ‖setiap sedemikian sehingga untuk setiap berlaku . Berdasarkan lemma 3.3, terdapat ‖ ( (3.2) diperoleh )‖ ‖ untuk suatu . Sehingga kita dapatkan sedemikian sehingga untuk berlaku . lemma 3.3, terdapat ‖ ‖ ‖ ‖ Untuk‖ ‖ ‖ berlaku . Hal ini‖‖kontradiksi dengan untuk semua ‖‖ ‖ ‖Sehingga ‖ untuk ‖ kita ‖ suatu ‖ sedemikian ‖suatu konstan untuk konstan Sehingga kita untuk suatu konstan Sehingga kita dapatkan dapatkan kita dapatkan untuk . Sehingga dapatkan ‖ ‖ konstan sehingga semua berlaku ... Di lain‖pihak, ‖ ‖ ( ) ‖ ‖ konstan sedemikian sehingga untuk semua berlaku . Di pihak, ‖ ‖ ‖ ‖ ( ) ‖ (‖ ‖ ‖lain ‖ ‖ ‖‖ ‖ ‖ ‖ )‖ ‖‖ ‖ dan untuk (suatu . Sehingga‖berlaku ‖ ‖ ‖ ‖ ‖ )‖ ‖ ) ‖ ‖Untuk ‖( ‖ ‖ ‖ diperoleh ‖ ‖ . Sehingga berlaku . Hal .ini kontradiksi dengan untuk semua untuk suatu konstan Sehingga kita dapatkan‖ ‖‖ h(3.2) untuk suatu konstan (3.2) diperoleh ‖‖ ‖‖ dengan ‖ ‖ .‖‖Hal ‖ ‖ ‖Untuk ‖ ‖ kita ‖dapatkan ‖ kontradiksi ‖ ‖ Untuk ‖ ‖ Dari (3.2) diperoleh ‖ ‖ berlaku ini‖ kontradiksi berlaku . Hal ini dengan untuk semua ‖ ‖ ( ) ‖ ‖ h ‖ ‖ ‖ ‖ . Hal ini kontradiksi untuk semua ‖Untuk ‖ ‖ berlaku ‖ ‖ dengan ‖ dan untuk suatu . Sehingga berlaku ‖ .untuk ‖ berlaku ‖ ‖. Sehingga ‖‖ ‖ .. Hal ‖ untuk Untuk ini ‖ ‖ dengan ‖‖ . Sehingga ‖‖ Untuk Untuk berlaku Hal ini kontradiksi kontradiksi dengan ‖‖ ‖suatu ‖berlaku ‖ ‖‖‖ ‖berlaku berlaku dan Hal ini kontradiksi dengan untuk semua suatu ( )‖‖ ((‖‖ Untuk)) ‖ ‖ dan ‖ berlaku ‖ ‖ dan untuk suatu . Sehingga berlaku ( )‖ ‖ ‖‖ ‖‖ dan untuk suatu ‖ dengan ‖ .. Sehingga danini untuk suatu Sehingga untukberlaku suatu berlaku. Sehingga ‖berlaku ‖ Untuk . Hal ini kontradiksi dengan untuk semua Hal ini kontradiksi dengan untuk ‖ ‖ ‖ berlaku ‖ ‖ berlaku Untukdan .‖ Hal kontradiksi untuk semua Didefinisikan Sehingga )( ) ( ) ( ) () Sehingga ( ((( ))) ()Didefinisikan (( )) ) () ( ( )( ) Didefinisikan

semua k dan untuk suatu e>0. Sehingga berlaku JikaJika tidak memenuhi (2.10), maka Jika tidak memenuhi (2.10), maka memenuhi (2.10), maka tidak memenuhi (2.10), maka Jika tidak memenuhi (2.10), dan makauntuk dansuatu untuk suatu. Sehingga . Sehingga ‖ ‖ ‖ ‖ berlakuberlaku ( Jika

(

)

( maka tidak)(memenuhi )(2.10),

)

idak memenuhiKedua (2.10),ruas maka dikurangi oleholeh didapatkan uhi (2.10),oleh maka dikurangi maka didapatkan Kedua ruas dikurangi oleh maka maka didapatkan Kedua ruas dikurangi maka didapatkan )Kedua ruas dikurangi oleh maka didapatkan

( ) memenuhi (2.10), )maka ( ( ( ( ) dapatkan(

( (() ( ) )

)

(

) )

) ‖

)

‖

Kedua ruas dikurangi oleh maka didapatkan Berdasarkan asumsi SCD-MA didapatkan

uas dikurangi oleh maka didapatkan asumsi Berdasarkan asumsi SCD-MA didapatkan ( didapatkan ) ‖didapatkan iBerdasarkan oleh SCD-MA maka didapatkan ‖ asumsi SCD-MA

‖

‖

Dengan demikian metode spectral conjugate descent menghasilkan arah pencarian dk yang menurun. Dengan menggunakan pencarian garis Armijo yang ‖ ‖‖ metode termodifikasi, ini konvergen global. ‖ simpulan dan saran

‖ ‖ ‖ ‖) ( ) (( ( ( ) ‖) ‖‖) ‖)‖ (‖ )(( ( ‖( ‖)( )) ) ) ) ) maka didapatkan ‖ ‖ ( ( ( ) ) ) Metode nonlinear spectral conjugate descent baru Berdasarkan asumsi SCD-MA didapatkan yang merupakan gabungan dari metode conjugate rkan asumsi SCD-MA didapatkan Berdasarkan asumsi( SCD-MA didapatkan ( ( ) ) ‖ ‖ (‖‖ ( ‖ ( )( )) ) ‖ ‖ ‖ ‖‖ ‖ SCD-MA ( ( didapatkan ) )) )) ‖ ( descent dan metode spectral conjugate gradient ‖ ( ( ) ) ‖‖ ‖ mempunyai arah pencarian yang menurun ‖ ‖ ( ( ( ) ) ) ‖ ‖ ( ) ‖ ‖ ( () (‖ ‖ ( ) terbukti ) ) ( ) ‖ ‖ asumsi SCD-MA didapatkan (descent direction). Dengan menggunakan pencarian ( (‖ ) ‖ ) ( (‖ ‖ ‖( ) ) ( ) )‖ ‖ garis Strong Wolfe, metode ini konvergen global. Sehingga ‖ Sehingga ‖ ( ( ‖ ( ( )( ) ) ) ‖ ‖ ‖ Sehingga ‖ ( ( ) ) ‖‖ ‖ ) ‖ ‖ ‖ ( ( ) Dengan ) ‖‖ ‖ menggunakan pencarian garis Armijo yang ‖ ‖‖ ‖ ‖ ‖ termodifikasi yang dilaporkan merupakan pencarian ‖ ‖ ‖ ‖ ( ) ‖ ‖ ‖ ‖ ‖‖ ‖ ( ) ‖‖ ‖( ‖ ( ‖) ) garis yang efisien, metode spectal conjugate descent ( ) ‖ ‖ ‖ ‖ Didefinisikan memberikan hasil yang konvergen global. Selain ‖ ‖Sehingga na Didefinisikan ( ) ‖ ‖ Didefinisikan pencarian garis Armijo yang termodifikasi, masih Sehingga ‖ ‖ ‖ ‖ ‖ ‖ terdapat dua pencarian garis tidak eksak yang ‖ ‖ { } { { } ‖ ‖}termodifikasi ‖ (‖ yang perlu diteliti kekonvergenan {) } ( ) ( ) ‖ ‖( ) sikan ‖ ‖ metode nonlinear spectral conjugate descent dengan ‖ ‖ ‖ ‖‖ ‖ ‖ ‖ pencarian garis tersebut sehingga dapat digunakan } maka . ‖ ‖ tkan . didapatkan maka didapatkan ‖ ‖‖ ‖ . ‖Didefinisikan ‖ ( ) Didefinisikan maka didapatkan . sebagai bahan penelitian selanjutnya. ‖ ‖{ } {Teorema }Asumsi Teorema 3.5. 3.5. Misalkan Asumsi SCD-MA berlaku, dan dan dihasilkan oleholeh algoritma ( ) dan 5. Misalkan Asumsi SCD-MA berlaku, dihasilkan oleh algoritma Misalkan SCD-MA berlaku, dihasilkan algoritma ( Asumsi) SCD-MA berlaku, Teorema 3.5. Misalkan dan dihasilkan oleh algoritma { } SCD-MA. Maka Maka } SCD-MA. Maka ‖ ‖ { daftar pustaka SCD-MA. dapatkan . ‖ ‖ Maka ( ) ( ) algoritma A berlaku, . dan‖ ‖ dihasilkan oleh ‖ ‖‖ ‖ ‖ ‖ ‖ ‖ Birgin EG & Martinez JM, 2001. A Spectral Conjugate Gradient ‖ ‖ a 3.5. Misalkan SCD-MA berlaku, ‖ ‖dan dihasilkan oleh algoritma ‖ Asumsi ‖ Method for Unconstrained Optimization. Appl. Math. Optim.; kan . maka didapatkan . ‖ ‖ kan Asumsi SCD-MA berlaku, dan dihasilkan oleh algoritma Bukti. Andaikan tidak benar bahwa Maka terdapat suatu konstan maka didapatkan . ‖ ‖ ‖ ikan tidak benar Maka suatu‖konstan Maka terdapat ‖ bahwa ‖ Bukti. Andaikan tidak benar 43: 117-128.suatu konstan ‖ ‖bahwa ‖ ‖terdapat Bukti. Andaikan tidak benar bahwa Maka terdapat suatu konstan A. Maka ‖ ‖ ‖ oleh sedemikian sehingga setiap berlaku . terdapat Berdasarkan lemma 3.3, 3.3, terdapat ‖ untuk ‖ untuk ‖‖ 3.3, ‖algoritma sehingga setiap berlaku . Berdasarkan lemma sedemikian sehingga berlaku . Berdasarkan lemma terdapat . Misalkanuntuk Asumsi SCD-MA berlaku, dan dihasilkan ‖setiap ‖SCD-MA Teorema 3.5. Misalkan berlaku, dan terdapat dihasilkan oleh algoritma sedemikian sehingga untuk setiap . Berdasarkan lemma 3.3, ‖ berlaku ‖ Asumsi ‖ ‖ Maka terdapat suatu konstan ‖ ‖ ‖ ‖ konstan sehingga semua berlaku pihak, ‖ untuk ‖ untuk ‖ ‖ . Di. lain sehingga semua berlaku . semua Di lain pihak, konstan untuksedemikian sedemikian sehingga berlaku Di lain pihak, aka sedemikian konstan sedemikian sehingga‖ untuk semua berlaku ‖ ‖ . Di lain pihak, SCD-MA. Maka ‖ Andaikan tidak benar bahwa Maka terdapat suatu konstan ‖ ‖ ‖ ‖ rlaku . Berdasarkan lemma 3.3, terdapat ‖k benar bahwa ‖ ‖ ‖. ‖‖Sehingga ‖suatu Maka terdapat suatu .konstan konstan Sehingga kita kita dapatkan ‖ ‖ konstan ‖ ‖ untuk untuk suatu kita dapatkan untuk suatu konstan . Sehingga dapatkan ‖ian sehingga untuk ‖ berlaku ‖ ‖ ‖3.3, untuk suatu konstan . Sehingga kita dapatkan ‖ ‖ setiap . Berdasarkan lemma terdapat ‖ ‖ ntuk semua berlaku . Di lain pihak, ‖ ‖ ‖ ‖ a untuk berlaku lemma 3.3, ‖ . ‖Berdasarkan kan tidaksetiap benar bahwa Maka terdapat suatuterdapat konstan sedemikian sehingga untuk semua berlaku ‖ ‖‖ ‖‖ ‖ ‖ . ‖‖Di lain ‖ ‖ ‖ ‖ ‖ terdapat ‖‖ pihak, . Sehingga kitaBukti. dapatkan ‖ ‖ Andaikan tidak benar bahwa Maka terdapat suatu konstan demikian sehingga untuk semua berlaku . Di lain pihak, ‖ ‖ ‖ ‖ ‖ ‖ ehingga untuk setiap berlaku . Berdasarkan lemma 3.3, ‖ ‖ untuk suatu konstan . Sehingga kita dapatkan ‖ dengan ‖ ‖‖ ‖ untuk berlaku semua ‖ semua ‖dengan ‖berlaku ‖sedemikian sedemikian sehingga untuk setiap . Berdasarkan lemma 3.3, terdapat ‖sehingga ‖ . Sehingga ‖ini kontradiksi ‖‖ .untuk Hal ini kontradiksi untuk ‖‖ . ‖Hal ‖ . berlaku Untuk Hal ini kontradiksi dengan untuk semua suatu konstan Untuk kita semua berlaku . Di lain pihak, ‖ berlaku ‖ dapatkan Untuk ‖ ‖berlaku . Hal ini kontradiksi dengan ‖ ‖ untuk semua

( oleh ( ikurangi )

48 Dai YH, Liao LZ & Li D, 2004. On Restart Procedures for the Conjugate Gradient Method. Numerical Algorithms; 35:249260. Kim M, Kwon S & Oh S, 2008. The Performance of A Modified Armijo Line Search Rule in BFGS Optimization Method. Journal of The Chungcheong Mathematical Society; 21(1):117-127. Liu J & Jiang Y, 2012. Global Convergence of A Spectral Conjugate Gradient Method for Unconstrained Optimization. Abstract and Applied Analysis; Vol. 2012. doi: 10.1155/2012/758287

Sains & Mat, Vol. 2 No. 2, April 2014: 42–48 Wei Z, Qi L, Ito S, 2000. New step-size rules for optimization problems. Guangxi: Department of Mathematics and Information Science, Guangxi University. Wei XW, Li GY & Qi LQ, 2008. Global Convergence of The PolakRibiere-Polyak Conjugate Gradient Method with an ArmijoType Inexact Line Search for Nonconvex Unconstrained Optimization Problems. Mathematics of Computation; 77(264):2173-2193. Zhang L, Zhou W & Li D, 2006. Global Convergence of a Modified Fletcher-Reeves Conjugate Gradient Method with Armijo-Type Line Search. Numer. Math; 104:561-572.