CAKRAWALA PENDIDIKAN

VOLUME 16, NOMOR 1, APRIL 2014

ISSN 1410-9883

CAKRAWALA PENDIDIKAN FORUM KOMUNIKASI ILMIAH DAN EKSPRESI KREATIF ILMU PENDIDIKAN

Teaching Dictation using Dictation Drills Global Convergence of the Modified Fletcher-reeves Conjugate Gradient Method with the Modified Armijo-type Line Search Membangun Mindset Entrepreneur pada Mahasiswa LPTK sebagai Alternatif Menyiapkan Lapangan Pekerjaan di Masa Depan Pendidikan dalam Keluarga dan Keberhasilan Pendidikan Karakter Peran Logika Politik dalam Kompetiisi Politik Verb Processes in English Sentences of the Books of Art Penguatan Partisipasi Politik Masyarakat dalam Pemilihan Umum Seleksi Calon Mahasiswa Baru terhadap Kualitas Lulusan Improving the Skill in Writing Descriptive Paragraph of English Education Department Students Identifikasi Kesulitan Belajar bagi Mahasiswa Pengaruh Motivasi Kerja terhadap Produktivitas Kerja Karyawan The Influence of TAI Method in Teaching Reading of Procedure Text for SMP Students Pengaruh Penggunaan Metode Kontekstual Bermedia VCD dan Keterampilan Belajar terhadap Prestasi Belajar Keterkaitan antara Berpikir Kreatif dan Produk Kreatif Guru Matematika SMP dalam Membuat Soal Matematika Kontekstual Errors on Writing Made by the Students of Law Faculty

ISSN 1410-9883

CAKRAWALA PENDIDIKAN Forum Komunikasi Ilmiah dan Ekspresi Kreatif Ilmu Pendidikan Terbit dua kali setahun pada bulan April dan Oktober Terbit pertama kali April 1999

Ketua Penyunting Kadeni Wakil Ketua Penyunting Syaiful Rifa’i Penyunting Pelaksana R. Hendro Prasetianto Udin Erawanto Riki Suliana Prawoto Penyunting Ahli Miranu Triantoro Masruri Karyati Nurhadi Pelaksana Tata Usaha Yunus Nandir Sunardi

Alamat Penerbit/Redaksi: STKIP PGRI Blitar, Jalan Kalimantan No. 49 Blitar,Telepon (0342)801493. Langganan 2 nomor setahun Rp 50.000,00 ditambah ongkos kirim Rp 5.000,00. Uang langganan dapat dikirim dengan wesel ke alamat Tata Usaha. CAKRAWALA PENDIDIKAN diterbitkan oleh Sekolah Tinggi Keguruan dan Ilmu Pendidikan PGRI Blitar. Ketua: Dra. Hj. Karyati, M.Si, Pembantu Ketua: M. Khafid Irsyadi, ST.,S.Pd Penyunting menerima sumbangan tulisan yang belum pernah diterbitkan dalam media cetak lain. Syarat-syarat, format, dan aturan tata tulis artikel dapat diperiksa pada Petunjuk bagi Penulis di sampul belakang-dalam jurnal ini. Naskah yang masuk ditelaah oleh Penyunting dan Mitra Bestari untuk dinilai kelayakannya. Penyunting melakukan penyuntingan atau perubahan pada tulisan yang dimuat tanpa mengubah maksud isinya.

ISSN 1410-9883

CAKRAWALA PENDIDIKAN Forum Komunikasi Ilmiah dan Ekspresi Kreatif Ilmu Pendidikan Volume 16, Nomor 1, April 2014

Daftar Isi Teaching Dictation using Dictation Drills .......................................................................... Annisa Rahmasari

1

Global Convergence of the Modified Fletcher-reeves Conjugate Gradient Method with the Modified Armijo-type Line Search ....................................................................... Dahliatul Hasanah

8

Membangun Mindset Entrepreneur pada Mahasiswa LPTK sebagai Alternatif Menyiapkan Lapangan Pekerjaan di Masa Depan .............................................................. Ekbal Santoso

17

Pendidikan dalam Keluarga dan Keberhasilan Pendidikan Karakter ................................. Endang Wahyuni

25

Peran Logika Politik dalam Kompetiisi Politik .................................................................. Miranu Triantoro

31

Verb Processes in English Sentences of the Books of Art .................................................. Rainerius Hendro Prasetianto

37

Penguatan Partisipasi Politik Masyarakat dalam Pemilihan Umum................................... Udin Erawanto

43

Seleksi Calon Mahasiswa Baru terhadap Kualitas Lulusan ............................................... Agus Budi Santosa

51

Improving the Skill in Writing Descriptive Paragraph of English Education Department Students .............................................................................................................................. Astried Damayanti

58

Identifikasi Kesulitan Belajar bagi Mahasiswa .................................................................. Karyati

67

Pengaruh Motivasi Kerja terhadap Produktivitas Kerja Karyawan .................................... Ninik Srijani

72

The Influence of TAI Method in Teaching Reading of Procedure Text for SMP Students Saiful Rifa’i

80

Pengaruh Penggunaan Metode Kontekstual Bermedia VCD dan Ketwrampilan Belajar terhadap Prestasi Belajar .................................................................................................... Sudjianto

86

Keterkaitan antara Berpikir Kreatif dan Produk Kreatif Guru Matematika SMP dalam Membuat Soal Matematika Kontekstual ............................................................................ Suryo Widodo

97

Errors on Writing Made by the Students of Law Faculty ................................................... Varia Virdania Virdaus Desain sampul: H. Prawoto Setting dan Cetak: IDC Malang, Telp./Faks. (0341)576 446, email: [email protected]

110

Petunjuk Penulisan Cakrawala Pendidikan 1. Naskah belum pernah diterbitkan dalam media cetak lain, diketik spasi rangkap pada kertas kuarto, panjang 10–20 halaman, dan diserahkan paling lambat 3 bulan sebelum penerbitan, dalam bentuk ketikan di atas kertas sebanyak 2 eksemplar dan pada disket komputer IBM PC atau kompatibel. Berkas naskah pada disket komputer diketik dengan menggunakan pengolah kata Microsoft Word. 2. Artikel yang dimuat dalam jurnal ini meliputi tulisan tentang hasil penelitian, gagasan konseptual, kajian dan aplikasi teori, tinjauan kepustakaan, dan tinjauan buku baru. 3. Semua karangan ditulis dalam bentuk esai, disertai judul subbab (heading) masing-masing bagian, kecuali bagian pendahuluan yang disajikan tanpa judul subbab. Peringkat judul sub-bab dinyatakan dengan jenis huruf yang berbeda, letaknya rata tepi kiri halaman, dan tidak menggunakan nomor angka, sebagai berikut. PERINGKAT 1 (HURUF BESAR SEMUA TEBAL, RATA TEPI KIRI) Peringkat 2 (Huruf Besar-kecil Tebal, Rata Tepi Kiri) Peringkat 3 (Huruf Besar-kecil Tebal, Miring, Rata Tepi Kiri) 4. Artikel konseptual meliputi (a) judul, (b) nama penulis, (c) abstrak (50–75 kata), (d) kata kunci, (e) identitas peulis (tanpa gelar akademik), (f) pendahuluan (tanpa judul subbab) yang berisi latar belakang dan tujuan atau ruang lingkup tulisan, (g) isi/pembahasan (terbagi atas sub-subjudul), (h) penutup, dan (i) daftar rujukan. Artikel hasil penelitian disajikan dengan sistematika: (a) judul, (b) nama (nama) peneliti, (c) abstrak, (d) kata kunci, (e) identitas peneliti (tanpa gelar akademik) (f) pendahuluan (tanpa judul subbab) berisi pembahasan kepustakaan dan tujuan penelitian, (g) metode, (h) hasil, (i) pembahasan, (j) kesimpulan dan saran, dan (k) daftar rujukan. 5. Daftar rujukan disajikan mengikuti tatacara seperti contoh berikut dan diurutkan secara alfabetis dan kronologis. Anderson, D.W., Vault, V.D., dan Dickson, C.E. 1993. Problems and Prospects for the Decades Ahead: Competency Based Teacher Education. Berkeley: McCutchan Publishing Co. Huda, N. 1991. Penulisan Laporan Penelitian untuk Jurnal. Makalah disajikan dalam Lokakarya Penelitian Tingkat Dasar bagi Dosen PTN dan PTS di Malang Angkatan XIV, Pusat Penelitian IKIP MALANG, Malang, 12 Juli. Prawoto. 1988. Pengaruh Penginformasian Tujuan Pembelajaran dalam Modul terhadap Hasil Belajar Siswa SD PAMONG Kelas Jauh. Tesis tidak diterbitkan. Malang: FPS IKIP MALANG.. Russel, T. 1993. An Alternative Conception: Representing Representation. Dalam P.J. Black & A. Lucas (Eds.). Children’s Informal Ideas in Science (hlm. 62-84). London: Routledge. Santosa, R. Gunawan. 2002. Aplikasi Teorema Polya Pada Enumerasi Graf sederhana, (online), (http://home.unpar.ac.id/integral.pdf.html, diakses 29 Desember 2006) Sihombing, U. 2003. Pendataan Pendidikan Berbasis Masyarakat. http://www.puskur.or.id. Diakses 21 April 2006 Zainuddin, M.H. 1999. Meningkatkan Mutu Profesi Keguruan Indonesia. Cakrawala Pendidikan, 1(1):45–52. 6. Naskah diketik dengan memperhatikan aturan tentang penggunaan tanda baca dan ejaan yang dimuat dalam Pedoman Umum Ejaan Bahasa Indonesia yang Disempurnakan (Depdikbud, 1987).

8 CAKRAWALA PENDIDIKAN, VOLUME 16, NOMOR 1, APRIL 2014

GLOBAL CONVERGENCE OF THE MODIFIED FLETCHERREEVES CONJUGATE GRADIENT METHOD WITH THE MODIFIED ARMIJO-TYPE LINE SEARCH

Dahliatul Hasanah Jurusan Matematika Universitas Negeri Malang e-mail: [email protected]

Abstract: A conjugate gradient method is well-known for solving large scale unconstrained optimization problem. However, the direction generated by a conjugate gradient method may not be a descent direction. We propose an algorithm utilizing the modified Fletcher-Reeves conjugate gradient method and the modified Armijotype line search. We prove that the direction generated is a descent direction and the algorithm is globally convergent if the objective function has Lipschitz continuous gradient. Keywords: Conjugate gradient method, Descent direction, Fletcher-Reeves conjugate gradient method, modified Armijo-type line search, Global convergent. Abstrak: Metode Conjugate Gradient merupakan metode yang terkenal untuk menyelesaikan masalah optimasi tanpa kendala dalam skala besar. Akan tetapi arah yang dihasilkan metode ini dimungkinkan bukan merupakan arah yang menurun. Peneliti mengusulkan suatu algoritma yang menggabungkan metode FletcherReeves Conjugate Gradient dan pencarian arah Armijo termodifikasi. Dalam artkel ini akan ditunjukkan bahwa arah yang dihasilkan metode gabungan ini merupakan arah yang menurun dan algoritmanya konvergen global jika fungsi objektifnya mempunyai gradient yang memenuhi kondisi Lipschitz dan kontinyu. Kata kunci: Metode Conjugate Gradient, Arah yang menurun, Metode FletcherReeves Conjugate Gradient, Pencarian garis Armijo termodifikasi, Konvergen global.

INTRODUCTION

min , . (1.1) where f is nonlinear function whose gradient

The conjugate gradient method is a wellknown method for solving large scale unconstrained optimization problems due to its low memory requirements and strong local and global properties. Many types of conjugate gradient methods had been developed to provide a method with more robust and faster optimization algorithm for nonlinear problems. In general, the nonlinear conjugate gradient method is designed to solve the following unconstrained optimization problem:

is denoted by . Let be the initial guess of the solution of (1.1). The iterative formula of the conjugate gradient method is given by where is the step length is obtained by carrying out some line search, and the direction

8

is defined by

Hasanah, Global Convergence of the Modified Fletcher-Reeves Conjugate Gradient Method 9

(1.2) where is a parameter such that when applied to minimize a strictly convex quadratic function, the directions and are conjugate with respect to the Hessian of the objective function. Fletcher-Reeves conjugate gradient method formulates parameter denoted as

which is

as follows:

, the directional derivative of f at

along the direction

is given by

It can be seen that if the step length is carried out by the exact line search, then for any

the descent property of given in (1.2) is not guaranteed in general. In the case that is not a descent direction, Al-Baali suggested to use the steepest descent direction

(1.3) For

generated by the Fletcher-Reeves method is also guaranteed to be a descent direction if the line search is carried out by the strong Wolfe-Powell line search. Global convergence of this method has been proved by AlBaali (1985). However, if the line search is Armijotype line search or Wolfe-type line search,

instead of given by (1.2). Birgin and Martinez (2001) proposed three kinds of spectral conjugate gradient methods by combining conjugate gradient method and spectral gradient method. The direction

is given by

, we have

Zoutendijk (1970) had proved that the Fletcher-Reeves method with exact line search is globally convergent. A direction

where and parameter is computed in three ways as follows:

is the spectral gradient which is evaluated by

where . In the numerical results, these methods perform very effectively. However, the direction generated by these methods may not be a descent direction. Motivated by the success of the spectral conjugate gradient method, Liu et.al (2012) proposed a new method by combining the conjugate gradient method and the spectral gradient method. The direction is generated in the same way as in the conjugate gradient method, and following way

and

are specified in the

Under some mild conditions, the global convergence of this method has been guaranteed with the strong Wolfe line search. Yu et.al (2010) proposed a spectral conjugate gradient method for impulse noise removal. The search direction generated by this method is guaranteed to be descent direction. Moreover, under the strong Wolfe line search, this method is globally convergent. The global convergence of the FletcherReeves and the Polak-Ribiere-Polyak methods with Armijo inexact line search has


been discussed in a systematic way. For finding an effective and efficient step length, considerable researches have been made provided an iterate

From (1.3), (2.1), and (2.2), we have

and a descent

direction . There are at least four types of inexact line search procedures. The Armijotype line search is one of several inexact line search procedures which guarantees a sufficient degree of accuracy to ensure the algorithm convergence. The Armijo-type line search is finding such that is the smallest nonnegative integer j satisfying

where and . The iterative scheme in the Armijo-type line search is often referred to as backtracking. This tends to make finding the step length vary in the predictable manner.

By induction, we can get It is clear that if the exact line search is used to determine the step length, then . Thus,

In this case, the modified Fletcher-Reeves method reduces to the standard FletcherReeves method.

THE MODIFIED ARMIJO-TYPE LINE SEARCH

Modification of Armijo line search is based on using the function THE MODIFIED FLETCHER-REEVES CONJUGATE GRADIENT METHOD

Zhang et.al (2006) proposed a conjugate gradient method by modifying a FletcherReeves conjugate gradient method to be similar with a spectral conjugate gradient method but with different parameters

and

. This modification to the FletcherReeves conjugate gradient method ensures that the direction generated is always a descent direction. In the modified Fletcher-Reeves method, the direction is defined by the following way (2.1) where

where is a simple symmetric and positive definite matrix proposed by Wei et.al (2000). This modified line search can be applied by using for instead of for convenience. Wei, et.al (2008) proposed the modified Armijo-type line search in the following way. Let

, , and

,

be given. Let we denote The Armijo-type line search is

to find where is the smallest nonnegative integer j such that

is described by (1.3) and (3.1)

and (3.2) where

is defined as

,


Parameter plays an important rule for improving the initial step length. It has been proved that if the direction generated is a descent direction, then it is guaranteed that there exists a nonnegative integer j satisfying the Armijo-type line search. Wei, et.al (2008) also introduced a reasonable choice for selecting quadratic model ries of order

two

based on the

which is a Taylor seof the function

around ciently small, introduce

. If

is suffi-

by

It is reported that this choice works quite well

by

selecting .

ALGORITHM

The following algorithm is the algorithm of the modified Fletcher-Reeves conjugate gradient method in which its step length is chosen by the Armijo-type line search. Algorithm MFR-MA Step 1 Given ,

Let

be a

very small real number, then we select the following way

in

such that

o Compute

;

o Compute

;

o If

else end o Let ; o Set j = 0; o Take

,

o While ;

;

constants ,

,

Step 2 Take a starting point 0;

, ; and let k =

Step 3 Set Step

Find

and

4

While

do


end o Output Let the next iterate

;

Evaluate

;

Compute the spectral gradient Compute

by

Generate

by

Let

;

by

;

; ;

Output k and GLOBAL CONVERGENCE

ated by Algorithm MFR-MA is contained in

Global convergence of the Algorithm MFR-MA will be proved in this section under the following assumption. Assumption MFR-MA 1) The level

set is

bounded where

is the starting point.

2) The gradient of the objective function satisfies the Lipschitz condition, i.e. there exists

such that for all

such that (5.1) In addition, by the Assumption MFR-MA, there exists a constant all k satisfy

By the modified Armijo condition, ing sequence. This implies that

is a decreasgener-

Therefore, . We have the Modified Armijo condition, that is

such that for

(5.2) Lemma 1. Suppose that Assumption MFRMA holds. Then and

,

then we get

. It also implies that there exists a constant

(5.3) Proof : From (5.1) we obtain


This implies

and

We know that

for all

, and the two series are series of nonnegative real numbers. Hence, the series are decreasing. This leads to and . This property is very important for proving the global convergence of Algorithm MFRMA.

Since

. Lemma 2. Suppose that the Assumption MFR-MA holds. If there exists a constant such that for all then there exists a constant

for all

such that

for all k satisfy (5.4) Proof : Using (1.2), (1.3), (eq. of spectral), and triangle inequality of the Euclidean norm, we obtain

satisfies the Lipschitz condition and

Since

,

, then

, then

From (5.3), this implies that there exists a constant

and an integer K such that for all

,

For any

, we have

Therefore, we obtain

Letting

gives

for all k.


Lemma 3. Suppose that the Assumption MFR-MA holds. Let

be the sequence of points

generated by the Algorithm MFR-MA. Then there exists a constant

such that for all k,

Proof : We prove (5.5) by considering the following cases: Case 1.

. By the modified Fletcher-Reeves method, we have

Hence, the inequality (5.5) is satisfied with Case 2.

. From the definition of . If

.

, (3.1) and (3.2) cannot simultaneously satisfied for

does not satisfy (3.1) then we have

By the Mean Value theorem, there exists

such that

Then we get

Dividing by

on both sides gives

Now we subtract

from both sides, then

By the Assumption MFR-MA and Cauchy-Schwarz inequality, we have

Consequently,

Hence we obtain

Since

If

, then

does not satisfy (3.2), we have

. Then


By definition of

we obtain

Dividing both sides of the inequality by

Next, we multiply both sides by

Subtracting both sides by

yields

. So we get

gets

By the Assumption MFR-MA and the fact that

, then

Then

Now we introduce a constant

Then we get

by

as required.

Theorem 1. Suppose that the Assumption MFR-MA holds. Let be the sequence of points generated by the Algorithm MFRMA. Then

By lemma 2, we can obtain a constant such that for all k, On the other hand, by lemma 3, we have

Proof : We now prove this theorem by a contradiction. Assume that the conclusion is not true. Then there exist a constant such that for all k,

If we combine the results of both lemmas, we have


We know that by letting

, we have

. Then this contradicts with k. Therefore, there

for all holds

This completes the proof. REFERENCES Al-Baali, A., Descent property and global convergence of the Fletcher_reeves method with inexact line search, IMA J. Numer. Anal, 5 (1985), pp. 121-124. Birgin, E., Martinez, J., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43 (2001), pp. 117-128. Liu, J., Jiang, Y., Global convergence of a spectral conjugate gradient method for un-

constrained optimization, Abstract and Applied Analysis, 2012 (2012). Wei, Z., Qi, L., Ito, S., New step-size rules for optimization problems, Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxin, P. R. China, October, 2000. Wei, Z., Li, G., Qi, L., Global convergence of the Polak-Ribiere-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems, Mathematics of Computation, 77 (2008), pp. 2178-2193. Yu, G., Huang, J., Zhou, Y., A descent spectral conjugate gradient method for impulse noise removal, Applied Mathematics Letters, 23 (2010), pp. 555-560. Zhang, L., Zhou, W., Li, D., Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik, 104 (2006), pp. 561-572. Zoutendijk, G., Nonlinear programming, computational methods, Abadie,J. Integer and Nonlinear Programming, (1970), pp. 37-86.

CAKRAWALA PENDIDIKAN

Recommend Documents