Matematiksel optimizasyon - Mathematical optimization

Tarafından verilen grafik z = f (x, y) = −(x² + y²) + 4. Küresel maksimum (x, y, z) = (0, 0, 4) mavi bir noktayla gösterilir.

Nelder-Mead minimum arama Simionescu'nun işlevi. Tek yönlü köşeler değerlerine göre sıralanır, 1 en düşük (fx En iyi değeri.

Matematiksel optimizasyon (alternatif olarak yazılır optimizasyon) veya matematiksel programlama bazı mevcut alternatifler arasından en iyi unsurun (bazı kriterlere göre) seçilmesidir.^[1] Tüm kantitatif disiplinlerde çeşitli optimizasyon problemleri bilgisayar Bilimi ve mühendislik -e yöneylem araştırması ve ekonomi ve çözüm yöntemlerinin geliştirilmesi ilgi çekmiştir. matematik asırlardır.^[2]

En basit durumda, bir optimizasyon sorunu içerir maksimize etmek veya küçültmek a gerçek işlev sistematik olarak seçerek giriş izin verilen bir küme içinden değerler ve hesaplama değer işlevin. Optimizasyon teorisi ve tekniklerinin diğer formülasyonlara genelleştirilmesi, geniş bir alan oluşturur. Uygulamalı matematik. Daha genel olarak, optimizasyon, tanımlanmış bir hedef işlevin "mevcut en iyi" değerlerini bulmayı içerir. alan adı (veya girdi), çeşitli farklı türde amaç işlevleri ve farklı etki alanları dahil.

Optimizasyon sorunları

Bir optimizasyon problemi şu şekilde temsil edilebilir:

Verilen: a işlevi f : Bir → ℝ bazılarından Ayarlamak Bir için gerçek sayılar

Aranan: bir element x₀ ∈ Bir öyle ki f(x₀) ≤ f(x) hepsi için x ∈ Bir ("küçültme") veya öyle ki f(x₀) ≥ f(x) hepsi için x ∈ Bir ("maksimizasyon").

Böyle bir formülasyona optimizasyon sorunu veya a matematiksel programlama problemi (doğrudan ilgili olmayan bir terim bilgisayar Programlama, ancak hala kullanılıyor, örneğin doğrusal programlama - görmek Tarih altında). Pek çok gerçek dünya ve teorik problem bu genel çerçevede modellenebilir.

Aşağıdakiler geçerli olduğundan

${ displaystyle f sol ( mathbf {x} _ {0} sağ) geq f sol ( mathbf {x} sağ) Leftrightarrow { tilde {f}} sol ( mathbf {x} _ {0} sağ) leq { tilde {f}} left ( mathbf {x} sağ)}$

ile

${ displaystyle { tilde {f}} sol ( mathbf {x} sağ): = - f sol ( mathbf {x} sağ), , { tilde {f}} ,: , A rightarrow mathbb {R}}$

minimizasyon problemlerini çözmek daha uygundur. Ancak bunun tersi de geçerli olacaktır.

Bu teknik kullanılarak formüle edilen sorunlar, fizik tekniği şu şekilde ifade edebilir: enerji küçültme, fonksiyonun değerinden bahsetmişken f enerjisini temsil eden sistemi olmak modellenmiş. İçinde makine öğrenme, bir veri modelinin kalitesini sürekli olarak değerlendirmek için her zaman gereklidir. maliyet fonksiyonu burada minimum, optimal (en düşük) hata ile olası optimum parametreler kümesini ifade eder.

Tipik, Bir biraz alt küme of Öklid uzayı ℝⁿ, genellikle bir dizi ile belirtilir kısıtlamalar, üyelerinin eşitlik veya eşitsizlikler Bir tatmin etmek zorunda. alan adı Bir nın-nin f denir arama alanı ya da seçim setiunsurları ise Bir arandı aday çözümler veya uygulanabilir çözümler.

İşlev f çeşitli şekillerde an amaç fonksiyonu, bir kayıp fonksiyonu veya maliyet fonksiyonu (küçültme),^[3] a fayda fonksiyonu veya Fitness fonksiyonu (maksimizasyon) veya belirli alanlarda bir enerji fonksiyonu veya enerji işlevsel. Amaç işlevi en aza indiren (veya hedef buysa maksimize eden) uygulanabilir bir çözüme, en uygun çözüm.

Matematikte geleneksel optimizasyon problemleri genellikle minimizasyon anlamında ifade edilir.

Bir yerel minimum x* bazılarının var olduğu bir öğe olarak tanımlanır δ > 0 öyle ki

${ displaystyle forall mathbf {x} A ; { text {nerede}} ; sol Vert mathbf {x} - mathbf {x} ^ { ast} sağ Vert leq delta, ,}$

ifade f(x*) ≤ f(x) tutar;

yani etrafındaki bir bölgede x* tüm fonksiyon değerleri o elemandaki değerden büyük veya ona eşittir. Yerel maksimumlar benzer şekilde tanımlanır.

Yerel bir minimum, en az yakındaki öğeler kadar iyi olsa da, küresel minimum en azından uygulanabilir unsurlar kadar iyidir. Genel olarak, amaç işlevi olmadığı sürece dışbükey bir minimizasyon probleminde, birkaç yerel minimum olabilir. dışbükey problem, eğer dahili bir yerel minimum varsa (uygulanabilir unsurlar kümesinin kenarında değil), aynı zamanda küresel minimumdur, ancak konveks olmayan bir problem, hepsinin global minimum olması gerekmeyen birden fazla yerel minimuma sahip olabilir.

Konveks olmayan problemleri çözmek için önerilen çok sayıda algoritma - ticari olarak mevcut çözücülerin çoğu dahil - yerel olarak en uygun çözümler ile küresel olarak en uygun çözümler arasında bir ayrım yapamaz ve ilkini orijinal soruna gerçek çözümler olarak ele alır. Global optimizasyon şubesi Uygulamalı matematik ve Sayısal analiz konveks olmayan bir problemin gerçek optimal çözümüne sonlu zamanda yakınsamayı garanti edebilen deterministik algoritmaların geliştirilmesiyle ilgilidir.

Gösterim

Optimizasyon sorunları genellikle özel gösterimle ifade edilir. İşte bazı örnekler:

Bir fonksiyonun minimum ve maksimum değeri

Aşağıdaki gösterimi düşünün:

${ displaystyle min _ {x in mathbb {R}} ; sol (x ^ {2} +1 sağ)}$

Bu minimum değer amaç fonksiyonunun x² + 1, seçerken x setinden gerçek sayılar ℝ. Bu durumda minimum değer 1'dir ve x = 0.

Benzer şekilde, gösterim

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

amaç fonksiyonunun maksimum değerini sorar 2x, nerede x herhangi bir gerçek sayı olabilir. Bu durumda, amaç işlevi sınırsız olduğu için böyle bir maksimum yoktur, dolayısıyla cevap "sonsuzluk "veya" tanımsız ".

Optimal girdi argümanları

Aşağıdaki gösterimi düşünün:

${ displaystyle { underet {x in (- infty, -1]} { operatorname {arg , min}}} ; x ^ {2} +1,}$

Veya eşdeğer olarak

${ displaystyle { underet {x} { operatorname {arg , min}}} ; x ^ {2} +1, ; { text {konu:}} ; x in (- infty , -1].}$

Bu, değerini (veya değerlerini) temsil eder. tartışma x içinde Aralık (−∞,−1] amaç işlevini en aza indiren (veya en aza indiren) x² + 1 (bu işlevin gerçek minimum değeri, sorunun istediği şey değildir). Bu durumda cevap şudur: x = −1, dan beri x = 0 uygulanabilir değildir, yani, uygulanabilir set.

Benzer şekilde,

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

Veya eşdeğer olarak

${ displaystyle { underet {x, ; y} { operatorname {arg , max}}} ; x cos y, ; { text {konu:}} ; x [-5 , 5], ; y içinde mathbb {R},}$

temsil etmek {x, y} amaç fonksiyonunun değerini maksimize eden (veya maksimize eden) bir çift (veya çift) x çünkü y, eklenen kısıtlama ile x aralıkta yatmak [−5,5] (yine, ifadenin gerçek maksimum değeri önemli değildir). Bu durumda, çözümler form çiftleridir {5, 2kπ} ve {−5, (2k + 1)π}, nerede k tüm aralıklar tamsayılar.

Operatörler arg min ve arg max bazen şu şekilde de yazılır argmin ve argmaxve durun minimum argüman ve maksimum argüman.

Tarih

Fermat ve Lagrange Optima'yı belirlemek için hesap tabanlı formüller bulurken Newton ve Gauss optimuma doğru ilerlemek için önerilen yinelemeli yöntemler.

Dönem "doğrusal programlama "belirli optimizasyon durumları için George B. Dantzig teorinin çoğu tarafından tanıtılmış olmasına rağmen Leonid Kantorovich 1939'da. (Programlama bu bağlamda atıfta bulunmaz bilgisayar Programlama, ancak kullanımından gelir program Birleşik Devletler ordusu tarafından önerilen eğitime atıfta bulunmak ve lojistik Dantzig'in o zaman üzerinde çalıştığı problemlerdi.) Dantzig, Simpleks algoritması 1947'de ve John von Neumann teorisini geliştirdi ikilik aynı yıl içinde.^{[kaynak belirtilmeli ]}

Matematiksel optimizasyondaki diğer önemli araştırmacılar şunları içerir:

Başlıca alt alanlar

• Konveks programlama amaç işlevi olduğu durumu inceler dışbükey (küçültme) veya içbükey (maksimizasyon) ve kısıtlama kümesi dışbükey. Bu, doğrusal olmayan programlamanın belirli bir durumu olarak veya doğrusal veya dışbükey ikinci dereceden programlamanın genelleşmesi olarak görülebilir.
  • Doğrusal programlama (LP), bir tür dışbükey programlama, amaç fonksiyonunun olduğu durumu inceler. f doğrusaldır ve kısıtlamalar yalnızca doğrusal eşitlikler ve eşitsizlikler kullanılarak belirtilir. Böyle bir kısıtlama setine a çokyüzlü veya a politop Öyleyse sınırlı.
  • İkinci dereceden koni programlama (SOCP) dışbükey bir programdır ve belirli tipte ikinci dereceden programları içerir.
  • Yarı belirsiz programlama (SDP), altta yatan değişkenlerin olduğu bir dışbükey optimizasyon alt alanıdır. yarı belirsiz matrisler. Doğrusal ve dışbükey ikinci dereceden programlamanın bir genellemesidir.
  • Konik programlama genel bir dışbükey programlama biçimidir. LP, SOCP ve SDP'nin tümü, uygun koni tipine sahip konik programlar olarak görülebilir.
  • Geometrik programlama nesnel ve eşitsizlik kısıtlamalarının şu şekilde ifade edildiği bir tekniktir posynomlar ve eşitlik kısıtlamaları tek terimli konveks bir programa dönüştürülebilir.
• Tamsayılı programlama bazı veya tüm değişkenlerin üstlenmek için kısıtlandığı doğrusal programları inceler tamsayı değerler. Bu dışbükey değildir ve genel olarak normal doğrusal programlamadan çok daha zordur.
• İkinci dereceden programlama objektif fonksiyonun ikinci dereceden terimlere sahip olmasına izin verirken, uygulanabilir küme doğrusal eşitlikler ve eşitsizliklerle belirtilmelidir. İkinci dereceden terimin belirli formları için, bu bir tür dışbükey programlamadır.
• Kesirli programlama Doğrusal olmayan iki fonksiyonun oranlarının optimizasyonunu inceler. Özel içbükey kesirli program sınıfı, bir dışbükey optimizasyon problemine dönüştürülebilir.
• Doğrusal olmayan programlama Amaç fonksiyonunun veya kısıtlamaların veya her ikisinin doğrusal olmayan kısımlar içerdiği genel durumu inceler. Bu, konveks bir program olabilir veya olmayabilir. Genel olarak, programın dışbükey olup olmadığı, onu çözmenin zorluğunu etkiler.
• Stokastik programlama bazı kısıtlamaların veya parametrelerin bağlı olduğu durumu inceler rastgele değişkenler.
• Sağlam optimizasyon Stokastik programlama gibi, optimizasyon probleminin altında yatan verilerdeki belirsizliği yakalama girişimidir. Sağlam optimizasyon, bir belirsizlik kümesi ile tanımlanan belirsizliklerin olası tüm gerçekleşmelerinde geçerli olan çözümleri bulmayı amaçlamaktadır.
• Kombinatoryal optimizasyon Uygulanabilir çözümler kümesinin ayrık olduğu veya tek bir düzeye indirgenebileceği problemlerle ilgilenir. ayrık bir.
• Stokastik optimizasyon arama işleminde rastgele (gürültülü) işlev ölçümleri veya rastgele girdiler ile kullanılır.
• Sonsuz boyutlu optimizasyon Uygulanabilir çözümler kümesinin sonsuz bir alt kümesi olduğu durumu inceler.boyutlu işlevler alanı gibi alan.
• Sezgisel ve metasezgisel Optimize edilen problem hakkında çok az varsayımda bulunun veya hiç varsayımda bulunmayın. Sezgisel yöntemler genellikle herhangi bir optimal çözüm bulunması gerektiğini garanti etmez. Öte yandan, birçok karmaşık optimizasyon problemi için yaklaşık çözümler bulmak için buluşsal yöntemler kullanılır.
• Kısıtlama memnuniyeti amaç işlevinin olduğu durumu inceler f sabittir (bu, yapay zeka, Özellikle de otomatik muhakeme ).
  • Kısıt programlama değişkenler arasındaki ilişkilerin kısıtlar şeklinde ifade edildiği bir programlama paradigmasıdır.
• Ayrık programlama, en az bir kısıtlamanın yerine getirilmesi gerektiği, ancak hepsinin değil olduğu durumlarda kullanılır. Programlamada özellikle kullanılır.
• Uzay haritalama bir mühendislik sisteminin, uygun fiziksel olarak anlamlı bir kaba veya uygun olanı kullanarak yüksek kaliteli (hassas) model doğruluğuna modellemesi ve optimizasyonu için bir kavramdır. vekil model.

Bazı alt alanlarda, teknikler öncelikle dinamik bağlamlarda optimizasyon için tasarlanmıştır (yani, zaman içinde karar verme):

• Varyasyon hesabı koordinatların bir fonksiyonunu değiştirerek bir eylem integralini bir uç noktaya kadar optimize etmeye çalışır.
• Optimal kontrol teori, kontrol politikalarını ortaya çıkaran varyasyonlar hesabının bir genellemesidir.
• Dinamik program çözme yaklaşımı stokastik optimizasyon stokastik, rastgelelik ve bilinmeyen model parametreleri ile ilgili problem. Optimizasyon stratejisinin problemi daha küçük alt problemlere bölmeye dayandığı durumu inceler. Bu alt problemler arasındaki ilişkiyi tanımlayan denkleme, Bellman denklemi.
• Denge kısıtlı matematiksel programlama kısıtlamaların içerdiği yer varyasyonel eşitsizlikler veya tamamlayıcılık.

Çok amaçlı optimizasyon

Bir optimizasyon problemine birden fazla hedef eklemek karmaşıklık katar. Örneğin, yapısal bir tasarımı optimize etmek için, hem hafif hem de sert bir tasarım arzu edilir. İki hedef çeliştiğinde, bir değiş tokuş yaratılmalıdır. En hafif bir tasarım, en sert tasarım ve bazı ağırlık ve sağlamlıktan ödün veren sonsuz sayıda tasarım olabilir. Bir ölçüte göre diğeri pahasına gelişen takas tasarımları kümesi, Pareto seti. En iyi tasarımların sertliğine karşı ağırlığı çizen eğri, Pareto sınırı.

Bir tasarım, başka herhangi bir tasarım tarafından domine edilmemişse, "Pareto optimal" (eşdeğer olarak, "Pareto verimli" veya Pareto kümesinde) olarak değerlendirilir: Bazı açılardan başka bir tasarımdan daha kötü ve hiçbir açıdan daha iyi değilse, o zaman hakimdir ve Pareto optimal değildir.

"Favori çözümü" belirlemek için "Pareto optimal" çözümleri arasından seçim, karar vericiye verilir. Başka bir deyişle, problemin çok amaçlı optimizasyon olarak tanımlanması, bazı bilgilerin eksik olduğunu gösterir: istenen hedefler verilir, ancak bunların kombinasyonları birbirine göre derecelendirilmez. Bazı durumlarda, eksik bilgiler karar vericiyle etkileşimli oturumlar aracılığıyla elde edilebilir.

Çok amaçlı optimizasyon sorunları daha da genelleştirilmiştir. vektör optimizasyonu (kısmi) sıralamanın artık Pareto sıralaması tarafından verilmediği sorunlar.

Çok modlu veya global optimizasyon

Optimizasyon sorunları genellikle çok modludur; yani çok sayıda iyi çözüme sahiptirler. Hepsi küresel olarak iyi olabilir (aynı maliyet fonksiyonu değeri) veya küresel olarak iyi ve yerel olarak iyi çözümlerin bir karışımı olabilir. Çoklu çözümlerin tümünü (veya en azından bir kısmını) elde etmek, çok modlu bir optimize edicinin amacıdır.

Yinelemeli yaklaşımları nedeniyle klasik optimizasyon teknikleri, çoklu çözümler elde etmek için kullanıldıklarında tatmin edici bir şekilde çalışmazlar, çünkü algoritmanın birden çok çalışmasında farklı başlangıç ​​noktalarında bile farklı çözümlerin elde edileceği garanti edilmez.

Ortak yaklaşımlar küresel optimizasyon Birden fazla yerel ekstremanın mevcut olabileceği problemler şunları içerir: evrimsel algoritmalar, Bayes optimizasyonu ve benzetimli tavlama.

Kritik noktaların ve ekstremanın sınıflandırılması

Fizibilite sorunu

tatmin edilebilirlik sorunu, aynı zamanda fizibilite sorunu, sadece herhangi birini bulma sorunu Makul çözüm nesnel değer dikkate alınmaksızın. Bu, amaç değerinin her çözüm için aynı olduğu ve dolayısıyla herhangi bir çözümün optimal olduğu matematiksel optimizasyonun özel durumu olarak kabul edilebilir.

Çoğu optimizasyon algoritmasının uygulanabilir bir noktadan başlaması gerekir. Böyle bir noktayı elde etmenin bir yolu, Rahatlayın bir kullanarak fizibilite koşulları gevşek değişken; Yeterli gevşeklik olduğunda, herhangi bir başlangıç ​​noktası mümkündür. Ardından, bolluk sıfır veya negatif olana kadar bu bolluk değişkenini en aza indirin.

Varoluş

aşırı değer teoremi nın-nin Karl Weierstrass kompakt bir küme üzerinde sürekli gerçek değerli bir fonksiyonun maksimum ve minimum değerine ulaştığını belirtir. Daha genel olarak, kompakt bir küme üzerinde daha düşük bir yarı-sürekli fonksiyon minimuma ulaşır; kompakt bir setteki üst yarı sürekli işlev, maksimum bakış açısına veya görüşüne ulaşır.

Optimallik için gerekli koşullar

Fermat teoremlerinden biri Kısıtlanmamış sorunların optimumunun şu adreste bulunduğunu belirtir: sabit noktalar, birinci türevi veya amaç fonksiyonunun gradyanı sıfır olduğunda (bkz. ilk türev testi ). Daha genel olarak şu adreste bulunabilirler: kritik noktalar, amaç fonksiyonunun ilk türevi veya gradyanı sıfır olduğunda veya tanımsız olduğunda veya seçim kümesinin sınırında. Birinci türev (ler) in bir iç optimumda sıfıra eşit olduğunu belirten bir denklem (veya denklemler seti), "birinci dereceden koşul" veya bir birinci dereceden koşullar kümesi olarak adlandırılır.

Eşitlik kısıtlı problemlerin optimumunu şu şekilde bulabilirsiniz: Lagrange çarpanı yöntem. Eşitlik ve / veya eşitsizlik kısıtlamaları olan problemlerin optimumları, 'Karush – Kuhn – Tucker koşulları '.

Optimallik için yeterli koşullar

İlk türev testi ekstrema olabilecek noktaları belirlerken, bu test minimum olan noktayı maksimum olan veya olmayan noktadan ayırt etmez. Amaç fonksiyonu iki kez türevlenebilir olduğunda, bu durumlar ikinci türevi veya ikinci türev matrisini kontrol ederek ayırt edilebilir ( Hessen matrisi ) kısıtsız problemlerde veya amaç fonksiyonunun ikinci türevlerinin matrisinde ve kısıtlamalar sınırdaki Hessian kısıtlı problemlerde. Maksimumları veya minimumları diğer sabit noktalardan ayıran koşullara 'ikinci dereceden koşullar' denir (bkz.İkinci türev testi '). Bir aday çözüm birinci dereceden koşulları yerine getiriyorsa, o zaman ikinci dereceden koşulların karşılanması da en azından yerel iyimserliği sağlamak için yeterlidir.

Optima'nın hassasiyeti ve sürekliliği

zarf teoremi bir temelde yatan optimum çözümün değerinin nasıl değiştiğini açıklar. parametre değişiklikler. Bu değişikliği hesaplama sürecine karşılaştırmalı statik.

maksimum teorem nın-nin Claude Berge (1963) optimal bir çözümün sürekliliğini, temeldeki parametrelerin bir fonksiyonu olarak tanımlar.

Optimizasyon hesabı

İki kere türevlenebilir fonksiyonlara sahip kısıtsız problemler için, bazıları kritik noktalar nerede olduğu noktaları bularak bulunabilir gradyan Amaç fonksiyonun sıfırdır (yani, sabit noktalar). Daha genel olarak sıfır alt gradyan için yerel bir minimum bulunduğunu onaylar konveks ile minimizasyon problemleri fonksiyonlar ve diğeri yerel olarak Lipschitz fonksiyonları.

Ayrıca, kritik noktalar, kesinlik of Hessen matrisi: Hessian ise pozitif kritik bir noktada kesin, o zaman nokta yerel bir minimumdur; Hessian matrisi negatif tanımlıysa, nokta yerel maksimumdur; son olarak, eğer belirsizse, o zaman mesele bir tür Eyer noktası.

Kısıtlı sorunlar, çoğu zaman, aşağıdakilerin yardımıyla kısıtsız sorunlara dönüştürülebilir. Lagrange çarpanları. Lagrange rahatlama aynı zamanda zor kısıtlı sorunlara yaklaşık çözümler sağlayabilir.

Amaç işlevi bir dışbükey işlev, bu durumda herhangi bir yerel minimum aynı zamanda genel bir minimum olacaktır. Dışbükey işlevleri en aza indirmek için verimli sayısal teknikler vardır, örneğin iç nokta yöntemleri.

Hesaplamalı optimizasyon teknikleri

Problemleri çözmek için araştırmacılar kullanabilir algoritmalar sınırlı sayıda adımda biten veya yinelemeli yöntemler bir çözüme yakınsayan (belirli bazı problem sınıflarında) veya Sezgisel bu, bazı sorunlara yaklaşık çözümler sağlayabilir (yinelemelerinin yakınsaması gerekmez).

Optimizasyon algoritmaları

• Simpleks algoritması nın-nin George Dantzig, için tasarlandı doğrusal programlama.
• Tek yönlü algoritmanın uzantıları, ikinci dereceden programlama ve için doğrusal kesirli programlama.
• Tek yönlü algoritmanın özellikle aşağıdakiler için uygun olan çeşitleri ağ optimizasyonu.
• Kombinatoryal algoritmalar
• Kuantum optimizasyon algoritmaları

Yinelemeli yöntemler

yinelemeli yöntemler problemlerini çözmek için kullanılır doğrusal olmayan programlama olup olmadıklarına göre farklılık gösterir değerlendirmek Hessianlar, degradeler veya yalnızca işlev değerleri. Hessianlar (H) ve gradyanları (G) değerlendirmek yakınsama oranını iyileştirirken, bu büyüklüklerin var olduğu ve yeterince sorunsuz değiştiği fonksiyonlar için, bu tür değerlendirmeler hesaplama karmaşıklığı (veya her bir yinelemenin hesaplama maliyeti). Bazı durumlarda, hesaplama karmaşıklığı aşırı derecede yüksek olabilir.

Optimize ediciler için önemli bir kriter, sadece gerekli fonksiyon değerlendirmelerinin sayısıdır, çünkü bu genellikle zaten büyük bir hesaplama çabasıdır, genellikle temelde N değişkenler üzerinde çalışmak zorunda olan optimize edicinin kendisinden çok daha fazla çaba gerektirir. optimize ediciler, ancak hesaplanması daha da zordur, ör. gradyanı yaklaştırmak en az N + 1 fonksiyon değerlendirmesi alır. 2. türevlerin (Hessian matrisinde toplanan) yaklaşımları için, fonksiyon değerlendirme sayısı N² sırasındadır. Newton yöntemi 2. dereceden türevleri gerektirir, bu nedenle her yineleme için işlev çağrılarının sayısı N² sırasındadır, ancak daha basit bir saf gradyan optimize edici için yalnızca N'dir. Bununla birlikte, gradyan optimize ediciler genellikle Newton'un algoritmasından daha fazla yinelemeye ihtiyaç duyar. İşlev çağrılarının sayısına göre hangisinin en iyi olduğu, sorunun kendisine bağlıdır.

• Hessianları (veya yaklaşık Hessianları kullanarak) değerlendiren yöntemler sonlu farklar ):
  • Newton yöntemi
  • Sıralı ikinci dereceden programlama: Küçük-orta ölçekli ölçek için Newton tabanlı bir yöntem kısıtlı sorunlar. Bazı sürümler büyük boyutlu sorunları çözebilir.
  • İç nokta yöntemleri: Bu, kısıtlı optimizasyon için geniş bir yöntem sınıfıdır. Bazı iç nokta yöntemleri yalnızca (alt) gradyan bilgisini kullanır ve diğerleri ise Hessianların değerlendirmesini gerektirir.
• Gradyanları veya yaklaşık gradyanları bir şekilde (veya hatta alt gradyanları) değerlendiren yöntemler:
  • Koordinat iniş yöntemler: Her yinelemede tek bir koordinatı güncelleyen algoritmalar
  • Eşlenik gradyan yöntemleri: Yinelemeli yöntemler büyük sorunlar için. (Teoride, bu yöntemler, ikinci dereceden nesnel işlevlere sahip sonlu sayıda adımda sonlanır, ancak bu sonlu sonlandırma, sonlu kesinlikli bilgisayarlarda pratikte gözlenmez.)
  • Dereceli alçalma (alternatif olarak, "en dik iniş" veya "en dik çıkış"): Muazzam sorunların yaklaşık çözümlerini bulmak için ilgiyi tazelemiş olan (yavaş) bir tarihsel ve teorik ilgi yöntemi.
  • Alt gradyan yöntemleri - Büyükler için yinelemeli bir yöntem yerel olarak Lipschitz fonksiyonları kullanma genelleştirilmiş gradyanlar. Boris T. Polyak'ı takiben, alt gradyan projeksiyon yöntemleri, eşlenik gradyan yöntemlerine benzer.
  • Paket iniş yöntemi: Yerel olarak Lipschitz işlevleriyle küçük-orta ölçekli problemler için, özellikle de dışbükey küçültme sorunlar. (Eşlenik gradyan yöntemlerine benzer)
  • Elipsoid yöntemi: Küçük sorunlar için yinelemeli bir yöntem yarı konveks nesnel fonksiyonlar ve özellikle bazı kombinatoryal optimizasyon problemlerinin polinom zaman karmaşıklığını kurmada büyük teorik ilgi. Quasi-Newton yöntemleriyle benzerlikleri vardır.
  • Koşullu gradyan yöntemi (Frank – Wolfe) ile özel olarak yapılandırılmış problemlerin yaklaşık en aza indirilmesi için doğrusal kısıtlamalar özellikle trafik ağlarında. Genel kısıtsız problemler için bu yöntem, modası geçmiş olarak kabul edilen gradyan yöntemine indirgenir (neredeyse tüm problemler için).
  • Quasi-Newton yöntemleri: Orta-büyük problemler için yinelemeli yöntemler (örneğin N <1000).
  • Eşzamanlı pertürbasyon stokastik yaklaşım Stokastik optimizasyon için (SPSA) yöntemi; rastgele (verimli) gradyan yaklaşımı kullanır.
• Yalnızca fonksiyon değerlerini değerlendiren yöntemler: Eğer bir problem sürekli olarak türevlenebilir ise, o zaman gradyanlar sonlu farklar kullanılarak tahmin edilebilir, bu durumda gradyan bazlı bir metot kullanılabilir.
  • İnterpolasyon yöntemler
  • Desen arama daha iyi yakınsama özelliklerine sahip yöntemler Nelder – Mead buluşsal yöntemi (basitlerle) aşağıda listelenmiştir.

Küresel yakınsama

Daha genel olarak, amaç işlevi ikinci dereceden bir işlev değilse, birçok optimizasyon yöntemi, bazı yineleme alt dizilerinin bir optimal çözüme yakınsamasını sağlamak için başka yöntemler kullanır. Yakınsamayı sağlamanın ilk ve hala popüler olan yöntemi şunlara dayanır: satır aramaları, bir işlevi bir boyut boyunca optimize eden. Yakınsama kullanımlarını sağlamak için ikinci ve giderek daha popüler bir yöntem güven bölgeleri. Hem hat aramaları hem de güven bölgeleri modern yöntemlerde kullanılır. türevlenemez optimizasyon. Genellikle, global bir optimize edici, gelişmiş yerel optimize edicilerden çok daha yavaştır (örneğin BFGS ), yerel optimize ediciyi farklı başlangıç ​​noktalarından başlatarak çoğu zaman verimli bir global optimizer oluşturulabilir.

Sezgisel

Ayrıca (sonlu olarak sonlandırılıyor) algoritmalar ve (yakınsak) yinelemeli yöntemler, var Sezgisel. Sezgisel, çözümü bulması garanti edilmeyen (matematiksel olarak), ancak yine de belirli pratik durumlarda yararlı olan herhangi bir algoritmadır. Bazı iyi bilinen sezgisel yöntemlerin listesi:

Başvurular

Mekanik

İçindeki sorunlar katı gövde dinamiği (özellikle eklemli katı cisim dinamikleri), katı cisim dinamiklerini bir çözme girişimi olarak görüntüleyebileceğiniz için genellikle matematiksel programlama teknikleri gerektirir. adi diferansiyel denklem bir kısıtlama manifoldunda;^[5] kısıtlamalar, "bu iki nokta her zaman çakışmalıdır", "bu yüzey başka herhangi bir yere nüfuz etmemelidir" veya "bu nokta her zaman bu eğri üzerinde bir yerde olmalıdır" gibi çeşitli doğrusal olmayan geometrik kısıtlamalardır. Ayrıca, temas kuvvetlerini hesaplama problemi bir çözülerek yapılabilir. doğrusal tamamlayıcılık problemi, bu aynı zamanda bir QP (ikinci dereceden programlama) problemi olarak da görülebilir.

Birçok tasarım problemi, optimizasyon programları olarak da ifade edilebilir. Bu uygulamaya tasarım optimizasyonu denir. Bir alt küme, mühendislik optimizasyonu ve bu alanın yeni ve büyüyen bir başka alt kümesi multidisipliner tasarım optimizasyonu, birçok problemde yararlı olsa da, özellikle uzay Mühendisliği sorunlar.

Bu yaklaşım kozmoloji ve astrofizikte uygulanabilir.^[6]

Ekonomi ve finans

Ekonomi optimizasyonuyla yeterince yakından bağlantılı ajanlar Etkili bir tanımın ekonomiyi ilgili olarak tanımladığı qua bilim olarak "insan davranışının amaç ve sonuç arasındaki ilişki olarak incelenmesi kıt "alternatif kullanımlarla" anlamına gelir.^[7] Modern optimizasyon teorisi, geleneksel optimizasyon teorisini içerir, ancak aynı zamanda oyun Teorisi ve ekonomik çalışma denge. İktisadi Edebiyat Dergisi kodları matematiksel programlamayı, optimizasyon tekniklerini ve ilgili konuları aşağıda sınıflandırın: JEL: C61-C63.

Mikroekonomide, yardımcı program maksimizasyonu sorunu ve Onun ikili problem, harcama minimizasyonu sorunu, ekonomik optimizasyon problemleridir. Tutarlı davrandıkları ölçüde, tüketiciler maksimize ettiği varsayılmaktadır. Yarar, süre firmalar genellikle, kar. Ayrıca, aracılar genellikle risk almayan, dolayısıyla riskten kaçınmayı tercih ediyor. Varlık fiyatları aynı zamanda optimizasyon teorisi kullanılarak modellenmiştir, ancak temelde yatan matematik optimizasyona dayanmaktadır. Stokastik süreçler statik optimizasyon yerine. Uluslararası ticaret teorisi ayrıca ülkeler arasındaki ticaret modellerini açıklamak için optimizasyonu kullanır. Optimizasyonu portföyler ekonomide çok amaçlı optimizasyona bir örnektir.

1970'lerden bu yana, ekonomistler zaman içinde dinamik kararları modelledi. kontrol teorisi.^[8] Örneğin, dinamik model ara çalışmak için kullanılır işgücü piyasası davranışı.^[9] Belirleyici ve stokastik modeller arasında önemli bir ayrım vardır.^[10] Makro iktisatçılar inşa etmek dinamik stokastik genel denge (DSGE) çalışanların, tüketicilerin, yatırımcıların ve hükümetlerin birbirine bağlı optimizasyon kararlarının sonucu olarak tüm ekonominin dinamiklerini tanımlayan modeller.^[11][12]

Elektrik Mühendisliği

Optimizasyon tekniklerinin bazı yaygın uygulamaları elektrik Mühendisliği Dahil etmek aktif filtre tasarım^[13] süper iletken manyetik enerji depolama sistemlerinde başıboş alan azaltma, uzay haritalama tasarımı mikrodalga yapılar^[14] ahize antenleri,^[15][16][17] elektromanyetik tabanlı tasarım. Mikrodalga bileşenlerinin ve antenlerin elektromanyetik olarak doğrulanmış tasarım optimizasyonu, uygun bir fiziğe dayalı veya ampirik vekil model ve uzay haritalama keşfinden beri metodolojiler uzay haritalama 1993 yılında.^[18][19]

İnşaat mühendisliği

Optimizasyon, inşaat mühendisliğinde yaygın olarak kullanılmaktadır. İnşaat yönetimi ve Ulaştırma Mühendisliği optimizasyona büyük ölçüde dayanan inşaat mühendisliğinin ana dalları arasındadır. Optimizasyonla çözülen en yaygın inşaat mühendisliği problemleri yolların kesilip doldurulması, yapıların ve altyapıların yaşam döngüsü analizi,^[20] kaynak seviyelendirme,^[21][22] su kaynağı tahsisi, trafik yönetim^[23] ve zamanlama optimizasyonu.

Yöneylem araştırması

Optimizasyon tekniklerini yoğun olarak kullanan bir başka alan da yöneylem araştırması.^[24] Yöneylem araştırması, gelişmiş karar vermeyi desteklemek için stokastik modelleme ve simülasyonu da kullanır. Yöneylem araştırması giderek daha fazla kullanıyor stokastik programlama olaylara uyum sağlayan dinamik kararları modellemek; bu tür sorunlar büyük ölçekli optimizasyonla çözülebilir ve stokastik optimizasyon yöntemler.

Kontrol Mühendisliği

Matematiksel optimizasyon, çok modern kontrolör tasarımında kullanılır. Gibi üst düzey denetleyiciler model tahmin kontrolü (MPC) veya gerçek zamanlı optimizasyon (RTO) matematiksel optimizasyonu kullanır. Bu algoritmalar çevrim içi çalışır ve kontrol edilecek sistemin bir modelini ve kısıtlamaları içeren matematiksel bir optimizasyon problemini yinelemeli olarak çözerek, bir proses tesisindeki tıkanma açıklıkları gibi karar değişkenleri için değerleri tekrar tekrar belirler.

Jeofizik

Optimizasyon teknikleri düzenli olarak kullanılmaktadır. jeofizik parametre tahmin problemleri. Bir dizi jeofizik ölçüm verildiğinde, ör. sismik kayıtlar için çözmek yaygındır fiziki ozellikleri ve geometrik şekiller altta yatan kayalar ve sıvılar. Jeofizikteki problemlerin çoğu doğrusal değildir ve hem deterministik hem de stokastik yöntemler yaygın olarak kullanılmaktadır.

Moleküler modelleme

Doğrusal olmayan optimizasyon yöntemleri yaygın olarak kullanılmaktadır. konformasyonel analiz.

Hesaplamalı sistem biyolojisi

Optimizasyon teknikleri, model oluşturma, optimal deneysel tasarım, metabolik mühendislik ve sentetik biyoloji gibi hesaplama sistemleri biyolojisinin birçok alanında kullanılmaktadır.^[25] Doğrusal programlama Fermantasyon ürünlerinin maksimum olası verimini hesaplamak için uygulanmıştır,^[25] ve çoklu mikroarray veri setlerinden gen düzenleyici ağları çıkarmak için^[26] yanı sıra yüksek verimli verilerden transkripsiyonel düzenleyici ağlar.^[27] Doğrusal olmayan programlama enerji metabolizmasını analiz etmek için kullanılmıştır^[28] ve biyokimyasal yollarda metabolik mühendisliğe ve parametre tahminine uygulanmıştır.^[29]

Makine öğrenme

Çözücüler

Ayrıca bakınız

Notlar

daha fazla okuma

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Dışbükey Optimizasyon. Cambridge: Cambridge University Press. ISBN  0-521-83378-7.
• Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. Londra: Akademik Basın. ISBN  0-12-283952-8.
• Lee, Jon (2004). A First Course in Combinatorial Optimization. Cambridge University Press. ISBN  0-521-01012-8.
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2. baskı). Berlin: Springer. ISBN  0-387-30303-0.
• Snyman, J. A.; Wilke, D. N. (2018). Practical Mathematical Optimization : Basic Optimization Theory and Gradient-Based Algorithms (2. baskı). Berlin: Springer. ISBN  978-3-319-77585-2.

Dış bağlantılar

• "Decision Tree for Optimization Software". Links to optimization source codes
• "Global optimization".
• "EE364a: Convex Optimization I". Course from Stanford University.
• Varoquaux, Gaël. "Mathematical Optimization: Finding Minima of Functions".