Satır arama - Line search

İçinde optimizasyon, satır arama strateji iki temelden biridir yinelemeli bulmak için yaklaşımlar yerel minimum ${ displaystyle mathbf {x} ^ {*}}$ bir amaç fonksiyonu ${ displaystyle f: mathbb {R} ^ {n} - mathbb {R}}$. Diğer yaklaşım güven bölgesi.

Hat arama yaklaşımı önce bir iniş yönü hangi amaç fonksiyonu boyunca ${ displaystyle f}$ küçültülür ve ardından ne kadar uzağa gideceğini belirleyen bir adım boyutu hesaplar ${ displaystyle mathbf {x}}$ bu yönde hareket etmelidir. İniş yönü çeşitli yöntemlerle hesaplanabilir, örneğin dereceli alçalma veya yarı-Newton yöntemi. Adım boyutu tam olarak veya tam olarak belirlenemez.

Örnek kullanım

Aşağıda, 4. adımda bir satır araması kullanan örnek bir gradyan yöntemi verilmiştir.

1. Yineleme sayacını ayarla ${ displaystyle displaystyle k = 0}$ve ilk tahminde bulunun ${ displaystyle mathbf {x} _ {0}}$ minimum için
2. Tekrar et:
3. Hesapla a iniş yönü ${ displaystyle mathbf {p} _ {k}}$
4. Seç ${ displaystyle displaystyle alpha _ {k}}$ 'gevşek bir şekilde' küçültmek ${ displaystyle h ( alpha) = f ( mathbf {x} _ {k} + alpha mathbf {p} _ {k})}$ bitmiş ${ displaystyle alpha in mathbb {R} _ {+}}$
5. Güncelleme ${ displaystyle mathbf {x} _ {k + 1} = mathbf {x} _ {k} + alpha _ {k} mathbf {p} _ {k}}$, ve ${ textstyle k = k + 1}$
6. A kadar ${ displaystyle | nabla f ( mathbf {x} _ {k + 1}) |}$

Satır arama adımında (4), algoritma ya kesinlikle küçültmek h, çözerek ${ displaystyle h '( alpha _ {k}) = 0}$veya gevşekçeyeterli bir azalma isteyerek h. İlkine bir örnek eşlenik gradyan yöntemi. İkincisi, kesin olmayan satır araması olarak adlandırılır ve bir dizi yolla gerçekleştirilebilir, örneğin geri izleme satırı araması veya kullanarak Wolfe koşulları.

Diğer optimizasyon yöntemleri gibi, satır araması ile birleştirilebilir benzetimli tavlama bazılarının üzerinden atlamasına izin vermek yerel minimum.

Algoritmalar

Doğrudan arama yöntemleri

Bu yöntemde, önce minimum parantez içine alınmalıdır, böylece algoritma noktaları tanımlamalıdır x₁ ve x₂ öyle ki aranan asgari, aralarında yatıyor. Aralık daha sonra hesaplama yoluyla bölünür ${ displaystyle f (x)}$ iki iç noktada, x₃ ve x₄ve iki dış noktadan hangisinin bitişik olmadığını reddetmek x₃ ve x₄ en düşük fonksiyon değerine sahip. Sonraki adımlarda, yalnızca bir ekstra dahili noktanın hesaplanması gerekir. Aralığı bölmenin çeşitli yöntemlerinden,^[1] altın bölüm araması aramanın nasıl ilerlediğine bakılmaksızın aralık oranları korunduğu için özellikle basit ve etkilidir:

${ displaystyle { frac {1} { varphi}} (x_ {2} -x_ {1}) = x_ {4} -x_ {1} = x_ {2} -x_ {3} = varphi (x_ {2} -x_ {4}) = varphi (x_ {3} -x_ {1}) = varphi ^ {2} (x_ {4} -x_ {3})}$

nerede

${ displaystyle varphi = { frac {1} {2}} (1 + { sqrt {5}}) yaklaşık 1,618}$

Ayrıca bakınız

• Altın bölüm araması
• Izgara araması
• Öğrenme oranı
• Kalıp arama (optimizasyon)
• Sekant yöntemi

Referanslar

daha fazla okuma

• Dennis, J. E., Jr.; Schnabel, Robert B. (1983). "Newton Metodunun Küresel Yakınsak Değişiklikleri". Kısıtsız Optimizasyon ve Doğrusal Olmayan Denklemler için Sayısal Yöntemler. Englewood Kayalıkları: Prentice-Hall. sayfa 111–154. ISBN  0-13-627216-9.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Satır Arama Yöntemleri". Sayısal Optimizasyon. New York: Springer. sayfa 34–63. ISBN  0-387-98793-2.
• Sun, Wenyu; Yuan, Ya-Xiang (2006). "Satır Arama". Optimizasyon Teorisi ve Yöntemleri: Doğrusal Olmayan Programlama. New York: Springer. s. 71–117. ISBN  0-387-24975-3.