Yöntem en dik iniş(İngiliz literatüründe "en dik iniş yöntemi"), optimizasyon problemlerini çözmek için, amaç fonksiyonunun ekstremumunu (minimum veya maksimum) belirlemenize olanak tanıyan yinelemeli bir sayısal yöntemdir (birinci dereceden):
gerçek etki alanındaki fonksiyon argümanının (kontrollü parametreler) değerleridir.
Söz konusu yönteme uygun olarak amaç fonksiyonunun ekstremumu (maksimum veya minimum), fonksiyonun en hızlı artış (azalış) yönünde belirlenir, yani. fonksiyonun gradyanı (anti-gradyan) yönünde. Bir noktada gradyan fonksiyonu koordinat eksenleri üzerindeki izdüşümleri fonksiyonun koordinatlara göre kısmi türevleri olan bir vektördür:
burada i, j,…, n koordinat eksenlerine paralel birim vektörlerdir.
Taban noktasındaki gradyan 
yüzeye kesinlikle diktir ve yönü, fonksiyondaki en hızlı artışın yönünü gösterir ve ters yön (antigradyan), sırasıyla fonksiyonun en hızlı azalma yönünü gösterir.
En dik iniş yöntemi daha fazla gelişme Gradyan iniş yöntemi. İÇİNDE genel durum Bir fonksiyonun ekstremumunu bulma süreci yinelemeli bir prosedürdür ve aşağıdaki şekilde yazılır:
bir fonksiyonun maksimumunu bulmak için "+" işaretinin kullanıldığı ve bir fonksiyonun minimumunu bulmak için "-" işaretinin kullanıldığı;
Formülle belirlenen birim yön vektörü:
- degrade modülü, fonksiyonun degrade veya anti-gradyan yönünde artış veya azalma oranını belirler:
Adım boyutunu belirleyen ve tüm i'inci yönler için aynı olan bir sabit.
Adım boyutu, hareket yönündeki amaç fonksiyonu f(x)'in minimum koşulundan, yani tek boyutlu optimizasyon probleminin gradyan veya antigradyan yönünde çözülmesinin bir sonucu olarak seçilir:
Başka bir deyişle adım büyüklüğü şu denklemin çözülmesiyle belirlenir:
Bu nedenle hesaplama adımı, hareket fonksiyon iyileşene, dolayısıyla bir noktada uç noktaya ulaşana kadar gerçekleştirilecek şekilde seçilir. Bu noktada, arama yönü yeniden belirlenir (gradyan kullanılarak) ve amaç fonksiyonunun yeni bir optimum noktası aranır, vb. Böylece bu yöntemde arama daha büyük adımlarla gerçekleşir ve fonksiyonun gradyanı daha az sayıda noktada hesaplanır.
İki değişkenli bir fonksiyon durumunda bu yöntem aşağıdaki geometrik yoruma sahiptir: bir noktadan hareketin yönü, noktasındaki seviye çizgisine dokunmaktadır. İniş yörüngesi zikzaktır ve bitişik zikzak bağlantıları birbirine diktir. İniş yönleri vektörlerinin komşu noktalardaki diklik koşulu aşağıdaki ifadeyle yazılır:
f(x) fonksiyonunun eşit seviye çizgisi grafiğinde gösterilen, en dik iniş yöntemini kullanarak uç noktaya doğru hareketin yörüngesi
Optimum çözüm arayışı yinelemeli hesaplama adımında (birkaç kriter) sona erer:
Arama yörüngesi mevcut arama noktasının küçük bir mahallesinde kalır:
Amaç fonksiyonunun artışı değişmez:
Amaç fonksiyonunun yerel minimum noktasındaki gradyanı sıfır olur:
Gradyan iniş yönteminin bir vadi boyunca hareket ederken çok yavaş olduğu ve amaç fonksiyonundaki değişken sayısı arttıkça yöntemin bu davranışının tipik hale geldiği unutulmamalıdır. Dağ geçidi, seviye çizgileri yaklaşık olarak elips şeklinde olan ve yarı eksenleri birçok kez farklı olan bir çöküntüdür. Bir dağ geçidinin varlığında iniş yörüngesi küçük bir adımla zikzak çizgisi şeklini alır, bunun sonucunda minimuma inen iniş hızı büyük ölçüde yavaşlar. Bu, bu fonksiyonların antigradyan yönünün minimum noktaya doğru önemli ölçüde sapması ve bunun da hesaplamada ek bir gecikmeye yol açmasıyla açıklanmaktadır. Sonuç olarak algoritma hesaplama verimliliğini kaybeder.
Oluk fonksiyonu
Gradyan yöntemi, birçok modifikasyonuyla birlikte yaygındır ve etkili yöntemİncelenen nesnelerin optimumunu aramak. Gradyan aramanın (yukarıda tartışılan yöntemlerin yanı sıra) dezavantajı, onu kullanırken fonksiyonun yalnızca yerel ekstremumunun tespit edilebilmesidir. Başkalarını bulmak için yerel aşırılıklar başka başlangıç noktalarından aramak gerekir. Ayrıca gradyan yöntemlerinin yakınsama oranı da gradyan hesaplamalarının doğruluğuna ö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.
Hesaplama yöntemi
Adım 1: Bir fonksiyonun gradyanını hesaplamak için analitik ifadelerin tanımı (sembolik biçimde)
2. Adım: Başlangıç yaklaşımını ayarlayın
3. Adım: Son arama yönünü sıfırlamak için algoritmik prosedürü yeniden başlatma ihtiyacı belirlenir. Yeniden başlatma sonucunda en hızlı iniş yönünde tekrar arama yapılır.
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). Adım degrade yöntemi 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ı) düzeltmesindeki 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 bir biçimidir. 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.
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 durumda, fonksiyonun minimumunu elde etmek için bir adım yeterli değildir; sonraki hesaplamalar sonucu iyileştirinceye 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 sürede çö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 
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 ayrıca dağ geçidi yöntemi ve çok ekstremal yöntem gibi çok boyutlu optimizasyon problemlerini de dikkate alır.
1. En dik iniş yöntemi
Bu yöntemin özü, daha önce bahsedilen yöntemin kullanılmasıdır. koordinat iniş yöntemi eksenlerden birine paralel bir yönde belirli bir noktadan bu yöndeki minimum noktaya kadar bir arama gerçekleştirilir. 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 basit bir biçimde denklem (1.3) şu şekilde yazılabilir:
Vf(x) ve dx vektörleri arasındaki açı nerede. Belirli bir dx değeri için, dx'in yönünün -Vf(x) 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) |
