Alt gradyan yöntemi - Subgradient method - Wikipedia

Alt gradyan yöntemleri vardır yinelemeli yöntemler çözmek için dışbükey küçültme sorunlar. Başlangıçta tarafından geliştirilmiştir Naum Z. Shor ve diğerleri 1960'larda ve 1970'lerde, alt gradyan yöntemleri, türevlenemeyen nesnel bir işleve uygulandığında bile yakınsaktır. Amaç işlevi ayırt edilebilir olduğunda, kısıtlanmamış problemler için alt gradyan yöntemleri, yöntemle aynı arama yönünü kullanır. en dik iniş.

Alt gradyan yöntemleri, iki kez sürekli türevlenebilir dışbükey fonksiyonları en aza indirmek için uygulandığında Newton yönteminden daha yavaştır. Bununla birlikte, Newton'un yöntemi, türevlenemeyen sapmalara sahip problemlerde yakınsama konusunda başarısız olur.

Son yıllarda bazıları iç nokta yöntemleri konveks minimizasyon problemleri için önerilmiştir, ancak alt gradyan projeksiyon metotları ve ilgili grup iniş metotları rekabetçi kalır. Çok fazla boyuta sahip dışbükey minimizasyon problemleri için, alt gradyan-projeksiyon yöntemleri uygundur çünkü az depolama gerektirirler.

Alt gradyan projeksiyon yöntemleri genellikle ayrıştırma teknikleriyle büyük ölçekli problemlere uygulanır. Bu tür ayrıştırma yöntemleri genellikle bir problem için basit dağıtılmış bir yönteme izin verir.

Klasik alt gradyan kuralları

İzin Vermek ${ displaystyle f: mathbb {R} ^ {n} - mathbb {R}}$ olmak dışbükey işlev etki alanı ile ${ displaystyle mathbb {R} ^ {n}}$. Klasik bir alt gradyan yöntemi yinelenir

${ displaystyle x ^ {(k + 1)} = x ^ {(k)} - alpha _ {k} g ^ {(k)} }$

nerede ${ displaystyle g ^ {(k)}}$ gösterir hiç alt gradyan nın-nin ${ displaystyle f }$ -de ${ displaystyle x ^ {(k)} }$, ve ${ displaystyle x ^ {(k)}}$ ... ${ displaystyle k ^ {th}}$ yinelemesi ${ displaystyle x}$. Eğer ${ displaystyle f }$ türevlenebilir, bu durumda tek alt gradyanı gradyan vektörüdür ${ displaystyle nabla f}$ kendisi olabilir. ${ displaystyle -g ^ {(k)}}$ iniş yönü değil ${ displaystyle f }$ -de ${ displaystyle x ^ {(k)}}$. Bu nedenle bir liste tutuyoruz ${ displaystyle f _ { rm {en iyi}} }$ şu ana kadar bulunan en düşük amaç fonksiyon değerini takip eden, yani

${ displaystyle f _ { rm {en iyi}} ^ {(k)} = min {f _ { rm {en iyi}} ^ {(k-1)}, f (x ^ {(k)}) }.}$

Adım boyutu kuralları

Alt gradyan yöntemleri tarafından birçok farklı adım boyutu kuralı kullanılır. Bu makale, yakınsama için beş klasik adım boyutu kuralına dikkat çekiyor. kanıtlar biliniyor:

• Sabit adım boyutu, ${ displaystyle alpha _ {k} = alpha.}$
• Sabit adım uzunluğu, ${ displaystyle alpha _ {k} = gamma / lVert g ^ {(k)} rVert _ {2}}$hangi verir ${ displaystyle lVert x ^ {(k + 1)} - x ^ {(k)} rVert _ {2} = gamma.}$
• Kare şeklinde toplanabilir ancak toplanamayan adım boyutu, yani tatmin edici herhangi bir adım boyutu

${ displaystyle alpha _ {k} geq 0, qquad sum _ {k = 1} ^ { infty} alpha _ {k} ^ {2} < infty, qquad sum _ {k = 1} ^ { infty} alpha _ {k} = infty.}$

• Tüketilemeyen küçülme, yani tatmin edici herhangi bir adım boyutu

${ displaystyle alpha _ {k} geq 0, qquad lim _ {k ila infty} alpha _ {k} = 0, qquad sum _ {k = 1} ^ { infty} alfa _ {k} = infty.}$

• Saydam olmayan azalan adım uzunlukları, yani ${ displaystyle alpha _ {k} = gamma _ {k} / lVert g ^ {(k)} rVert _ {2}}$, nerede

${ displaystyle gamma _ {k} geq 0, qquad lim _ {k to infty} gamma _ {k} = 0, qquad sum _ {k = 1} ^ { infty} gama _ {k} = infty.}$

Beş kuralın tümü için, adım boyutları, yöntem yinelenmeden önce "çevrimdışı" olarak belirlenir; adım boyutları önceki yinelemelere bağlı değildir. Alt gradyan yöntemlerinin bu "çevrim dışı" özelliği, farklılaştırılabilir işlevler için alçalma yöntemlerinde kullanılan "çevrimiçi" adım boyutu kurallarından farklıdır: Farklılaştırılabilir işlevleri en aza indirmeye yönelik birçok yöntem, Wolfe'un yakınsama için yeterli koşullarını karşılar; geçerli nokta ve mevcut arama yönü. Bertsekas'ın kitaplarında artımlı sürümler de dahil olmak üzere alt gradyan yöntemleri için aşamalı boyut kurallarının kapsamlı bir tartışması verilmiştir.^[1]Bertsekas, Nedic ve Özdağlar. ^[2]

Yakınsama sonuçları

Sabit adım uzunluğu ve ölçeklendirilmiş alt gradyanlar için Öklid normu bire eşit olarak, alt gradyan yöntemi minimum değere keyfi olarak yakın bir yaklaşıma yakınsar, yani

${ displaystyle lim _ {k ile infty} f _ { rm {en iyi}} ^ {(k)} - f ^ {*} < epsilon}$ sonucu Shor.^[3]

Bu klasik alt gradyan yöntemlerinin performansı düşüktür ve artık genel kullanım için önerilmemektedir.^[4][5] Bununla birlikte, basit olmaları ve problemin özel yapısından yararlanmak için kolayca uyarlanabildikleri için özel uygulamalarda hala yaygın olarak kullanılmaktadırlar.

Alt gradyan-projeksiyon ve grup yöntemleri

1970'lerde, Claude Lemaréchal ve Phil Wolfe, dışbükey minimizasyon problemleri için iniş "demet yöntemleri" önermiştir.^[6] O zamandan beri "paket yöntemleri" teriminin anlamı önemli ölçüde değişti. Modern versiyonlar ve tam yakınsama analizi Kiwiel tarafından sağlandı.^[7] Çağdaş paket yöntemleri genellikle "seviye Boris T. Polyak'ın (1969) "alt gradyan-projeksiyon" yönteminden teknikler geliştirmek için "adım boyutlarını seçmek için kurallar" Ancak, demet yöntemlerinin alt gradyan projeksiyon yöntemlerine göre çok az avantaj sunduğu sorunlar vardır.^[4][5]

Kısıtlı optimizasyon

Öngörülen alt gradyan

Alt gradyan yönteminin bir uzantısı, öngörülen alt gradyan yöntemi, kısıtlı optimizasyon problemini çözen

küçültmek ${ displaystyle f (x) }$ tabi

${ mathcal {C}}} içinde { displaystyle x$

nerede ${ displaystyle { mathcal {C}}}$ bir dışbükey küme. Öngörülen alt gradyan yöntemi yinelemeyi kullanır

${ displaystyle x ^ {(k + 1)} = P sol (x ^ {(k)} - alfa _ {k} g ^ {(k)} sağ)}$

nerede ${ displaystyle P}$ projeksiyon ${ displaystyle { mathcal {C}}}$ ve ${ displaystyle g ^ {(k)}}$ herhangi bir alt gradyanı ${ displaystyle f }$ -de ${ displaystyle x ^ {(k)}.}$

Genel kısıtlamalar

Alt gradyan yöntemi, eşitsizlik kısıtlı problemi çözmek için genişletilebilir

küçültmek ${ displaystyle f_ {0} (x) }$ tabi

${ displaystyle f_ {i} (x) leq 0, quad i = 1, noktalar, m}$

nerede ${ displaystyle f_ {i}}$ dışbükeydir. Algoritma, kısıtsız durumla aynı formu alır

${ displaystyle x ^ {(k + 1)} = x ^ {(k)} - alpha _ {k} g ^ {(k)} }$

nerede ${ displaystyle alpha _ {k}> 0}$ adım boyutudur ve ${ displaystyle g ^ {(k)}}$ hedefin bir alt gradyanı veya sınırlama fonksiyonlarından biridir. ${ displaystyle x. }$ Al

${ displaystyle g ^ {(k)} = { başlar {durumlar} kısmi f_ {0} (x) & { text {if}} f_ {i} (x) leq 0 ; forall i = 1 dots m kısmi f_ {j} (x) & { text {bazıları için}} j { text {böyle}} f_ {j} (x)> 0 end {durumlar}}}$

nerede ${ displaystyle kısmi f}$ gösterir alt farklı nın-nin ${ displaystyle f }$. Mevcut nokta uygulanabilirse, algoritma nesnel bir alt gradyan kullanır; mevcut nokta uygulanabilir değilse, algoritma ihlal edilen herhangi bir kısıtlamanın bir alt gradyanı seçer.

Referanslar

daha fazla okuma

• Bertsekas, Dimitri P. (1999). Doğrusal Olmayan Programlama. Belmont, MA.: Athena Scientific. ISBN  1-886529-00-0.
• Bertsekas, Dimitri P .; Nedic, Angelia; Özdağlar, Asuman (2003). Konveks Analiz ve Optimizasyon (İkinci baskı). Belmont, MA.: Athena Scientific. ISBN  1-886529-45-0.
• Bertsekas, Dimitri P. (2015). Konveks Optimizasyon Algoritmaları. Belmont, MA.: Athena Scientific. ISBN  978-1-886529-28-1.
• Shor, Naum Z. (1985). Türevlenemeyen Fonksiyonlar İçin Minimizasyon Yöntemleri. Springer-Verlag. ISBN  0-387-12763-1.

• Ruszczyński, Andrzej (2006). Doğrusal Olmayan Optimizasyon. Princeton, NJ: Princeton University Press. sayfa xii + 454. ISBN  978-0691119151. BAY  2199043.

Dış bağlantılar

• EE364A ve EE364B, Stanford'un dışbükey optimizasyon kurs dizisi.