Optimizasyon

Matematikte matematiksel programlama ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tamsayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder.

 

Örneğin bu problem şöyle olabilir: Verilen: f fonksiyonu: Adan R ye tanımlı. (R:Reel Sayılar) Aranan : Ada öyle bir x0 var mı ki; tüm x değerleri için f(x0) f(x)ifadesini sağlasın ("minimizasyon") veya f(x0) f(x) ifadesini sağlasın ("maksimizasyon"). Böylesi bir formulasyona optimizasyon problemi ya da matematiksel programlama problemi denir ( terimin bilgisayar programlama ile direkt bir ilgisi yoktur, ama yine de lineer programlamada kullanılan bir ifadedir).Pek çok gerçek ve teorik problemler bu genel çerçevede modellenebilir.Bu teknik kullanılarak formüle edilen problemlere fizik bilminin ilgi alanından bir örnek verilecek olursa, bilgisayar monitörlerinin enerji minimizasyonundan söz edilebilir.O halde, yukarıdaki f fonksiyonu modellenen sistemdeki enerjiyi temsil edecekti. Bu tür problemlerde "A kümesi" genellikle, bir takım daraltıcı kısıtlar, eşitlikler ve eşitsizlikler ile yerine verilecek(denenecek) değerleri sağlayan öklidyen uzayın (Rn) bir alt kümesidir.f fonksiyonundaki Anın tanım aralığına "arama uzayı", Anın alacağı değerlerin kümesine ise çözüm adayları ya da olası çözümler denir. f fonksiyouna objektif(nesnel) ya da paha(maliyet) fonksiyonu denir.İstenilen objeyi minimize ya da maksimize eden(amaca göre) olası A çözümüne ise "optimal çözüm" denir.

Genellikle, problemin olası çözümü ve objektif fonksiyonu dışbükeylik göstermez, birden çok yerel "minimum" ve "maksimum" noktalarına rastlanabilir. x* da bulunan ve tüm xler için x > 0 iken ifadesi ile sağlanıyorsa; x* civarında bir yerlerde fonksiyonun tüm değerlerinin, bu noktadaki değerden büyük veya ona eşit olduğu söylenebilir, o halde bu nokta bir "Yerel Minimum" noktasıdır.(Yerel Maksimum da benzer şekilde ifade edilebilir). Dışbükey olmayan problemlerin çözümünde pek çok algoritma kullanılmasına rağmen (çoğunlukla ticari amaca yönelik çözüm üreten algoritmalar) yine de yerel optimal noktalar ve gerçek optimal noktaral arasındaki farkların ayırt ve tespit edilmesinde yetersiz kalınmakta ve orijinal probleme bir adım geriden yaklaşılmaktadır.Deterministik algoritmaların gelişimi ile ilgilenip, yakınsayan ve dışbükey olmayan ifadeleri -sınırlı bir zamanda- gerçek bir optimal ifadeye ayrıştırabilen uygulamalı matematik ve nümerik analiz branşlarına global optimizasyon denir.
Başlıca alt dalları

Doğrusal Programlama : f objektif fonksiyonun doğrusal olduğu ve A kümesinin yalnızca doğrusal eşitlik veya eşitsizlikler ile ulaşılabilir olduğu durumlarda bu isim kullanılır. Böylesi bir A kümesine, sınırlandırılmamış ise polihedron, sınırlı ile politop denir. Tamsayı Programlama : Doğrusal programların bir ya da daha çok değişkeni tamsayı ile ifade edildiği durumlarda kullanılır. Kuadratik Programlama: A değeri doğrusal eşitlik veya eşitsizlikler ile gösterilmek kaidesi ile; objektif fonksiyonun kuadratik değerler almasına müsaade eder. Doğrusal olmayan Programlama: Objektif fonksiyon ya da kısıtların doğrusal olmadığı genel durumları inceler. Konveks Programlama objektif fonksiyon ve kısıtın bükey bir fonksiyon biçminde ifade edilebileceği durumları inceler.Non-Lineer programlaman özel bir hâli olarak düşünülebilir.

İkinci Derece Koni Programlama (SOCP). Yarı-Belirli Programlama (SDP) Değişkenleri yarı tanımlı olacak şekilde, Bükey optimizasyonun bir alt dalıdır. Lineer ve Konveks Kuadratik programlaman genel bir hâlidir. Stokastik Programlama: Kısıt ve parametrelerin rastgele değişkenlere bağlı olduğu durumları inceler. Robust Optimizasyonu/Programlama: Optimizasyon problemindeki belirsiz bilgiyi yakalamaya çalışan bir tür stokastik programlamatır.Stokastik programlama gibi, belirsiz bilgiye dayalı olarak çalışmaz ancak problemi girilen bilginin rastgele etkinliği ve şans temelinden kopmadan çözemez. Tümleşik Optimizasyon : Olası çözüm kümesi içeren problemlerin mümkün ise daha kolay çözülebilir bir şekle indirgenmesi esasına dayanır. Sonsuz-Boyutlu Optimizasyon : Olası çözüm kümesinin (Fonksiyonlar kümesi gibi) sonsuz boyutlu bir uzaya ait olup, olmadığını araştırır. Kısıt Sağlaması f fonskiyonun sabit olup, olamaaycağını araştırır (Bu metod yapay zeka alanında kullanılır, özellikle de otomatikleşmiş ilişkilendirme konusunda yardımcı olur).Ayırıcı Programlama kullanularak, seçilen ve önem adledilen (en az) bir kısıtın sağlanması temin edilmesi esasına dayanır. Yörünge Optimizasyonu: Hava ve uzay araçları için kullanılan özel bir optimizasyon türüdür.

Altdallara göre farklılık gösterecek şekilde, çeşitli teknikler dizayn edilmiştir:
Değişkenler Hesabı Objektif fonksiyonun zaman aralıklarından seçilen değişik noktalara nasıl reaksiyon verdiğinin incelenmesi ile kullanılan yöntemdir. Optimal Kontrol Teorisi değişkenler hesabının çeşitli genellemelerinin toplanmış halidir. Dinamik Programlama Büyük parçaların daha küçük boyutlara indirgenmesi optimizasyon stratejisini yöneten metottur.Bu tür alt problemler ile ilgili olan eşitliklere Bellman eşitliği denir.
Teknikler İki kez diferansiyeli alınabilen fonksiyonlar için, kısıt bulundurmayan problemler objektif fonksiyonun gradyanının sıfıra eşit olduğu noktaların (istasyon noktaların) yeri tespit edilip,[Hessian matrix] ile her noktanın sınıfı belirlenerek çözülebilir.Eğer Hessian pozitif tanımlı ise bu nokta "Yerel Minimum", negatif tanımlı ise "Yerel Maksimum"dur.

Şayet tanımsız ise de bir tür saddle point olduğu söylenebilir. Ancak, her zaman türev almak olası değildir.Objektif fonksiyonun düzgünlüğüne göre metodların ana sınıflandırması şöyle yapılabilir:
Tümleşik Metodlar Türeve-Serbest Metodlar Birinci Derece Metodlar İkinci Derece Metodlar
Bazı metodlar özel isimleri ile de yukarıdaki dört gruptan birine denk gelecek şekilde listenebilir:
Gradyan İniş ya da Dik iniş metodu. Nelder-Mead Metodu ya da the Amoeba metodu. Alt-Gradyan Metodu - Gradyan metodunun, gradyan bulunmayan durumlar için kullanılan hali.Tekyönlü Metod Elipsoid Metod Yğın Metodu [[Newton Metodu] Kazi-Newton Metodu Dahili Nokta Metodu Birleşik Gradyan Metodu Hat Araması - tek boyulu optimizasyon için kullanılan bir teknik, genellikle başka bir tekniğe yardımcı olması için kullanılır.
Kısıt problemleri genellikle Lagrange Çarpanı ile kısıttan bağımsız bir forma getirilir. Bir kaç popüler metod daha:
Tepe Tırmanışı Benzetimli Tavlama Kuantum Benzetimli Tavlama Tabu Araması Kiriş Araması Genetik Algoritmalar Karınca Sürüsü Optimizasyonu Evrim Stratejisi Stokastik Tünel Diferansiyel Evrim Sürü Parçacıkları Armoni Araması Arı Algoritması

Kullanım alanları Yapı-Araç İskeleti dinamiğine ilişkin problemler sıklık ile matematiksel programlama teknikleri gerektirmektedir.Yapı-Araç İskeleti, manifold ile kısıtlanmış bir basit diferansiyel denklemin çözümüne ihtiyaç duyan bir yönelim olarak değerlendirilebilir.Bu durumda kısıtlar non-lineer olmayan gemotetrik çeşitliliktedir, öneğin "bu iki nokta daima temas etmeli", "bu alan diğerine etki etmemeli" ya da "bu nokta her zaman bu eğri üzerinde olmalı" gibi.Ayrıca temas halindeki kuvvetlere ilişkin problemler de lineer uyumluluk çatısı altında çözüldüğünden, buna da bir tür QP (Kuadratir Programlama) Problemi gözüyle bakılabilir. Pek çok dizayn problemi de optimizasyon programları ile çözülmektedir.Bu tür uygulamalara dizayn optimizasyonu denir.Bu alanda bilinen ve büyümekte olan bir alt kol çok disiplinli dizayn optimizasyonudur.

Bu tür, pek çok problemde kullanışlı olduğu gibi aynı zamanda da uzay mühendisliği sahasına uyarlanabilmektedir. Ekonomi de matematiksel programlamaya ağır bir bağımlılık duyar.Mikroiktisatda sık karşılaşılan bir problem olan marjinal fayda ve bundan kaynaklanan ikilik olan harcamaları minimize etme problemi iktisadî bir optimizasyon problemidir. Tüketiciler ve firmalar fayda/kar oranlarını maksimize etmek durumundadırlar.Ticaret teorisi de milletler arası ticari ortaklığın izahında optimizasyona sık sık başvurur. Sabit genel giderli zaman maliyet problemleride önemli bir optimizasyon problemidir. Özellikle inşaat ve endüstri mühendisliğinde bu problemle sıkça karşılaşılır. Doğrusal programlama, sezgisel ve üst sezgisel yöntemler bu problem türünün optimizasyonu için kullanılmaktadır. Optimizasyon tekniklerinin sıkça kullanıldığı bir diğer alan da operasyon araştırmasıdır.

Tarihçe Dik İniş adıyla bilinen ilk optimizasyon tekniğinin tarihi Gaussa dek uzanır. Tarihi olarak, 1940larda George Dantzig tarafından ortaya atılan lineer Programlama kuramı en yaşlı optimizasyon terimidir. Programlama terimi bu bağlamda Bilgisayar Programcılığını ifade etmez.Program teriminin kullanımı ABD Ordusunun, kendi içtimai ve lojistik takvimini belirlemede konteyner kullandığı "program" terimi ile ilişkilidir.(Daha sonra ise "program" terimi devlet bütçesinin düzenlenmesinde kullanılmış ve günümüzde de yüksek teknolojik araştırmaların sahasına da geçmiştir.) Optimizasyon Alanına Katkı Sağlayan Diğer Önemli Matematikçiler:
John von Neumann Leonid Vitalyevich Kantorovich Naum Z. Shor Leonid Khachian Boris Polyak Yurii Nesterov Arkadii Nemirovskii Michael J. Todd Richard Bellman Hoang Tuy
Ayrıca bakınız

arg max Oyun Teorisi Operasyon Araştırma İşlem Optimizasyonu Fuzzy logic Rastgele Optimizasyon Değişkenler Eşitsizliği Değişkenler Hesabı Tek Yönlü Algoritma Dahili Nokta Metodu Radyal Temelli Fonksiyon Brachistochrone Optimizasyon Yazılımı Optimizasyon Problemi Dinamik Programlama
Problem Çözücüler

NAG Numerical Libraries-NAG kütüphanesi çeşitli problem ve durumlardan oluşan optimizasyona dair geniş bir arşiv sunuyor.http://www.nag.co.uk/optimization/index.asp NPSOL - Non-Lineer progralama problemlerinin çözümü için geliştirilmiş bir Fortran paketi. OpenOpt - Pyhton dilinde yazılmış ücretsiz çözücüleri sağlayan bir araç-kutusu IPOPT - Açık kaynak kodlu ilkel-ikincil dahli metodlar ile çalışan bir NLP çözücü. KNITRO - Non-Lineet problemler için bir çözücü. CPLEX Mathematica