Bir işleve girme kuralları
İÇİNDE en dik iniş yöntemi yönü, ▽f(x) fonksiyonunun gradyan vektörünün yönünün tersi olan bir vektör, arama yönü olarak seçilir. İtibaren matematiksel analiz grad f(x)=▽f(x) vektörünün fonksiyondaki en hızlı artışın yönünü karakterize ettiği bilinmektedir (fonksiyonun gradyanına bakınız). Bu nedenle - grad f (X) = -▽f(X) vektörüne denir anti-gradyan ve en hızlı düşüş yönüdür. En dik iniş yönteminin uygulandığı yineleme ilişkisi şu şekildedir: X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
burada λ k >0 adım boyutudur. Adım boyutu seçimine bağlı olarak şunları alabilirsiniz: çeşitli seçenekler Gradyan yöntemi. Optimizasyon işlemi sırasında adım boyutu λ sabitse, bu yönteme ayrı adımlı gradyan yöntemi adı verilir. λ k =min f(X k + λS k) koşulundan λ k seçilirse, ilk yinelemelerdeki optimizasyon süreci önemli ölçüde hızlandırılabilir.
λk'yi belirlemek için herhangi bir tek boyutlu optimizasyon yöntemi kullanılır. Bu durumda yönteme en dik iniş yöntemi denir. Kural olarak, genel durum Fonksiyonun minimumunu elde etmek için bir adım yeterli değildir; sonraki hesaplamalar sonucun iyileştirilmesine izin verene kadar süreç tekrarlanır.
Eğer uzay bazı değişkenlerde çok uzamışsa o zaman bir “dağ geçidi” oluşur. Arama yavaşlayabilir ve "dağ geçidinin" dibinde zikzak çizebilir. Bazen kabul edilebilir bir zaman diliminde çözüme ulaşılamayabilir.
Yöntemin diğer bir dezavantajı ||▽f(X k)|| durdurma kriteri olabilir.<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Örnek. Fonksiyonu en aza indirmek için x k =(-2, 3) noktasından başlayarak, en dik iniş yöntemini kullanarak x k +1 noktasını belirleyin.
Arama yönü olarak geçerli noktadaki gradyan vektörünü seçin 
Durdurma kriterini kontrol edelim. Sahibiz 
Fonksiyonun değerini f(X 1) = 35 başlangıç noktasında hesaplayalım.
antigradyan yön boyunca adım atın
Fonksiyonun değerini yeni bir noktada hesaplayalım
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Bu doğrultuda amaç fonksiyonunun minimuma ulaşacağı bir adım bulalım. Fonksiyonun bir ekstremumunun varlığı için gerekli koşuldan
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
veya f'(X 2) = 2598 λ 1 – 425 = 0.
λ 1 = 0,164 adımını elde ederiz
Bu adımı tamamlamak şu noktaya yol açacaktır 
burada gradyan değeri 
, fonksiyon değeri f(X 2) = 0,23. Antigradyan yönünde bir adım attığımız noktadan itibaren doğruluk elde edilmez.
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f'(X 2) = 11,76 – 6,12λ 1 = 0
λ 1 = 0,52 elde ederiz 
Sorunun beyanı
Fonksiyon verilsin f(x) Rn
Gerekli f(x) X = Rn
Arama stratejisi
xk
} , k = 0,1,...,
Öyle ki 
, k = 0,1,...
. Sıra noktaları ( xk
) kuralına göre hesaplanır
amaç nerede x 0 kullanıcı tanımlı; adım boyutu teşekkürler Her değer için belirlenen k durumdan
Problem (3), gerekli minimum koşul kullanılarak ve ardından yeterli minimum koşulun kontrol edilmesiyle çözülebilir. Bu yol, minimize edilecek yeterince basit bir fonksiyonla veya yeterince ön bir yaklaşımla kullanılabilir. karmaşık fonksiyon 
polinom P(t k)
(genellikle ikinci veya üçüncü dereceden) ve daha sonra koşulun yerine koşul, koşulun yerine de koşul geçer. 
Sıralama (xk)
noktada biter xk
, bunun için , nerede ε
- belirli bir küçük pozitif sayı veya k ≥ M
, Nerede M
- sınırlı sayıda yineleme veya iki eşitsizliğin aynı anda iki kez yürütülmesi 
, 
Nerede e 2
- küçük pozitif sayı. Soru, bir noktanın xk
İstenilen yerel minimum noktanın bulunan yaklaşımı olarak kabul edilir X*
, ek araştırmalarla çözülür.
Yöntemin geometrik yorumu n=2 Şek. 4.
Koordinat iniş yöntemi
Sorunun beyanı
Fonksiyon verilsin f(x) , sette aşağıda sınırlanmıştır Rn ve tüm noktalarında sürekli kısmi türevlere sahiptir.
f(x) uygulanabilir çözümler kümesinde X = Rn , yani öyle bir nokta bul ki
Arama stratejisi
Sorunu çözme stratejisi bir dizi nokta oluşturmaktır ( xk
} , k = 0,1,...,
Öyle ki , k = 0,1,...
. Sıra noktaları ( xk
) kurala uygun olarak döngüler üzerinden hesaplanır
(4)
Nerede J - hesaplama döngüsü numarası; j = 0,1,2,...; k - döngü içindeki yineleme numarası, k = 0,1,...,n - 1; e k +1 , k = 0,l,...,n - 1 -birim vektör, (k+1) -inci projeksiyonu 1'e eşit olan; nokta x 00 kullanıcı tanımlı, adım boyutu teşekkürler koşulundan seçilir
veya 
.
Geçerli durumda seçilen koşul ise teşekkürler
yerine getirilmezse adım yarıya indirilir ve süre 
tekrar hesaplanır. Sabit bir j için sayı ile bir yinelemede bunu görmek kolaydır. k
nokta değişikliklerinin yalnızca bir projeksiyonu x jk
, bir numarası olan k+1
ve sayı ile tüm döngü boyunca J
, yani itibaren k = 0
ve bitiyor k = n -1
, nokta değişiminin tüm n projeksiyonları xj0
. Bu noktadan sonra xjn
numara atandı x j + 1,0
hesaplamalarda başlangıç noktası olarak alınır. j+1
döngü. Hesaplama şu noktada biter x jk
üç sayım sonu kriterinden en az biri karşılandığında: 
, veya , veya eşitsizliklerin çift uygulanması.
Hesaplamalar sonucunda elde edilen noktalar bir dizinin elemanları olarak yazılabilir. (xl), Nerede l=n*j+k - noktanın seri numarası,
Yöntemin n = 2 için geometrik yorumu Şekil 2'de gösterilmektedir. 5.
4. Frank-Wolfe yöntemi .
Bir içbükey fonksiyonun maksimum değerini bulmamız gerektiğini varsayalım.
Koşullar altında
Bu problemin karakteristik bir özelliği, kısıt sisteminin yalnızca doğrusal eşitsizlikler içermesidir. Bu özellik, incelenen noktanın yakınındaki doğrusal olmayan özelliğin değiştirilmesinin temelini oluşturur. amaç fonksiyonu doğrusal, bu nedenle orijinal problemin çözümü doğrusal programlama problemlerinin sıralı çözümüne indirgenir.
Soruna çözüm bulma süreci, soruna uygun çözümlerin bulunduğu bölgeye ait bir noktanın belirlenmesiyle başlar.
270
kulübeler Konu bu olsun X(k)
daha sonra bu noktada fonksiyonun gradyanı (57) hesaplanır
Ve doğrusal bir fonksiyon oluşturun
Daha sonra bu fonksiyonun (58) ve (59) kısıtlamaları altındaki maksimum değerini bulun. Bu sorunun çözümünü noktaya göre belirleyelim z(k)
. Daha sonra noktanın koordinatları orijinal problemin yeni uygulanabilir çözümü olarak alınır. X(k+1)
:
Nerede λk - hesaplama adımı adı verilen ve sıfır ile bir (0) arasında yer alan belirli bir sayı<λk < 1). Это число λk keyfi olarak alınan veya belirlenen
böylece fonksiyonun o noktadaki değeri X (k +1) f(X (k +1)) , bağlı olarak λk , maksimumdu. Bunu yapmak için denklemin bir çözümünü bulmanız ve onun en küçük kökünü seçmeniz gerekir. Değeri birden büyükse şunu koymalıyız: λk=1 . Sayıyı belirledikten sonra λk bir noktanın koordinatlarını bulma X(k+1) içindeki amaç fonksiyonunun değerini hesaplayın ve yeni bir noktaya geçme ihtiyacını belirleyin X(k+2) . Böyle bir ihtiyaç varsa, o zaman noktada hesaplayın X(k+1) Amaç fonksiyonunun gradyanı, karşılık gelen doğrusal programlama problemine gidin ve çözümünü bulun. Noktanın koordinatlarını belirleyin ve X(k+2) ve daha fazla hesaplamanın gerekliliğini araştırın. Sonlu sayıda adımdan sonra orijinal problemin çözümü gerekli doğrulukta elde edilir.
Yani (57) - (59) problemine Frank-Wolfe yöntemini kullanarak çözüm bulma süreci aşağıdaki aşamaları içerir:
1. Sorunun ilk uygun çözümünü belirleyin.
2. Kabul edilebilir bir çözüm noktasında fonksiyon (57)'nin gradyanını bulun.
3. (60) fonksiyonunu oluşturun ve (58) ve (59) koşulları altındaki maksimum değerini bulun.
4. Hesaplama adımını belirleyin.
5. Formüller (61) kullanılarak yeni bir uygun çözümün bileşenleri bulunur.
6. Bir sonraki uygun çözüme geçme ihtiyacını kontrol edin. Gerekirse 2. aşamaya geçin, aksi takdirde orijinal soruna kabul edilebilir bir çözüm bulunur.
Ceza fonksiyonları yöntemi.
İçbükey fonksiyonun maksimum değerini belirleme problemini düşünün
f (x 1, x 2, .... x n) koşullar altında g ben (x 1, x 2, .... x n) ≤ b ben (i=l, m) , x j ≥ 0 (j=1, n) , Nerede g ben (x 1, x 2, .... x n) - dışbükey fonksiyonlar.
Bu sorunu doğrudan çözmek yerine fonksiyonun maksimum değerini bulun. F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) bu, problemin amaç fonksiyonunun ve bazı fonksiyonların toplamıdır.
H(x 1, x 2, ...., x n) bir kısıtlama sistemi tarafından tanımlanan ve çağrılan ceza fonksiyonu. Ceza fonksiyonu çeşitli şekillerde oluşturulabilir. Ancak çoğu zaman öyle görünüyor
A a ben > 0
- ağırlıklandırma katsayılarını temsil eden bazı sabit sayılar.
Ceza fonksiyonunu kullanarak kabul edilebilir bir çözüm elde edene kadar sırayla bir noktadan diğerine hareket ederler. Bu durumda bir sonraki noktanın koordinatları formül kullanılarak bulunur.
Son ilişkiden şu sonuç çıkar: Eğer önceki nokta orijinal problemin uygulanabilir çözümleri bölgesindeyse, o zaman köşeli parantez içindeki ikinci terim sıfıra eşittir ve bir sonraki noktaya geçiş yalnızca hedefin eğimi tarafından belirlenir. işlev. Belirtilen nokta kabul edilebilir çözüm bölgesine ait değilse, bu terim nedeniyle sonraki yinelemelerde kabul edilebilir çözüm bölgesine dönüş sağlanır.
kararlar. Aynı zamanda daha az bir ben
kabul edilebilir bir çözüm ne kadar hızlı bulunursa, ancak tespitinin doğruluğu azalır. Bu nedenle yinelemeli süreç genellikle nispeten küçük değerlerle başlar. bir ben
ve devam ettikçe bu değerler giderek artar.
Dolayısıyla, dışbükey programlama problemine ceza fonksiyonu yöntemini kullanarak çözüm bulma süreci aşağıdaki adımları içerir:
1. Başlangıç uygun çözümünü belirleyin.
2. Hesaplama adımını seçin.
3. Tüm değişkenler için, amaç fonksiyonunun kısmi türevlerini ve problemin uygun çözüm aralığını belirleyen fonksiyonları bulun.
4. Formül (72) kullanılarak problemin olası yeni çözümünü belirleyen noktanın koordinatları bulunur.
5. Bulunan noktanın koordinatlarının problem kısıtlamaları sistemini karşılayıp karşılamadığını kontrol edin. Değilse, bir sonraki aşamaya geçin. Bulunan noktanın koordinatları soruna kabul edilebilir bir çözüm belirliyorsa bir sonraki kabul edilebilir çözüme geçmenin gerekliliği araştırılır. Gerekirse 2. aşamaya geçin, aksi takdirde orijinal soruna kabul edilebilir bir çözüm bulunmuştur.
6. Ağırlık katsayılarının değerlerini ayarlayın ve 4. adıma geçin.
Arrow-Hurwitz yöntemi.
Doğrusal olmayan programlama problemlerine ceza fonksiyonu yöntemini kullanarak çözüm bulurken değerleri seçtik bir ben Bu da belirlenen noktaların uygun çözüm bölgesine olan uzaklığında önemli dalgalanmalara neden olmuştur. Sorun Arrow-Hurwitz yöntemiyle çözüldüğünde bu dezavantaj ortadan kaldırılır; buna göre bir sonraki adımda sayılar bir ben (k) formülle hesaplanır
Başlangıç değerleri olarak bir ben (0) negatif olmayan rastgele sayıları alın.
ÖRNEK ÇÖZÜM
Örnek 1.
Bir fonksiyonun yerel minimumunu bulun
Bir noktanın tanımlanması xk
1. Ayarlayalım.
2. Hadi koyalım k = 0 .
3 0 . Haydi hesaplayalım
4 0. Haydi hesaplayalım 
. 5. adıma geçelim.
5 0. Durumu kontrol edelim 
. 6. adıma geçelim.
6 0. Hadi ayarlayalım t0 = 0,5 .
7 0. Haydi hesaplayalım
8 0. Hadi karşılaştıralım 
. Sahibiz 
. Sonuç: koşulu k = 0
idam edilmez. Hadi ayarlayalım t0 = 0,25
7, 8. adımları tekrarlayarak ilerleyin.
7 01. Hesaplayalım.
8 01. Hadi karşılaştıralım f(x1) ve f(x0) . Çözüm: f(x1)< f (x 0) . 9. adıma geçelim.
9 0. Haydi hesaplayalım
Sonuç: inanıyoruz k =1 ve 3. adıma geçin.
3 1. Haydi hesaplayalım
4 1. Haydi hesaplayalım 
. 5. adıma geçelim.
5 1. Durumu kontrol edelim k ≥ M: k = 1< 10 = M . 6. adıma geçelim.
6 1. Hadi ayarlayalım t1 = 0,25.
7 1. Haydi hesaplayalım
8 1. Hadi karşılaştıralım f (x 2) ile f (x 1) . Çözüm: f(x2)< f (х 1). 9. adıma geçelim.
9 1. Haydi hesaplayalım
Sonuç: inanıyoruz k = 2 ve 3. adıma geçin.
3 2. Haydi hesaplayalım
4 2. Hesaplayalım. 5. adıma geçelim.
5 2. Durumu kontrol edelim k ≥ M : k = 2< 10 = М 6. adıma gidin.
6 2. Hadi ayarlayalım t 2 =0,25 .
7 2. Haydi hesaplayalım
8 2. Hadi karşılaştıralım f(x3) Ve f(x2) . Çözüm: f(x3)< f (х 2) .9. adıma gidin.
9 2. Haydi hesaplayalım 
Sonuç: inanıyoruz k = 3 ve 3. adıma geçin.
3 3. Haydi hesaplayalım
4 3. Hesaplayalım. 5. adıma geçelim.
5 3. Durumu kontrol edelim k ≥ M : k = 3<10 = М 6. adıma gidin.
6 3. Hadi ayarlayalım t3 = 0,25.
7 3. Haydi hesaplayalım
8 3. Hadi karşılaştıralım f(x4) Ve f(x3) :f(x4)< f (х 3) .
9 3. Haydi hesaplayalım 
Koşullar karşılandığında k = 2,3 . Hesaplama
bitti. Bulunan nokta
Şek. Ortaya çıkan 3 nokta noktalı bir çizgiyle birbirine bağlanır.
II. Nokta Analizi x 4 .
İşlev 
iki kez türevlenebilir olduğundan minimum için yeterli koşulları şu noktada kontrol edeceğiz: x 4
. Bunu yapmak için Hessian matrisini analiz edelim.
Matris sabit ve pozitif tanımlıdır (ör. . H > 0
) açısal minörlerinin her ikisi de pozitif olduğundan. Bu nedenle nokta 
yerel minimum noktanın bulunan yaklaşımıdır ve değer 
değerin bulunan yaklaşımıdır f(x*) =0
. koşulu unutmayın H > 0
, aynı zamanda fonksiyonun tam dışbükeyliği için bir koşul vardır 
. Sonuç olarak, küresel minimum noktaya ilişkin yaklaşıklıklar bulunmuştur. f(x)
ve minimum değeri R2
. ■
Örnek 2
Bir fonksiyonun yerel minimumunu bulun
I. Bir noktanın tanımı xk Hesaplamaların tamamlanmasına ilişkin kriterlerden en az birinin karşılandığı.
1. Ayarlayalım.
Fonksiyonun rastgele bir noktada gradyanını bulalım
2. Hadi koyalım k = 0 .
3 0 . Haydi hesaplayalım
4 0. Haydi hesaplayalım . 5. adıma geçelim.
5 0. Durumu kontrol edelim 
. 6. adıma geçelim.
6° Bir sonraki nokta formülle bulunur
Ortaya çıkan ifadeleri koordinatların yerine koyalım.
Fonksiyonun minimumunu bulalım f(t 0) İle t 0 koşulsuz bir ekstremum için gerekli koşulları kullanarak:
Buradan t 0 =0,24
. Çünkü 
, bulunan adım değeri fonksiyonun minimumunu sağlar f(t 0)
İle t 0
.
Hadi tanımlayalım 
7 0. bulacağız
8°. Haydi hesaplayalım
Sonuç: inanıyoruz k = 1 ve 3. adıma geçin.
3 1. Haydi hesaplayalım
4 1. Haydi hesaplayalım 
5 1. Durumu kontrol edelim k ≥ 1: k = 1< 10 = М.
6 1. Hadi tanımlayalım
7 1. bulacağız 
:
8 1. Haydi hesaplayalım
İnanıyoruz k = 2 ve 3. adıma geçin.
3 2. Haydi hesaplayalım
4 2. Haydi hesaplayalım
5 2. Durumu kontrol edelim k ≥ M: k = 2< 10 = M .
6 2. Hadi tanımlayalım
7 2. bulacağız 
8 2. Haydi hesaplayalım
İnanıyoruz k =3 ve 3. adıma geçin.
3 3. Haydi hesaplayalım
4 3. Hesaplayalım.
Hesaplama tamamlandı. Bulunan nokta
II. Nokta Analizi x 3 .
Örnek 1.1'de (Bölüm 2 §1) fonksiyonun olduğu gösterilmiştir. f(x) kesinlikle dışbükeydir ve bu nedenle nokta3'te küresel minimum noktanın bulunan yaklaşımıdır X* .
Örnek 3.
Bir fonksiyonun yerel minimumunu bulun
I. Bir noktanın tanımı xjk Hesaplamaların tamamlanmasına ilişkin kriterlerden en az birinin karşılandığı.
1. Haydi ayarlayalım
Fonksiyonun rastgele bir noktada gradyanını bulalım 
2. Haydi ayarlayalım j = 0.
3 0 . Koşulun karşılanıp karşılanmadığını kontrol edelim
4 0. Hadi ayarlayalım k = 0.
5 0. Koşulun karşılanıp karşılanmadığını kontrol edelim
6 0. Haydi hesaplayalım
7 0. Durumu kontrol edelim 
8 0. Hadi ayarlayalım
9 0. Haydi hesaplayalım 
, Nerede
10 0 . Durumu kontrol edelim
Sonuç: Varsayıyoruz ve 9. adıma geçiyoruz.
9 01. Haydi hesaplayalım x 01 artışlarla
10 01. Durumu kontrol edelim 
11 0 . Koşulları kontrol edelim
İnanıyoruz k =1 ve 5. adıma gidin.
5 1. Durumu kontrol edelim
6 1. Haydi hesaplayalım
7 1. Durumu kontrol edelim
8 1. Hadi ayarlayalım
9 1. Haydi hesaplayalım
10 1. Durumu kontrol edelim 
:
11 1. Koşulları kontrol edelim
İnanıyoruz k = 2 , 5. adıma gidin.
5 2. Durumu kontrol edelim. Ayarlayalım, 3. adıma geçin.
3 1. Durumu kontrol edelim
4 1. Hadi ayarlayalım k = 0.
5 2. Durumu kontrol edelim
6 2. Haydi hesaplayalım
7 2. Durumu kontrol edelim
8 2. Hadi ayarlayalım
9 2. Haydi hesaplayalım
10 2. Durumu kontrol edelim 
11 2. Koşulları kontrol edelim
İnanıyoruz k =1 ve 5. adıma gidin.
5 3. Durumu kontrol edelim
6 3. Haydi hesaplayalım
7 3. Koşulları kontrol edelim
8 3. Hadi ayarlayalım
9 3. Haydi hesaplayalım
10 3. Durumu kontrol edelim 
11 3. Koşulları kontrol edelim
Hadi ayarlayalım k = 2 ve 5. adıma gidin.
5 4. Durumu kontrol edelim 
İnanıyoruz j = 2, x 20 = x 12 ve 3. adıma geçin.
3 2. Durumu kontrol edelim
4 2. Hadi ayarlayalım k =0 .
5 4. Durumu kontrol edelim
6 4. Haydi hesaplayalım
7 4. Durumu kontrol edelim
8 4. Hadi ayarlayalım
9 4. Haydi hesaplayalım
10 4. Durumu kontrol edip 11. adıma geçelim.
11 4. Koşulları kontrol edelim
Koşullar sayılarla ardışık iki döngüde karşılanır j=2 Ve j -1= 1 . Hesaplama tamamlandı, nokta bulundu
Şek. Ortaya çıkan 6 nokta noktalı bir çizgiyle birbirine bağlanır.
Koordinat iniş yönteminde koordinat eksenlerine paralel düz parçalardan oluşan kesikli bir çizgi boyunca iniyoruz.
II. x21 noktasının analizi.
Örnek 1.1'de fonksiyonun olduğu gösterilmiştir. f(x)
kesinlikle dışbükeydir, benzersiz bir minimuma sahiptir ve bu nedenle bir noktaya sahiptir 
küresel minimum noktanın bulunan yaklaşımıdır.
Yukarıda tartışılan tüm gradyan yöntemlerinde noktaların sırası (xk) fonksiyonun durağan noktasına yakınsar f(x) Bu fonksiyonun özelliklerine ilişkin oldukça genel önermelerle. Özellikle teorem doğrudur:
Teorem. Eğer f(x) fonksiyonu aşağıda sınırlıysa, gradyanı Lipschitz koşulunu () ve değer seçimini karşılar tn Yukarıda açıklanan yöntemlerden biriyle üretilmişse, başlangıç noktası ne olursa olsun x 0 :
.
Planın pratik uygulamasında
k =1, 2, … n.
herkes için yinelemeler durur ben, ben = 1, 2, ..., n , gibi koşullar
,
minimumu bulmanın doğruluğunu karakterize eden belirli bir sayı nerede.
Teoremin koşulları altında, gradyan yöntemi, fonksiyonda veya tam alt sınıra yakınsama sağlar (eğer fonksiyon f(x) minimumu yoktur; pirinç. 7) veya dizinin limiti olan sabit bir noktadaki fonksiyonun değerine (x k). Bu noktada bir eyer gerçekleştiğinde örnekler bulmak hiç de zor değil, minimum değil. Uygulamada, gradyan iniş yöntemleri eyer noktalarını güvenle atlar ve amaç fonksiyonunun minimumlarını bulur (genel durumda, yerel olanlar).
ÇÖZÜM
Gradyan kısıtlamasız optimizasyon yöntemlerinin örnekleri yukarıda tartışılmıştır. Yapılan çalışmalar sonucunda aşağıdaki sonuçlar çıkarılabilir:
1. Kısıtlamaların varlığında bir ekstremum bulmanın az ya da çok karmaşık sorunları, özel yaklaşımlar ve yöntemler gerektirir.
2. Kısıtlamalı problemlerin çözümüne yönelik birçok algoritma, bir adım olarak sınırlandırılmamış minimizasyonu içerir.
3. Çeşitli yöntemlerİnişler, iniş yönünü seçme şekli ve bu yöndeki adımın uzunluğu bakımından birbirinden farklılık gösterir.
4. Sorunun formülasyonunu tanımlayan fonksiyonların herhangi bir özelliğini dikkate alacak bir teori henüz yoktur. Bir problemin çözümü sürecinde yönetimi daha kolay olan yöntemler tercih edilmelidir.
Gerçek uygulamalı optimizasyon problemleri çok karmaşıktır. Modern yöntemler optimizasyonlar her zaman gerçek sorunları insan yardımı olmadan çözmeyi başaramaz.
REFERANSLAR
1. Kosorukov O.A. Yöneylem Araştırması: Bir Ders Kitabı. 2003
2. Pantleev A.V. Örneklerde ve problemlerde optimizasyon yöntemleri: ders kitabı. Fayda. 2005
3. Shishkin E.V. Yöneylem araştırması: ders kitabı. 2006
4. Akulich I.L. Örneklerde ve problemlerde matematiksel programlama. 1986
5. Ventzel E.S. Yöneylem Araştırması. 1980
6. Ventzel E.S., Ovcharov L.A. Olasılık teorisi ve mühendislik uygulamaları. 1988
©2015-2019 sitesi
Tüm hakları yazarlarına aittir. Bu site yazarlık iddiasında bulunmaz, ancak ücretsiz kullanım.
Sayfa oluşturulma tarihi: 2017-07-02
Dipnot: Bu ders, en dik iniş yöntemi ve Davidon-Fletcher-Powell yöntemi gibi çok parametreli optimizasyon yöntemlerini geniş ölçüde kapsamaktadır. Ayrıca en etkili olanı belirlemek için yukarıdaki yöntemlerin karşılaştırmalı bir analizi yapılır, avantajları ve dezavantajları belirlenir; ve aynı zamanda vadi yöntemi ve çok ekstremal yöntem gibi çok boyutlu optimizasyon problemlerini de dikkate alır.
1. En dik iniş yöntemi
Öz bu yöntem daha önce bahsedilenleri kullanmak mı koordinat iniş yöntemi arama şu adresten yapılıyor: verilen nokta eksenlerden birine paralel bir yönde, o yöndeki minimum noktaya kadar. Arama daha sonra diğer eksene paralel bir yönde gerçekleştirilir ve bu şekilde devam eder. Yönler elbette sabittir. Bu yöntemi, her aşamada minimum nokta arayışının "en iyi" yönde gerçekleştirileceği şekilde değiştirmeye çalışmak mantıklı görünmektedir. Hangi yönün "en iyi" olduğu belli değil ama biliniyor ki degrade yönü fonksiyondaki en hızlı artışın yönüdür. Dolayısıyla ters yön, fonksiyonun en hızlı azalış yönüdür. Bu özellik aşağıdaki gibi gerekçelendirilebilir.
x noktasından bir sonraki x + hd noktasına doğru hareket ettiğimizi varsayalım; burada d belirli bir yön ve h belirli uzunlukta bir adımdır. Sonuç olarak hareket (x 1, x 2, ..., x n) noktasından noktasına yapılır. (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Nerede
Fonksiyon değerlerindeki değişim ilişkilerle belirlenir
| (1.3) |
Birinci dereceden zx i'ye kadar, kısmi türevler x noktasında hesaplanır. df fonksiyonundaki değişimin en büyük değerini elde etmek için denklem (1.2)'yi sağlayan d i yönleri nasıl seçilmelidir? Kısıtlı bir maksimizasyon probleminin ortaya çıktığı yer burasıdır. Fonksiyonu belirlemek için Lagrange çarpanları yöntemini uygulayalım.
Kısıt (1.2)'yi karşılayan df değeri, fonksiyon aşağıdaki durumlarda maksimuma ulaşır:
Maksimuma ulaşır. Türevi
Buradan,
 |
(1.6) |
O halde di ~ df/dx i ve d yönü x noktasında V/(x) yönüne paraleldir.
Böylece, en büyük yerel artış Belirli bir küçük h adımı için fonksiyon, d, Vf(x) veya g(x)'in yönü olduğunda ortaya çıkar. Bu nedenle en dik inişin yönü yöndür.
Daha fazla basit biçimde denklem (1.3) şu şekilde yazılabilir:
Vf(x) ve dx vektörleri arasındaki açı nerede. İçin verilen değer dx'te dx'in yönünün -Vf(x)'in yönüyle çakışmasını seçerek df'yi en aza indiririz.
Yorum. Gradyan yönü sabit seviyeli bir çizgi üzerindeki herhangi bir noktaya diktir, çünkü bu doğru boyunca fonksiyon sabittir. Dolayısıyla, eğer (d 1, d 2, ..., d n) seviye çizgisi boyunca küçük bir adımsa, o zaman
Ve bu nedenle
 |
(1.8) |
Ayrıca degrade yönünde en iyi noktayı değil, mevcut noktadan daha iyi bir noktayı arayabilirsiniz.
Tüm yerel optimizasyon yöntemleri arasında uygulanması en kolay olanıdır. oldukça var zayıf koşullar yakınsama vardır ancak yakınsama oranı oldukça düşüktür (doğrusal). Gradyan yöntemi adımı genellikle Fletcher-Reeves yöntemi gibi diğer optimizasyon yöntemlerinin bir parçası olarak kullanılır.
Tanım [ | ]
İyileştirmeler[ | ]
Gradyan iniş yönteminin bir vadi boyunca hareket ederken çok yavaş olduğu ortaya çıkıyor ve amaç fonksiyonundaki değişkenlerin sayısı arttıkça yöntemin bu davranışı tipik hale geliyor. Bu fenomenle mücadele etmek için özü çok basit olan kullanılır. İki adımlı gradyan iniş yapıp üç nokta elde ettikten sonra üçüncü adım, vadinin tabanı boyunca birinci ve üçüncü noktaları birleştiren vektör yönünde atılmalıdır.
İkinci dereceden yakın fonksiyonlar için eşlenik gradyan yöntemi etkilidir.
Yapay sinir ağlarında uygulama[ | ]
Gradyan iniş yöntemi, bazı değişikliklerle birlikte, algılayıcı eğitimi için yaygın olarak kullanılır ve yapay sinir ağları teorisinde geri yayılım yöntemi olarak bilinir. Algılayıcı tipi bir sinir ağını eğitirken, ağın ağırlık katsayılarını en aza indirecek şekilde değiştirmek gerekir. ortalama hata Girişe bir dizi eğitim giriş verisi sağlandığında sinir ağının çıkışında. Resmi olarak, gradyan iniş yöntemini kullanarak yalnızca bir adım atmak için (ağ parametrelerinde yalnızca bir değişiklik yapmak), eğitim verilerinin tamamını sırayla ağ girişine göndermek, her nesne için hatayı hesaplamak gerekir. eğitim verilerini alın ve ağ katsayılarının gerekli düzeltmesini hesaplayın (ancak bu düzeltmeyi yapmayın) ve tüm verileri gönderdikten sonra, her ağ katsayısının (gradyanların toplamı) ayarlanmasındaki miktarı hesaplayın ve katsayıları "bir adım" düzeltin . Açıkçası, geniş bir eğitim verisi seti ile algoritma son derece yavaş çalışacaktır, bu nedenle pratikte ağ katsayıları genellikle her eğitim elemanından sonra ayarlanır; burada gradyan değeri, yalnızca bir eğitim üzerinde hesaplanan maliyet fonksiyonunun gradyanı ile yaklaşık olarak hesaplanır. eleman. Bu yöntem denir stokastik gradyan inişi veya operasyonel gradyan inişi . Stokastik gradyan inişi stokastik yaklaşımın biçimlerinden biridir. Stokastik yaklaşımlar teorisi, stokastik gradyan iniş yönteminin yakınsaması için koşullar sağlar.
Bağlantılar [ | ]
- J. Mathews. En Dik İniş veya Gradyan Yöntemi Modülü. (kullanılamayan bağlantı)
Edebiyat [ | ]
- Akulich I. L.Örneklerde ve problemlerde matematiksel programlama. - M.: Yüksekokul, 1986. - S. 298-310.
- Gill F., Murray W., Wright M. Pratik optimizasyon = Pratik Optimizasyon. - M.: Mir, 1985.
- Korshunov Yu.M., Korshunov Yu. Sibernetiğin matematiksel temelleri. - M .: Energoatomizdat, 1972.
- Maksimov Yu.A., Fillipovskaya E.A. Doğrusal olmayan programlama problemlerini çözmek için algoritmalar. - M.: MEPhI, 1982.
- Maximov Yu. Doğrusal ve ayrık programlama için algoritmalar. - M.: MEPhI, 1980.
- Korn G., Korn T. Bilim adamları ve mühendisler için matematik el kitabı. - M .: Nauka, 1970. - S. 575-576.
- S. Yu. Gorodetsky, V. A. Grishagin. Doğrusal olmayan programlama ve çok ekstremal optimizasyon. - Nijniy Novgorod: Nizhny Novgorod Üniversitesi Yayınevi, 2007. - s. 357-363.
Her yinelemede en dik iniş yöntemini kullanırken adım boyutu A k fonksiyonun minimum koşulundan seçilir f(x) iniş yönünde, yani
f(x[k] -A k f"(x[k])) = f(x[k] -af"(x[k])) .
Bu durum, antigradyan boyunca hareketin, fonksiyonun değeri olduğu sürece meydana geldiği anlamına gelir. f(x) azalır. Matematiksel açıdan bakıldığında, her yinelemede tek boyutlu minimizasyon probleminin şu şekilde çözülmesi gerekir: A işlevler
J (A) = f(x[k]-af"(x[k])) .
En dik iniş yönteminin algoritması aşağıdaki gibidir.
- 1. Başlangıç noktasının koordinatlarını ayarlayın X.
- 2. Bu noktada X[k], k = 0, 1, 2, ... gradyan değerini hesaplar f"(x[k]) .
- 3. Adım boyutu belirlenir A k, tek boyutlu minimizasyonla A işlevler j (A) = f(x[k]-af"(x[k])).
- 4. Noktanın koordinatları belirlenir X[k+ 1]:
X Ben [k+ 1]=x Ben [k] -A k F" Ben (X[k]), i = 1,..., s.
5. Sterilizasyon işleminin durdurulması koşulları kontrol edilir. Bunlar yerine getirilirse hesaplamalar durur. Aksi halde 1. adıma geçin.
Söz konusu yöntemde, noktadan hareketin yönü X[k] noktada seviye çizgisine dokunuyor X[k+ 1] (Şekil 2.9). İniş yörüngesi zikzaktır ve bitişik zikzak bağlantıları birbirine diktir. Aslında bir adım A k minimize edilerek seçilir A işlevler? (A) = f(x[k] -af"(x[k])) . Önkoşul minimum fonksiyon D J (a)/da = 0. Karmaşık bir fonksiyonun türevini hesapladıktan sonra, iniş yönleri vektörlerinin komşu noktalardaki diklik koşulunu elde ederiz:
D J (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.
Pirinç. 2.9.
Gradyan yöntemleri minimuma yakınsıyor yüksek hız(hızda geometrik ilerleme) düzgün dışbükey fonksiyonlar için. Bu tür işlevler en büyük M ve en azından M ikinci türevler matrisinin özdeğerleri (Hessian matrisi)
birbirinden çok az farklılık gösterir, yani matris N(x) iyi şartlandırılmış. şunu hatırlatalım özdeğerler ben ben Ben =1, …, N matrisler karakteristik denklemin kökleridir
Bununla birlikte, pratikte, kural olarak, minimize edilen fonksiyonlar, ikinci türevlerin kötü koşullandırılmış matrislerine sahiptir. (t/ay<< 1). Bu tür fonksiyonların bazı yönlerdeki değerleri diğer yönlere göre çok daha hızlı (bazen birkaç büyüklük sırasına göre) değişir. En basit durumda düz yüzeyleri oldukça uzundur (Şekil 2.10) ve daha karmaşık durumlarda bükülür ve vadilere benzerler. Bu özelliklere sahip fonksiyonlara denir oluk. Bu fonksiyonların antigradyan yönü (bkz. Şekil 2.10), minimum noktaya doğru önemli ölçüde sapar, bu da yakınsama hızının yavaşlamasına yol açar.
Pirinç. 2.10.
Gradyan yöntemlerinin yakınsama oranı aynı zamanda gradyan hesaplamalarının doğruluğuna da önemli ölçüde bağlıdır. Genellikle minimum noktaların yakınında veya bir su birikintisi durumunda meydana gelen doğruluk kaybı, genellikle gradyan iniş sürecinin yakınsamasını bozabilir. Yukarıdaki nedenlerden dolayı, gradyan yöntemleri genellikle bir problemin çözümünün ilk aşamasında diğer daha etkili yöntemlerle birlikte kullanılır. Bu durumda asıl nokta X minimum noktadan uzaktır ve antigradyan yönündeki adımlar, fonksiyonda önemli bir azalma elde edilmesini mümkün kılar.
