Bir bilgisayar mühendisi için programlama dili, öğrendiklerini sınadığı, deneyler yaptığı bir laboratuardır ve mühendisler deneylerini, kestiremedikleri sonuçları gözlemlemek için değil, öngördükleri sonuçları doğrulamak için yapar...

Lagrange Çarpanları

Bizi tercih eden her öğrenciye tablet veriyoruz.
www.iste.edu.tr
Lagrange çarpanları yöntemi, yöntemle ilgili detaylar ve matlab kod örneği.

Lagrange çarpanlarına ilk olarak temel bileşenler analizinde rastlamıştım ama bu bir optimizasyon tekniği olduğu için pek çok yöntemin temelinde bu yönteme rastlamak mümkün. Temel bileşenler analizinde özdeğer ayrışımına neden ihtiyaç duyulduğu meselesini kurcalayınca, özvektörlerin boylarının sınırlandırılması için Lagrange çarpanları metodunun kullanıdığına tanık olursunuz. Başka bir yazıda yöntemin temel bileşenler analizinde nasıl kullanıldığını derinlemesine işleriz, ama şimdi asıl konumuza odaklanalım.

Bu yazıyı okumadan önce gradyan ile ilgili olan şuradaki yazıya göz atmanız faydalı olabilir.

Problem

Hayal etmesi kolay olsun diye önce 2 değişkenli fonksiyonlarla 3 boyutlu uzayda çalışıp daha sonra çok değişkenli fonksiyonlar için bir genelleme yapacağız. Elimizde bir f(x,y) fonksiyonu olsun ve bu fonksiyonun ekstremum (maksimum veya minimum) noktalarını bulmaya çalışıyor olalım. Bunun için farklı farklı yöntemler kullanılabilir ama yukarıda bağlantısını verdiğim yazıyı okuduysanız aklınıza hemen gradyan iniş metodunun da gelmiş olması gerekiyor. Şimdi problemimize g(x,y)=c şeklinde (c sabit herhangi bir sayı) bir kısıtlama koyalım. Bunun anlamı şu; kısıt olmasaydı direkt f'yi minimum veya maksimum yapacak değerleri arardık. Ama şimdi artık g(x,y)=c'yi sağlayan (x,y) değerleri f'ye yazıldığında alınabilecek en düşük ve en yüksek değerleri ve bu değerlerin alınmasını sağlayacak (x,y) noktalarını arıyoruz.

Lagrange'in o an tam olarak hangi problemi çözmeye çalıştığını bilemiyorum ama bu tip problemler için güzel bir çözüm yöntemi ortaya koymuş. Kavramlar genelde soyut olduğu için yöntemin temelindeki fikri somutlaştırmaya çalışacağım. f(x,y) 3 boyutlu uzayda bir yüzey denklemi. Bu denklem bir dağın yüzeyini temsil ediyor olsun. Kısıt denklemimiz olan g(x,y)=c ise bir eğri. Bu da, eğri dağ yüzeyine düşürüldüğünde, dağın yüzeyindeki bir patikayı temsil etsin. Bu durumda problemimiz de şu hale geliyor; bu patikanın dağ yüzeyi üzerindeki en alçak veya en yüksek noktalarını nasıl buluruz? Patikada ilerlerken bastığımız herhangi bir noktanın o civardaki en yüksek veya en alçak nokta olup olmadığı nasıl anlarız? Aslında çözümün sözel ifadesi oldukça basit; yürüdüğümüz esnada eğer yükseklik artarken azalmaya başladıysa veya azalırken artmaya başladıysa o nokta, patikanın dışınan çıkılmadan gidilebilecek o civardaki en yüksek veya en alçak noktalardan, yani yerel ekstremum noktalardan biridir. Şimdi bu basit fikri, dağ örneğini göz önünde bulundurarak matematiğe dökelim.

Yöntemin Temelindeki Fikir

Yukarıda bahsettiğimiz g=c eğrisi, g yüzeyinin seviye eğrilerinden biridir. g yüzeyinin gradyanı seviye eğrilerine dik olduğu için g=c eğrisine de eğri üzerindeki her noktada diktir. Yani gradyanın, eğri üzerinde yapılabilecek hareketler yönünde bir bileşeni yoktur ve bu da eğri üzerinde ilerlenirken g yüzey fonksiyonunun değerinin sabit kaldığı anlamına gelir (zaten =c demişiz). Bunları sadece bilgilerimizi tazelemek için yazdım, bizi ilgilendiren asıl mesele, g=c eğrisi üzerinde ilerlerken f'nin nasıl değiştiği. g=c eğrisi üzerinde ilerlerken f'de bir ekstremum noktaya vardığımızı anlamak için f'nin artarkan azalmaya veya azalırken artmaya başladığını gözlememiz gerektiğini söylemiştik. Dolayısıyla g=c eğrisi üzerindeki bir noktanın f'nin g=c kısıtlı bir ekstremumu olabilmesi için bu noktada eğri üzerinde yapılacak sonsuz küçüklükteki bir hareket f'nin değişmesine neden olmamalı. Yani f'nin en büyük artışı göstermesi için takip edilecek yönü gösterdiğini bildiğimiz gradyanın, g=c eğrisinde hareket edilebilecek doğrultu yönünde bir bileşeninin olmaması gerekir. Eğri ile kısıtlı f'nin bir ekstremum noktasında iken yalnızca eğrinin bu noktadaki teğeti doğrultusunda hareket edilebileceği için f'nin gradyanı bu teğete diktir. Zaten g'nin gradyanı g=c eğrisine ve dolayısıyla bu eğrinin teğetine dik olduğundan f'nin gradyanı ile g'nin gradyanı aynı doğrultuda olmalıdır. Böylelikle problemimizin çözümü için gerekli ipucunu yakaldık; g=c kısıtı ile f'nin ekstremum noktalarında f ve g'nin gradyanları o noktalardaki seviye eğrilerine değen ortak teğete dik olacak şekilde aynı doğrultuda uzanmalı.

Gradyanların aynı doğrultuda olduğunu anladık. Peki ama gradyanların yönleri ve büyüklükleri aynı olmak zorunda mı? Tabi ki hayır. Gradyanın, fonksiyonun en çok artış gösterdiği yönü gösterirdiğini ve gradyanın büyüklüğünün artış miktarını verdiğini biliyoruz. g azalırken aradığımız extremumlardan birine yaklaştığımızda f artıyor olabilir ve bunun tersi de mümkün. O zaman f'nin gradyanı g'ninki ile aynı yönde olmak zorunda değil. g'nin artış miktarı f'ninkine eşit olmak zorunda da değil. Normalde yön ve büyüklükler aynı olsaydı direkt gradyanları birbirlerine eşitleyebilirdik. Ama bu durumda gradyanlardan birinin boyunu kısan veya arttıran ve aynı zamanda yönler zıtsa bunuda ifade edebilecek bir çarpan ekleyerek eşitlik sağlayabiliriz. İşte bu çarpanı mucidinin adıyla anıyoruz; "Lagrange çarpanı".

Lagrange çarpanı ile gradyanların eşitliğinin sağlanması

İfadelerin tümünü eşitliğin soluna alıp gradyanları açarsak:

Lagrange çarpanları yönemi, Gradyanlar aldıktan sonra elde edilen ifade

Bu aşamada x, y ve Lagrange çarpanımız λ (lamda) olmak üzere 3 bilinmeyenimiz var. Gradyanların farkından elde edeceğimiz 2 denklem ile birlikte elimizde kısıtın denklemi de bulunduğundan, 3 tane de denklemimiz var:

Lagrange çarpanları yönemi, üç bilinmeyenli üç denklem

Artık aradığımız noktalara ulaşmak için yapmamız gereken tek şey 3 bilinmeyenli bu 3 denklemi kullanarak bilinmeyenleri çözmek.

Matematikçileri bilirsiniz; temiz çalışırlar ve genellemeleri severler. Dağınıklığı toparlamak adına bu denklemleri tek bir fonksiyon ile temsil etmek hoş olurdu. Bunu nasıl yapabiliriz, ona bir bakalım.

Neyin gradyanı bu üç denklemi verecek?

Öyle bir fonksiyon yazalım ki gradyanını hesapladığımızda, elimizdeki bu 3 ifade gradyanın bileşenleri olsun. Böylece yazacağımız fonksiyonun gradyanını sıfıra eşitlediğimizde aslında baştaki kısıtlı optimizasyon problemini çözmüş olalım.

Lagrange fonksiyonu

İşte bu da, gradyanının bileşenleri o 3 ifadeye eşit olan Lagrange fonksiyonu. Böylelikle kısıtlı bir fonksiyon optimizasyon problemini kısıtsız hale getirmiş oluyoruz. Kısıt fonksiyonunun, c solda kalacak şekilde kapalı halde (g(x,y)=0 şeklinde) verildiğini farzedersek daha sade bir ifade yazabiliriz:

Kısıt kapalı şekilde ifade edilmişse lagrange fonksiyonu

Başka kaynaklarda Lagrange çarpanının önündeki - yerine + görebilirsiniz. Bu işaretin hiçbir önemi yok. - yerine + yazarsanız, işaret - iken çözüm olarak bulacağınız λ değerlerini bu sefer - ile çarpılmış halde bulacaksınız. Zaten asıl ilgilendiğimiz değişken λ olmadığı için onun değerinin bir önemi de yok. Yukarıda da söylediğimiz gibi bu değişkenin tek görevi g'nin gradyanın boyunu ve yönünü ayarlayarak f'ninkine eşitlemek.

Birden Çok Kısıt Fonksiyonu ve Daha Çok Değişken

Birden çok kısıt fonksiyonumuz varken önce tek bir kısıtı kullanarak Lagrange fonksiyonunu yazdığımızı düşünelim. Sonra yazdığımız fonksiyondan, başka bir Lagrange çarpanı ile çarptığımız ikinci kısıt fonksiyonunu çıkararak ikinci Lagrange fonksiyonumuzu yazalım ve bunu tüm kısıt fonksiyonlarını kullanana kadar tekrar edelim. Tamamen aynı mantıkla, en son elde edeceğimiz Lagrange fonksiyonunun gradyanını sıfıra eşitleyereyerek yine çözüme ulaşabiliyoruz. Özetle, eğer birden çok kısıtımız varsa, her kısıtı başka bir çarpanla çarpıp minimum veya maksimum noktalarına ulaşmaya çalıştığımız fonksiyondan çıkararak Lagrange fonksiyonumuzu elde edebiliyoruz.

Bir yandan okurken, bir yandan da okuduklarımızı gözümüzde canlandırabilmek için şimdiye kadar işlemlerimizi hep 3 boyutlu uzaydaki bir yüzey fonksiyonu üzerinde gösterdik. Tabi ki yazdığımız herşey daha çok değişkeni olan fonksiyonlar için de geçerli. O zaman yöntemin daha genel ifadesini n tane değişken ve m tane kısıt için yazalım:

Lagrange fonksiyonunun en genel ifadesi

Bu fonksiyonun gradyanını hesapladığımızda, kısıtların gradyanlarının farklı λ değerleri ile çarpımlarının toplamının başta anlattığımız mantığa uygun olarak f'nin gradyanı ile aynı doğrultuda olduğunu farketmişsinizdir.

Lagrange Fonksiyonu ve Gradyan İniş

Aklınıza geldiyse vazgeçin, çünkü Lagrange fonksiyonunu gradyan iniş ile optimize etmek mümkün değil. Bulduğumuz çözümler her zaman Lagrange fonksiyonunun eyer noktalarına denk gelir. (Fonksiyonların durağan olduğu ama minimum ya da maksimum olmadığı noktalara eyer noktaları deniyor. Bu noktalarda fonksiyon genelde bir doğrultuda artarken azalmaya başlar ama başka bir doğrultuda da azalırken artmaya başlar ve fonksiyonun grafiği eyere benzer.) Gradyan iniş/çıkış ve benzer metotlar yerel minimum/maksimum noktaları bulmaya odaklandığından, Lagrange fonksiyonu üzerinde aradığımız noktaları bulmamızı sağlayamaz.

Yine de Lagrange fonksiyonunu bu tür yöntemlerle çözülebilecek hale getirmek mümkün. Eğer çözümleri, fonksiyonun gradyanının boyu (bileşenlerin karelerinin toplamının karekökü) üzerinde ararsak, vektörün boyu en az 0 olabileceği için çözümler, gradyanın boyunun yerel minimumlarına denk gelir. Hatta karekök ile uğraşmamak için karekök gözardı edilip boyun karesi üzerinden de çözüme gidilebilir. Böylece gradyan iniş veya benzer yöntemler ile çözüm elde edilebilir. Ancak karelerin toplamı karmaşık denklemlerde işi biraz daha zorlaştırabilir. Ayrıca çözüm için izlenecek yol biraz dolambaçlı bir hale geliyor. Şöyle ki; f foksiyonunun g kısıtlı yerel minimum noktasını bulmak için, f ve g ile elde ettiğimiz Lagrange fonksiyonunun gradyanının boyunun karesinin minimum noktasına, gradyan iniş metodu ile ulaşmamız gerekiyor.

Örnek

Şimdi yukarıda edindiğimiz teorik bilgileri bir örnek çözerek pekiştirelim ve işlemleri grafiklere döküp yöntemin mantığını doğru anladığımızdan emin olalım.

%---------------------------------
% Lagrange Çarpanları Matlab Kod Örneği
% Hüseyin Atasoy
% www.atasoyweb.net
% Nisan 2015
%---------------------------------

syms f g x y lc; % Kullanacağımız semboller
f=-(x^2+y^2+10); % Ekstremumlarını aradığımız fonksiyon. Yazıdaki örnekte dağ yüzeyimiz
g=x^2-3*y-16; % Kısıt fonksiyonumuz. Yazıdaki örnekte patikamız
%(İlla ki g=c formatında göstermek istersek c=16: g=x^2*y=16)

L=f-lc*g; % Tek kısıtlı Lagrange fonksiyonumuz (lc: Lagrange çarpanı)
gradyan=[diff(L,x), diff(L,y), diff(L,lc)]; % Lagrange fonksiyonumuzun gradyanı
cozumler=solve(gradyan); % 3 bilinmeyenli 3 denklemi çözdürüyoruz.

% Aslında işimiz bitti, çözümler elimizde. Ama şimdi yaptıklarımızı
% grafiklere dökelim.

cizimAraligi=[-10 10];
fig=figure;hold on;
set(fig,'defaultLineLineWidth',2);
axis equal;

% Önce 2 boyutlu düzlemde f'nin seviye eğrilerini ve g'yi çizelim.
ezcontour(f,cizimAraligi);
h=ezplot(g,cizimAraligi);
set(h,'Color','r');

% Çözümleri ekrana verip grafik üzerinde de işaretleyelim.
fprintf('Çözüm sayısı: %i\n',size(cozumler.lc,1));
for i=1:size(cozumler.lc,1)
    fprintf('x%i y%i lc%i: %f\t%f\t%f\n',i,i,i,double(cozumler.x(i)),double(cozumler.y(i)), ...
                                                                     double(cozumler.lc(i)));
    scatter(cozumler.x(i),cozumler.y(i),'oblack','LineWidth',2);
    
    % Her iki fonksiyonun da çözüm noktasında gradyanlarını hesaplayalım.
    x_=cozumler.x(i);
    y_=cozumler.y(i);
    gradF=subs(subs([diff(f,x) diff(f,y)],x,x_),y,y_);
    gradG=subs(subs([diff(g,x) diff(g,y)],x,x_),y,y_);

    % Gradyan vektörlerini çizdirip aynı doğrultuda olduklarını görelim.
    quiver(x_,y_,gradF(1),gradF(2),'b');
    quiver(x_,y_,gradG(1),gradG(2),'r');

    % Çözüm, çizilmiş seviye eğrilerine denk düşmeyebileceği için 
    % tam çözüm noktasından geçen seviye eğrisini (f=c) çizdiğimizden emin olalım.
    c=subs(subs(f,x,x_),y,y_);
    h=ezplot(f-c,cizimAraligi);
    set(h,'Color','black');
end

% Bu sefer 3 boyutlu yüzeye eğriyi düşürüp çözümleri 3 boyutlu uzayda da görelim.
figure; hold on;
colormap(gray); % Gri olsun ki üzerinde çizeceklerimiz noktalar renklere karışmasın.
ezsurf(f);
% g=0 eğrisini çizelim. Yalnız burada eğri yüzeye düşürülmeden çizilecek.
ezplot(solve(g,y));

% Şimdi yazıdaki patika örneğini daha iyi anlamak için eğriyi yüzeye
% düşürelim. Yüzeye düşürülmüş eğrinin x ve y koordinatları g'den, z ise f'den gelecek.
x_=cizimAraligi(1):0.5:cizimAraligi(2); % Adımı büyütüp işlemi hızlandırabiliriz.
y__=subs(g,x,x_); % x'e değerler verip y'leri hesaplıyoruz. (y'li denklemler)
y_=zeros(1,size(y__,2));
z_=zeros(1,size(y__,2));
for i=1:size(y__,2)
    y_(i)=solve(y__(i)); % y'yi bir tarafa atıp denklemi çözüyoruz.

    % z'yi de g'nin x ve y koordinatlarını yüzey fonksiyonunda yerlerine
    % yazıp z eksenindeki karşılıklarını hesaplayarak elde ediyoruz.
    z_(i)=subs(subs(f,x,x_(i)),y,y_(i));
end

% Yüzeye düşürdüğümüz noktaların temsil ettiği eğriyi çiziyoruz.
plot3(x_,y_,z_,'r','LineWidth',2);

% Şimdi hem eğri üzerinde, hem de yüzeye düşürülmüş eğri üzerinde
% çözümleri işaretleyip görelim.
for j=1:size(cozumler.x,1)
    xNok=cozumler.x(j);
    yNok=cozumler.y(j);

    scatter(xNok,yNok,'oblue','LineWidth',3);

    zNok=subs(subs(f,x,xNok),y,yNok);
    scatter3(xNok,yNok,zNok,'ored','LineWidth',3);
end

view(-40,14); % Grafiğe noktaları net görebileceğimiz bir açıdan bakalım.

Kod aşağıdaki çıktıyı ve grafikleri üretecek:

Çözüm sayısı: 3
x1 y1 lc1:  0.000000    -5.333333    -3.555556
x2 y2 lc2:  3.391165    -1.500000    -1.000000
x3 y3 lc3: -3.391165    -1.500000    -1.000000

Lagrange çarpanları örneği

Son olarak grafikleri yorumlayalım. Yöntemin işleyişini grafiğe dökmek için iki seçeneğimiz vardı. Ya 3 boyutlu yüzeyi 2 boyutlu bir düzleme düşürüp (seviye eğrilerini çizerek) kısıt eğrisini aynı düzlemde çizeriz (soldaki grafik) ya da kısıt eğrisini 3 boyutlu yüzeyin üzerine düşürüp ne olup bittiğini orada inceleriz (sağdaki grafik).

İlk grafikteki kırmızı eğri g=0 eğrimiz. Kırmızı oklar, g fonksiyonunun çözüm noktalarındaki gradyanları ve tabi ki tümü eğriye dik. Mavi oklarsa f fonksiyonunun aynı noktalardaki gradyanları. Gradyanların yukarıda belirttiğimiz gibi aynı doğrultularda olduklarını ve boylarıyla yönlerinin farklı olduğunu (yönleri eşit olabilirdi) görmek mümkün.

İkinci grafikteki yüzey f yüzeyimiz. Mavi eğri g=0 eğrimiz ve yüzey üzerindeki kırmızı eğri, g=0 eğrisinin yüzey üzerine düşürülmüş hali. Çözüm olarak bulduğumuz noktaları yüzey üzerinde işaretlediğimizde (kırmızı noktalar), başta verdiğimiz dağ örneğine uygun olarak f'nin değerinin, 1. ve 3. noktalardan geçilirken artarken azalmaya ve 2. noktadan geçilirken azalırken artmaya başladığını görebiliyoruz.

Harici Bağlantılar

Sayfayı
Yayın tarihi: 24 Mayıs 2015 Pazar, 22:50
Anahtar kelimeler: lagrange çarpanları, lagrange multipliers, gradyan, gradient, matlab, kod örneği

Yorum Gönder

 
Yorumunuzu -1. yoruma yanıt olarak gönderiyorsunuz. Yanıtlamayı iptal etmek için buraya tıklayabilirsiniz.

 

Yorumlar

Onaylanmış yorum bulunmuyor.
 
 
Sayfa 37 sorgu ile 0.004 saniyede oluşturuldu.
Atasoy Blog v4 © 2008-2017 Hüseyin Atasoy