Türevlenebilir fonksiyonun f(x) noktasındaki gradyanı X isminde N boyutlu vektör f(x) bileşenleri fonksiyonun kısmi türevleri olan f(x), noktada hesaplanır X, yani

f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T .

Bu vektör noktadan geçen düzleme diktir X ve fonksiyonun düz yüzeyine teğet f(x), bir noktadan geçmek X.Böyle bir yüzeyin her noktasında fonksiyon f(x) aynı değeri alır. Fonksiyonu çeşitli sabit değerlere eşitleyerek C 0 , C 1 , ..., topolojisini karakterize eden bir dizi yüzey elde ederiz (Şekil 2.8).

Gradyan vektörü, belirli bir noktada fonksiyondaki en hızlı artışa doğru yönlendirilir. Degradenin karşısındaki vektör (-f’(x)) , isminde anti-gradyan ve fonksiyonun en hızlı azalmasına yöneliktir. Minimum noktada fonksiyonun gradyanı sıfırdır. Gradyan ve minimizasyon yöntemleri olarak da adlandırılan birinci dereceden yöntemler, gradyanların özelliklerine dayanır. Genel durumda bu yöntemlerin kullanılması, bir fonksiyonun yerel minimum noktasını belirlemenize olanak tanır.

Açıkçası, eğer ek bilgi yoksa, o zaman başlangıç ​​noktasından itibaren X konuya girmek akıllıca olur X, antigradyan yönünde uzanmak - fonksiyonun en hızlı azalması. İniş yönü olarak seçim[R k ] anti-gradyan - f'(x ) [k] X[R bu noktada

], formun yinelemeli bir sürecini elde ederiz X[ 1] = k+[R]-X f'(x ) , a k f"(x > 0; R=0, 1, 2, ...

ve k

Koordinat formunda bu süreç şu şekilde yazılır: R+1]=x ben [[R] - x benf(x f'(x ) bir k

/x ben N; R= 0, 1, 2,...

ben = 1, ..., k+[R Yinelemeli süreci durdurmanın bir kriteri olarak, || argümanının küçük bir artış koşulunun yerine getirilmesi. +l][R] || <= e , либо выполнение условия малости градиента

|| - X[R f'(x ) || <= g ,

+l]

Burada e ve g'ye küçük miktarlar verilmiştir. a k f"(x.

Belirtilen koşulların eşzamanlı olarak yerine getirilmesinden oluşan birleşik bir kriter de mümkündür. Gradyan yöntemleri adım boyutunu seçme şekli bakımından birbirinden farklılık gösterir a k f"(x Sabit adımlı yöntemde tüm yinelemeler için belirli bir sabit adım değeri seçilir. Oldukça küçük bir adım

fonksiyonun yani eşitsizliğin azalmasını sağlayacaktır R+1]) = f(x f(x[ [k] – f'(x )) < f(x f'(x ) .

Ancak bu, minimum noktaya ulaşmak için kabul edilemeyecek kadar çok sayıda yineleme yapılması ihtiyacına yol açabilir. Öte yandan çok büyük bir adım, fonksiyonda beklenmeyen bir artışa neden olabilir veya minimum nokta etrafında salınımlara (döngü) yol açabilir. Adım büyüklüğünün seçimi için gerekli bilginin elde edilmesinin zorluğu nedeniyle, sabit adımlı yöntemler pratikte nadiren kullanılmaktadır.

Degrade olanlar yineleme sayısı ve güvenilirlik açısından daha ekonomiktir değişken adım yöntemleri, hesaplamaların sonuçlarına bağlı olarak adım boyutu bir şekilde değiştiğinde. Pratikte kullanılan bu tür yöntemlerin çeşitlerini ele alalım.

Her yinelemede en dik iniş yöntemini kullanırken adım boyutu a k f"(x fonksiyonun minimum koşulundan seçilir f(x) iniş yönünde, yani
f(x[R]–ak f’(x[R])) = f(x f'(x – af"(x[R])) .

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[R]-af"(x[R])) .

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[R], k = 0, 1, 2, ... gradyan değerini hesaplar - X[R]) .

3. Adım boyutu belirlenir A k, tek boyutlu minimizasyonla A işlevler j (A) = f(x[R]-af"(x[R])).

4. Noktanın koordinatları belirlenir X[X[ 1]:

x ben [ X[ 1]= x ben[R]– a k f’ i (x[R]), i = 1,..., s.

5. Sterasyon 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[R] noktada seviye çizgisine dokunuyor k+[X[ 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 f'(x -af"(x[R])) . Bir fonksiyonun minimumu için gerekli koşul J D(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: DJ[X[ 1]- X[R]) = 0.

Pirinç. 2.9. En dik iniş yönteminin geometrik yorumu Gradyan yöntemleri, düzgün dışbükey fonksiyonlar için yüksek hızda (geometrik ilerleme hızı) minimuma yakınsar. 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) =1, …, N iyi şartlandırılmış. Özdeğerlerin l i olduğunu hatırlayın,

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.

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. X 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

minimum noktadan uzaktır ve antigradyan yönündeki adımlar, fonksiyonda önemli bir azalma elde edilmesini mümkün kılar.

Yukarıda tartışılan gradyan yöntemleri, genel durumda bir fonksiyonun minimum noktasını yalnızca sonsuz sayıda yinelemede bulur. Eşlenik gradyan yöntemi, küçültülmekte olan fonksiyonun geometrisiyle daha tutarlı arama yönleri üretir. Bu, yakınsama hızını önemli ölçüde artırır ve örneğin ikinci dereceden fonksiyonun en aza indirilmesine olanak tanır.

f(x) = (x, Hx) + (b, x) + a simetrik pozitif tanımlı bir matris ile N sınırlı sayıda adımda P,

fonksiyon değişkenlerinin sayısına eşittir. N Minimum noktaya yakın herhangi bir düzgün fonksiyona ikinci dereceden bir fonksiyonla iyi bir şekilde yaklaşılabilir, bu nedenle eşlenik gradyan yöntemleri ikinci dereceden olmayan fonksiyonları en aza indirmek için başarıyla kullanılır. Bu durumda sonlu olmaktan çıkıp yinelemeli hale gelirler. X Tanım gereği iki boyutlu vektör Ve en isminde konjuge matrise göre konjuge H (veya, -eşlenik), eğer skaler çarpım ise(X Peki) = 0. Burada N - simetrik pozitif tanımlı boyut matrisi N

X P.[R]) Eşlenik gradyan yöntemlerindeki en önemli sorunlardan biri, yönlerin verimli bir şekilde oluşturulması sorunudur. Fletcher-Reeves yöntemi, her adımda antigradiyenti dönüştürerek bu sorunu çözer. -f(x[R], konjuge-önceden bulunan yönlerle birleşin İniş yönü olarak seçim, İniş yönü olarak seçim, ..., İniş yönü olarak seçim[R-1].

Öncelikle bu yöntemi ikinci dereceden bir fonksiyonun en aza indirilmesi problemiyle ilişkili olarak ele alalım. İniş yönü olarak seçim[R Yol Tarifi

] aşağıdaki formüller kullanılarak hesaplanır: R] = -- X[R]) P[ -f(x[R+b k-1 R>= 1;

-l], p = -’(veya) .

F R b değerleri -f(x[R], İniş yönü olarak seçim[R-1 yönler olacak şekilde seçilir konjuge-1] vardı :

(-f(x[R], -eşlenik[HP 1])= 0.

k-

,

Sonuç olarak, ikinci dereceden fonksiyon için

yinelemeli minimizasyon süreci şu şekildedir R f'(x X[[R]=x[R],

+ak p İniş yönü olarak seçim[R] - Nerede HP iniş yönü m adım; ve k- adım boyutu.İkincisi, fonksiyonun minimum koşulundan seçilir A f(x)

fonksiyonun yani eşitsizliğin azalmasını sağlayacaktır R] + İle[R]) = f(x[R] + hareket yönünde, yani tek boyutlu minimizasyon probleminin çözülmesi sonucunda: [R]) .

a k r

ar

İkinci dereceden bir fonksiyon için X Fletcher-Reeves eşlenik gradyan yönteminin algoritması aşağıdaki gibidir. -f(x = -- X) .

1. Bu noktada HP hesaplanmış A 2. Açık . m adım, yukarıdaki formüller kullanılarak adım belirlenir X[X[ 1].

k f(x[R+1]) ve dönem - X[R+1]) .

3. Değerler hesaplanır - X) Ve X[R 4. Eğer = 0, sonra nokta+1] fonksiyonun minimum noktasıdır -f(x[R f(x).

Aksi takdirde yeni bir yön belirlenir N -+l] ilişkiden ve bir sonraki iterasyona geçiş gerçekleştirilir. Bu prosedür, ikinci dereceden bir fonksiyonun minimumunu en fazla adımlar. Xİkinci dereceden olmayan fonksiyonları en aza indirirken, Fletcher-Reeves yöntemi sonludan yinelemeli hale gelir. Bu durumda sonrasında X[N -(p+

yinelemeli minimizasyon süreci şu şekildedir R f'(x 1)Prosedür 1-4'ün tekrarı, değiştirme ile periyodik olarak tekrarlanır[R]=x[R],

] aşağıdaki formüller kullanılarak hesaplanır: R] Açık[R])+ +1] ve hesaplamalar belirli bir sayı olan 'da biter. Bu durumda yöntemin aşağıdaki modifikasyonu kullanılır: HP 1 -f(x[R+b k-1 R>= 1;

= x k+);

fonksiyonun yani eşitsizliğin azalmasını sağlayacaktır R] + = -f’(x[R]) = f(x[R] B[R];

.

p = -f'( ak p+ap ak p Burada BEN- birçok dizin: N -= (0, n, 2

p, maaş, ...) X, yani yöntem her seferinde güncellenir İniş yönü olarak seçim = adımlar. Eşlenik gradyan yönteminin geometrik anlamı aşağıdaki gibidir (Şekil 2.11). Belirli bir başlangıç ​​noktasından X iniş yönünde gerçekleştirilir -f"(x). X bu noktada İniş yönü olarak seçim, gradyan vektörü belirlenir ] anti-gradyan -) f"(x İniş yönü olarak seçim). Çünkü İniş yönü olarak seçim , konjuge fonksiyonun yönündeki minimum noktasıdır İniş yönü olarak seçim O İniş yönü olarak seçim vektöre dik

. Daha sonra, fonksiyonun yön boyunca minimumunu buluyoruz. N -= (0, n, 2

vesaire. 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 açık değil, ancak 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 şekilde 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

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)

Şekil 3. En dik iniş yönteminin geometrik yorumu. Her adımda, bir sonraki iterasyonun L ışınındaki fonksiyonun minimum noktası olacağı şekilde seçilir.

Gradyan yönteminin bu versiyonu, aşağıdaki hususlara göre adım seçimine dayanmaktadır. Bu noktadan, f fonksiyonunun bu yönde, yani ışındaki minimumuna ulaşana kadar antigradyan yönünde hareket edeceğiz:

Başka bir deyişle, bir sonraki iterasyonun f fonksiyonunun L ışınındaki minimum noktası olacağı şekilde seçilir (bkz. Şekil 3). Gradyan yönteminin bu versiyonuna en dik iniş yöntemi denir. Bu arada, bu yöntemde bitişik adımların yönlerinin dik olduğuna dikkat edin.

En dik iniş yöntemi, her adımda tek boyutlu bir optimizasyon probleminin çözülmesini gerektirir. Uygulama, bu yöntemin genellikle sabit adımlı gradyan yönteminden daha az işlem gerektirdiğini göstermektedir.

Ancak genel durumda, en dik iniş yönteminin teorik yakınsama oranı, sabit (optimal) adımlı gradyan yönteminin yakınsama oranından daha yüksek değildir.

Sayısal örnekler

Sabit adımlı gradyan iniş yöntemi

Gradyan iniş yönteminin sabit bir adımla yakınsamasını incelemek için fonksiyon seçildi:

Elde edilen sonuçlardan, eğer boşluk çok büyükse yöntemin saptığı, eğer boşluk çok küçükse yavaş yakınsadığı ve doğruluğun kötü olduğu sonucuna varabiliriz. Yöntemin yakınsadığı adımlardan en büyüğünü seçmek gerekir.

Adım bölmeli gradyan yöntemi

Gradyan iniş yönteminin adım bölümü (2) ile yakınsamasını incelemek için fonksiyon seçildi:

İlk yaklaşım (10,10) noktasıdır.

Kullanılan durdurma kriteri:

Deneyin sonuçları tabloda gösterilmektedir:

Elde edilen sonuçlardan optimal parametre seçimi hakkında şu sonuca varabiliriz: Her ne kadar yöntem parametre seçimine çok duyarlı olmasa da.

En dik iniş yöntemi

En dik iniş yönteminin yakınsamasını incelemek için aşağıdaki fonksiyon seçildi:

İlk yaklaşım (10,10) noktasıdır. Kullanılan durdurma kriteri:

Tek boyutlu optimizasyon problemlerini çözmek için altın bölüm yöntemi kullanıldı.

Yöntem 9 yinelemede 6e-8 doğruluk elde etti.

Buradan, en dik iniş yönteminin adımlı bölünmüş gradyan yönteminden ve sabit adımlı gradyan iniş yönteminden daha hızlı yakınsadığı sonucuna varabiliriz.

En dik iniş yönteminin dezavantajı tek boyutlu bir optimizasyon probleminin çözülmesini gerektirmesidir.

Gradyan iniş yöntemlerini programlarken parametreleri seçerken dikkatli olmalısınız, yani

• · Sabit adımlı gradyan iniş yöntemi: adım 0,01'den küçük seçilmelidir, aksi takdirde yöntem sapar (çalışılan fonksiyona bağlı olarak yöntem böyle bir adımla bile sapabilir).
• · Adım bölmeli gradyan yöntemi parametre seçimine çok duyarlı değildir. Parametre seçme seçeneklerinden biri:
• · En dik iniş yöntemi: Altın oran yöntemi (uygulanabilir olduğunda) tek boyutlu bir optimizasyon yöntemi olarak kullanılabilir.

Eşlenik gradyan yöntemi, çok boyutlu bir alanda koşulsuz optimizasyon için yinelemeli bir yöntemdir. Yöntemin temel avantajı, ikinci dereceden bir optimizasyon problemini sonlu sayıda adımda çözmesidir. Bu nedenle, öncelikle ikinci dereceden fonksiyoneli optimize etmek için eşlenik gradyan yöntemi anlatılır, yinelemeli formüller türetilir ve yakınsama oranına ilişkin tahminler verilir. Bundan sonra, ek yöntemin keyfi bir fonksiyonu optimize etmek için nasıl genelleştirildiği gösterilmiş, yöntemin çeşitli varyantları dikkate alınmış ve yakınsaklık tartışılmıştır.

Optimizasyon probleminin ifadesi

Bir küme verilmiş olsun ve bu küme üzerinde bir amaç fonksiyonu tanımlansın. Optimizasyon problemi, kümedeki amaç fonksiyonunun tam üst veya tam alt sınırının bulunmasından oluşur. Amaç fonksiyonunun alt sınırına ulaşılan noktalar kümesi belirlenir.

Eğer öyleyse, optimizasyon problemine kısıtsız denir. Eğer öyleyse, optimizasyon problemine kısıtlı denir.

İkinci dereceden fonksiyonel için eşlenik gradyan yöntemi

Yöntemin beyanı

Aşağıdaki optimizasyon problemini göz önünde bulundurun:

Burada simetrik bir pozitif tanımlı boyut matrisi var. Bu optimizasyon problemine ikinci dereceden denir. Dikkat. Bir fonksiyonun ekstremumunun koşulu sisteme eşdeğerdir. Fonksiyon alt sınırına denklemle tanımlanan tek bir noktada ulaşır. Böylece, bu optimizasyon problemi bir doğrusal denklem sisteminin çözümüne indirgenir. Eşlenik gradyan yönteminin fikri şu şekildedir: Temel olsun. Daha sonra herhangi bir nokta için vektör tabana genişletilir, böylece formda temsil edilebilir.

Sonraki her bir yaklaşım aşağıdaki formül kullanılarak hesaplanır:

Tanım. İki vektörün simetrik matris B'ye göre eşlenik olduğu söylenir, eğer

Eşlenik gradyan yönteminde bir taban oluşturma yöntemini açıklayalım. Başlangıç ​​yaklaşımı olarak rastgele bir vektör seçiyoruz. Her yinelemede aşağıdaki kurallar seçilir:

Temel vektörler aşağıdaki formüller kullanılarak hesaplanır:

Katsayılar, ve vektörleri A'ya göre eşlenik olacak şekilde seçilir.

İle belirtirsek, birkaç basitleştirmeden sonra eşlenik gradyan yöntemini pratikte uygularken kullanılan son formülleri elde ederiz:

Eşlenik gradyan yöntemi için aşağıdaki teorem geçerlidir: Let Teoremi, burada simetrik pozitif tanımlı bir boyut matrisidir. Daha sonra eşlenik gradyan yöntemi birden fazla adımda yakınsamaz ve aşağıdaki ilişkiler geçerlidir:

Yöntemin yakınsaması

Tüm hesaplamalar doğruysa ve başlangıç ​​verileri doğruysa, yöntem, sistemin boyutu olan yinelemelerden daha fazla olmayan bir sürede sistemi çözmeye yakınsar. Daha rafine bir analiz, yineleme sayısının, A matrisinin farklı özdeğerlerinin sayısını aşmadığını gösterir. Yakınsama oranını tahmin etmek için aşağıdaki (oldukça kaba) tahmin doğrudur:

Matrisin maksimum ve minimum özdeğerlerine ilişkin tahminler biliniyorsa, yakınsama oranını tahmin etmenizi sağlar. Uygulamada en sık aşağıdaki durdurma kriteri kullanılır:

Hesaplama karmaşıklığı

Yöntemin her yinelemesinde işlemler gerçekleştirilir. Ürünü hesaplamak için bu sayıda işlem gereklidir; bu, her yinelemede en çok zaman alan prosedürdür. Diğer hesaplamalar O(n) işlemlerini gerektirir. Yineleme sayısı n'den fazla olmadığından yöntemin toplam hesaplama karmaşıklığı aşmaz.

Sayısal örnek

Eşlenik gradyan yöntemini kullanarak bu sistemin çözümünün iki yinelemede elde edildiği bir sistemi çözmek için eşlenik gradyan yöntemini uygulayalım. Matrisin özdeğerleri 5, 5, -5'tir - aralarında iki farklı vardır, bu nedenle teorik tahmine göre yineleme sayısı ikiyi geçemez

Eşlenik gradyan yöntemi, SLAE'leri pozitif tanımlı bir matrisle çözmek için en etkili yöntemlerden biridir. Yöntem, sınırlı sayıda adımda yakınsamayı garanti eder ve gerekli doğruluk çok daha erken elde edilebilir. Temel sorun, hataların birikmesi nedeniyle temel vektörlerin ortogonalliğinin ihlal edilebilmesi ve bu durumun yakınsamayı olumsuz etkilemesidir.

Genel olarak eşlenik gradyan yöntemi

Şimdi, küçültülmüş fonksiyonelin ikinci dereceden olmadığı durum için eşlenik gradyan yönteminin bir modifikasyonunu ele alalım: Sorunu çözeceğiz:

Sürekli türevlenebilir fonksiyon. Bu sorunu çözmek amacıyla eşlenik gradyan yöntemini değiştirmek için A matrisini içermeyen formüller elde etmek gerekir:

üç formülden biri kullanılarak hesaplanabilir:

1. - Fletcher-Reeves yöntemi

• 2. - Polak-Ribi'ere yöntemi

Fonksiyon ikinci dereceden ve kesinlikle dışbükey ise, o zaman üç formülün tümü aynı sonucu verir. If keyfi bir fonksiyonsa, formüllerin her biri eşlenik gradyan yönteminin kendi modifikasyonuna karşılık gelir. Üçüncü formül, fonksiyonu ve yöntemin her adımında fonksiyonun Hessian'ının hesaplanmasını gerektirdiğinden nadiren kullanılır.

Fonksiyon ikinci dereceden değilse, eşlenik gradyan yöntemi sonlu sayıda adımda yakınsamayabilir. Üstelik her adımda doğru hesaplama ancak nadir durumlarda mümkündür. Bu nedenle hataların birikmesi, vektörlerin artık fonksiyonun azalma yönünü göstermemesine neden olur. Sonra bir aşamada inanırlar. Kabul edildiği tüm sayıların kümesi ile gösterilecektir. Sayılara yöntem güncelleme anları denir. Uygulamada genellikle mekanın boyutunun nerede olduğu seçilir.

Yöntemin yakınsaması

Fletcher-Reeves yöntemi için, minimize edilen fonksiyona çok katı olmayan koşullar getiren bir yakınsama teoremi vardır: Teorem. Aşağıdaki koşulların karşılanmasına izin verin:

Çeşitlilik sınırlıdır

Türev, Lipschitz koşulunu bazı komşuluklarda bir sabitle karşılar

M'yi ayarlar: .

Polak-Reiber yöntemi için yakınsaklık, tam dışbükey bir fonksiyon olduğu varsayımı altında kanıtlanmıştır. Genel durumda Polak-Reiber yönteminin yakınsamasını kanıtlamak imkansızdır. Tam tersine şu teorem doğrudur: Teorem. Polak-Reiber yönteminde her adımdaki değerlerin tam olarak hesaplandığını varsayalım. Sonra bir fonksiyon ve şöyle bir başlangıç ​​tahmini var.

Ancak pratikte Polak-Reiber yöntemi daha iyi sonuç verir. Pratikte en yaygın durdurma kriteri: Gradyan normu belirli bir eşiğin altına düşer Fonksiyonun değeri ardışık m iterasyon boyunca hemen hemen değişmeden kalır

Hesaplama karmaşıklığı

Polak-Reiber veya Fletcher-Reeves yöntemlerinin her yinelemesinde, fonksiyon ve gradyanı bir kez hesaplanır ve tek boyutlu optimizasyon problemi çözülür. Dolayısıyla eşlenik gradyan yönteminin bir adımının karmaşıklığı, en dik iniş yönteminin bir adımının karmaşıklığıyla aynı büyüklüktedir. Uygulamada eşlenik gradyan yöntemi en iyi yakınsama hızını gösterir.

Eşlenik gradyan yöntemini kullanarak fonksiyonun minimumunu arayacağız

Bu fonksiyonun minimumu 1'dir ve (5, 4) noktasında ulaşılır. Bu fonksiyonu örnek olarak kullanarak Polak-Reiber ve Fletcher-Reeves yöntemlerini karşılaştıralım. Her iki yöntemdeki yinelemeler, mevcut adımda degradenin kare normu küçüldüğünde durur. Seçimde altın oran yöntemi kullanılıyor

Eşlenik gradyan yönteminin iki versiyonu uygulanmıştır: ikinci dereceden bir fonksiyonu en aza indirmek için ve keyfi bir işlevi en aza indirmek için. İlk durumda yöntem vektör fonksiyonu tarafından uygulanır. FindSolution(matris bir,vektör b) Burada A ve b ikinci dereceden optimizasyon probleminin tanımında yer alan matris ve vektördür. Rastgele işlevselliği en aza indirmek için iki işlevden birini kullanabilirsiniz: vektör FletcherRievesMethod(int spaceSize, Function F, vektör (*GradF) (vektör )) vektör PolakRibiereMethod(int spaceSize, Function F, vektör (*GradF) (vektör )) Her iki işlevin parametreleri aynıdır ve şu anlama gelir: spaceSize - alanın boyutu (minimum duruma getirilmiş işlevin bağlı olduğu değişkenlerin sayısı) F - simge durumuna küçültülecek işlevin işaretçisi. Fonksiyon double formunda olmalıdır<имя функции>(vektör ) GradF - küçültülmüş fonksiyonelin gradyanını hesaplayan bir fonksiyonun işaretçisi Her iki yöntem de, tek boyutlu bir optimizasyon problemini çözmek için bir yardımcı fonksiyon kullanır. Program, altın bölüm yöntemini kullanarak tek boyutlu optimizasyon uygular.

Gradyan iniş yöntemleri optimizasyon problemlerini çözmek için oldukça güçlü araçlardır. Yöntemlerin en büyük dezavantajı uygulanabilirliğin sınırlı olmasıdır. Eşlenik gradyan yöntemi, gradyan iniş yöntemlerinde olduğu gibi, yalnızca bir noktadaki artışın doğrusal kısmı hakkındaki bilgileri kullanır. Dahası, eşlenik gradyan yöntemi ikinci dereceden problemleri sonlu sayıda adımda çözmenize olanak tanır. Diğer birçok problemde eşlenik gradyan yöntemi aynı zamanda gradyan iniş yönteminden daha iyi performans gösterir. Gradyan yönteminin yakınsaması, önemli ölçüde tek boyutlu optimizasyon probleminin ne kadar doğru çözüldüğüne bağlıdır. Olası yöntem döngüleri güncellemeler kullanılarak çözülür. Bununla birlikte, eğer bir yöntem bir fonksiyonun yerel minimumuna girerse, büyük olasılıkla ondan kaçamayacaktır.

Her yinelemede en dik iniş yöntemini kullanırken adım boyutu A R fonksiyonun minimum koşulundan seçilir f(x) iniş yönünde, yani

f(x[R] -A R -f"(x[R])) = f(x f'(x -af"(x[R])) .

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[R]-af"(x[R])) .

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[R], k = 0, 1, 2, ... gradyan değerini hesaplar -f"(x[R]) .
• 3. Adım boyutu belirlenir A k, tek boyutlu minimizasyonla A işlevler j (A) = f(x[R]-af"(x[R])).
• 4. Noktanın koordinatları belirlenir X[X[ 1]:

X N(x) [X[ 1]1)Prosedür 1-4'ün tekrarı, değiştirme ile periyodik olarak tekrarlanır N(x) [R] -A R F" N(x) (X[R]), i = 1,..., s.

5. Sterasyon 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[R] noktada seviye çizgisine dokunuyor k+[X[ 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 f'(x -af"(x[R])) . Bir fonksiyonun minimumu için gerekli koşul Bir fonksiyonun minimumu için gerekli koşul J D Karmaşık bir fonksiyonun türevini hesapladıktan sonra, iniş yönleri vektörlerinin komşu noktalardaki diklik koşulunu elde ederiz:

Bir fonksiyonun minimumu için gerekli koşul J (a)/da = -f"(x[X[ 1]-f"(x[R]) = 0.

Pirinç. 2.9.

Gradyan yöntemleri, düzgün dışbükey fonksiyonlar için yüksek hızda (geometrik ilerleme hızı) minimuma yakınsar. Bu tür işlevler en büyük En dik iniş yönteminin geometrik yorumu ve en azından M ikinci türevler matrisinin özdeğerleri (Hessian matrisi)

birbirinden çok az farklılık gösterir, yani matris ikinci türevler matrisinin özdeğerleri (Hessian matrisi) iyi şartlandırılmış. Özdeğerlerin l i olduğunu hatırlayın, N(x) =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.

En dik iniş yöntemi (İ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ı arttığı (azaldığı) yö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, gradyan iniş yönteminin daha da geliştirilmiş halidir. Genel olarak, bir fonksiyonun ekstremumunu bulma süreci yinelemeli bir prosedürdür ve şu ş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 dokunur. İ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, sayısız modifikasyonuyla birlikte, incelenen nesnelerin optimumunu aramak için yaygın ve etkili bir yöntemdir. Gradyan aramanın (yukarıda tartışılan yöntemlerin yanı sıra) dezavantajı, onu kullanırken fonksiyonun yalnızca yerel ekstremumunun tespit edilebilmesidir. Diğer yerel ekstremumları bulmak için başka başlangıç ​​noktalarından arama yapmak 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

1. Adım: 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.