Matematiksel optimizasyon (Mathematical optimization)

Matematiksel optimizasyon (alternatif olarak optimizasyon olarak da yazılır) veya matematiksel programlama, tanımlanmış bir dizi mevcut alternatif arasından belirli kriterlere dayalı olarak en uygun öğeyi seçme işlemidir. Tipik olarak iki ana alt alana kategorize edilir: ayrık optimizasyon ve sürekli optimizasyon. Optimizasyon problemleri, bilgisayar bilimi ve mühendislikten yöneylem araştırması ve ekonomiye kadar çeşitli niceliksel disiplinlerde ortaya çıkar ve etkili çözüm metodolojilerinin araştırılması, yüzyıllar boyunca matematiğin temel odağı olmuştur.

Daha geniş bir perspektiften bakıldığında, bir optimizasyon problemi, izin verilen bir alandan girdi değerlerinin sistematik seçimi ve ardından fonksiyonun çıktısının değerlendirilmesi yoluyla gerçek değerli bir fonksiyonun maksimize edilmesini veya minimize edilmesini içerir. Optimizasyon teorisini ve bununla ilişkili teknikleri çeşitli problem formülasyonlarına genişletmek, uygulamalı matematikte önemli bir alanı temsil eder.

Optimizasyon Sorunları

Optimizasyon sorunları, değişkenlerinin doğasına, özellikle de sürekli mi yoksa ayrık mı olduklarına bağlı olarak genellikle iki ana kategoriye ayrılır:

• Ayrık değişkenlere sahip bir optimizasyon problemine ayrık optimizasyon adı verilir; burada amaç sayılabilir bir kümeden tamsayı, permütasyon veya grafik gibi optimal bir öğeyi tanımlamaktır.
• Sürekli değişkenleri içeren bir soruna sürekli optimizasyon adı verilir ve sürekli bir etki alanı içindeki optimum bağımsız değişkenlerin tanımlanması gerekir. Bu kategori hem kısıtlı hem de çok modlu sorunları kapsar.

Bir optimizasyon problemi resmi olarak şu şekilde ifade edilebilir:

Verilenler: Bir fonksiyon ${\displaystyle f:A\rightarrow \mathbb {R}$ bir A kümesinden gerçek sayılara

eşleme.

Aranan: Tüm x ∈ için f(x§1516§) ≤ f(x) olacak şekilde bir x§56§ ∈ A öğesi A (minimizasyonu temsil eder) veya tüm x ∈ A için (maksimizasyonu temsil eder) f(x§3334§) ≥ f(x) olacak şekilde.

Bu tür formülasyona optimizasyon problemi veya matematiksel programlama problemi adı verilir. Bu terim, bilgisayar programlamayla doğrudan ilişkili olmasa da, örneğin doğrusal programlamada yaygın olmaya devam etmektedir. Bu kapsamlı çerçeve içerisinde çok sayıda gerçek dünya ve teorik zorluk etkili bir şekilde modellenebilir.

Aşağıdaki eşdeğerliğin geçerliliği göz önüne alındığında:

yalnızca minimizasyon problemlerini ele almak yeterlidir. Tersine, eşit derecede geçerli bir yaklaşım, yalnızca maksimizasyon problemlerine odaklanmayı gerektirir.

Fizikte, bu teknikle formüle edilen problemler genellikle enerji minimizasyonu olarak adlandırılır; burada fonksiyonun değeri f, söz konusu sistemin enerjisini belirtir. Makine öğreniminde, bir veri modelinin kalitesinin sürekli değerlendirilmesi zorunludur; bu değerlendirme genellikle minimum değerin, mümkün olan en düşük hatayla ilişkili potansiyel olarak en uygun parametreler kümesini gösterdiği bir maliyet fonksiyonu aracılığıyla gerçekleştirilir.

A kümesi tipik olarak Öklid uzayının bir alt kümesini oluşturur ${\displaystyle \mathbb {R} ^{n}$. Bu alt küme sıklıkla bir dizi kısıtlama tarafından tanımlanır; bunlar, A'nın tüm öğelerinin karşılaması gereken eşitlikler veya eşitsizlikler olabilir. f işlevi için A etki alanı, arama alanı veya seçim kümesi olarak adlandırılır ve bağımsız öğeleri aday çözümler veya uygun çözümler olarak belirtilir.

f işlevi, amaç işlevi, ölçüt işlevi dahil olmak üzere çeşitli adlarla bilinir, kayıp işlevi veya amaç minimizasyon olduğunda maliyet işlevi. Maksimizasyon problemleri için buna yardımcı işlev veya uygunluk işlevi adı verilebilir. Belirli disiplinlerde buna enerji fonksiyonu veya enerji fonksiyoneli de denir. Optimal çözüm, amaç fonksiyonunu minimuma indiren veya maksimuma çıkaran uygulanabilir bir çözüm olarak tanımlanır.

Matematik alanında, standart optimizasyon problemleri genellikle minimizasyon görevleri olarak formüle edilir.

x* olarak gösterilen yerel minimum, kendisi için pozitif bir değer δ > Şu koşulu karşılayan 0 mevcut:

${\displaystyle \forall \mathbf {x} \ A'da\;{\text{burada}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,$

f(x*) ≤ f(x) eşitsizliği karşılanır;

Bu, x*'in belirli bir komşuluğu içinde, tüm işlev değerlerinin x*'deki değerden büyük veya ona eşit olduğu anlamına gelir. Yerel maksimumlar benzer bir tanımla karakterize edilir.

Yerel minimum, hemen komşu öğelerin değerine eşit veya daha üstün bir değeri temsil etse de, küresel minimum, mümkün olan her öğenin değerini aşar veya ona eşittir. Tipik olarak minimizasyon problemlerinde, amaç fonksiyonu dışbükey olmadığı sürece birden fazla yerel minimum mevcut olabilir. Dışbükey bir problem için, bir iç yerel minimum (uygulanabilir kümenin sınırında bulunmayan) aynı zamanda küresel minimumu da oluşturur. Bununla birlikte, dışbükey olmayan bir problem birkaç yerel minimuma sahip olabilir ve bunların tümü mutlaka küresel minimum olarak nitelendirilemez.

Dışbükey olmayan sorunları çözmek için tasarlanmış çok sayıda algoritma, çoğu ticari çözücü de dahil olmak üzere, sıklıkla yerel optimum ve küresel optimum çözümler arasında ayrım yapamaz ve genellikle yerel optimumları sorunun gerçek çözümleri olarak ele alır. Küresel optimizasyon, uygulamalı matematik ve sayısal analiz kapsamında, dışbükey olmayan bir problemin sonlu bir zaman dilimi içinde gerçek optimal çözümüne yakınlaşmayı sağlayabilecek deterministik algoritmalar oluşturmaya adanmış özel bir alandır.

Gösterim Kuralları

Optimizasyon sorunları sıklıkla belirli gösterim sistemleri kullanılarak temsil edilir. Aşağıdaki örnekler bunu göstermektedir:

Bir Fonksiyonun Minimum ve Maksimum Değerlerini Belirleme

Sonraki gösterimi inceleyin:

dk x ∈<!-- ∈ --> R ( x §3132§ + §3738§ ) {\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)

Bu gösterim, x§34§ + 1 amaç fonksiyonunun mümkün olan en düşük değerini belirtir; burada x, gerçek sayılar kümesinden seçilir ${\displaystyle \mathbb {R}$. Bu özel örnekte minimum değer 1'dir ve x 0'a eşit olduğunda elde edilir.

Benzer şekilde, gösterim

${\displaystyle \max _{x\in \mathbb {R} }\;2x$

2x amaç fonksiyonunun mümkün olan en yüksek değerini belirlemeye çalışır; x herhangi bir gerçek sayıyı temsil eder. Ancak bu senaryoda, amaç fonksiyonu sınırsız olduğundan sonlu bir maksimum mevcut değildir ve bu da "sonsuz" veya "tanımsız" sonucunu doğurur.

Optimal Giriş Bağımsız Değişkenleri

Sonraki gösterim şunu göstermektedir:

a r g m i n x ∈<!-- ∈ --> ( −<!-- − --> ∞<!-- ∞ --> , −<!-- − --> §4344§ ] x §5657§ + §6263§ , {\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,

Alternatif olarak şu şekilde de ifade edilebilir:

a r g m i n x x §3435§ + §4041§ , şuna tabidir: x ∈ ( − ∞ , − §7071§ ] . {\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].

Bu ifade, (−∞,−1] aralığı içindeki ve x§78§ + 1 amaç fonksiyonu için minimum değeri veren x bağımsız değişken değerlerini/değerlerini tanımlar. Bu sorgunun, işlevin minimum değerini değil, onu üreten bağımsız değişkenleri aradığını belirtmek önemlidir. Sonuç olarak, çözüm x = −1, x = 0'in mümkün olmadığı göz önüne alındığında, yani tanımlanan uygulanabilir kümenin dışında kalıyor.

Benzer bir şekilde,

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,$

Alternatif olarak belirtilirse,

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{tabii ki:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

Bu, x'in [−5,5] aralığı içinde olduğu kısıtlamasına tabi olarak, x çünkü y amaç fonksiyonunun değerini maksimuma çıkaran {x, y çiftini/çiftlerini belirtir. İfadenin spesifik maksimum değeri bu bağlamda anlamlı değildir. Sonuç olarak, çözümler {5, 2kπ ve {−5, (2k + 1)π olarak yapılandırılmış çiftlerdir; burada k herhangi bir tam sayıyı temsil eder.

arg min ve arg max operatörleri alternatif olarak şu şekilde gösterilir: argmin ve argmax, sırasıyla minimum bağımsız değişkenini ve maksimum bağımsız değişkenini belirtir.

Geçmiş

Fermat ve Lagrange, optimum noktaları belirlemek için analize dayalı formüller geliştirdi. Bunun tersine, Newton ve Gauss optimuma yaklaşmak için yinelemeli metodolojiler geliştirdiler.

George B. Dantzig, belirli optimizasyon senaryolarını tanımlamak için "doğrusal programlama" terimini icat etti; ancak altta yatan teorinin önemli bir kısmı daha önce 1939'da Leonid Kantorovich tarafından oluşturulmuştu. Bu bağlamda Programlamanın bilgisayar programlamayla ilgili olmadığını belirtmek önemlidir; daha doğrusu, Amerika Birleşik Devletleri ordusunun önerilen eğitim ve lojistik programlarını belirtmek için program terimini kullanmasından kaynaklanmaktadır ve bu, Dantzig'in o dönemde araştırdığı sorunları oluşturmaktadır. Dantzig daha sonra Simplex algoritmasını 1947'de yayınladı. Aynı zamanda John von Neumann ve diğer araştırmacılar, ikililik teorisi de dahil olmak üzere doğrusal programlamanın teorik temellerine katkıda bulundular.

Matematiksel optimizasyon alanında önde gelen diğer araştırmacılar arasında şunlar yer almaktadır:

Başlıca Alt Alanlar

• Dışbükey programlama, amaç fonksiyonunun minimizasyon problemleri için dışbükey veya maksimizasyon problemleri için içbükey olduğu ve kısıtlama kümesinin kendisinin dışbükey olduğu senaryoları araştırır. Bu yaklaşım, doğrusal olmayan programlamanın belirli bir örneği veya doğrusal veya dışbükey ikinci dereceden programlamanın daha geniş bir genellemesi olarak düşünülebilir.
  • Dışbükey programlamanın bir alt kümesi olan doğrusal programlama (LP), f amaç fonksiyonunun doğrusal olduğu ve kısıtlamaların yalnızca doğrusal eşitlikler ve eşitsizliklerle tanımlandığı durumlara odaklanır. Sınırlandırıldığında böyle bir kısıtlama kümesine çokyüzlü veya politop adı verilir.
  • İkinci dereceden koni programlama (SOCP), ikinci dereceden programların belirli kategorilerini kapsayan bir dışbükey programlama biçimi oluşturur.
  • Yarı kesin programlama (SDP), yarı kesin matrisler olan temel değişkenlerle karakterize edilen dışbükey optimizasyonun bir alt alanını temsil eder. Bu yöntem hem doğrusal hem de dışbükey ikinci dereceden programlamanın genelleştirilmesine hizmet eder.
  • Konik programlama, dışbükey programlama için genelleştirilmiş bir çerçeve oluşturur. Doğrusal programlama (LP), ikinci dereceden koni programlama (SOCP) ve yarı kesin programlamanın (SDP) her biri, uygun koni türü kullanıldığında konik programlar olarak kavramsallaştırılabilir.
  • Geometrik programlama, nesnel ve eşitsizlik kısıtlarının posinomial olarak ifade edildiğinde, eşitlik kısıtlarının ise tek terimli olarak ifade edildiğinde dışbükey bir programa dönüştürülmesini sağlayan bir metodolojidir.
• Tamsayı programlama, bir alt kümenin veya tüm değişkenlerin tamsayı değerleriyle sınırlandırıldığı doğrusal programları araştırır. Bu yaklaşım doğası gereği dışbükey değildir ve standart doğrusal programlamayla karşılaştırıldığında genellikle çok daha büyük hesaplama zorlukları sunar.
• İkinci dereceden programlama, uygun kümenin doğrusal eşitlikler ve eşitsizliklerle tanımlanması koşuluyla, amaç fonksiyonunun ikinci dereceden terimleri içermesine izin verir. İkinci dereceden terimin belirli konfigürasyonları altında bu yöntem, dışbükey programlama alanına girer.
• Kesirli programlama iki doğrusal olmayan fonksiyon arasındaki oranların optimizasyonunu araştırır. Belirli bir kategori olan içbükey kesirli programlar, dışbükey optimizasyon problemlerine dönüştürülebilir.
• Doğrusal olmayan programlama, amaç fonksiyonunun, kısıtlamaların veya her ikisinin de doğrusal olmayan bileşenler içerdiği senaryoları ele alır. Bu tür programlar dışbükey olabilir veya olmayabilir; bu, genellikle çözümlerinin karmaşıklığını etkileyen bir özelliktir.
• Stokastik programlama, belirli kısıtlamaların veya parametrelerin rastgele değişkenlere bağlı olduğu durumları inceler.
• Stokastik programlamaya benzer şekilde, sağlam optimizasyon, bir optimizasyon problemindeki veri belirsizliğini hesaba katmaya çalışır. Amacı, bir belirsizlik seti tarafından tanımlandığı şekilde, belirsizliklerin tüm potansiyel belirtileri karşısında geçerli kalan çözümleri belirlemektir.
• Kombinatoryal optimizasyon, ayrı bir dizi uygulanabilir çözümle karakterize edilen sorunları veya bu kadar ayrık bir biçime dönüştürülebilen sorunları ele alır.
• Arama süreci rastgele veya gürültülü fonksiyon ölçümleri veya rastgele girdiler içerdiğinde stokastik optimizasyon uygulanır.
• Sonsuz boyutlu optimizasyon, uygun çözüm kümesinin, örneğin bir fonksiyon uzayı gibi sonsuz boyutlu bir uzayın bir alt kümesini oluşturduğu senaryoları araştırır.
• Sezgisel yöntemler ve metasezgiseller, optimizasyon sorununa ilişkin çok az varsayımla veya hiç varsayım olmadan çalışır. Buluşsal yöntemler genellikle en uygun çözümün keşfedilmesini garanti etmese de, çok sayıda karmaşık optimizasyon zorluğuna yönelik yaklaşık çözümleri belirlemek için sıklıkla kullanılır.
• Kısıtlama tatmini, yapay zekada, özellikle otomatik muhakemede uygulanan bir prensip olan f amaç fonksiyonunun sabit kaldığı durumları inceler.
  • Kısıt programlama, değişkenler arasındaki ilişkilerin kısıtlamalar olarak ifade edildiği bir paradigmayı temsil eder.
• Ayrık programlama, belirtilen kısıtlamaların hepsinin olmasa da en az birinin karşılanması gereken bağlamlarda kullanılır ve planlama uygulamalarında özel bir fayda sağlar.
• Uzay haritalama, uygun ve fiziksel olarak anlamlı bir kaba veya yedek modelden yararlanarak yüksek kaliteli model doğruluğu elde etmek amacıyla mühendislik sistemlerinin modellenmesine ve optimize edilmesine yönelik bir metodolojidir.

Birkaç alt alan, özellikle zaman içinde karar almayı içeren, dinamik bağlamlarda optimizasyona yönelik teknikler geliştirir:

• Varyasyonlar hesabı, belirli bir hedefe ulaşmak için en uygun yolları belirlemeye odaklanır; örneğin, mümkün olan en az alana sahip, tanımlanmış bir sınıra sahip bir yüzey belirlemek.
• Optimal kontrol teorisi, kontrol politikalarını dahil ederek varyasyon hesaplamasını genişletir.
• Dinamik programlama, rastgele veya bilinmeyen model parametreleriyle karakterize edilen stokastik optimizasyon problemlerini çözmek için bir yöntem sunar. Bu yaklaşım, bir sorunu Bellman denklemiyle açıklanan karşılıklı ilişkilerle birlikte daha küçük alt sorunlara ayrıştıran bir optimizasyon stratejisi içerir.
• Denge kısıtlamalarıyla matematiksel programlama, kısıtlamaların değişken eşitsizlikleri veya tamamlayıcılıkları kapsadığı senaryoları içerir.

Çok Amaçlı Optimizasyon

Birden fazla hedefi bir optimizasyon problemine dahil etmek, doğası gereği karmaşıklığını artırır. Örneğin, yapısal bir tasarımın optimize edilmesinde genellikle hem hafiflik hem de sağlamlık aranır. Hedefler çatıştığında, bir değiş-tokuş gerekli hale gelir ve potansiyel olarak en hafif tek bir tasarım, en sert tek bir tasarım ve ağırlık ile sağlamlık arasında uzlaşmayı temsil eden sonsuz sayıda tasarımla sonuçlanır. Bir kriteri geliştirirken diğerini potansiyel olarak azaltan değiş-tokuş tasarımlarının toplamına Pareto seti denir. Bu optimal tasarımlar için ağırlığın katılığa karşı grafiksel temsili Pareto sınırını oluşturur.

Bir tasarımda başka bir tasarım baskın değilse, "Pareto optimal" ("Pareto etkin" olarak da bilinir veya Pareto kümesine ait) olarak kabul edilir. Hakimiyet, bir tasarımın başka bir tasarımla karşılaştırıldığında bazı açılardan aşağı olması ve hiçbir açıdan üstün olmaması ve dolayısıyla onu Pareto dışı optimal hale getirmesi durumunda ortaya çıkar.

Bir dizi "Pareto optimal" çözümden "favori çözüm"ün seçilmesi genellikle karar vericiye verilir. Bu, bir problemi çok amaçlı optimizasyon olarak formüle etmenin, özellikle arzu edilen hedeflerin göreceli önceliklendirilmesine ilişkin bilgi eksikliğine işaret ettiği anlamına gelir. Belirli senaryolarda bu eksik bilgi, karar vericiyle etkileşimli oturumlar aracılığıyla ortaya çıkarılabilir.

Çok amaçlı optimizasyon problemleri, kısmi sıralamanın mutlaka Pareto kriteri tarafından tanımlanmadığı vektör optimizasyon problemlerine daha da genelleştirilmiştir.

Çok Modlu ve Global Optimizasyon

Optimizasyon sorunları sıklıkla çoklu yöntem sergiler; bu da birden fazla etkili çözümü kapsadıkları anlamına gelir. Bu çözümler ya tekdüze olarak küresel olarak optimal olabilir (aynı maliyet fonksiyonu değerlerine sahip olabilir) ya da küresel ve yerel olarak optimal sonuçların bir kombinasyonunu içerebilir. Çok modlu bir optimizasyon aracının birincil hedefi, bu çoklu çözümlerin tümünü veya en azından önemli bir alt kümesini tanımlamaktır.

Geleneksel optimizasyon teknikleri, yinelemeli doğaları nedeniyle, çoğu zaman birden fazla çözümü tanımlamakta yetersiz kalır. Bu sınırlama, birden çok algoritma yürütmesinde farklı başlangıç noktaları olsa bile, farklı çözümler keşfetme garantisinin bulunmaması nedeniyle ortaya çıkar.

Küresel optimizasyon sorunlarını, özellikle birden fazla yerel ekstremum varlığıyla karakterize edilenleri ele almak için öne çıkan metodolojiler arasında evrimsel algoritmalar, Bayes optimizasyonu ve benzetilmiş tavlama yer alır.

Kritik Noktaların ve Ekstrem Noktaların Sınıflandırılması

Fizibilite Sorunu

Fizibilite sorunu olarak da bilinen tatmin edilebilirlik sorunu, nesnel değerini dikkate almadan herhangi bir uygulanabilir çözümün tanımlanmasını içerir. Bu senaryo, tüm uygulanabilir çözümlerin aynı amaç değerini paylaştığı ve bu tür her çözümü optimum hale getirdiği matematiksel optimizasyonun belirli bir örneği olarak kavramsallaştırılabilir.

Çok sayıda optimizasyon algoritması, başlangıçta bir uygun nokta gerektirir. Bunu başarmaya yönelik ortak bir strateji, gevşek bir değişkenin eklenmesi yoluyla fizibilite koşullarının gevşetilmesini içerir; Yeterli bolluk herhangi bir başlangıç ​​noktasının mümkün olmasını sağlar. Daha sonra bu gevşeklik değişkeni, boş veya negatif bir değere ulaşana kadar simge durumuna küçültülür.

Optima'nın Varlığı

Karl Weierstrass'ın ekstrem değer teoremi, kompakt bir kümede tanımlanan sürekli gerçek değerli bir fonksiyonun hem maksimum hem de minimum değerlerine ulaşacağını öne sürer. Daha genel anlamda, kompakt bir kümedeki alt yarı sürekli fonksiyon minimum değerine ulaşırken kompakt kümedeki üst yarı sürekli fonksiyon maksimuma ulaşır.

Optimallik için Gerekli Koşullar

Fermat'ın bir teoremi, kısıtlanmamış problemler için optimumun, amaç fonksiyonunun sıfır birinci türevi veya gradyanı ile karakterize edilen durağan noktalarda meydana geldiğini ileri sürer. Daha kapsamlı olarak, optimum, birinci türevin veya gradyanın sıfır veya tanımsız olduğu kritik noktalara veya uygun bölgenin sınırı boyunca yerleştirilebilir. Birinci türevin/türevlerin bir iç optimumda sıfıra eşit olduğunu belirten bir denklem veya denklem sistemi, 'birinci dereceden koşul' veya bir dizi birinci dereceden koşullar olarak adlandırılır.

Lagrange çarpanı yöntemi, eşitlik kısıtlamalarına tabi problemlerde optimumu belirlemek için kullanılabilir. Hem eşitlik hem de eşitsizlik kısıtlamalarını içeren problemler için 'Karush–Kuhn–Tucker koşulları' optimumun belirlenmesine yönelik bir çerçeve sağlar.

Optimallik için Yeterli Koşullar

İlk türev testi potansiyel ekstremum noktayı belirleyebilse de minimum, maksimum veya eyer noktası arasında ayrım yapmaz. İki kez türevlenebilen amaç fonksiyonları için bu ayrımlar, kısıtlanmamış problemlerde ikinci türev veya Hessian matrisi (ikinci türevlerin matrisi) incelenerek yapılabilir. Kısıtlı problemlerde hem amaç fonksiyonunun hem de kısıtlamaların ikinci türevlerini içeren kenarlı Hessian kullanılır. Maksimum veya minimumları diğer durağan noktalardan ayıran kriterlere 'ikinci derece koşullar' adı verilir. Prospektif bir çözüm birinci dereceden koşulları karşılıyorsa, ikinci dereceden koşullara bağlılığı en azından yerel optimalliği doğrulamak için yeterlidir.

Optima'nın Hassasiyeti ve Sürekliliği

Zarf teoremi, temel parametredeki bir değişikliğe yanıt olarak optimal çözümün değerindeki değişikliği açıklar. Bu değişikliğin niceliğini belirlemeye yönelik analitik prosedüre karşılaştırmalı statik adı verilir.

Claude Berge'nin 1963'te ortaya attığı maksimum teoremi, bir optimal çözümün sürekliliğini temel parametrelerine göre açıklamaktadır.

Optimizasyon Hesabı

İki kez türevlenebilir fonksiyonlar içeren kısıtlamasız optimizasyon problemlerinde kritik noktalar, amaç fonksiyonunun gradyanının sıfır olduğu durağan noktalar olarak tanımlanabilir. Daha geniş anlamda, dışbükey veya yerel Lipschitz fonksiyonlarıyla (sinir ağı kaybı fonksiyon minimizasyonunda karşılaşılanlar gibi) minimizasyon problemleri için, sıfır alt derecesi, yerel bir minimumun tanımlanmasını doğrular. Ayrıca pozitif-negatif momentum tahmini, yerel minimumlardan kaçmayı ve amaç fonksiyonunun global minimumuna yakınsamayı kolaylaştırabilir.

Kritik noktalar, Hessian matrisinin kesinliğine dayalı olarak daha fazla kategorize edilebilir: kritik bir noktada pozitif belirli bir Hessian, yerel bir minimumu belirtir; negatif belirli bir Hessian yerel bir maksimumu belirtir; ve belirsiz bir Hessian, bir eyer noktası önerir.

Kısıtlı optimizasyon problemleri, Lagrange çarpanlarının uygulanması yoluyla sıklıkla sınırlandırılmamış formlara dönüştürülür. Ek olarak, Lagrangian gevşemesi, karmaşık kısıtlı problemler için yaklaşık çözümler türetmeye yönelik bir yöntem sunar.

Eğer amaç fonksiyonu dışbükeyse, herhangi bir yerel minimum, doğası gereği bir küresel minimumu temsil eder. Dışbükey fonksiyonları en aza indirmek için iç nokta teknikleri gibi etkili sayısal yöntemler mevcuttur.

Küresel Yakınsama

Amaç fonksiyonu ikinci dereceden olmadığında, çok sayıda optimizasyon algoritması, bir dizi yinelemenin optimal bir çözüme yakınsamasını garanti etmek için stratejiler kullanır. Temel ve yaygın olarak kullanılan bir yakınsama güvence yöntemi, bir fonksiyonu tek bir boyut boyunca optimize eden hat aramalarını içerir. Yakınsamanın sağlanmasına yönelik alternatif ve giderek yaygınlaşan bir yaklaşım, güven bölgelerinden faydalanmaktadır. Hem hat aramaları hem de güven bölgeleri, çağdaş türevlenemeyen optimizasyon tekniklerinin ayrılmaz bir parçasıdır. Tipik olarak küresel optimize ediciler, gelişmiş yerel optimize edicilere (örn. BFGS) kıyasla daha yavaş performans sergiler; sonuç olarak etkili bir küresel optimize edici, genellikle yerel bir optimize edicinin birden fazla farklı başlangıç ​​noktasından başlatılmasıyla sentezlenebilir.

Hesaplamalı Optimizasyon Teknikleri

Optimizasyon sorunlarını çözmek için araştırmacılar, sınırlı sayıda adımla sonuçlanan algoritmalar, belirli sorun sınıfları için bir çözüme yakınsamak üzere tasarlanmış yinelemeli yöntemler veya yinelemeleri mutlaka yakınsamasa bile yaklaşık çözümler sunan buluşsal yöntemler kullanabilir.

Optimizasyon Algoritmaları

• George Dantzig tarafından geliştirilen Simplex algoritması, özellikle doğrusal programlama için tasarlanmıştır.
• Simplex algoritmasının uzantıları ikinci dereceden programlama ve doğrusal-kesirli programlama için geliştirilmiştir.
• Simplex algoritmasının çeşitleri özellikle ağ optimizasyon sorunlarına çok uygundur.
• Kombinatoryal Algoritmalar
• Kuantum Optimizasyon Algoritmaları

Yinelemeli Yöntemler

Doğrusal olmayan programlama problemlerini çözmek için kullanılan yinelemeli yöntemler, Hessian'ların, gradyanların veya yalnızca fonksiyon değerlerinin değerlendirilmesine dayalı olmalarıyla farklılık gösterir. Hessian'ların (H) ve gradyanların (G) değerlendirilmesi, bu niceliklerin mevcut olduğu durumlarda yeterince düzgün fonksiyonlar için yakınsama oranını artırabilse de, bu tür değerlendirmeler aynı zamanda yineleme başına hesaplama karmaşıklığını (veya maliyetini) artırır. Belirli senaryolarda bu hesaplama yükü, engelleyici derecede yüksek hale gelebilir.

Optimize edicileri değerlendirmenin birincil kriteri, gerekli işlev değerlendirmelerinin sayısıdır; çünkü bu genellikle önemli bir hesaplama çabası oluşturur ve çoğu zaman öncelikle N değişkeni işleyen optimize edicinin dahili işlemlerini aşar. Türevler optimize ediciler için ayrıntılı bilgiler sunarken, bunların hesaplanması daha zordur; örneğin, eğimi yaklaşık olarak hesaplamak en az N+1 fonksiyon değerlendirmesini gerektirir. Hessian matrisi içinde derlenen ikinci dereceden türevlerin yaklaşımları için, fonksiyon değerlendirmelerinin sayısı N² ile ölçeklenir. İkinci dereceden türevler gerektiren Newton'un yöntemi, N² işlev çağrılarıyla orantılı yineleme başına bir hesaplama maliyeti doğururken, daha basit bir saf gradyan optimize edici yalnızca N çağrı gerektirir. Bununla birlikte, gradyan optimize ediciler genellikle Newton'un algoritmasından daha fazla yineleme gerektirir. İşlev çağrılarının sayısına ilişkin en uygun seçim, spesifik soruna bağlıdır.

• • Newton'un yöntemi
  • Sıralı ikinci dereceden programlama, küçük ve orta ölçekli kısıtlı problemler için uygun, belirli değişkenlerin büyük boyutlu zorlukları ele alabilen Newton tabanlı bir metodolojiyi temsil eder.
  • İç nokta yöntemleri, kısıtlı optimizasyon için geniş bir teknik kategorisi oluşturur; bunlardan bazıları yalnızca (alt)gradyan bilgisine dayanır ve diğerleri Hessian'ların değerlendirilmesini gerektirir.
• • Koordinat iniş yöntemleri: Her adımda tek bir koordinatı yinelemeli olarak ayarlayan algoritmalar.
  • Eşlenik gradyan yöntemleri, büyük ölçekli problemler için tasarlanmış yinelemeli yaklaşımlardır. Teorik olarak bu yöntemler ikinci dereceden amaç fonksiyonlarına uygulandığında sonlu sonlandırma elde eder; ancak bu sonlu sonlandırma, sonlu duyarlıklı hesaplama sistemlerinde pratik olarak gerçekleştirilmez.
  • "En dik iniş" veya "en dik tırmanış" olarak da bilinen gradyan iniş, tarihsel ve teorik öneme sahip bir yöntemdir. Doğası gereği yavaş olsa da, olağanüstü büyük ölçekli sorunlara yaklaşık çözümlerin belirlenmesine yönelik ilgi yeniden canlandı.
  • Alt gradyan yöntemleri, genelleştirilmiş gradyanlar kullanan, büyük yerel Lipschitz fonksiyonları için yinelemeli bir yaklaşımı temsil eder. Boris T. Polyak'ın belirttiği gibi alt gradyan projeksiyon yöntemleri, eşlenik gradyan yöntemlerine benzerlik gösterir.
  • Demet iniş yöntemi, yerel Lipschitz fonksiyonlarını içeren, özellikle dışbükey minimizasyon problemleri için uygun olan ve eşlenik gradyan yöntemleriyle benzerlikler gösteren, küçük ve orta büyüklükteki problemler için yinelemeli bir tekniktir.
  • Elipsoid yöntemi, yarı dışbükey amaç fonksiyonlarını içeren küçük ölçekli problemler için yinelemeli bir tekniktir. Özellikle belirli kombinatoryal optimizasyon problemlerinin polinom zaman karmaşıklığını oluşturmak açısından önemli bir teorik ilgiye sahiptir ve Quasi-Newton yöntemleriyle ortak özellikler taşır.
  • Koşullu gradyan yöntemi (Frank–Wolfe), özellikle trafik ağları bağlamında, doğrusal kısıtlamalar içeren özel olarak yapılandırılmış sorunların yaklaşık olarak en aza indirilmesi için tasarlanmıştır. Genel olarak kısıtlanmamış problemler için bu yöntem, çoğu uygulama için büyük ölçüde geçerliliğini yitirdiği düşünülen gradyan yöntemini basitleştirir.
  • Yarı Newton yöntemleri, orta ila büyük ölçekli problemler için uygun yinelemeli tekniklerdir (örneğin, genellikle N < 1000 olduğunda).
  • Eşzamanlı Pertürbasyon Stokastik Yaklaşımı (SPSA) yöntemi, rastgele ancak etkili bir gradyan yaklaşımı kullanan stokastik optimizasyonda uygulanır.
• • Enterpolasyon yöntemleri
  • Nelder-Mead buluşsal yöntemine (basitliklerden yararlanan) kıyasla üstün yakınsama özelliklerine sahip olan model arama yöntemleri.
  • Ayna inişi

Buluşsal Yöntem

Sonlu sonlu algoritmalara ve yakınsak yinelemeli yöntemlere ek olarak buluşsal yöntemler de mevcuttur. Buluşsal yöntem, en uygun çözümü bulması matematiksel olarak garanti edilmese de belirli pratik bağlamlarda değerli olduğu kanıtlanan bir algoritma olarak tanımlanır.

Uygulamalar

Mekanik

Katı cisim dinamiğindeki problemler, özellikle de eklemli katı cisim dinamiği, sıklıkla matematiksel programlama tekniklerini gerektirir. Bunun nedeni, katı cisim dinamiğinin, bu kısıtlamaların çeşitli doğrusal olmayan geometrik koşulları içerdiği bir kısıtlama manifoldu üzerindeki sıradan bir diferansiyel denklemin çözümü olarak kavramsallaştırılabilmesidir; örneğin, "bu iki nokta her zaman çakışmalı", "bu yüzey başka hiçbir yüzeye girmemelidir" veya "bu nokta her zaman bu eğri üzerinde bir yerde yer almalıdır." Ayrıca temas kuvvetlerinin hesaplanması, ikinci dereceden programlama (QP) problemi olarak da yorumlanabilen doğrusal tamamlayıcılık probleminin çözümü yoluyla ele alınabilir.

Çok sayıda tasarım problemi sıklıkla optimizasyon programları olarak formüle edilir; bu alana tasarım optimizasyonu adı verilir. Mühendislik optimizasyonu bir alt kümeyi oluştururken, farklı ve genişleyen bir alt alan da multidisipliner tasarım optimizasyonudur; bu, geniş çapta uygulanabilir olmasına rağmen, havacılık ve uzay mühendisliği problemlerinde özellikle fayda sağlamıştır.

Bu yaklaşım kozmoloji ve astrofizikte uygulanabilir.

Ekonomi ve finans

Ekonomi ve etmen optimizasyonu arasındaki içsel bağlantı, ekonomiyi bilim olarak, alternatif uygulamalara sahip "amaçlar ve kıt araçlar arasındaki bir ilişki olarak insan davranışının incelenmesi" olarak karakterize eden etkili bir tanımla vurgulanmaktadır. Çağdaş optimizasyon teorisi geleneksel yaklaşımları kapsarken aynı zamanda oyun teorisi ve ekonomik denge analizi ile de kesişmektedir. Journal of Economic Literatür sınıflandırma sisteminde matematiksel programlama, optimizasyon metodolojileri ve ilgili konular JEL:C61-C63 altında kategorize edilir.

Mikroekonomi sıklıkla ekonomik optimizasyon problemlerini, özellikle de fayda maksimizasyon problemini ve buna karşılık gelen ikili harcama minimizasyon problemini ele alır. Tutarlı davranış varsayıldığında, tüketicilerin faydalarını maksimuma çıkaracakları varsayılırken, firmaların genellikle karlarını maksimuma çıkaracakları varsayılır. Ayrıca, ekonomik birimler sıklıkla riskten kaçınan olarak modellenmektedir, bu da riskten kaçınma tercihini göstermektedir. Optimizasyon teorisi aynı zamanda varlık fiyatlarının modellenmesine de uygulanır, ancak temel matematiksel çerçeve statik optimizasyon yerine stokastik süreçlerin optimize edilmesini içerir. Ayrıca, uluslararası ticaret teorisi ülkeler arasındaki ticaret dinamiklerini açıklamak için optimizasyon ilkelerini kullanır. Portföy optimizasyonu, ekonomik alandaki çok amaçlı optimizasyonun belirgin bir örneğidir.

Ekonomistler 1970'lerden bu yana zaman içindeki dinamik karar alma süreçlerini modellemek için kontrol teorisinden yararlanıyorlar. Örneğin, işgücü piyasası davranışlarını analiz etmek için dinamik arama modelleri kullanılıyor. Deterministik ve stokastik modelleme yaklaşımları arasında temel bir farklılık vardır. Makroekonomistler, genel ekonomik dinamikleri işçiler, tüketiciler, yatırımcılar ve devlet kurumları tarafından yapılan birbirine bağımlı optimizasyon seçimlerinin bir sonucu olarak karakterize eden dinamik stokastik genel denge (DSGE) modelleri oluşturur.

Elektrik Mühendisliği

Optimizasyon teknikleri, elektrik mühendisliğinde, aktif filtre tasarımı, süper iletken manyetik enerji depolama sistemlerinde başıboş alanların azaltılması, mikrodalga yapıları için uzay haritalama tasarımı, cep telefonu antenleri ve elektromanyetik tabanlı tasarım gibi alanları kapsayan çok sayıda uygulama alanı bulur. 1993'teki başlangıcından bu yana, genellikle uygun fizik tabanlı veya ampirik vekil modellerle birleştirilen uzay haritalama metodolojileri, mikrodalga bileşenlerinin ve antenlerin elektromanyetik olarak doğrulanmış tasarım optimizasyonunda yaygın olarak kullanılmıştır. Ayrıca optimizasyon teknikleri, güç akışı analizinin ayrılmaz bir parçasıdır.

İnşaat Mühendisliği

Optimizasyon ilkeleri inşaat mühendisliğinin çeşitli alanlarında yaygın olarak uygulanmaktadır. Özellikle inşaat yönetimi ve ulaştırma mühendisliği, inşaat mühendisliği içerisinde optimizasyona önemli bir bağımlılık sergileyen temel alt disiplinleri temsil eder. Optimizasyon yoluyla ele alınan yaygın inşaat mühendisliği zorlukları arasında yol açma ve doldurma işlemleri, yapıların ve altyapının yaşam döngüsü değerlendirmeleri, kaynak dengeleme, su kaynağı dağıtımı, trafik yönetimi ve program optimizasyonu yer alır.

Yöneylem Araştırması

Yöneylem araştırması, optimizasyon tekniklerini kapsamlı bir şekilde kullanan başka bir disiplini oluşturur. Bu alan aynı zamanda gelişmiş karar verme süreçlerini kolaylaştırmak için stokastik modelleme ve simülasyondan da yararlanır. Gelişen olaylara yanıt olarak uyum sağlayan dinamik kararları modellemek için stokastik programlamayı kullanma yönünde yöneylem araştırmasında büyüyen bir eğilim vardır; bu sorunlar, büyük ölçekli optimizasyon ve stokastik optimizasyon metodolojilerinden elde edilen çözümlere uygundur.

Kontrol Mühendisliği

Matematiksel optimizasyon, çağdaş denetleyici tasarımında önemli bir rol oynar. Model öngörülü kontrol (MPC) ve gerçek zamanlı optimizasyon (RTO) dahil olmak üzere gelişmiş kontrol sistemleri, matematiksel optimizasyonu entegre eder. Çevrimiçi çalışan bu algoritmalar, sistem kısıtlamalarını ve kontrollü sistemin bir modelini içeren bir matematiksel optimizasyon problemini tekrar tekrar çözerek karar değişkenleri için değerleri (örneğin, bir proses tesisindeki tıkaç açıklıkları) yinelemeli olarak belirler.

Jeofizik

Jeofizik parametre tahmin zorluklarında optimizasyon teknikleri rutin olarak uygulanır. Sismik kayıtlar gibi belirli bir dizi jeofizik ölçümden, yer altı kayalarının ve sıvılarının fiziksel özelliklerini ve geometrik konfigürasyonlarını çıkarmak standart bir uygulamadır. Çoğu jeofizik problem doğası gereği doğrusal değildir ve hem deterministik hem de stokastik metodolojilerin yaygın şekilde uygulanmasını gerektirir.

Moleküler Modelleme

Doğrusal olmayan optimizasyon metodolojileri konformasyonel analiz alanında yaygın olarak kullanılmaktadır.

Hesaplamalı Sistem Biyolojisi

Optimizasyon metodolojileri, hesaplamalı sistem biyolojisi kapsamında model oluşturma, optimal deneylerin tasarımı, metabolik mühendislik ve sentetik biyolojiyi kapsayan çeşitli alanlarda yaygın olarak kullanılmaktadır. Spesifik olarak, fermantasyon ürünlerinin elde edilebilecek maksimum verimini belirlemek ve yüksek verimli verilerden türetilen transkripsiyonel düzenleyici ağların yanı sıra çeşitli mikrodizi veri kümelerinden gen düzenleyici ağları çıkarmak için doğrusal programlamadan yararlanılmıştır. Ayrıca, doğrusal olmayan programlama, enerji metabolizmasının analizinde ve bunun metabolik mühendisliğe uygulanmasında ve biyokimyasal yollardaki parametrelerin tahmininde etkili olmuştur.

Makine Öğrenimi

Çözücüler

Notlar

Notlar

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Dışbükey Optimizasyon. Cambridge: Cambridge Üniversitesi Yayınları. ISBN 0-521-83378-7.

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Dışbükey Optimizasyon. Cambridge: Cambridge Üniversitesi Yayınları. ISBN 0-521-83378-7.Gill, P.E.; Murray, W.; Wright, M.H. (1982). Pratik Optimizasyon. Londra: Academic Press. ISBN 0-12-283952-8.Lee, Jon (2004). Kombinatoryal Optimizasyonda İlk Kurs. Cambridge Üniversitesi Yayınları. ISBN 0-521-01012-8.Nocedal, Jorge; Wright, Stephen J. (2006). Sayısal Optimizasyon (2. baskı). Berlin: Springer. ISBN 0-387-30303-0.
  • "Optimizasyon Yazılımı için Karar Ağacı"."EE364a: Dışbükey Optimizasyon I". Stanford Üniversitesi'nden kurs.Varoquaux, Gaël. "Matematiksel Optimizasyon: Fonksiyonların Minimalarını Bulma".Kaynak: TORİma Akademi Arşivi