Eşlenik gradyan yöntemini kullanarak yerel bir ekstremumu bulma. Seyrek matris çarpımı

Yalnızca gradyan hesaplamasına dayalı gradyan yöntemleri R(X), birinci dereceden yöntemlerdir, çünkü adım aralığında doğrusal olmayan fonksiyonun yerini alırlar R(X) doğrusal.

Sadece birinciyi değil aynı zamanda ikinci türevlerini de kullanan ikinci dereceden yöntemler R(X) şu anki noktada. Bununla birlikte, bu yöntemlerin kendi çözülmesi zor problemleri vardır - bir noktada ikinci türevlerin hesaplanması ve dahası, optimumdan çok uzakta, ikinci türevlerin matrisi kötü koşullandırılmış olabilir.

Eşlenik gradyan yöntemi, birinci ve ikinci dereceden yöntemlerin avantajlarını birleştirerek dezavantajlarını ortadan kaldırma girişimidir. Açık başlangıç ​​aşamaları(optimumdan uzak) yöntem birinci dereceden bir yöntem gibi davranır ve optimumun yakınında ikinci dereceden yöntemlere yaklaşır.

İlk adım, en dik iniş yönteminin ilk adımına benzer, ikinci ve sonraki adımlar her seferinde belirli bir noktadaki gradyan vektörlerinin ve bir önceki yönün doğrusal birleşimi olarak oluşturulan yönde seçilir.

Yöntem algoritması aşağıdaki gibi yazılabilir (vektör formunda):

x 1 = x 0 – h dereceli R(x 0),

x ben+1 = x ben – h .

α değeri yaklaşık olarak ifadeden bulunabilir.

Algoritma şu şekilde çalışır. Başlangıç ​​noktasından X 0 dk arıyorum R(X) gradyan yönünde (yöntemi ile) hızlı iniş), daha sonra bulunan noktadan başlayarak min arama yönü ikinci ifadeyle belirlenir. Minimumu yönde arama herhangi bir şekilde gerçekleştirilebilir: minimumu geçerken tarama adımını ayarlamadan sıralı tarama yöntemini kullanabilirsiniz, böylece yönde minimuma ulaşmanın doğruluğu adım boyutuna bağlıdır H.

İkinci dereceden bir fonksiyon için R(X) bir çözüm bulunabilir N adımlar (P– sorunun boyutu). Diğer işlevler için arama daha yavaş olacaktır ve bazı durumlarda, güçlü etki hesaplama hataları.

Eşlenik gradyan yöntemini kullanarak iki boyutlu bir fonksiyonun minimumunu aramak için olası yörüngelerden biri Şekil 2'de gösterilmektedir. 1.

Minimumu bulmak için eşlenik gradyan yönteminin algoritması.

Başlangıç ​​aşaması. Gradyan yönteminin yürütülmesi.

İlk yaklaşımı ayarlayın X 1 0 ,X 2 0. Kriterin değerinin belirlenmesi R(X 1 0 ,X 2 0). k = 0 olarak ayarlayın ve başlangıç ​​aşamasının 1. adımına gidin.

Adım 1. Ve
.

Adım 2. Degrade modülü ise

Adım 3.

X k+1 = X k – H mezun R(X k)).

Adım 4. R(X 1 bin +1, X 2 bin +1). Eğer R(X 1 bin +1, X 2 bin +1)< R(X 1k, X 2 k), ardından k = k+1 olarak ayarlayın ve 3. adıma gidin. R(X 1 bin +1, X 2 bin +1) ≥ R(X 1k, X 2 k), ardından ana aşamaya gidin.

Ana sahne.

Adım 1. R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k) hesaplayın . Algoritmaya uygun olarak merkezi veya eşleştirilmiş bir örnekten kısmi türevlerin değerini hesaplayın Ve . Gradyan modülü değerini hesaplayın
.

Adım 2. Degrade modülü ise
, sonra hesaplamayı durdurun ve (x 1 k, x 2 k) noktasının optimum nokta olduğunu düşünün. Aksi halde 3. adıma geçin.

Adım 3. Aşağıdaki formüle göre α katsayısını hesaplayın:

Adım 4. Formülü kullanarak hesaplayarak iş adımını gerçekleştirin

x k+1 = x k – h .

Adım 5. Kriter değerini belirleyin R(X 1 bin +1, X 2 bin +1). k = k+1 olarak ayarlayın ve 1. adıma gidin.

Örnek.

Karşılaştırma için önceki örneğin çözümünü düşünün. İlk adımı en dik iniş yöntemini kullanarak atıyoruz (Tablo 5).

Tablo 5

En iyi nokta bulunmuştur. Bu noktada türevleri hesaplıyoruz: dr./ dx 1 = –2.908; dr./ dx 2 =1.600; Bir önceki noktadaki eğimin etkisini hesaba katan α katsayısını hesaplıyoruz: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Yöntemin algoritmasına uygun bir çalışma adımı atıyoruz, elde ediyoruz X 1 = 0,502, X 2 = 1.368. Sonra her şey aynı şekilde tekrarlanır. Aşağıda, tabloda. Şekil 6 sonraki adımlar için mevcut arama koordinatlarını göstermektedir.

Tablo 6

“Eşlenik gradyan yöntemi” terimi, alışılmış hale gelen anlamsız ifadelerin nasıl olduğu gibi kabul edildiğine ve herhangi bir kafa karışıklığına neden olmadığına bir örnektir. Gerçek şu ki, pratik açıdan ilgi çekmeyen özel bir durum dışında, gradyanlar eşlenik değildir ve eşlenik yönlerin gradyanlarla hiçbir ilgisi yoktur. Yöntemin adı şu gerçeği yansıtıyor: bu yöntem koşulsuz bir ekstremum bulmak gradyan kavramlarını birleştirir amaç fonksiyonu ve ilgili talimatlar.

Aşağıda kullanılan gösterimle ilgili birkaç kelime.

İki vektörün skaler çarpımı $x^Ty$ olarak yazılır ve skalerlerin toplamını temsil eder: $\sum_(i=1)^n\, x_i\,y_i$. $x^Ty = y^Tx$ olduğuna dikkat edin. Eğer x ve y dikse, o zaman $x^Ty = 0$. Genel olarak $x^Ty$ ve $x^TA_x$ gibi 1x1 matrise dönüşen ifadeler skaler olarak kabul edilir.

Eşlenik gradyan yöntemi başlangıçta doğrusal sistemleri çözmek için geliştirildi. cebirsel denklemler tip:

x nerede değil ünlü vektör, b bilinen bir vektördür ve A bilinen, kare, simetrik, pozitif tanımlı bir matristir. Bu sistemi çözmek, karşılık gelen ikinci dereceden formun minimumunu bulmaya eşdeğerdir.
İkinci dereceden form, aşağıdaki formdaki bir x vektörünün basitçe skaler, ikinci dereceden bir fonksiyonudur:

$f\,(x) = (\frac(1)(2))\,x^TA_x\,-\,b^Tx\,+\,c$, (2)

Matris arasında böyle bir bağlantının varlığı doğrusal dönüşüm bir ve skaler fonksiyon f(x) bazı formülleri göstermeyi mümkün kılar doğrusal cebir sezgisel çizimler. Örneğin, sıfırdan farklı herhangi bir x vektörü için aşağıdakiler doğruysa, A matrisinin pozitif tanımlı olduğu söylenir:

$x^TA_x\,>\,0$, (3)

Şekil 1 neye benzediklerini göstermektedir ikinci dereceden formlar sırasıyla pozitif tanımlı bir matris (a), negatif tanımlı bir matris (b), pozitif-belirsiz bir matris (c), belirsiz bir matris (d) için.

Yani, A matrisi pozitif tanımlıysa, denklem 1 sistemini çözmek yerine ikinci dereceden fonksiyonunun minimumunu bulabilirsiniz. Üstelik eşlenik gradyan yöntemi bunu n veya daha az adımda yapacaktır; burada n, bilinmeyen vektör x'in boyutudur. Herhangi birinden beri pürüzsüz fonksiyon minimum noktası civarında ikinci dereceden bir yaklaşımla iyi bir şekilde tahmin edilirse, aynı yöntem en aza indirmek için kullanılabilir ve ikinci dereceden fonksiyonlar. Bu durumda yöntem sonlu olmaktan çıkar, yinelemeli hale gelir.

Daha fazlasını göz önünde bulundurarak eşlenik gradyan yöntemini düşünmeye başlamanız önerilir. basit yöntem Bir fonksiyonun ekstremumunu arama - en dik iniş yöntemi. Şekil 2, en dik iniş yöntemini kullanarak minimum noktaya kadar hareketin yörüngesini göstermektedir. Bu yöntemin özü:

• x(0) başlangıç ​​noktasında gradyan hesaplanır ve hareket, amaç fonksiyonu azalıncaya kadar antigradyan yönünde gerçekleştirilir;
• fonksiyonun azalmayı bıraktığı noktada eğim tekrar hesaplanır ve iniş yeni bir yönde devam eder;
• minimum noktaya ulaşılana kadar işlem tekrarlanır.

İÇİNDE bu durumda her yeni hareket yönü bir öncekine diktir. Yeni bir yön seçmenin daha akıllıca bir yolu yok mu? Vardır ve buna eşlenik yönler yöntemi denir. Ve eşlenik gradyan yöntemi eşlenik yön yöntemleri grubuna aittir. Şekil 3, eşlenik gradyan yöntemini kullanarak minimum noktaya kadar hareketin yörüngesini göstermektedir.

Eşlenik tanımı şu şekilde formüle edilir: iki x ve y vektörüne A-eşleni (veya A matrisine göre eşlenik) veya A-ortogonal denir. nokta çarpım x ve Ay sıfıra eşittir, yani:

$x^TA_y\,=\,0$, (4)

Eşleniklik diklik kavramının bir genellemesi olarak düşünülebilir. Aslında A matrisi birim matris olduğunda, eşitlik 4'e göre x ve y vektörleri diktir. Diklik ve eşleniklik kavramları arasındaki ilişkiyi göstermenin başka bir yolu daha vardır: Şekil 3'ü zihinsel olarak uzatın, böylece elipslerden eşit düzeydeki çizgiler dairelere dönüşür ve eşlenik yönler basitçe dik olur.

Eşlenik yönlerin nasıl hesaplanacağı görülecektir. Bir tanesi olası yollar– Lineer cebir yöntemlerini, özellikle de Gram-Schmidt dikleştirme sürecini kullanın. Ancak bunun için A matrisini bilmeniz gerekir, bu nedenle çoğu görev için (örneğin, çok katmanlı sinir ağlarının eğitimi) bu yöntem uygun değildir. Neyse ki, eşlenik yönünü hesaplamanın başka yinelemeli yolları da vardır; en ünlüsü Fletcher-Reeves formülüdür:

$d_((i+1)) = d_((i+1))\,+\,\beta_((i+1))\,d_i$ , (5)

$\beta_((i+1)) = \frac(r_((i+1))^T)(r_(i)^T)\,\frac(r_((i+1)))(r_( (i)))$, (6)

Formül 5, yeni eşlenik yönünün, dönüş noktasındaki antigradyan ve önceki hareket yönünün formül 6 ile hesaplanan katsayı ile çarpılmasıyla elde edilmesi anlamına gelir. Eğer küçültülmüş fonksiyon şu şekilde hesaplanırsa, formül 5 ile hesaplanan yönlerin eşlenik olduğu ortaya çıkar. form 2'de verilmiştir. Yani ikinci dereceden eşlenik gradyan yöntemi, fonksiyonları en az n adımda bulur (n, arama uzayının boyutudur). Fonksiyonlar için genel görünüm Algoritma sonlu olmaktan çıkar ve yinelemeli hale gelir. Aynı zamanda Fletcher ve Reeves, algoritmik prosedürün her n + 1 adımda bir sürdürülmesini önermektedir.

Eşlenik yönünü belirlemek için başka bir formül olan Polak-Ribiere formülünü verebilirsiniz:

$\beta_((i+1)) = \frac(r_((i+1))^T\,(r_((i+1))\,-\,r_((i))))(r_ (i)^T\,r_((i))$, (7)

Fletcher-Reeves yöntemi şu durumda yakınsar: başlangıç ​​noktası gerekli minimum değere oldukça yakındır, oysa Polak-Reiber yöntemi nadir durumlarda süresiz olarak döngü yapabilir. Ancak ikincisi sıklıkla birleşir ilkinden daha hızlı yöntem. Neyse ki, Polak-Reiber yönteminin yakınsaması $\beta = \max \(\beta;\,0\)$ seçilerek garanti edilebilir. Bu, algoritmanın $\beta \leq 0$ koşulu altında yeniden başlatılmasına eşdeğerdir. Son arama yönünü unutup algoritmayı en dik iniş yönünde yeniden başlatmak için algoritmik prosedürün yeniden başlatılması gerekir.

1. Antigradyan şu şekilde hesaplanır: keyfi nokta x(0) .
   

   $d_((0)) = r_((0)) = -\,f"(x_((0)))$

2. Fonksiyon azaldıkça hesaplanan yöne doğru iner, yani minimuma indiren bir (i)’yi arar.
   

   $f\,(x_((i))\,+\,a_((i))\,d_((i))))$

3. Önceki paragrafta bulunan noktaya gidin
   

   $x_((i+1)) = x_((i))\,+\,a_((i))\,d_((i))$

4. Bu noktada antigradiyentin hesaplanması
   

   $r_((i+1)) = -\,f"(x_((i+1))))$

5. Formül 6 veya 7'yi kullanan hesaplamalar. Algoritmayı yeniden başlatmak, yani son arama yönünü unutup algoritmayı en dik iniş yönünde yeniden başlatmak için, Fletcher-Reeves formülüne göre, Polak için her n + 1 adımda bir 0 atanır. -Reiber formülü - $\beta_ ((i+1)) = \max \(\beta_((i+1))),\,0\)$
6. Yeni eşlenik yönünü hesapla
   

   $d_((i+1)) = r_((i+1))\,+\,\beta_((i+1))\,d_((i))$

7. 2. noktaya gidin.

Yukarıdaki algoritmadan, 2. adımda fonksiyonun tek boyutlu minimizasyonunun gerçekleştirildiği anlaşılmaktadır. Bunu yapmak için özellikle Fibonacci yöntemini, altın bölüm yöntemini veya ikiye bölme yöntemini kullanabilirsiniz. Newton-Raphson yöntemi daha hızlı yakınsama sağlar ancak bunun için Hessian matrisini hesaplayabilmek gerekir. İÇİNDE ikinci durum optimizasyon için kullanılan değişken, her yineleme adımında aşağıdaki formül kullanılarak hesaplanır:

$$a = -\,\frac((f")^T\,(x)\,d)(d^T\,f""(x)\,d)$$

$f""(x)\,= \begin(pmatrix) \frac(\partial^2\,f)(\partial x_1\,\partial x_1)&\frac(\partial^2\,f)(\ kısmi x_1\,\kısmi x_2)&\cdots&\frac(\partial^2\,f)(\partial x_1\,\partial x_n)& \\ \frac(\partial^2\,f)(\partial x_2 \,\kısmi x_1)&\frac(\partial^2\,f)(\partial x_2\,\partial x_2)& \cdots&\frac(\partial^2\,f)(\partial x_2\,\partial x_n)& \\ \vdots&\vdots&\ddots&\vdots &\\ \frac(\partial^2\,f)(\partial x_n\,\partial x_1)& \frac(\partial^2\,f)( \partial x_n\,\partial x_2)&\cdots&\frac(\partial^2\,f)(\partial x_n\,\partial x_n) \end(pmatrix)$
Hessian matrisi

Öğretimde birleşik yön yönteminin kullanılması hakkında birkaç söz sinir ağları. Bu durumda çağa dayalı öğrenme kullanılır, yani amaç fonksiyonu hesaplanırken eğitim setinin tüm şablonları sunulur ve hata fonksiyonunun ortalama karesi (veya bunun bazı modifikasyonları) hesaplanır. Gradyan hesaplanırken de aynı durum geçerlidir, yani tüm eğitim seti üzerindeki toplam gradyan kullanılır. Her örneğin gradyanı algoritma kullanılarak hesaplanır geri yayılım(BackProp).

Sonuç olarak, eşlenik gradyan yönteminin yazılım uygulaması için olası algoritmalardan birini sunuyoruz. Bu durumda eşleniklik Fletcher-Reeves formülü kullanılarak hesaplanır ve tek boyutlu optimizasyon için yukarıdaki yöntemlerden biri kullanılır. Bazı yetkili uzmanlara göre, algoritmanın yakınsama hızı, yukarıdaki algoritmanın 2. adımında kullanılan optimizasyon formülüne çok az bağlıdır, bu nedenle, örneğin, türevlerin hesaplanmasını gerektirmeyen altın bölüm yöntemini önerebiliriz.

Eşlenik yönleri hesaplamak için Fletcher-Reeves formülünü kullanan eşlenik yönler yönteminin bir çeşidi.

r:= -f"(x) // amaç fonksiyonunun antigradiyent'i

d:= r // başlangıç ​​yönü iniş antigradyan ile çakışıyor

Sigma yeni: = r T * r // antigradyan modülün karesi

Sigma 0: = Sigma yeni

// Arama döngüsü (sayaçta veya hatada çıkış)
ben iken< i max and Sigma new >Eps 2 * Sigma 0
başlamak
j:=0
Sigma d: = d T * d

// Tek boyutlu minimizasyon döngüsü (d yönünde alçalma)
tekrarlamak
bir: =
x: = x + a
j: = j + 1
(j >= j max) veya (a 2 * Sigma d) kadar<= Eps 2)

R: = -f"(x) // amaç fonksiyonunun yeni noktada ters gradyanı
Eski Sigma: = Yeni Sigma
Yeni Sigma: = r T * r
beta: = Sigma yeni / Eski Sigma
d: = r + beta * d // Eşlenik yönünü hesapla
k: = k + 1

Eğer (k = n) veya (r T * d<= 0) then // Рестарт алгоритма
başlamak
d:=r
k:=0
son

ben: = ben + 1
son

Eşlenik gradyan yöntemi birinci dereceden bir yöntemdir ve aynı zamanda yakınsama oranı ikinci derecedendir. Bu, geleneksel gradyan yöntemleriyle olumlu şekilde karşılaştırılır. Örneğin, ikinci dereceden bir fonksiyon için en dik iniş yöntemi ve koordinat iniş yöntemi yalnızca limitte yakınlaşırken, eşlenik gradyan yöntemi ikinci dereceden fonksiyonu sonlu sayıda yinelemede optimize eder. Genel fonksiyonları optimize ederken eşlenik yön yöntemi, en dik iniş yönteminden 4-5 kat daha hızlı yakınsar. Bu durumda, ikinci dereceden yöntemlerden farklı olarak, ikinci kısmi türevlerin emek yoğun hesaplamalarına gerek yoktur.

Edebiyat

• N.N.Moiseev, Yu.P.Ivanilov, E.M.Stolyarova "Optimizasyon yöntemleri", M. Nauka, 1978
• A. Fiacco, G. McCormick "Doğrusal olmayan programlama", M. Mir, 1972
• W.I. Zangwill "Doğrusal olmayan programlama", M. Sovyet radyosu, 1973
• Jonathan Richard Shewchuk "İkinci dereceden gradyan yöntemleri", Bilgisayar Bilimleri Okulu Carnegie Mellon Üniversitesi Pittsburg, 1994

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

fonksiyonun değişken sayısına eşit, sonlu sayıda adım n'de simetrik pozitif tanımlı bir matris H ile. 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.

Tanım gereği, skaler çarpım (x, H) = 0 ise, iki n boyutlu x ve y vektörüne H matrisine eşlenik (veya H-eşlenik) denir. Burada H, nxn boyutunda simetrik pozitif tanımlı bir matristir.

Eşlenik gradyan yöntemlerindeki en önemli sorunlardan biri, yönlerin verimli bir şekilde oluşturulması sorunudur. Fletcher-Reeves yöntemi bu sorunu, her adımda antigradyan -f(x[k])'yi p[k] yönüne, H-eşlenisini daha önce bulunan p, p, ..., p yönlerine dönüştürerek çözer. Öncelikle bu yöntemi ikinci dereceden bir fonksiyonun en aza indirilmesi problemiyle ilişkili olarak ele alalım.

Yönler p[k] aşağıdaki formüller kullanılarak hesaplanır:

p[k] = -f’(x[k])+k-1p, k >= 1; p = -f’(x).

k-1 değerleri p[k], p yönleri H-eşleniği olacak şekilde seçilir:

(p[k], Hp)= 0.

Sonuç olarak, ikinci dereceden fonksiyon için

yinelemeli minimizasyon süreci şu şekildedir

x =x[k] +akp[k],

burada p[k] k'inci adımdaki iniş yönüdür; ak adım boyutudur. İkincisi, f(x) fonksiyonunun a hareket yönündeki minimum koşulundan, yani tek boyutlu minimizasyon probleminin çözülmesinin bir sonucu olarak seçilir:

f(х[k] + aкр[k]) = f(x[k] + ар [k]).

İkinci dereceden bir fonksiyon için

Fletcher-Reeves eşlenik gradyan yönteminin algoritması aşağıdaki gibidir.

1. x noktasında p = -f’(x) hesaplanır.

2. K. adımda yukarıdaki formüller kullanılarak ak adımı belirlenir. ve x noktası.

3. f(x) ve f’(x) değerleri hesaplanır.

4. Eğer f'(x) = 0 ise x noktası f(x) fonksiyonunun minimum noktasıdır. Aksi takdirde, yeni yön p ilişkiden belirlenir.

ve bir sonraki iterasyona geçiş gerçekleştirilir. Bu prosedür, ikinci dereceden bir fonksiyonun minimumunu n'den fazla olmayan adımda bulacaktır. İkinci dereceden olmayan fonksiyonları en aza indirirken, Fletcher-Reeves yöntemi sonludan yinelemeli hale gelir. Bu durumda, (n+1)'inci yinelemeden sonra, 1-4 prosedürleri döngüsel olarak x'in yerine x[n+1] getirilerek tekrarlanır ve hesaplamalar, belirli bir sayı olan 'de sona erer. Bu durumda yöntemin aşağıdaki modifikasyonu kullanılır:

x = x[k] +akp[k],

p[k] = -f’(x[k])+k-1p, k >= 1;

f(x[k] + akp[k]) = f(x[k] + ap[k];

Burada I bir dizi indekstir: I = (0, n, 2n, 3n, ...), yani yöntem her n adımda bir güncellenir.

Eşlenik gradyan yönteminin geometrik anlamı aşağıdaki gibidir (Şekil 1.19). Belirli bir x başlangıç ​​noktasından itibaren p = -f"(x) yönünde iniş gerçekleştirilir. X noktasında, f"(x) gradyan vektörü belirlenir. X, fonksiyonun p yönündeki minimum noktası olduğundan, f'(x) p vektörüne diktir. Daha sonra p vektörü bulunur, p'ye H-eşleni. Daha sonra fonksiyonun minimumu p vb. yönünde bulunur.

Pirinç. 1.19. Eşlenik gradyan yönteminde iniş yörüngesi

Eşlenik yön yöntemleri, minimizasyon problemlerinin çözümünde en etkili yöntemler arasındadır. Ancak sayma işlemi sırasında meydana gelen hatalara karşı hassas olduklarını unutmamak gerekir. Çok sayıda değişkenle hata o kadar artabilir ki, ikinci dereceden bir fonksiyon için bile işlemin tekrarlanması gerekecek, yani işlem her zaman n adıma sığmaz.

İkinci dereceden kısıtsız optimizasyonun sayısal yöntemleri, Newton yöntem algoritmalarının çeşitleri

İkinci dereceden yöntemlerin özellikleri. İkinci dereceden kısıtsız optimizasyon yöntemleri, minimize edilmiş f(x) fonksiyonunun ikinci kısmi türevlerini kullanır. Bu yöntemlerin özü aşağıdaki gibidir.

Çok değişkenli f(x) fonksiyonunun x* noktasındaki ekstremumu için gerekli koşul, bu noktadaki gradyanının sıfıra eşit olmasıdır:

F'(x)'in x[k] noktası civarında Taylor serisine genişletilmesi, birinci dereceden terimlere kadar, önceki denklemi formda yeniden yazmamızı sağlar.

f"(x) f’(x[k]) + f"(x[k]) (x - x[k]) 0.

Burada f"(x[k]) Н(х[k]), minimize edilen fonksiyonun ikinci türevlerinin matrisidir (Hessian matrisi). Sonuç olarak, f fonksiyonunu minimizasyon problemini çözmek için ardışık yaklaşımlar oluşturmaya yönelik yinelemeli süreç (x) ifadesiyle tanımlanır

x x[k] - H-1(x[k]) f’(x[k]) ,

burada H-1(x[k]) Hessian matrisinin ters matrisidir ve H-1(x[k])f’(x[k]) р[k] iniş yönüdür.

Ortaya çıkan minimizasyon yöntemine Newton yöntemi denir. Bu yöntemde p[k] yönündeki adım boyutunun birliğe eşit olduğu varsayılmaktadır. Belirli varsayımlar altında yinelemeli sürecin uygulanması sonucunda elde edilen (x[k]) noktaları dizisi, f(x) fonksiyonunun bazı sabit x* noktalarına yakınsar. Eğer Hessian matrisi H(x*) pozitif tanımlı ise, x* noktası f(x) fonksiyonunun kesin yerel minimumunun bir noktası olacaktır. x[k] dizisi, yalnızca amaç fonksiyonunun Hessian matrisinin her yinelemede pozitif tanımlı olması durumunda x* noktasına yakınsar.

Eğer f(x) fonksiyonu ikinci dereceden ise, başlangıçtaki x yaklaşımına ve oluk derecesine bakılmaksızın, Newton metodu kullanılarak minimumu tek adımda bulunur. Bu, herhangi bir x noktasındaki р[k] H-1(x[k])f’(x[k]) iniş yönünün her zaman minimum x* noktasına olan yön ile çakışması gerçeğiyle açıklanmaktadır. Eğer f(x) fonksiyonu ikinci dereceden değil dışbükey ise, Newton'un yöntemi onun yinelemeden yinelemeye monoton bir şekilde azalmasını garanti eder. Dağ geçidi fonksiyonları en aza indirilirken Newton yönteminin yakınsama oranı gradyan yöntemlerine göre daha yüksektir. Bu durumda, p[k] vektörü, f(x) fonksiyonunun minimum noktasına olan yönü göstermez, ancak vadi ekseni boyunca büyük bir bileşene sahiptir ve minimum yönüne, f(x) noktasından çok daha yakındır. antigradyan.

Newton yönteminin önemli bir dezavantajı, dışbükey olmayan fonksiyonlar için yakınsaklığın başlangıç ​​yaklaşımı x'e bağlı olmasıdır. Eğer x minimum noktadan yeterince uzaktaysa, yöntem farklılaşabilir, yani yineleme sırasında sonraki her nokta minimum noktadan bir öncekine göre daha uzak olacaktır. Yöntemin yakınsaması, ilk yaklaşımdan bağımsız olarak, yalnızca p[k] H-1(x[k])f'(x[k]] iniş yönünün seçilmesiyle değil, aynı zamanda a adım boyutunun seçilmesiyle de sağlanır. bu yön boyunca. İlgili algoritmaya adım kontrollü Newton yöntemi adı verilir. Bu durumda yinelemeli süreç şu ifadeyle belirlenir:

x x[k] - akH-1(x[k])f’(x[k]).

Adım boyutu ak, f(x) fonksiyonunun a hareket yönündeki minimum koşulundan, yani tek boyutlu minimizasyon probleminin çözülmesinin bir sonucu olarak seçilir:

f(x[k] – ak H-1(x[k])f'(x[k]) (f(x[k] - aH-1(x[k])f'(x[k]) ).

Algoritmanın bu versiyonuna Newton-Raphson yöntemi de denir. Newton yönteminin bu versiyonunun grafiksel bir yorumu Şekil 1'de sunulmaktadır. 1.20. Şeklin belirtme çizgileri, adımı belirlemek için optimizasyona tabi tutulan tek boyutlu fonksiyonların grafiklerini gösterir.

Pirinç. 1.20. Newton-Raphson yönteminin geometrik yorumu

Newton-Raphson yönteminin algoritması aşağıdaki gibidir. Yineleme süreci başlamadan önce bazı eylemler gerçekleştirilir. Yani, f'([x]) gradyanını oluşturan formüllerden oluşan bir vektör (yani birinci kısmi türevlerin bir vektörü) ve Hessian matrisi H(x)'i oluşturan formüllerden oluşan bir matris (ör. , ikinci kısmi türevlerin bir matrisi). Daha sonra yinelemeli döngüde x vektörünün bileşenlerinin değerleri bu formüllerde yerine konulur ve bu diziler sayı dizileri haline gelir.

1. x başlangıç ​​noktasında, p - H-1(x)f’() iniş yönünü belirleyen bir vektör hesaplanır. Böylece çok boyutlu problem tek boyutlu optimizasyon problemine indirgenir.

2. K'inci yinelemede, ak adımı belirlenir (Şekil 1.20'de gösterilen şemaya göre; bu amaçla tek boyutlu bir optimizasyon problemi çözülür) ve x noktası belirlenir.

3. f(x) değeri hesaplanır.

4. Bu algoritmayı uygulayan alt programdan çıkma koşulları kontrol edilir. Bu koşullar, en dik iniş yöntemini kullanarak bir alt programdan çıkma koşullarına benzer. Bu koşullar yerine getirilirse hesaplamalar sonlandırılır. Aksi halde yeni bir yön hesaplanır

р –H-1(x[k])f’([k])

ve bir sonraki yinelemeye, yani 2. adıma geçiş gerçekleştirilir.

Newton yöntemine göre yineleme başına hesaplama sayısı, kural olarak, gradyan yöntemlerine göre çok daha fazladır. Bu, amaç fonksiyonunun ikinci türevlerinin matrisini hesaplama ve tersine çevirme (veya daha az emek gerektiren bir denklem sistemini çözme) ihtiyacıyla açıklanmaktadır. Bununla birlikte, Newton yöntemini kullanarak yeterince yüksek doğruluk derecesine sahip bir çözüm elde etmek, genellikle gradyan yöntemlerine göre çok daha az yineleme gerektirir. Bu nedenle Newton'un yöntemi önemli ölçüde daha etkilidir. Minimize edilen f(x) fonksiyonunun karşıladığı gereksinimlere bağlı olarak süper doğrusal veya ikinci dereceden yakınsama oranına sahiptir. Bununla birlikte, bazı problemlerde, minimuma indirilen fonksiyonun ikinci türevlerinin matrisini hesaplama ihtiyacı nedeniyle Newton yöntemini kullanan yinelemenin karmaşıklığı çok büyük olabilir ve bu, önemli miktarda bilgisayar zamanı gerektirir.

Bazı durumlarda gradyan yöntemleri ile Newton yönteminin birleştirilmesi tavsiye edilir. Minimizasyon sürecinin başlangıcında, x noktası x* uç noktasından uzakta olduğunda, gradyan yöntemlerinin bazı çeşitleri kullanılabilir. Daha sonra gradyan yönteminin yakınsama oranı azaldığında Newton yöntemine geçebilirsiniz. Veya hesaplama işlemi sırasında hataların birikmesi nedeniyle Hessian matrisi bazı yinelemelerde negatif tanımlı olabilir veya tersine çevrilemeyebilir. Bu gibi durumlarda, optimizasyon rutinleri H-1(x[k]) E'ye dayanır; burada E, birim matristir. Yineleme en dik iniş yöntemi kullanılarak gerçekleştirilir.

Newton yönteminin Levenberg-Marquardt yöntemi (Matris ayarlamalı Newton yöntemi) adı verilen başka bir modifikasyonunda, bu matrisin düzenlileştirilmesi, Hessian matrisinin dizi noktalarında pozitif kesinliğini sağlamak için kullanılır. Levenberg-Marquardt yönteminde noktalar şu yasaya göre oluşturulur: matrisin pozitif kesinliğini sağlayan pozitif sayılar dizisi. Genellikle değer, matrisin en büyük elemanından daha büyük bir büyüklük sırası olarak alınır. Birçok standart programda durum böyledir. Eğer, o zaman , aksi takdirde Açıktır ki if , o zaman Levenberg-Marquardt yöntemi Newton'un yöntemidir ve eğer büyükse, o zaman büyük için Levenberg-Marquardt yöntemi gradyan yöntemine yakındır. Dolayısıyla parametrenin değerleri seçilerek Levenberg-Marquardt yönteminin yakınsamasını sağlamak mümkündür.

Önceki alt bölümlerde Cauchy ve Newton yöntemleri tartışılmıştı. Minimum noktadan önemli mesafelerde arama yaparken Cauchy yönteminin etkili olduğu kaydedildi. X* ve bu noktanın yakınında kötü "çalışıyor", oysa Newton'un yöntemi arama yaparken pek güvenilir değil X* Ancak uzak bir noktadan bakıldığında çok etkili olduğu ortaya çıkıyor. X(k) minimum noktaya yakındır. Bu ve sonraki alt bölümlerde Cauchy ve Newton yöntemlerinin pozitif özelliklerine sahip olan ve yalnızca birinci türevlerin değerlerinin hesaplanmasına dayanan yöntemler tartışılmaktadır. Dolayısıyla bu yöntemler bir yandan arama yaparken son derece güvenilirdir. X* uzak bir yerden X* ve diğer taraftan minimum noktanın yakınında hızla birleşir.

İkinci dereceden amaç fonksiyonlarına sahip problemlere yaklaşık olarak çözüm elde edilmesini sağlayan yöntemler N ondalık olmayan kesirlerin kullanımına bağlı olarak adımları arayacağız ikinci dereceden yakınsak. Bu tür yöntemler arasında yapıya dayalı bir algoritma sınıfını ayırt edebiliriz. yönleri birleştirin. Yukarıda, yönler sistemi için eşleniklik koşulu formüle edildi S(k) , k = 1, 2, 3,…, R ≤ N, ve simetrik matris İLE emir N N. Belirtilen yönlerin oluşturulması ile keyfi ikinci dereceden bir fonksiyonun toplamın toplamı biçimine dönüştürülmesi arasında da bir bağlantı kuruldu.

1) Bu tür problemler örneğin regresyon analizinde ortaya çıkar - Not çeviri

kareler; her biri boyunca sıralı bir arama yapıldığı sonucuna varılmıştır. Nözelliği olan yönler İLE-eşlenik, ikinci dereceden fonksiyonun minimum noktasını bulmanızı sağlar N değişkenler. Yalnızca amaç fonksiyonunun değerlerini kullanarak bir eşlenik yön sistemi belirleme prosedürü dikkate alınır. Aşağıda, eşlenik yönleri elde etmek için ikinci dereceden yaklaşım kullanılmıştır. f(x) ve degrade bileşenlerinin değerleri. Ek olarak, söz konusu yöntemlerin yinelemeden yinelemeye geçerken amaç fonksiyonunun azalmasını sağlamasını isteyeceğiz.

Kontrollü değişkenler uzayında iki keyfi farklı nokta verilsin X(0) ve X(1) . İkinci dereceden fonksiyonun gradyanı

f(x) = q(x) =Cx + b = g(x) (3.60)

Formülün yazımında kolaylık sağlamak amacıyla g(x) gösterimi burada tanıtılmıştır. Böylece,

G(X (0)) = CX (0) + B,

G(X (1)) = CX (1) + B.

Bir noktadan hareket ederken eğimdeki değişimi yazalım X(0) noktaya X (1) :

g(x) = G(X (1)) -G(X (0)) = C(X (1) - X (0)), (3.61)

g(x) = C X

Eşitlik (3.61), aşağıda kullanılacak ikinci dereceden fonksiyonların bir özelliğini ifade etmektedir.

1952'de Estens ve Stiefel, doğrusal denklem sistemlerini çözmek için esasen eşlenik gradyan yöntemi olan etkili bir yinelemeli algoritma önerdiler. Doğrusal denklemlerin sol taraflarını ikinci dereceden bir fonksiyonun gradyanının bileşenleri olarak değerlendirdiler ve bu fonksiyonu en aza indirme problemini çözdüler. Daha sonra Fletcher ve Reeves, yöntemin ikinci dereceden yakınsamasını kanıtladılar ve bunu ikinci dereceden olmayan fonksiyonlar durumuna genelleştirdiler. Fried ve Metzler (bazı yanlışlıklarla birlikte) bu yöntemin seyrek katsayı matrisli doğrusal sistemleri çözmek için kullanılma olasılığını gösterdi. (Seyrek matrisin tanımı için Ek A'ya bakın.) Diğer, daha genel algoritmalarla karşılaştırıldığında yöntemin uygulanmasının kolaylığını vurguladılar; bu, sunumumuzun perspektifinden özellikle önemli bir özelliktir.

Yöntemi amaç fonksiyonunun ikinci dereceden olduğu varsayımı altında ele alacağız:

f(x) = q(x) = a + b T x + ½ x TCX,

yinelemeler formül (3.42)'ye göre gerçekleştirilir, yani.

x = x +α s(x).

Her yinelemedeki arama yönleri aşağıdaki formüller kullanılarak belirlenir:

S(k) = -G(k) + (3,62)

S (0) = -G (0) , (3.63)

Nerede G(k) = F(X). Yön sistemi belirlendikten sonra her bir yön boyunca sıralı bir arama gerçekleştirildiğinden, koşulun genellikle tek boyutlu bir aramayı sonlandırmak için bir kriter olarak kullanıldığını hatırlamakta fayda var.

F (X)T'ler(k) = 0 (3,64)

Değerler ,Ben= 1, 2, 3,...,k - 1 yönü öyle seçilmiştir ki S(k) idi İLE-önceden oluşturulmuş tüm arama yönleriyle bağlantılı. İlk yönü ele alalım

S (1) = –G(1) + γ (0) S (0) = –G(1) –γ (0) g (0)

ve onunla eşleniklik koşulunu dayatmak S (0)

S (1)T C s(0) = 0,

Neresi TC s(0) = 0.

İlk yinelemede

S (0) = ;

buradan,

TC = 0

İkinci dereceden fonksiyonların (3.61) özelliğini kullanarak şunu elde ederiz:

T G = 0, (3.65)

γ (0) = – ( g T g(1))/( g T g(0)). (3.66)

Denklem (3.65)'ten şu sonuç çıkar:

g (1) T g (1) + γ (0) g (0) T g (1) – g (1) T g(0) – γ (0) g (0) T g(0) = 0.

Uygun bir α (0) seçimiyle ve (3.64) formülünü dikkate alarak, şunu elde ederiz:

g (1) T g(0) = 0.

Böylece,

S (2) = –G(2) + γ (0) S(0) + γ (1) S (1) .

ve koşulların karşılanması için γ (0) γ (1)'i seçin

s(2) TC s(0) = 0 ve s(2) C s(1) = 0,

yani koşullar İLE- s (2) yönünün s (0) ve s (1) yönleriyle eşlenikliği. (3.61) ve (3.64) formüllerini kullanarak burada γ (0) = 0 ve genel durumda γ ( Ben) = 0, Ben = 0, 1, 2,...,k-2, herhangi bir değerde k. Bundan, arama yönlerine ilişkin genel formülün Fletcher ve Reeves tarafından önerilen biçimde yazılabileceği anlaşılmaktadır:

S ( k) = –G (k) + sn (3,68)

Eğer f(x)- ikinci dereceden fonksiyon, belirlemeniz gereken minimum noktayı bulmak için N-1 bu tür talimatlar ve yerine getirme N düz bir çizgi boyunca arama yapar (yuvarlama hataları olmadığında). Eğer fonksiyon f(x) ikinci dereceden değilse, yönlerin ve karşılık gelen aramaların sayısı artar.

Bazı araştırmacılar, hesaplamalı deneyler yapma deneyimine dayanarak, her bir serinin uygulanmasından sonra şunu önermektedir: N veya N+ 1 adım, algoritmanın ilk yinelemesine geri döner ve s(x) = -g(x). Bu öneri, bazı durumlarda genel biçim işlevlerinin en aza indirilmesi yakınsamada bir yavaşlamaya yol açtığından, bir çalışma konusu olmaya devam etmektedir. Öte yandan, başlangıç ​​iterasyonuna döngüsel geçişler, doğrusal bağımlı yönler oluşturma olasılığı azaldığı için algoritmanın güvenilirliğini artırır. Ortaya çıkan yönün önceden elde edilen bir veya daha fazla yönün doğrusal bir kombinasyonu olduğu ortaya çıkarsa, o zaman karşılık gelen altuzaydaki arama nedeniyle yöntem bir çözüme götürmeyebilir. RN zaten gerçekleştirildi. Ancak pratikte bu tür durumların oldukça nadir olduğunu belirtmek gerekir. Yöntemin pratik problemlerin çözümünde çok etkili olduğu ortaya çıkıyor; tek parametreli bir hesaplama şemasının basitliği ve arama için gereken az miktarda bilgisayar belleği ile karakterize ediliyor. Bilgisayar belleğine yönelik nispeten düşük düzeydeki gereksinimler, Fletcher-Reeves (FR) yöntemini ve onun modifikasyonlarını özellikle büyük ölçekli sorunların çözümünde yararlı kılar.

Örnek 3.9. Fletcher-Reeves yöntemi

Bir fonksiyonun minimum noktasını bulun

f(x) = 4x+ 3X - 4x x + x

Eğer x = T.

Adım 1. f(x) =T,

S (0) = – F(X (0)) = – T.

Adım 2. Düz bir çizgi boyunca arama yapın:

x = x –α F(X (0)) → α = ⅛,

x =T - ⅛ T = [– ⅛, 0]T

Adım 3. k = 1.

S (1) = – T -[¼, 1] T = [– ¼, ½] T.

Adım 4. Düz bir çizgi boyunca arama yapın:

x = x+ α S(1) → α = ¼,

x =[– ⅛, 0]T - ¼ [¼, ½] T = [– , ]T,

F(X (2)) = T.

Böylece, x = x*. Amaç fonksiyonunun ikinci dereceden olması ve yuvarlama hatasının olmaması nedeniyle tek boyutlu iki arama sonucunda çözüm elde edilmiştir.

Mil ve Cantrell aşağıdaki formülü önererek Fletcher ve Reeves'in yaklaşımını genelleştirdiler.

x = x +α {– F(X (k)) + γ S(X)} (3.69)

nerede α ve γ - değerleri her yinelemede belirlenen parametreler. olarak bilinen bu yöntem hafızalı gradyan yöntemi Sorunu çözmek için gereken yineleme sayısı açısından oldukça verimlidir ancak Fletcher-Reeves yöntemine göre fonksiyon değerleri ve gradyan bileşenlerinin daha fazla hesaplanmasını gerektirir. Bu nedenle Mil ve Cantrell algoritması yalnızca amaç fonksiyonu ve gradyan bileşenlerinin değerlerinin tahmin edilmesinin herhangi bir zorlukla ilişkili olmadığı durumlarda faydalıdır.

Fletcher-Reeves yönteminin dikkate alınmasının, amaç fonksiyonunun ikinci dereceden olduğu ve doğru boyunca arama sırasında herhangi bir yuvarlama hatası olmadığı varsayımı altında gerçekleştirildiğini hatırlayalım. Ancak bir takım yöntemler uygulanırken eşlenik yönler bu varsayımlardan biri (veya her ikisi) dikkate alınmadan belirlenir. Bu yöntemler arasında muhtemelen en fazla ilgiyi hak eden, Polzk ve Ribière tarafından 1969'da geliştirilen yöntemdir. Yöntem, bir doğru boyunca kesin bir arama prosedürüne ve amaç fonksiyonuna yaklaşıma ilişkin daha genel bir varsayıma dayanmaktadır. Aynı zamanda

γ = , (3.70)

daha önce olduğu gibi nerede

G(X)= g(X) -G(X). (3.71)

Eğer α - değeri düz bir çizgi boyunca yapılan arama sonucunda belirlenen bir parametre ve γ, değeri (3.70) formülü kullanılarak hesaplanan bir parametredir, o zaman Polak-Ribiera eşlenik gradyan yöntemi aşağıdaki ilişkiler kullanılarak uygulanır:

x = x +α S(X),

S(X) = – F (X) + γ S(X). (3.72)

Polak-Ribier ve Fletcher-Reeves yöntemleri arasındaki tek farkın γ parametresinin seçim yöntemlerinde yattığını görmek kolaydır.

Tek boyutlu bir arama sırasında kesin hesaplamaların yapılmasına ve amaç fonksiyonunun daha genel (ikinci dereceden) bir yaklaşımına dayanan başka benzer yöntemler de bilinmektedir (örneğin bkz.). 1972'de Crowder ve Wolf ve ardından Powell, eşlenik gradyan yöntemlerinin, ilk yinelemeye periyodik geri dönüş olmadığında doğrusal bir yakınsama oranına sahip olduğunu kanıtladılar. Bu geri dönüşler, arama yönü vektörlerinin oluşturulması sürecini kesintiye uğratan özel bir prosedür uyarınca gerçekleştirilir ve ardından hesaplamalar, yapıya benzetilerek devam eder. S(X(0)). Yukarıda, bir dizi nedenden dolayı, ilk yinelemeye geri dönme prosedürünün varlığının, arama yönlerinin doğrusal olarak bağımlı vektörlerinin oluşturulmasından kaçınılmasına izin vermesi nedeniyle algoritmanın kararlılığını arttırdığı belirtilmiştir. Powell, Polak-Ribière yönteminin aynı zamanda ilk yinelemeye geri dönüş olmadığında doğrusal yakınsama hızıyla karakterize edildiğini kanıtladı, ancak genel amaç fonksiyonlarıyla problemleri çözerken Fletcher-Reeves yöntemine göre şüphesiz bir avantaja sahip ve daha az duyarlı. Tek boyutlu aramalar yapılırken yuvarlama hataları.

İlk yinelemeye dönüşü sağlayan ve aynı zamanda yuvarlama hatalarına karşı duyarlılığı düşük olan etkili prosedür ve yöntemlerin geliştirilmesi aktif araştırma konusu olmaya devam etmektedir. Beal, standart Fletcher-Reeves prosedürüne benzer bir eşlenik gradyan yöntemi önerdi, ancak aynı zamanda ilk yinelemeye geri dönerken gradyan boyunca yönü kullanmadı. İlk yinelemeye dönmeden hemen önce elde edilen yönün analizine dayanarak, çoklu geri dönüş gerektiren problemleri çözerken gerekli hesaplama miktarını azaltmanın nasıl mümkün olduğunu gösterdi. Powell, Beal'in stratejisinin yanı sıra ilk yinelemeye geri dönmeye yönelik diğer stratejileri de inceledi ve her bir diziden sonra geri dönme prosedürünün kullanılmasını önerdi. N adımlar veya eşitsizlik karşılandığında

| G(X)Tg(X) | ≥ 0.2 ||G(X)|| . (3.73)

Koşul (3.73) ile desteklenen Beale stratejisinin hem Fletcher - Reeves formülü hem de Polak - Ribière formülü ile birlikte başarıyla uygulanabileceğini gösterdi ve sonuçları, formülün üstünlüğünü doğrulayan bir dizi hesaplamalı deney gerçekleştirdi. Polak - Ribière yöntemi (geri dönüşlü) . Shannault, çizgi aramalarındaki yuvarlama hatalarının ve çeşitli geri izleme stratejilerinin eşlenik gradyan yöntemlerinin performansı üzerindeki etkisini araştırdı. Powell'ın geri izleme koşuluyla desteklenen Beale stratejisinin (uygun iki parametreli formülü kullanarak), tek boyutlu bir aramanın gerekli doğruluğunda önemli bir azalmaya ve dolayısıyla tam aramanın verimliliğinde önemli bir artışa yol açtığını gösterdi. eşlenik gradyan yönteminin hesaplama şeması. Shannault ayrıca bir çizgi boyunca arama yaparken geri izleme ve yuvarlama prosedürlerini kullanan Polak-Ribière yönteminin üstünlüğünü gösteren sayısal sonuçlar da sundu. Çalışma, yüksek boyutlu doğrusal olmayan programlama problemlerinin çözümünde eşlenik gradyan yöntemlerinin öncü rolünü göstermektedir.

Yarı-Newton yöntemleri

Bu yöntemler alt bölümde tartışılan yöntemlere benzer. 3.3.5, çünkü bunlar aynı zamanda ikinci dereceden fonksiyonların özelliklerine de dayanmaktadır. Yukarıda özetlenen yöntemlere uygun olarak, çözüm arayışı eşlenik yönlerden oluşan bir sistem boyunca gerçekleştirilir; yarı-Newton yöntemleri ise Newton yönteminin olumlu özelliklerine sahiptir, ancak yalnızca ilk türevleri kullanır. Bu sınıfın tüm yöntemlerinde, arama yönü vektörlerinin oluşturulması formül (3.42) kullanılarak gerçekleştirilir; S(X(k)) şu şekilde yazılır:

S(X) = –A F (X), (3.74)

Nerede A- sipariş matrisi N N, buna denir Metrikler. Bu formülle belirlenen yönler boyunca arama yöntemlerine yöntem adı verilir. değişken metrik, A matrisi her yinelemede değiştiği için. Daha kesin olarak, değişken metrik yöntem şu şekildedir: yarı-Newtonian Yönteme uygun olarak deneme noktasının hareketi aşağıdaki koşulu karşılıyorsa:

x =C G. (3.75)

Ne yazık ki, uzmanlaşmış literatür yukarıdaki terimlerin kullanımına ilişkin tek tip ve kesin öneriler geliştirmemiştir; söz konusu yöntemlerin geliştirilmesi ve uygulanmasının özellikleri hakkında eşit derecede önemli bilgiler taşıdıkları için bunları birbirinin yerine kullanılabilir olarak değerlendireceğiz.

Matrisin Hessian matrisinin tersini hesaplamak için aşağıdaki yineleme ilişkisini kullanırız:

A = A+ A(3.76)

Nerede A- düzeltme matrisi. Matris A(3.74) ve (3.42) formüllerinde kullanılacaktır. Görev bir matris oluşturmaktır A böylece sıra A (0) , A (1) , A (2) ,...,A(k +1) şuna bir yaklaşım verdi: N -1 = F (X*) -1 ; bir çözüm elde etmek için X* aşağıdaki durumlarda düz bir çizgi boyunca ilave bir arama yapılması gerekir: f(x)- ikinci dereceden fonksiyon. Yukarıda defalarca vurgulandığı gibi, ikinci dereceden fonksiyonların optimumunu bulmayı sağlayan bir yöntemin, genel formdaki doğrusal olmayan amaç fonksiyonlarına sahip problemlerin çözümünde başarıya yol açabileceğine inanmak için belirli nedenler vardır.

İkinci dereceden fonksiyonların (3.75) önemli özelliğine dönelim ve matrisin İLE-1 formülle yaklaşıktır

İLE-1 = β A, (3.77)

burada p skaler bir miktardır. En çok tercih edilen yaklaşım (3.75)'i karşılayan yaklaşımdır;

X= A G. (3.78)

Ancak böyle bir yaklaşıklık oluşturmanın imkansız olduğu açıktır, çünkü bulmak için G, matrisi bilmeniz gerekir A. Burada aşağıdaki gösterimler kullanılmıştır:

X= X– X, (3.79)

G= G(X) – G(X). (3.80)

Öte yandan, yeni yaklaşımın (3.75) formülünü karşılaması da gerekebilir:

X= β A G. (3.81)

(3.76) ifadesini (3.81) yerine koyarsak, şunu elde ederiz:

A G= X– A G. (3.82)

Doğrudan ikameyi kullanarak matrisin olduğunu doğrulayabilirsiniz.

bir = – (3.83)

bu denklemin çözümüdür. Burada en Ve z- keyfi vektörler, yani formül (3.83) belirli bir çözüm ailesini tanımlar. Eğer koyarsan

sen = X Ve z =A G, (3.84)

daha sonra iyi bilinen ve yaygın olarak kullanılan formülü uygulayan bir formül elde ederiz. Davidon'un yöntemi- Fletcher- Powell'ın(DFP):

A= A + – . (3.85)

Bu yinelenen formülün matrislerin simetri ve pozitif kesinlik özelliklerini koruduğu gösterilebilir. Bu nedenle eğer A(0) simetrik pozitif tanımlı bir matristir, bu durumda matrisler A (1) , A(2) , ... ayrıca yuvarlama hatalarının yokluğunda simetrik ve pozitif tanımlı olduğu ortaya çıkar; genellikle seçmek uygundur A (0) = BEN.

İlk varyasyon f(x) eşit

f(x) = F (X) X. (3.86)

(3.42) ve (3.74) formüllerini kullanarak şunu elde ederiz:

f(x) = F (X) α A F (X), (3.87)

f(x) = – α F (X) A F (X), (3.88)

ve eşitsizlik F (x(k+1)) < F(xk) eğer α > 0'ın herhangi bir değeri için sağlanırsa A pozitif tanımlı bir matristir. Böylece algoritma yinelemeden yinelemeye geçerken amaç fonksiyonunun azalmasını sağlar. Davidon-Fletcher-Powell yöntemi birkaç yıldır en yaygın kullanılan gradyan yöntemi olmaya devam etti. Kararlıdır ve pratikte ortaya çıkan çok çeşitli problemlerin çözümünde başarıyla kullanılmaktadır. Bu tür yöntemlerin ana dezavantajı, matrisin bilgisayar belleğinde saklanması gerekliliğidir. A emir N N.

Yöntem, problemi (5.1) çözmek için tasarlanmıştır ve birinci dereceden yöntemler sınıfına aittir. Yöntem, en dik iniş (yükselme) yönteminin bir modifikasyonudur ve amaç fonksiyonunun özelliklerini otomatik olarak hesaba katarak yakınsamayı hızlandırır.

Algoritmanın açıklaması

Adım 0. İlk yaklaşma noktası seçilir, adım uzunluğu parametresi , çözüm doğruluğu ve ilk arama yönü hesaplanır.

Adım k. Açık k-. adımda amaç fonksiyonunun minimumu (maksimumu) yönündeki noktadan çizilen bir doğru üzerinde bulunur. Bulunan minimum (maksimum) nokta bir sonraki noktayı belirler k yaklaşıklık, bundan sonra arama yönü belirlenir

Formül (5.4) eşdeğer biçimde yeniden yazılabilir.

.

Algoritma, koşul sağlandığı anda çalışmasını tamamlar; Son elde edilen yaklaşımın değeri çözüm olarak alınır.

Newton'un yöntemi

Yöntem, problemi (5.1) çözmek için tasarlanmıştır ve ikinci dereceden yöntemler sınıfına aittir. Yöntem, hedef fonksiyonun Taylor açılımına ve ekstrem noktada fonksiyonun gradyanının sıfır olduğu gerçeğine dayanmaktadır.

Aslında, bir noktanın arzu edilen ekstremum noktasına yeterince yakın olmasına izin verin. düşünelim Ben amaç fonksiyonunun gradyanının gradyanının inci bileşenini elde edin ve onu Taylor formülünü kullanarak birinci dereceden türevlere kadar bir noktada genişletin:

. (5.5)

Aşağıdakileri dikkate alarak formül (5.5)'i matris biçiminde yeniden yazıyoruz: :

noktasında amaç fonksiyonunun Hessian matrisi nerede?

Hessian matrisinin tekil olmadığını varsayalım. O zaman ters bir matrisi var. Denklemin (5.6) her iki tarafını solla çarparak şunu elde ederiz:

. (5.7)

Formül (5.7) Newton yönteminin algoritmasını tanımlar: yaklaşımların yeniden hesaplanması k

Algoritma, koşul sağlandığı anda çalışmasını sonlandırır

,

çözümün verilen doğruluğu nerede; Son elde edilen yaklaşımın değeri çözüm olarak alınır.

Newton-Raphson yöntemi

Yöntem birinci dereceden bir yöntemdir ve sistemleri çözmeye yöneliktir. N doğrusal olmayan denklemler c N bilinmiyor:

Özellikle, problemin (5.1) amaç fonksiyonunun durağan noktaları aranırken, denklem sisteminin koşulundan çözülmesi gerektiğinde bu yöntem uygulanabilir.

Bu nokta (5.9) sisteminin bir çözümü olsun ve noktanın yakınında olsun. Taylor formülünü kullanarak fonksiyonu bir noktada genişletirsek, şunu elde ederiz:

nereden (koşula göre) şu şekildedir

, (5.11)

vektör fonksiyonunun Jacobian matrisi nerede. Jacobi matrisinin tekil olmadığını varsayalım. O zaman ters bir matrisi var. Denklemin (5.11) her iki tarafını solla çarparsak, şunu elde ederiz: , Neresi

. (5.12)

Formül (5.12), Newton-Raphson yönteminin algoritmasını tanımlar: yaklaşımların yeniden hesaplanması k iterasyon aşağıdaki formüle göre gerçekleştirilir

Tek değişkenli durumda sistem (5.9) tek bir denkleme dönüştüğünde formül (5.13) formunu alır.

, (5.14)

noktasındaki fonksiyonun türevinin değeri nerede?

Şek. Şekil 5.2, denklemin çözümünü ararken Newton-Raphson yönteminin uygulanmasının bir diyagramını göstermektedir.

Açıklama 5.1. Nümerik yöntemlerin yakınsaması, kural olarak, büyük ölçüde ilk yaklaşıma bağlıdır.

Açıklama 5.2. Newton ve Newton-Raphson yöntemleri büyük miktarda hesaplama gerektirir (her adımda Hessian ve Jacobi matrislerinin hesaplanması ve ters çevrilmesi gerekir).

Açıklama 5.3. Yöntemleri kullanırken, amaç fonksiyonunda (özellik) birçok ekstremin bulunma olasılığını hesaba katmak gerekir. çok modluluk).

EDEBİYAT

1. Afanasyev M.Yu., Suvorov B.P. Ekonomide Yöneylem Araştırması: Ders Kitabı. – M.: Moskova Devlet Üniversitesi İktisat Fakültesi, TEIS, 2003 – 312 s.

2. Bazara M, Shetty K. Doğrusal olmayan programlama. Teori ve algoritmalar: Çev. İngilizce'den – M.: Mir, 1982 – 583 s.

3. Berman G.N. Matematiksel analiz dersi için problemlerin toplanması: Üniversiteler için ders kitabı. – St. Petersburg: “Özel Edebiyat”, 1998. – 446 s.

4. Wagner G. Yöneylem Araştırmasının Temelleri: 3 cilt halinde. Başına. İngilizce'den – M.: Mir, 1972. – 336 s.

5. Ventzel E. C. Yöneylem araştırması. Amaçlar, ilkeler, metodoloji - M.: Nauka, 1988. - 208 s.

6. Demidovich B.P. Matematiksel analizle ilgili problemlerin ve alıştırmaların toplanması . – M.: Nauka, 1977. – 528 s.

7. Degtyarev Yu.I. Yöneylem Araştırması. – M.: Daha yüksek. okul, 1986. – 320 s.

8. Nureyev R.M. Mikroekonomide problemlerin toplanması. – M.: NORM, 2006. – 432 s.

9. Solodovnikov A.İLE., Babaytsev V.A., Brailov A.V.İktisatta Matematik: Ders Kitabı: 2 bölüm halinde - M.: Finans ve İstatistik, 1999. - 224 s.

10. Taha H. Yöneylem Araştırmasına Giriş, 6. baskı: Çev. İngilizce'den – M.: Williams Yayınevi, 2001. – 912 s.

11. Himmelblau D. Uygulamalı doğrusal olmayan programlama: Transl. İngilizce'den – M.: Mir, 1975 – 534 s.

12. Şikin E.İÇİNDE., Shikina G.E. Yöneylem Araştırması: Ders Kitabı - M.: TK Welby, Prospekt Yayınevi, 2006. - 280 s.

13. Ekonomide Yöneylem Araştırması: Ders Kitabı. üniversiteler için el kitabı / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Ed. prof. N.Ş. – M.: Bankalar ve borsalar, UNITY, 1997. – 407 s.

14. Matrisler ve vektörler: Ders Kitabı. ödenek / Ryumkin V.I. – Tomsk: TSU, 1999. – 40 s.

15. Doğrusal denklem sistemleri: Ders Kitabı. ödenek / Ryumkin V.I. – Tomsk: TSU, 2000. – 45 s.

Doğrusal ve doğrusal olmayan fonksiyonların tanımları için bölüm 1.2'ye bakın.