Kimya teknolojisinde en dik iniş yöntemi. En dik iniş yöntemiyle minimum işlev

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. 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[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])) . Bir fonksiyonun minimumu için gerekli koşul 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, 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) iyi şartlandırılmış. Özdeğerlerin l i olduğunu hatırlayın, 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.

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. Matematiksel analizlerden, 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 degrade yöntemi için farklı seçenekler elde edebilirsiniz. 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 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

x k } , k = 0,1,..., Öyle ki , k = 0,1,... . Sıra noktaları ( x k ) 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, oldukça basit bir fonksiyonun minimize edilmesi için veya oldukça karmaşık bir fonksiyonun ön yaklaşımı için kullanılabilir. 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 x k , 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 x k İ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 ( x k } , k = 0,1,..., Öyle ki , k = 0,1,... . Sıra noktaları ( x k ) 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, orijinal problemin çözümünün doğrusal programlama problemlerinin sıralı çözümüne indirgenmesi nedeniyle, doğrusal olmayan amaç fonksiyonunun, incelenen noktanın yakınındaki doğrusal bir fonksiyonla değiştirilmesinin temelidir.
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ı x k

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ı x k 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. Farklı iniş yöntemleri, iniş yönünü ve bu yöndeki adımın uzunluğunu seçme açısı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 optimizasyon yöntemleri, gerçek sorunları insan yardımı olmadan çözmeyi her zaman 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 sağlar.
Sayfa oluşturulma tarihi: 2017-07-02

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[k R ] anti-gradyan -[k] ) f'(x X[k bu noktada

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

ve k

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

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

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

|| -X[k 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 k+1]) = f(x f(x[ [k] –[k] )) < f(x[k] ) .

a k 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 bilgilerin 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. a k f"(x Her yinelemede en dik iniş yöntemini kullanırken adım boyutu f(x) fonksiyonun minimum koşulundan seçilir
f(x[k]iniş yönünde, yani[k])) = f(x[k] –ak f’(x[k])) .

– af"(x f(x) Bu durum, antigradyan boyunca hareketin, fonksiyonun değeri olduğu sürece meydana geldiği anlamına gelir. A azalır. Matematiksel açıdan bakıldığında, her yinelemede tek boyutlu minimizasyon probleminin şu şekilde çözülmesi gerekir:
J (A) = f(x[k]-af"(x[k])) .

işlevler

1. Başlangıç ​​noktasının koordinatlarını ayarlayın X.

2. Bu noktada X[k], k = En dik iniş yönteminin algoritması aşağıdaki gibidir. -X[k]) .

3. Adım boyutu belirlenir A 0, 1, 2, ... gradyan değerini hesaplar A k, tek boyutlu minimizasyonla (A) = f(x[k]-af"(x[k])).

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

işlevler j k+ 1]x ben [[k]= xi[k]), i = 1,..., s.

– a k f’ i (x

5. Sterasyon işleminin durdurulması koşulları kontrol edilir. Bunlar yerine getirilirse hesaplamalar durur. Aksi halde 1. adıma geçin. X[k Söz konusu yöntemde, noktadan hareketin yönü 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])) . D J (a)/da = 0. Bir fonksiyonun minimumu için gerekli koşul

Karmaşık bir fonksiyonun türevini hesapladıktan sonra, iniş yönleri vektörlerinin komşu noktalardaki diklik koşulunu elde ederiz: DJ[k+ 1]-X[k]) = 0.

Pirinç. 2.9. M En dik iniş yönteminin geometrik yorumu M 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

ve en azından N(x) ikinci türevler matrisinin özdeğerleri (Hessian matrisi) Ben =1, …, N birbirinden çok az farklılık gösterir, yani matris

iyi şartlandırılmış. Özdeğerlerin l i olduğunu hatırlayı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. oluk.(t/ay

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. X Pirinç. 2.10. Oluk fonksiyonu

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

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 fonksiyon değişkenlerinin sayısına eşittir.

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. N Tanım gereği iki X boyutlu vektör Ve en isminde konjuge matrise göre H matrise göre(veya -eşlenik), eğer skaler çarpım ise, (X Peki) = 0. Burada N - simetrik pozitif tanımlı boyut matrisi N X

P. 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.[k]) -f(x yönde[k], matrise göre P İniş yönü olarak seçim, İniş yönü olarak seçim, ..., İniş yönü olarak seçim[k-önceden bulunan yönlerle birleşin

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

Yol Tarifi k] = --X[k]) ] aşağıdaki formüller kullanılarak hesaplanır: yönde[k P[ k>= 1;

+b k-1 -l],’-eşlenik), eğer skaler çarpım ise) .

p = - k F yönde[k], İniş yönü olarak seçim[k b değerleri matrise göre-1 yönler olacak şekilde seçilir :

(yönde[k], -1] vardı[-eşlenik 1])= 0.

HP

,

k-

Sonuç olarak, ikinci dereceden fonksiyon için k f'(x yinelemeli minimizasyon süreci şu şekildedir[k]X[[k],

Nerede İniş yönü olarak seçim[k] - =x -eşlenik+ak p iniş yönü m adım; ve k-İle A adım boyutu.

fonksiyonun yani eşitsizliğin azalmasını sağlayacaktır k] + İkincisi, fonksiyonun minimum koşulundan seçilir[k]) = f(x[k] + f(x) [k]) .

hareket yönünde, yani tek boyutlu minimizasyon probleminin çözülmesi sonucunda:

a k r

ar Xİkinci dereceden bir fonksiyon için yönde = --X) .

Fletcher-Reeves eşlenik gradyan yönteminin algoritması aşağıdaki gibidir. -eşlenik 1. Bu noktada A hesaplanmış . 2. Açık X[k+ 1].

m adım, yukarıdaki formüller kullanılarak adım belirlenir f(x[k+1]) k -X[k+1]) .

ve dönem -X) 3. Değerler hesaplanır X[k Ve 4. Eğer= 0, sonra nokta yönde[k+1] fonksiyonun minimum noktasıdır

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

Sonuç olarak, ikinci dereceden fonksiyon için k f'(x = x[k]X[[k],

Yol Tarifi k] (p+[k])+ 1)Prosedür 1-4'ün tekrarı, değiştirme ile periyodik olarak tekrarlanır -eşlenik 1 yönde[k P[ k>= 1;

Açık X);

fonksiyonun yani eşitsizliğin azalmasını sağlayacaktır k] + +1] ve hesaplamalar belirli bir sayı olan 'da biter. Bu durumda yöntemin aşağıdaki modifikasyonu kullanılır:[k]) = f(x[k] = -f’(x[k];

.

B p = -f'( ak p p = -f'(+ap Burada BEN simetrik pozitif tanımlı boyut matrisi- birçok dizin:

= (0, n, 2 X p, maaş, ...) İniş yönü olarak seçim = , yani yöntem her seferinde güncellenir adımlar. X Eşlenik gradyan yönteminin geometrik anlamı aşağıdaki gibidir (Şekil 2.11). Belirli bir başlangıç ​​noktasından f"(x iniş yönünde gerçekleştirilir X fonksiyonun yönündeki minimum noktasıdır İniş yönü olarak seçim, O ] anti-gradyan -) vektöre dik İniş yönü olarak seçim. Daha sonra vektör bulunur İniş yönü olarak seçim , matrise göre- ile eşlenik İniş yönü olarak seçim. Daha sonra, fonksiyonun yön boyunca minimumunu buluyoruz. İniş yönü olarak seçim vesaire.

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 sürecin tekrarlanması gerekecek, yani. bunun için süreç her zaman uymaz simetrik pozitif tanımlı boyut matrisi- birçok dizin:

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ı 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, 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ç fonksiyonunun f(x) minimumunun 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

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.