Quadratic Approximation ile Local Ekstremum Noktalarının Hesaplanması
En iyileme, en uygun duruma getirme anlamı taşıyan optimizasyon, gerçek hayat senaryoları ile oldukça ilişikli ve genellikle maksimizasyon ve minimizasyon amacı barındıran yöntemler bütünüdür diyebiliriz. Bu bağlamda küçük ölçekli sistemlerden büyük yazılımlara kadar bir şeylerin -ki bu yazı kontekstinde fonksiyonlar olacak- en küçük, en büyük ya da olabildiğince küçük ve büyük değerlerine erişmeyi amaçladığımız farkındalığına erişebiliriz. Bu bir isteğe verilen yanıtın süresini minimize etmek de olabilir, bir alana yerleştirilecek eşyaların belirli kısıtlara tabi tutularak tasarlanması da olabilir. Bir başka deyişle optimizasyon işlemleri global maksimum ve minimumun bulunmasını amaçlayabileceği gibi belirli kısıt/aralıklar içerisindeki maksima ve minimalara ulaşmayı da amaçlayabilir. Bunlar yerel/lokal maksimum ve minimum olarak da adlandırılır. Ben de bu yazıda yerel maksimum ve minimum noktalarının bulunması amacıyla tasarlanmış yöntemlerden biri olan quadratic approximation metodundan bahsedeceğim.
Kuadratik Yaklaşım
Quadratic approximation dilimiz karşılığıyla kuadratik yaklaşım bir fonksiyonun yerel maksimum ya da minimum değerlerinin bulunması için 2. dereceden polinom üretilmesine dayanan bir yöntemdir. Yöntemin çözüm yoluna çağrışım yapması açısından yöntemi yazının devamında 2. dereceden polinom yaklaşımı olarak adlandıracağım.
Neden 2. dereceden bir polinom?
Karmaşık bir fonksiyon ile çalışmaktansa en küçük dereceli polinom ile çalışmak her zaman ilk tercihtir. Çeşitli matematiksel metodlarla fonksiyonlarımızı farklı dereceli fonksiyonlara yakınsayabilme olanağına sahibiz. O halde bu durumda fonksiyonlarımızı 2. dereceden bir polinoma dönüştürmek oldukça mantıklı olacaktır.
En küçük dereceli polinom ifade ile çalışmak istiyorsak neden 1. dereceden bir polinom ifade üretmiyoruz diye düşünürseniz bunun sebebi çok basit. 1. dereceden bir polinom doğrusal fonksiyonu ifade eder. Dolayısıyla yerel ekstremum noktaya sahip olamaz. Yerel ekstremum noktaya sahip olabilecek en küçük dereceli polinom 2. dereceden bir polinomdur.
Şunu biliyoruz ki bir x noktası yerel maksimum iken:
f(x) > f(x-1) ve f(x) ≥ f(x+1) koşullarının aynı anda sağlanması gerekir.
Bir yerel minimum için ise bu koşullar:
f(x) < f(x-1)ve f(x) < f(x+1) şeklindedir.
Bu bilgiler algoritmamızı oluştururken yol gösterecek.
2. dereceden polinom yöntemi adından da anlaşılacağı üzere fonksiyonu, 2. dereceden yaklaşık bir polinom ile ifade etmeye dayalı bir yöntemdir. Bu sebeple ana durumlarımızdan biri de 2. dereceden bir polinom üretmektir. Peki 2. dereceden bir polinomu nasıl elde ederiz?
2. Dereceden Polinom İfade Elde Etme
2. dereceden polinom ifade üretmek için eğer fonksiyonun türevinin değerlerine sahipsek Taylor serisinden faydalanabiliriz fakat biz türevlere sahip olmadığımız ve ekstra olarak türev değerlerini hesaplamak istemediğimiz için Lagrange Interpolasyon Polinomundan faydalanabiliriz.
Buradan rahatlıkla görebiliriz ki lagrange interpolasyon polinomunda n-1. dereceli bir polinom elde edebilmek için n adet noktaya ihtiyacımız var. Bu sebeple 2. dereceden bir polinom için fonksiyonun anlık olarak 3 noktasına ihtiyaç duyarız. Bilinen 3 nokta ile üretilen 2. dereceden polinomun ifadesi:
Evet şimdi fonksiyonumuzun z* noktasında bir yerel maksimum değerinin olduğunu varsayalım. Bu z* noktasındaki değeri yukarıdaki formülümüzün notasyonunda elde edelim.
Yalınlaştırmak adına
dersek ifademiz şuna dönüşecektir:
Şimdi ifadeyi dağıtalım:
Az önce z* noktamızı varsayımsal olarak yerel maksimum kabul etmiştik o halde bu z* noktasında fonksiyonun türevi 0 olmalıdır. Fonksiyonumuzun türevini hesaplayacak olursak:
f`(z)=0 bilgisinden faydalanarak yukarıdaki türev fonksiyonunu 0'a eşitleyip z’yi yalnız bıraktığımızda
eşitliğini elde etmiş oluruz. İfadede F’leri yerine koyup dağıtırsak z* artık daha yalın bir şekilde
eşitliğiyle temsil edilebilir. Artık fonksiyonumuzu 2. dereceden bir polinomla ifade ederek yeni tahmini yerel maksimum noktamızın nasıl hesaplayacağımız bilgisine erişmiş olduk. Bu yeni kök hesabını yazının başında anlattığım koşullarla harmanlayarak algoritmamızı nasıl işleteceğimize geçebiliriz.
Kuadratik Yaklaşım Algoritması:
Yukarıda bir sonraki tahmini yerel maksimum noktamızın nasıl hesaplanacağına dair bir çıkarım yapmıştık. Sırada ekstremum noktalardaki karşılaştırmaları kullanmak var.
Bu yerel ekstremum noktaları tahmini bir aralık içinde aradığımızı varsayalım. (Burada için paranteze alma metodunun ön bilgisi kullanılır.)
Bu aralığın ilk değeri z1, son değeri z3 olsun. Sonuçta ekstremum noktamız aralık içerisinde olacağından bu sıralama z1, z*, z3 olur.
f(z*) = f*, f(z1) = f1, f(z2) = f2 için:
Yerel maksimumda f* > f1 ve f* > f3;
Yerel minimumda f* < f1 ve f* < f3 olduğunu biliyoruz.
Peki bizim z2 noktamız nerede? Öyle ki biz iteratif olarak kullanacağımız noktaları rassal olarak seçmiyoruz. Bunun için her iterasyonda belirli adım uzaklığı ötemizdeki noktamızı z2 olarak seçiyoruz. Bu adım uzunluğumuz ilk iterasyon için h olsun. Bu durumda z2 = z1 + h olarak bulunur. (Burada z3 de z2 + 2h olarak hesaplanır. Bunun için de yine paranteze alma metodundaki ön bilgiden faydalanıyoruz. Bu konu hakkında yazarsam referans link ekleyeceğim. Aslında tamamen adım uzunluğunun 2'ye katlanmasına bağlı bir değişimdir. Örneğin z4 = z3 +4h olarak bulunur. Yani kendisinden bir önceki noktadan adım uzunluğunu 2'ye katlar şekilde uzaklaşır.)
Evet çok güzel şimdi elimizde tüm bilgiler var. z2'yi de bulduk. z*‘nin z1 ve z3 arasında olduğunu da biliyoruz keza z2 de öyle. E peki z2 ve z* arasındaki sıralama nasıl? İşte algoritmamız bunun kararını vermeye dayalı aslında.
Ben yazı kapsamında yerel maksimum noktasının bulunmasından bahsedeceğim. Elimizde başlangıçta z1, z2, z3 noktaları var. Başlangıç için bizim en iyi noktamız varsayımsal olarak z2 olsun. Çıkardığımız formül ile tahmini yerel ekstremum noktamızı hesapladık. Eğer bizim z* değerimiz z2'den daha büyükse o halde bizim yeni en iyi/maksimum noktamız z* olmalı. z2 = z* atamasından sonra sonuçta z2 değerimiz değiştiğine göre bu yeni noktaya ait z1 ve z3 noktaları da hesaplanmalı. Yukarıda z1 ve z3'ü nasıl hesaplayacağımızdan bahsetmiştim.
z1 = z2 — h
z3= z2 +h
Artık bir adım ileri gittik. Peki bundan sonraki iterasyonlarda aynı adım uzunluğunu mu kullanacağız? Tabii ki hayır, sonuçta biz her iterasyonda yerel maksimumu aradığımız aralığı daraltıyoruz. (Bu daralmayı aşağıda oldukça profesyonel şekilde hazırladığım görselde gösterdim. Denedim en azından…)
Dolayısıyla her iterasyonda h değerimizi de küçültmemiz gerekir. Bu küçülme oranı ile h 1/4*(z3-z1) kadardır. (Aksi halde zaten z2'nin aynı kalması durumunda sonsuz döngü oluşur.)
Bu bilgiler ışığında z2, z* karşılaştırmasını, bunların yer değiştirmesini, yeni noktaların hesaplanmasını ve adım uzunluklarının küçültülmesini iteratif olarak gerçekleştirdiğimizde artık yerel maksimum noktamıza erişmiş oluruz.
Özetle:
Adım 1) Başlangıç değerlerini hesapla.
Adım 2) En iyi noktayı z2 seç.
Adım 3) Tahmini z* hesapla ve z2 ile karşılaştır.
Adım 4) Eğer z* > z2 ise yeni en iyi noktayı z* olarak belirle.
Adım 5) Sonlanma kriteri sağlanıyorsa dur.
Adım 5) Yeni z2 değeri mevcutsa bu değer üzerinden yeni z1 ve z3 değerlerini hesapla.
Adım 6) Adım uzunluğunu küçült.
Adım 7) Adım 3'e dön.
Peki algoritmamızı ne zaman sonlandıracağız?
Bu soruya verilebilecek en ilkel yöntem iterasyon limitidir. Iterasyon sayısı bir algoritmanın sonlandırılması için bir kriter olabilir. Iterasyonumuzu sınırlamanın yanı sıra daha sağlıklı olarak şunu da yapabiliriz.
Biz burada yeni nokta ve nokta değerleri elde ettiğimizden bu hesaplamalardaki değişimden faydalanabiliriz. Bir başka deyişle önceki hesapladığımız noktadaki fonksiyon değeri ile mevcut hesapladığımız yeni noktadaki fonksiyon değeri artık çok farklı değilse bu bir sonlandırma kriteri olabilir. Bu değişimin gözlemlenmesi için bağıl hatanın hesaplanmasından faydalanabiliriz. Evet ne dedik z2 ve z* arasındaki değişimi izleyebiliriz.
Bir başka yöntem olarak da kullandığımız aralıktan faydalanabiliriz. Yukarıda yerel maksimum noktamızın (z1,z3) aralığından olduğundan bahsetmiştim. Bu durumda aralık boyutumuz belirli bir değerden daha küçük olduğunda yine programı sonlandırabiliriz.
Kodlama
Algoritmanın kodlarına buradan erişebilirsiniz. Kodları denemek isteyenler için birkaç farklı fonksiyon değeri ve çözüm için verilebilecek örnek parametre değerleri ekledim, istenen fonksiyonu yorum satırından çıkarıp deneyebilirsiniz. Fonksiyonun yerel maksimum noktasının, verilen parametreler aracılığıyla hesaplanan aralıkta olması durumu dikkat edilmesi gereken bir husustur.
Kaynak: “Studies in Optimization” by D. M. Burley
