Metode penurunan paling curam adalah metode gradien langkah variabel. Pada setiap iterasi, nilai langkah k dipilih dari kondisi minimum fungsi f(x) dalam arah penurunan, yaitu.
Kondisi ini berarti bahwa pergerakan sepanjang antigradien terjadi selama nilai fungsi f(x) menurun. Dari sudut pandang matematis, pada setiap iterasi, perlu untuk memecahkan masalah minimalisasi satu dimensi sehubungan dengan fungsi
()=f(x(k)-f(x(k)))
Kami menggunakan metode bagian emas untuk ini.
Algoritma dari metode penurunan paling curam adalah sebagai berikut.
Koordinat titik awal x (0) diberikan.
Pada titik x (k) , k = 0, 1, 2, ..., nilai gradien f (x (k)) dihitung.
Ukuran langkah k ditentukan oleh minimalisasi satu dimensi sehubungan dengan fungsi
()=f(x(k)-f(x(k))).
Koordinat titik x (k) ditentukan:
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Kondisi untuk menghentikan proses iteratif diperiksa:
||f(x(k+1))|| .
Jika puas, maka perhitungan berhenti. Jika tidak, transisi ke langkah 1. Interpretasi geometris dari metode penurunan paling curam ditunjukkan pada gambar. satu.
Beras. 2.1. Diagram blok metode penurunan paling curam.
Implementasi metode dalam program:
Metode penurunan paling curam.
Beras. 2.2. Implementasi metode penurunan paling curam.
Kesimpulan: Dalam kasus kami, metode konvergen dalam 7 iterasi. Titik A7 (0,6641; -1,3313) adalah titik ekstrem. Metode konjugasi arah. Untuk fungsi kuadrat, Anda dapat membuat metode gradien, di mana waktu konvergensi akan terbatas dan sama dengan jumlah variabel n.
Kami menyebut beberapa arah dan konjugasi sehubungan dengan beberapa matriks Hess definit positif H jika:
Maka yaitu.. Oleh karena itu, dengan satuan H, arah konjugasi berarti tegak lurus mereka. Dalam kasus umum, H adalah non-sepele. Dalam kasus umum, konjugasi adalah penerapan matriks Hess ke vektor - itu berarti rotasi vektor ini dengan beberapa sudut, ekspansi atau kompresinya.
Dan sekarang sebuah vektor adalah ortogonal terhadap sebuah vektor, yaitu, konjugasi bukanlah ortogonalitas vektor, tetapi ortogonalitas dari vektor yang diputarat.i.i.
Beras. 2.3. Blok diagram metode konjugasi arah.
Implementasi metode dalam program: Metode arah konjugasi.
Beras. 2.4. Implementasi metode arah konjugasi.
Beras. 2.5. Plot metode konjugasi arah.
Kesimpulan: Titik A3 (0,6666; -1,3333) ditemukan dalam 3 iterasi dan merupakan titik ekstrem.
3. Analisis metode untuk menentukan nilai minimum, maksimum fungsi dengan adanya pembatasan
Ingatlah bahwa masalah umum optimasi bersyarat terlihat seperti ini
f(x) ® min, x W,
di mana W adalah himpunan bagian wajar dari R m . Sebuah subkelas dari masalah dengan kendala tipe kesetaraan dibedakan oleh fakta bahwa himpunan diberikan oleh kendala bentuk
f i (x) = 0, di mana f i: R m ®R (i = 1, …, k).
JadiW = (x R m: f i (x) = 0, i = 1, …, k).
Akan lebih mudah bagi kita untuk menulis indeks "0" untuk fungsi f. Dengan demikian, masalah optimasi dengan kendala tipe kesetaraan ditulis sebagai
f 0 (x) ® mnt, (3,1)
f i (x) = 0, i = 1, …, k. (3.2)
Jika kita sekarang dinotasikan dengan f a fungsi pada R m dengan nilai dalam R k , yang notasi koordinatnya berbentuk f(x) = (f 1 (x), …, f k (x)), maka (3.1)–( 3.2) juga dapat ditulis dalam bentuk
f 0 (x) ® min, f(x) = Q.
Secara geometris, masalah dengan kendala tipe kesetaraan adalah masalah menemukan titik terendah dari grafik fungsi f 0 di atas manifold (lihat Gambar 3.1).
Poin yang memenuhi semua batasan (yaitu, poin dari himpunan ) biasanya disebut diterima. Titik x* yang dapat diterima disebut minimum bersyarat dari fungsi f 0 di bawah kendala f i (x) = 0, i = 1, ..., k (atau solusi untuk masalah (3.1)–(3.2)), jika untuk semua titik yang dapat diterima x f 0 (x *) f 0 (x). (3.3)
Jika (3.3) dipenuhi hanya untuk x yang dapat diterima yang terletak di beberapa lingkungan V x * dari titik x*, maka kita berbicara tentang minimum bersyarat lokal. Konsep minima lokal dan global ketat bersyarat didefinisikan secara alami.
Rumusan masalah
Biarkan fungsinya f(x) R n
Diperlukan f(x) X = Rn
Strategi pencarian
x k
} , k = 0,1,...,
seperti yang 
, k = 0,1,...
. Titik urutan ( x k
) dihitung menurut aturan
dimana titiknya x 0 diatur oleh pengguna; ukuran langkah t k ditentukan untuk setiap nilai k dari kondisi
Soal (3) dapat diselesaikan dengan menggunakan kondisi minimum yang diperlukan diikuti dengan memeriksa kondisi minimum yang cukup . Cara ini dapat digunakan baik untuk fungsi yang cukup sederhana yang akan diminimalkan, atau untuk pendekatan awal dari fungsi yang agak kompleks. 
polinomial P(tk)
(biasanya derajat kedua atau ketiga), dan kemudian kondisinya diganti dengan kondisi , dan kondisi dengan kondisi 
Membangun urutan ( x k )
berakhir pada titik x k
, untuk mana , dimana ε
adalah bilangan positif kecil yang diberikan, atau k M
, di mana M
- membatasi jumlah iterasi, atau dengan dua pemenuhan simultan dari dua ketidaksetaraan 
, 
di mana 2
adalah bilangan positif kecil. Pertanyaannya adalah apakah suatu titik x k
dianggap sebagai perkiraan yang ditemukan dari titik minimum lokal yang diinginkan x *
, diselesaikan dengan penelitian tambahan.
Interpretasi geometris dari metode untuk n=2 dalam gambar. 4.
Metode penurunan koordinat
Rumusan masalah
Biarkan fungsinya f(x) , dibatasi dari bawah di set R n dan memiliki turunan parsial kontinu di semua titiknya.
f(x) pada himpunan solusi yang dapat diterima X = Rn , yaitu cari titik sedemikian rupa sehingga
Strategi pencarian
Strategi untuk memecahkan masalah terdiri dalam membangun urutan poin ( x k
} , k = 0,1,...,
seperti yang , k = 0,1,...
. Titik urutan ( x k
) dihitung dengan siklus sesuai dengan aturan
(4)
di mana j - nomor siklus perhitungan; j = 0,1,2,...; k - nomor iterasi di dalam loop, k = 0,1,...,n - 1; e k +1 , k = 0,l,...,n - 1 -vektor satuan, (k+1) -proyeksi yang sama dengan 1; dot x 00 ditetapkan oleh pengguna, ukuran langkah t k dipilih dari kondisi
atau 
.
Jika kondisi yang dipilih pada saat ini t k
tidak dieksekusi, langkahnya dibelah dua dan intinya 
dihitung ulang. Sangat mudah untuk melihat bahwa, untuk j tetap, dalam satu iterasi dengan nomor k
hanya satu titik proyeksi yang berubah x jk
, yang memiliki nomor k + 1
, dan selama seluruh siklus dengan nomor j
, yaitu dimulai dengan k = 0
dan berakhir k=n-1
, semua n proyeksi titik berubah x j0
. Setelah titik ini x jn
diberi nomor xj + 1.0
, dan diambil sebagai titik awal untuk perhitungan dalam j + 1
siklus. Perhitungan berakhir pada titik x jk
ketika setidaknya satu dari tiga kriteria akhir penghitungan terpenuhi: 
, atau , atau pemenuhan ganda ketidaksetaraan .
Poin yang diperoleh sebagai hasil perhitungan dapat ditulis sebagai elemen barisan (xl), di mana l=n*j+k - nomor seri titik,
Interpretasi geometrik dari metode untuk n = 2 ditunjukkan pada gambar. 5.
4. Metode Frank-Wolfe .
Biarkan diperlukan untuk menemukan nilai maksimum dari fungsi cekung
Dalam kondisi
Ciri khas dari masalah ini adalah bahwa sistem kendalanya hanya berisi pertidaksamaan linier. Fitur ini adalah dasar untuk mengganti fungsi tujuan non-linier dengan fungsi linier di sekitar titik yang diteliti, karena solusi dari masalah asli direduksi menjadi solusi sekuensial dari masalah pemrograman linier.
Proses mencari solusi masalah dimulai dengan menentukan titik yang termasuk dalam area solusi yang dapat diterima untuk
270
dacha. Biarkan ini menjadi intinya X(k)
kemudian pada titik ini gradien fungsi (57) dihitung
Dan bangun fungsi linier
Kemudian nilai maksimum dari fungsi ini ditemukan di bawah kendala (58) dan (59). Biarkan solusi dari masalah ini ditentukan oleh titik Z(k)
. Maka koordinat titik X(k+1)
:
Di mana k - beberapa angka, yang disebut langkah perhitungan dan disimpulkan antara nol dan satu (0<k < 1). Это число k mengambil sewenang-wenang atau menentukan
sehingga nilai fungsi di titik X (k + 1) f(X (k + 1)) bergantung kepada k , adalah maksimum. Untuk melakukan ini, Anda perlu menemukan solusi untuk persamaan dan memilih akar terkecilnya. Jika nilainya lebih besar dari satu, maka k=1 . Setelah menentukan nomor k mencari koordinat titik X(k+1) hitung nilai fungsi tujuan di dalamnya dan cari tahu kebutuhan untuk pindah ke titik baru X(k+2) . Jika ada kebutuhan seperti itu, maka hitung pada intinya X(k+1) gradien fungsi tujuan, buka masalah pemrograman linier yang sesuai dan temukan solusinya. Tentukan koordinat titik dan X(k+2) dan menyelidiki kebutuhan untuk perhitungan lebih lanjut. Setelah sejumlah langkah yang terbatas, solusi dari masalah asli diperoleh dengan akurasi yang diperlukan.
Jadi, proses mencari solusi masalah (57) - (59) dengan metode Frank-Wolfe meliputi langkah-langkah berikut:
1. Tentukan solusi fisibel awal untuk masalah tersebut.
2. Temukan gradien fungsi (57) pada titik solusi layak.
3. Bangun fungsi (60) dan temukan nilai maksimumnya dalam kondisi (58) dan (59).
4. Tentukan langkah perhitungannya.
5. Menggunakan rumus (61), komponen solusi layak baru ditemukan.
6. Periksa kebutuhan untuk pindah ke solusi yang dapat diterima berikutnya. Jika perlu, lanjutkan ke tahap 2, jika tidak, solusi yang dapat diterima untuk masalah awal ditemukan.
Metode fungsi penalti.
Pertimbangkan masalah menentukan nilai maksimum fungsi cekung
f (x 1, x 2, .... x n) dalam kondisi g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j 0 (j=1, n) , di mana g i (x 1, x 2, .... x n) adalah fungsi cembung.
Alih-alih menyelesaikan masalah ini secara langsung, temukan nilai maksimum dari fungsi tersebut F (x 1, x 2, ...., x n) \u003d f (x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) yang merupakan jumlah dari fungsi tujuan masalah, dan beberapa fungsi
H(x 1, x 2, ...., x n), ditentukan oleh sistem kendala dan disebut fungsi penalti. Fungsi penalti dapat dibangun dengan berbagai cara. Namun, itu paling sering berbentuk
TETAPI saya > 0
- beberapa angka konstan yang mewakili koefisien bobot.
Menggunakan fungsi penalti, satu secara berurutan bergerak dari satu titik ke titik lain sampai solusi yang dapat diterima diperoleh. Dalam hal ini, koordinat titik berikutnya ditemukan dengan rumus
Ini mengikuti dari hubungan terakhir bahwa jika titik sebelumnya berada di area solusi yang layak dari masalah asli, maka suku kedua dalam tanda kurung siku sama dengan nol dan transisi ke titik berikutnya hanya ditentukan oleh gradien dari fungsi tujuan. Jika titik yang ditunjukkan tidak termasuk dalam wilayah solusi layak, maka karena istilah ini, pada iterasi berikutnya, pengembalian ke wilayah solusi layak tercapai.
solusi. Namun, semakin sedikit aku
, semakin cepat solusi yang dapat diterima ditemukan, tetapi akurasi penentuannya menurun. Oleh karena itu, proses berulang biasanya dimulai pada nilai yang relatif kecil aku
dan, melanjutkannya, nilai-nilai ini secara bertahap meningkat.
Jadi, proses menemukan solusi untuk masalah pemrograman cembung dengan metode fungsi penalti meliputi langkah-langkah berikut:
1. Tentukan solusi fisibel awal.
2. Pilih langkah perhitungan.
3. Untuk semua variabel, ditemukan turunan parsial dari fungsi tujuan dan fungsi yang menentukan luas solusi yang dapat diterima untuk masalah tersebut.
4. Dengan rumus (72) temukan koordinat titik yang mendefinisikan solusi baru yang mungkin untuk masalah tersebut.
5. Periksa apakah koordinat titik yang ditemukan memenuhi sistem kendala masalah. Jika tidak, maka lanjutkan ke langkah berikutnya. Jika koordinat titik yang ditemukan menentukan solusi yang layak untuk masalah tersebut, maka kebutuhan untuk pindah ke solusi layak berikutnya diperiksa. Jika perlu, lanjutkan ke tahap 2, jika tidak, solusi yang dapat diterima untuk masalah awal ditemukan.
6. Atur bobot dan lanjutkan ke langkah 4.
Metode Panah-Hurwitz.
Saat menemukan solusi untuk masalah pemrograman nonlinier menggunakan metode fungsi penalti, kami memilih nilai aku , sewenang-wenang, yang menyebabkan fluktuasi signifikan dalam keterpencilan titik-titik yang ditentukan dari wilayah solusi yang layak. Kerugian ini dihilangkan dengan memecahkan masalah dengan metode Arrow-Hurwitz, yang menurutnya pada langkah berikutnya dari nomor aku (k) dihitung dengan rumus
Sebagai nilai awal aku (0) mengambil angka non-negatif sewenang-wenang.
CONTOH SOLUSI
Contoh 1.
Tentukan minimum lokal dari suatu fungsi
Definisi titik x k
1. Tetapkan.
2. Letakkan k = 0 .
tiga puluh. Menghitung
40 . Menghitung 
. Mari kita lanjutkan ke langkah 5.
lima puluh. Yuk cek kondisinya 
. Mari kita lanjutkan ke langkah 6.
60 . Mari kita atur t 0 \u003d 0,5 .
70. Menghitung
80. Mari kita bandingkan 
. Kita punya 
. Kesimpulan: syarat untuk k = 0
tidak dilakukan. Mari kita atur t0 = 0,25
, kami melanjutkan ke pengulangan langkah 7, 8.
701 . Mari kita hitung.
801 . Mari kita bandingkan f (x 1) dan f (x 0) . Kesimpulan: f(x1)< f (x 0) . Mari kita lanjutkan ke langkah 9.
90. Menghitung
Kesimpulan: kami percaya k=1 dan lanjutkan ke langkah 3.
3 1 . Menghitung
4 1 . Menghitung 
. Mari kita lanjutkan ke langkah 5.
5 1 . Yuk cek kondisinya k M: k = 1< 10 = M . Mari kita lanjutkan ke langkah 6.
6 1 . Mari kita atur t 1 \u003d 0,25.
7 1 . Menghitung
8 1 . Mari kita bandingkan f (x 2) dengan f (x 1) . Kesimpulan: f (x 2)< f (х 1). Mari kita lanjutkan ke langkah 9.
9 1 . Menghitung
Kesimpulan: kami percaya k = 2 dan lanjutkan ke langkah 3.
3 2 . Menghitung
4 2 . Mari kita hitung. Mari kita lanjutkan ke langkah 5.
5 2 . Yuk cek kondisinya k M : k = 2< 10 = М , lanjutkan ke langkah 6.
6 2 . Mari kita atur t2 =0,25 .
7 2 . Menghitung
8 2 . Mari kita bandingkan f (x 3) dan f (x 2) . Kesimpulan: f (x 3)< f (х 2) .Pergi ke langkah 9.
9 2 . Menghitung 
Kesimpulan: kami percaya k = 3 dan lanjutkan ke langkah 3.
3 3 . Menghitung
4 3 . Mari kita hitung. Mari kita lanjutkan ke langkah 5.
5 3 . Yuk cek kondisinya k M : k = 3<10 = М , lanjutkan ke langkah 6.
6 3 . Mari kita atur t 3 \u003d 0,25.
7 3 . Menghitung
8 3 . Mari kita bandingkan f (x 4) dan f (x 3) : f (x 4)< f (х 3) .
9 3 . Menghitung 
Kondisi terpenuhi di k = 2,3 . Perhitungan
selesai. Poin ditemukan
pada gambar. 3 titik yang diperoleh dihubungkan oleh garis putus-putus.
II. Analisis Poin x 4 .
Fungsi 
terdiferensialkan dua kali, jadi kami memeriksa kondisi cukup untuk minimum pada titik x 4
. Untuk melakukan ini, kami menganalisis matriks Hessian.
Matriksnya konstan dan pasti positif (mis. . H > 0
), karena kedua minor sudutnya dan positif. Oleh karena itu intinya 
adalah pendekatan yang ditemukan dari titik minimum lokal , dan nilai 
adalah pendekatan yang ditemukan dari nilai f(x*)=0
. Perhatikan bahwa kondisi H > 0
, secara bersamaan merupakan kondisi untuk kecembungan ketat fungsi 
. Oleh karena itu, ada pendekatan yang ditemukan dari titik minimum global f(x)
dan nilai terkecilnya pada R2
. ■
Contoh 2
Tentukan minimum lokal dari suatu fungsi
I. Penentuan titik x k, di mana setidaknya salah satu kriteria terminasi terpenuhi.
1. Tetapkan.
Temukan gradien suatu fungsi di titik sembarang
2. Letakkan k = 0 .
tiga puluh. Menghitung
40 . Menghitung . Mari kita lanjutkan ke langkah 5.
lima puluh. Yuk cek kondisinya 
. Mari kita lanjutkan ke langkah 6.
6°. Poin selanjutnya ditemukan oleh rumus
Mari kita substitusikan ekspresi yang diperoleh untuk koordinat dalam
Tentukan fungsi minimum f(t0) pada t0 menggunakan kondisi yang diperlukan untuk ekstrem tanpa syarat:
Dari sini t0 = 0,24
. Sebagai 
, nilai langkah yang ditemukan memberikan fungsi minimum f(t0)
pada t0
.
Mari kita definisikan 
70. Ayo temukan
8°. Menghitung
Kesimpulan: kami percaya k = 1 dan lanjutkan ke langkah 3.
3 1 . Menghitung
4 1 . Menghitung 
5 1 . Yuk cek kondisinya k 1: k = 1< 10 = М.
6 1 . Mari kita definisikan
7 1 . Ayo temukan 
:
8 1 . Menghitung
Kami percaya k = 2 dan lanjutkan ke langkah 3.
3 2 . Menghitung
4 2 . Menghitung
5 2 . Yuk cek kondisinya k M: k = 2< 10 = M .
6 2 . Mari kita definisikan
7 2 . Ayo temukan 
8 2 . Menghitung
Kami percaya k=3 dan lanjutkan ke langkah 3.
3 3 . Menghitung
4 3 . Mari kita hitung.
Perhitungannya sudah selesai. Poin ditemukan
II. Analisis Poin x 3 .
Pada Contoh 1.1 (Bab 2 1) ditunjukkan bahwa fungsi f(x) benar-benar cembung dan, oleh karena itu, pada titik 3 adalah perkiraan yang ditemukan dari titik minimum global X* .
Contoh 3
Tentukan minimum lokal dari suatu fungsi
I. Penentuan titik x jk , di mana setidaknya salah satu kriteria terminasi terpenuhi.
1. Tetapkan
Temukan gradien suatu fungsi di titik sembarang 
2. Atur j = 0.
tiga puluh. Yuk cek pemenuhan syaratnya
40 . Mari kita atur k = 0.
lima puluh. Yuk cek pemenuhan syaratnya
60 . Menghitung
70. Yuk cek kondisinya 
80. Mari kita atur
90. Menghitung 
, di mana
100 . Yuk cek kondisinya
Kesimpulan: kita asumsikan dan lanjutkan ke langkah 9.
9 01 . Menghitung x 01 selangkah demi selangkah
1001 . Yuk cek kondisinya 
110 . Yuk cek syaratnya
Kami percaya k=1 dan lanjutkan ke langkah 5.
5 1 . Yuk cek kondisinya
6 1 . Menghitung
7 1 . Yuk cek kondisinya
8 1 . Mari kita atur
9 1 . Menghitung
10 1 . Yuk cek kondisinya 
:
11 1 . Yuk cek syaratnya
Kami percaya k = 2 , lanjutkan ke langkah 5.
5 2 . Yuk cek kondisinya. Setel , lanjutkan ke langkah 3.
3 1 . Yuk cek kondisinya
4 1 . Mari kita atur k = 0.
5 2 . Yuk cek kondisinya
6 2 . Menghitung
7 2 . Yuk cek kondisinya
8 2 . Mari kita atur
9 2 . Menghitung
10 2 . Yuk cek kondisinya 
11 2 . Yuk cek syaratnya
Kami percaya k=1 dan lanjutkan ke langkah 5.
5 3 . Yuk cek kondisinya
6 3 . Menghitung
7 3 . Yuk cek syaratnya
8 3 . Mari kita atur
9 3 . Menghitung
10 3 . Yuk cek kondisinya 
11 3 . Yuk cek syaratnya
Mari kita atur k = 2 dan lanjutkan ke langkah 5.
5 4 . Yuk cek kondisinya 
Kami percaya j \u003d 2, x 20 \u003d x 12 dan lanjutkan ke langkah 3.
3 2 . Yuk cek kondisinya
4 2 . Mari kita atur k=0 .
5 4 . Yuk cek kondisinya
6 4 . Menghitung
7 4 . Yuk cek kondisinya
8 4 . Mari kita atur
9 4 . Menghitung
10 4 . Mari kita periksa kondisinya, lanjutkan ke langkah 11.
11 4 . Yuk cek syaratnya
Kondisi terpenuhi dalam dua siklus berturut-turut dengan angka j = 2 dan j -1 = 1 . Perhitungan selesai, poin ditemukan
pada gambar. 6, titik-titik yang diperoleh dihubungkan oleh garis putus-putus.
Dalam metode penurunan koordinat, kita turun sepanjang garis putus-putus yang terdiri dari segmen garis yang sejajar dengan sumbu koordinat.
II. Analisis titik x21.
Contoh 1.1 menunjukkan bahwa fungsi f(x)
benar-benar cembung, memiliki minimum tunggal, dan karenanya merupakan titik 
adalah pendekatan yang ditemukan dari titik minimum global.
Dalam semua metode gradien di atas, urutan titik ( x k ) konvergen ke titik stasioner dari fungsi f(x) di bawah proposisi yang cukup umum tentang sifat-sifat fungsi ini. Secara khusus, teorema ini benar:
Dalil. Jika fungsi f (x) dibatasi dari bawah, gradiennya memenuhi kondisi Lipschitz () dan pilihan nilai t n dihasilkan oleh salah satu metode yang dijelaskan di atas, maka apa pun titik awalnya x 0 :
pada .
Dalam implementasi praktis skema
k=1, 2, …n.
iterasi berhenti jika untuk semua i , i = 1, 2, ..., n , kondisi tipe
,
di mana adalah beberapa nomor yang diberikan yang mencirikan keakuratan menemukan minimum.
Di bawah kondisi teorema, metode gradien memastikan konvergensi dalam fungsi atau ke batas bawah terkecil (jika fungsi f(x) tidak memiliki minimum; Nasi. 7), atau ke nilai fungsi di beberapa titik stasioner, yang merupakan limit dari barisan (x ke ). Sangat mudah untuk menemukan contoh ketika pelana direalisasikan pada titik ini, dan bukan minimum. Dalam praktiknya, metode penurunan gradien dengan percaya diri melewati titik pelana dan menemukan minima dari fungsi tujuan (dalam kasus umum, minima lokal).
KESIMPULAN
Contoh metode gradien optimasi tak terbatas dipertimbangkan di atas. Sebagai hasil dari pekerjaan yang dilakukan, kesimpulan berikut dapat ditarik:
1. Masalah yang kurang lebih kompleks untuk menemukan ekstrem dengan adanya pembatasan memerlukan pendekatan dan metode khusus.
2. Banyak algoritma untuk menyelesaikan masalah dengan batasan termasuk minimisasi tanpa batasan sebagai tahap tertentu.
3. Metode penurunan yang berbeda berbeda satu sama lain dalam cara memilih arah penurunan dan panjang langkah sepanjang arah itu.
4. Sejauh ini tidak ada teori seperti itu yang akan memperhitungkan fitur fungsi apa pun yang menggambarkan rumusan masalah. Preferensi harus diberikan pada metode yang lebih mudah dikelola dalam proses pemecahan masalah.
Masalah optimasi yang diterapkan secara nyata sangat kompleks. Metode optimasi modern tidak selalu mengatasi pemecahan masalah nyata tanpa bantuan manusia.
BIBLIOGRAFI
1. Kosorukov O.A. Riset Operasi: Sebuah Buku Teks. 2003
2. Pantleev A.V. Metode optimasi dalam contoh dan tugas: buku teks. Keuntungan. 2005
3. Shishkin E.V. Riset operasi: buku teks. 2006
4. Akulich I.L. Pemrograman matematika dalam contoh dan tugas. 1986
5. Wentzel E.S. Operasi pencarian. 1980
6. Venttsel E.S., Ovcharov L.A. Teori probabilitas dan aplikasi tekniknya. 1988
©2015-2019 situs
Semua hak milik penulisnya. Situs ini tidak mengklaim kepengarangan, tetapi menyediakan penggunaan gratis.
Tanggal pembuatan halaman: 2017-07-02
Gbr.3. Interpretasi geometris dari metode penurunan paling curam. Pada setiap langkah, dipilih sehingga iterasi berikutnya adalah titik minimum fungsi pada sinar L.
Varian metode gradien ini didasarkan pada pilihan langkah dari pertimbangan berikut. Dari titik kita akan bergerak ke arah antigradien sampai kita mencapai minimum fungsi f dalam arah ini, yaitu, pada sinar:
Dengan kata lain, dipilih sehingga iterasi berikutnya adalah titik minimum dari fungsi f pada sinar L (lihat Gambar 3). Varian dari metode gradien ini disebut metode penurunan paling curam. Perhatikan, bahwa dalam metode ini arah langkah-langkah yang berdekatan adalah ortogonal.
Metode penurunan paling curam membutuhkan pemecahan masalah optimasi satu dimensi pada setiap langkah. Praktek menunjukkan bahwa metode ini seringkali membutuhkan operasi yang lebih sedikit daripada metode gradien dengan langkah konstan.
Dalam situasi umum, bagaimanapun, tingkat konvergensi teoritis dari metode penurunan paling curam tidak lebih tinggi dari tingkat konvergensi dari metode gradien dengan langkah yang konstan (optimal).
Contoh numerik
Metode Penurunan Gradien Langkah Konstan
Untuk mempelajari konvergensi metode penurunan gradien dengan langkah konstan, fungsi dipilih:
Dari hasil yang diperoleh, kita dapat menyimpulkan bahwa metode divergen jika frekuensinya terlalu besar, dan konvergen lambat jika frekuensinya terlalu kecil, dan akurasinya lebih buruk. Hal ini diperlukan untuk memilih langkah yang terbesar dari yang metode konvergen.
Metode gradien dengan pemisahan langkah
Untuk mempelajari konvergensi metode penurunan gradien dengan pemisahan langkah (2), fungsi berikut dipilih:
Pendekatan awal adalah titik (10,10).
Kriteria berhenti yang digunakan:
Hasil percobaan ditunjukkan pada tabel:
|
Berarti parameter |
Nilai parameter |
Nilai parameter |
Mencapai akurasi |
Jumlah iterasi |
Dari hasil yang diperoleh, kita dapat menyimpulkan bahwa pilihan parameter yang optimal adalah: , meskipun metode ini tidak terlalu sensitif terhadap pilihan parameter.
Metode Turun Tercuram
Untuk mempelajari konvergensi metode penurunan paling curam, fungsi berikut dipilih:
Pendekatan awal adalah titik (10,10). Kriteria berhenti yang digunakan:
Metode bagian emas digunakan untuk menyelesaikan masalah optimasi satu dimensi.
Metode tersebut memperoleh akurasi 6e-8 dalam 9 iterasi.
Dari sini kita dapat menyimpulkan bahwa metode penurunan paling curam konvergen lebih cepat daripada metode gradien pemisahan langkah dan metode penurunan gradien langkah konstan.
Kerugian dari metode penurunan paling curam adalah kebutuhan untuk memecahkan masalah optimasi satu dimensi.
Saat memprogram metode penurunan gradien, seseorang harus berhati-hati dalam memilih parameter, yaitu
- · Metode penurunan gradien dengan langkah konstan: langkah harus dipilih kurang dari 0,01, jika tidak, metode divergen (metode dapat menyimpang bahkan dengan langkah seperti itu, tergantung pada fungsi yang dipelajari).
- · Metode gradien dengan pemisahan langkah tidak terlalu sensitif terhadap pilihan parameter. Salah satu opsi yang dapat dipilih:
- · Metode penurunan paling curam: Sebagai metode optimasi satu dimensi, metode bagian emas (bila berlaku) dapat digunakan.
Metode gradien konjugasi adalah metode iteratif untuk optimasi tak terbatas dalam ruang multidimensi. Keuntungan utama dari metode ini adalah memecahkan masalah optimasi kuadrat dalam jumlah langkah yang terbatas. Oleh karena itu, metode gradien konjugasi untuk mengoptimalkan fungsi kuadrat pertama kali dijelaskan, rumus iteratif diturunkan, dan perkiraan tingkat konvergensi diberikan. Setelah itu, ditunjukkan bagaimana metode konjugasi digeneralisasi untuk mengoptimalkan fungsi arbitrer, berbagai versi metode dipertimbangkan, dan konvergensi dibahas.
Pernyataan masalah optimasi
Biarkan himpunan diberikan dan fungsi tujuan (fungsi tujuan) didefinisikan pada himpunan ini. Masalah optimasi adalah menemukan batas atas atau batas bawah yang tepat dari fungsi tujuan pada himpunan. Himpunan titik di mana batas bawah fungsi tujuan tercapai dilambangkan.
Jika, maka masalah optimasi disebut tidak dibatasi. Jika, maka masalah optimasi disebut terkendala.
Metode gradien konjugasi untuk fungsi kuadrat
Pernyataan metode
Pertimbangkan masalah optimasi berikut:
Di sini, adalah matriks ukuran pasti positif simetris. Masalah optimasi seperti itu disebut kuadrat. Perhatikan itu. Kondisi ekstrem suatu fungsi ekuivalen dengan sistem Fungsi mencapai batas bawahnya pada satu titik yang ditentukan oleh persamaan. Dengan demikian, masalah optimasi ini direduksi menjadi penyelesaian sistem persamaan linier Ide dari metode gradien konjugasi adalah sebagai berikut: Membiarkan menjadi basis dari c. Kemudian, untuk sembarang titik, vektor diekspansi dalam bentuk basis Jadi, dapat direpresentasikan sebagai
Setiap perkiraan berikutnya dihitung dengan rumus:
Definisi. Dua vektor dan disebut konjugasi terhadap matriks simetris B jika
Mari kita jelaskan metode membangun basis dalam metode gradien konjugasi Sebagai pendekatan awal, kami memilih vektor arbitrer. Pada setiap iterasi, aturan berikut dipilih:
Vektor basis dihitung dengan rumus:
Koefisien dipilih sehingga vektor dan konjugasi terhadap A.
Jika dilambangkan dengan, maka setelah beberapa penyederhanaan, kami memperoleh rumus akhir yang digunakan dalam penerapan metode gradien konjugasi dalam praktik:
Teorema berikut ini benar untuk metode gradien konjugasi: Teorema Let, di mana adalah matriks definit positif simetris dengan ukuran. Kemudian metode gradien konjugasi konvergen tidak lebih dari langkah dan hubungan berikut berlaku:
Konvergensi Metode
Jika semua perhitungan eksak, dan data awal eksak, maka metode konvergen ke solusi sistem tidak lebih dari iterasi, di mana adalah dimensi sistem. Analisis yang lebih baik menunjukkan bahwa jumlah iterasi tidak melebihi, di mana adalah jumlah nilai eigen yang berbeda dari matriks A. Untuk memperkirakan tingkat konvergensi, perkiraan (agak kasar) berikut ini benar:
Ini memungkinkan memperkirakan tingkat konvergensi jika perkiraan untuk nilai eigen maksimum dan minimum dari matriks diketahui.Dalam praktiknya, kriteria penghentian berikut paling sering digunakan:
Kompleksitas komputasi
Operasi dilakukan pada setiap iterasi metode. Jumlah operasi ini diperlukan untuk menghitung produk - ini adalah prosedur yang paling memakan waktu di setiap iterasi. Perhitungan lainnya membutuhkan operasi O(n). Kompleksitas komputasi total metode tidak melebihi - karena jumlah iterasi paling banyak n.
Contoh numerik
Kami menerapkan metode gradien konjugasi untuk menyelesaikan sistem, di mana C menggunakan metode gradien konjugasi, solusi sistem ini diperoleh dalam dua iterasi. Nilai eigen matriks - 5, 5, -5 - dua di antaranya berbeda, oleh karena itu, menurut perkiraan teoretis, jumlah iterasi tidak boleh melebihi dua
Metode gradien konjugasi adalah salah satu metode yang paling efisien untuk menyelesaikan SLAE dengan matriks definit positif. Metode ini menjamin konvergensi dalam jumlah langkah yang terbatas, dan akurasi yang diperlukan dapat dicapai jauh lebih awal. Masalah utama adalah bahwa, karena akumulasi kesalahan, ortogonalitas angin basis dapat dilanggar, yang memperburuk konvergensi
Metode gradien konjugasi secara umum
Sekarang mari kita pertimbangkan modifikasi metode gradien konjugasi untuk kasus ketika fungsi yang diperkecil bukan kuadrat: Kami akan memecahkan masalah:
Fungsi terdiferensiasi terus menerus. Untuk memodifikasi metode gradien konjugasi untuk menyelesaikan masalah ini, perlu untuk mendapatkan rumus yang tidak menyertakan matriks A:
dapat dihitung dengan menggunakan salah satu dari tiga rumus:
1. - Metode Fletcher-Reeves
- 2. - Metode Polak-Ribi`ere
Jika fungsinya kuadrat dan benar-benar cembung, maka ketiga rumus memberikan hasil yang sama. Jika adalah fungsi arbitrer, maka masing-masing rumus sesuai dengan modifikasinya sendiri dari metode gradien konjugasi. Rumus ketiga jarang digunakan karena memerlukan fungsi dan perhitungan Hessian fungsi pada setiap langkah metode.
Jika fungsinya bukan kuadrat, metode gradien konjugasi mungkin tidak konvergen dalam sejumlah langkah yang berhingga. Selain itu, perhitungan yang tepat pada setiap langkah hanya mungkin dalam kasus yang jarang terjadi. Oleh karena itu, akumulasi kesalahan mengarah pada fakta bahwa vektor tidak lagi menunjukkan arah fungsi menurun. Kemudian pada beberapa langkah mereka mengira. Himpunan semua angka yang diterima akan dilambangkan sebagai. Angka-angka tersebut disebut waktu pembaruan metode. Dalam praktiknya, seseorang sering memilih di mana dimensi ruang.
Konvergensi Metode
Untuk metode Fletcher-Reeves, ada teorema konvergensi yang memberlakukan kondisi yang tidak terlalu ketat pada fungsi yang diminimalkan: Teorema. Biarkan kondisi berikut dipenuhi:
Paket terbatas
Turunan memenuhi kondisi Lipschitz dengan konstanta di beberapa lingkungan
set M: .
Konvergensi dibuktikan untuk metode Polak-Reiber dengan asumsi bahwa fungsi tersebut benar-benar cembung. Dalam kasus umum, tidak mungkin untuk membuktikan konvergensi metode Polak-Reiber. Sebaliknya, teorema berikut ini benar: Teorema. Asumsikan bahwa dalam metode Polak-Reiber nilai pada setiap langkah dihitung dengan tepat. Kemudian ada fungsi, dan aproksimasi awal, sehingga.
Namun, metode Polak-Reiber bekerja lebih baik dalam praktiknya. Kriteria penghentian yang paling umum dalam praktik: Norma gradien menjadi kurang dari ambang batas tertentu Nilai fungsi selama m iterasi berturut-turut hampir tidak berubah
Kompleksitas komputasi
Pada setiap iterasi metode Polack-Reiber atau Fletcher-Reeves, fungsi dan gradiennya dihitung satu kali, dan masalah optimasi satu dimensi diselesaikan. Dengan demikian, kompleksitas satu langkah dari metode gradien konjugasi memiliki urutan yang sama dengan kompleksitas langkah dari metode penurunan paling curam. Dalam prakteknya, metode gradien konjugasi menunjukkan tingkat konvergensi terbaik.
Kami akan mencari fungsi minimum dengan metode gradien konjugasi
Minimum dari fungsi ini sama dengan 1 dan dicapai pada titik (5, 4). Mari kita bandingkan metode Polack-Reiber dan Fletcher-Reeves pada contoh fungsi ini. Iterasi di kedua metode berhenti ketika kuadrat dari norma gradien menjadi lebih kecil pada langkah saat ini. Metode bagian emas digunakan untuk seleksi.
|
Metode Fletcher-Reeves |
Metode Polack-Reiber |
|||||
|
Jumlah iterasi |
Solusi yang ditemukan |
Nilai fungsi |
Jumlah iterasi |
Solusi yang ditemukan |
Nilai fungsi |
|
|
(5.01382198,3.9697932) |
(5.03942877,4.00003512) |
|||||
|
(5.01056482,3.99018026) |
(4.9915894,3.99999044) |
|||||
|
(4.9979991,4.00186173) |
(5.00336181,4.0000018) |
|||||
|
(4.99898277,4.00094645) |
(4.99846808,3.99999918) |
|||||
|
(4.99974658,4.0002358) |
(4.99955034,3.99999976) |
Dua versi dari metode gradien konjugasi diterapkan: untuk meminimalkan fungsi kuadrat, dan untuk meminimalkan fungsi arbitrer. Dalam kasus pertama, metode ini diimplementasikan oleh fungsi vektor
Metode penurunan gradien adalah alat yang cukup ampuh untuk memecahkan masalah optimasi. Kerugian utama dari metode ini adalah area penerapan yang terbatas. Metode gradien konjugasi menggunakan informasi hanya tentang bagian linier dari kenaikan pada suatu titik, seperti pada metode penurunan gradien. Pada saat yang sama, metode gradien konjugasi memungkinkan pemecahan masalah kuadrat dalam jumlah langkah yang terbatas. Pada banyak masalah lain, metode gradien konjugasi juga mengungguli metode penurunan gradien. Konvergensi metode gradien pada dasarnya tergantung pada seberapa akurat masalah optimasi satu dimensi diselesaikan. Loop metode yang mungkin diperbaiki dengan pembaruan. Namun, jika metode tersebut mencapai minimum lokal dari fungsi tersebut, kemungkinan besar metode tersebut tidak akan dapat keluar darinya.
Anotasi: Dalam kuliah ini, metode optimasi multiparameter seperti metode penurunan paling curam dan metode Davidon-Fletcher-Powell dibahas secara luas. Selain itu, analisis komparatif dari metode di atas dilakukan untuk menentukan yang paling efektif, kelebihan dan kekurangannya diidentifikasi; dan juga mempertimbangkan masalah optimasi multivariat, seperti metode ngarai dan metode multi-ekstremitas.
1. Metode penurunan paling curam
Inti dari metode ini adalah dengan bantuan yang disebutkan sebelumnya metode penurunan koordinat pencarian dilakukan dari titik tertentu dalam arah yang sejajar dengan salah satu sumbu, ke titik minimum dalam arah ini. Pencarian kemudian dilakukan dalam arah yang sejajar dengan sumbu lainnya, dan seterusnya. Arahnya, tentu saja, tetap. Tampaknya masuk akal untuk mencoba memodifikasi metode ini sedemikian rupa sehingga pada setiap tahap pencarian titik minimum dilakukan di sepanjang arah "terbaik". Tidak jelas arah mana yang "terbaik", tetapi diketahui bahwa arah gradien adalah arah kenaikan tercepat fungsi. Oleh karena itu, arah yang berlawanan adalah arah penurunan tercepat dari fungsi. Properti ini dapat dibenarkan sebagai berikut.
Mari kita asumsikan bahwa kita bergerak dari titik x ke titik berikutnya x + hd , di mana d adalah beberapa arah dan h adalah langkah dengan panjang tertentu. Oleh karena itu, gerakan dilakukan dari titik (x 1, x 2, ..., x n) ke titik (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), di mana
Perubahan nilai fungsi ditentukan oleh relasi
| (1.3) |
Sampai dengan orde pertama zx i , dan turunan parsial dihitung pada titik x . Bagaimana seharusnya arah d i dipilih yang memenuhi persamaan (1.2) untuk mendapatkan perubahan terbesar dalam fungsi df ? Di sinilah masalah maksimalisasi dengan kendala muncul. Kami menerapkan metode pengganda Lagrange, dengan bantuan yang kami definisikan fungsinya
Nilai df yang memenuhi kendala (1.2) mencapai maksimum ketika fungsi
Mencapai maksimum. turunannya
Karena itu,
 |
(1.6) |
Maka di~df/dx i dan arah d sejajar dengan arah V/(x) di titik x.
Dengan demikian, peningkatan lokal terbesar fungsi untuk langkah kecil tertentu h terjadi ketika d adalah arah Vf(x) atau g(x) . Oleh karena itu, arah penurunan paling curam adalah arah
Dalam bentuk yang lebih sederhana, persamaan (1.3) dapat ditulis sebagai berikut:
Dimana adalah sudut antara vektor Vf(x) dan dx . Untuk nilai dx yang diberikan, kami meminimalkan df dengan memilih , sehingga arah dx sama dengan arah -Vf(x) .
Komentar. Arah gradien tegak lurus ke sembarang titik pada garis tingkat konstan, karena fungsinya konstan sepanjang garis ini. Jadi, jika (d 1 , d 2 , ..., d n) adalah anak tangga kecil di sepanjang garis datar, maka
Dan maka dari itu
 |
(1.8) |
Contoh 6.8.3-1. Tentukan minimum fungsi Q(x,y) dengan menggunakan metode GDS.
Misal Q(x,y) = x 2 +2y 2 ; x 0 = 2; y 0 = 1.
Mari kita periksa kondisi cukup untuk keberadaan minimum:
Mari kita lakukan satu iterasi sesuai dengan algoritma.
1. Q(x0,y0) = 6.
2.
Ketika x \u003d x 0 dan y \u003d y 0, 
3. Langkah l k \u003d l 0 \u003d 0,5
Jadi 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.
Inti dari metode ini adalah sebagai berikut. Dari titik yang dipilih (x 0 ,y 0) penurunan dilakukan ke arah anti-gradien sampai nilai minimum dari fungsi tujuan Q(x, y) sepanjang balok tercapai (Gbr. 6.8.4- 1). Pada titik yang ditemukan, balok menyentuh garis datar. Kemudian, dari titik ini, penurunan dilakukan ke arah anti-gradien (tegak lurus dengan garis datar) sampai balok yang sesuai menyentuh garis datar yang melewatinya di titik baru, dan seterusnya.
Mari kita nyatakan fungsi tujuan Q(x, y) dalam langkah l. Pada saat yang sama, kami mewakili fungsi tujuan pada langkah tertentu sebagai fungsi dari satu variabel, yaitu. ukuran langkah
Ukuran langkah pada setiap iterasi ditentukan dari kondisi minimum:
Min( (l)) l k = l*(x k , y k), l >0.
Jadi, pada setiap iterasi, pilihan langkah l k menyiratkan solusi dari masalah optimasi satu dimensi. Menurut metode pemecahan masalah ini, ada:
· metode analisis (NSA);
· Metode numerik (NCh).
Pada metode NSA, nilai langkah diperoleh dari kondisi , dan pada metode NSS, nilai lk ditemukan pada segmen dengan akurasi yang diberikan menggunakan salah satu metode optimasi satu dimensi.
Contoh 6.8.4-1. Tentukan fungsi minimum Q(x,y)=x 2 + 2y 2 dengan ketelitian e=0.1, pada kondisi awal: x 0 =2; y 0 = 1.
Mari kita lakukan satu iterasi dengan metode NSA.
=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .
Dari kondisi (l)=0 kita cari nilai l*: 
Fungsi yang dihasilkan l=l(x,y) memungkinkan Anda menemukan nilai l. Untuk x=2 dan y=1 kita memiliki l=0,3333.
Hitung nilai koordinat titik berikutnya:
Mari kita periksa pemenuhan kriteria penghentian iterasi untuk k=1:
Karena |2*0.6666|>0.1 dan |-0.3333*4|>0.1 , kondisi untuk mengakhiri proses iterasi tidak terpenuhi, mis. minimal tidak ditemukan. Oleh karena itu, Anda harus menghitung nilai baru l pada x=x 1 dan y=y 1 dan mendapatkan koordinat titik turun berikutnya. Perhitungan berlanjut sampai kondisi akhir penurunan terpenuhi.
Perbedaan metode NN numerik dengan metode analitik adalah pencarian nilai l pada setiap iterasi dilakukan dengan salah satu metode numerik optimasi satu dimensi (misalnya metode dikotomi atau metode golden section). Dalam hal ini, kisaran nilai yang dapat diterima dari l - berfungsi sebagai interval ketidakpastian.
