Doğrusal Olmayan Programlama
Doğrusal olmayan programlama, düzgün doğrusal olmayan bir amaç fonksiyonunun doğrusal olmayan kısıtlamalar altında optimizasyonunu yapar; bu alan hem optimallik teorisini hem de çözümleri hesaplayan algoritmaları kapsamaktadır.
Tanım
Doğrusal olmayan bir program, doğrusal olmayan eşitlik ve eşitsizlik kısıtlamalarıyla tanımlanan bir uygunluk kümesi üzerinde muhtemelen doğrusal olmayan bir amaç fonksiyonunu minimize etmektedir; konveks problemlerin aksine, birden fazla yerel optimuma sahip olabilmekte ve bu nedenle çoğu yöntem, gerekli optimallik koşullarını sağlayan noktaları aramaktadır.
Kapsam
Bu konu, kısıtsız minimizasyon, çizgi arama ve güven bölgesi stratejileri, gradyan, Newton ve yarı-Newton yöntemleri, birinci ve ikinci dereceden optimallik koşulları, Karush-Kuhn-Tucker koşulları ve kısıt yeterlilikleri ile ceza, artırılmış Lagrange ve sıralı karesel programlama gibi kısıtlı yöntemleri kapsamaktadır.
Temel sorular
- Kısıtlı doğrusal olmayan bir problemin yerel optimumunu hangi koşullar karakterize eder?
- İniş yöntemleri, kısıtsız bir problemin durağan noktasını nasıl bulur?
- Kısıtlamalar yinelemeli algoritmalara nasıl dahil edilir?
- Hesaplanan bir yerel optimuma ne zaman global olarak güvenilebilir?
Temel kuramlar
- Optimallik koşulları
- Birinci dereceden Karush-Kuhn-Tucker koşulları ve ikinci dereceden eğrilik koşulları, uygun kısıt yeterlilikleri altında kısıtlı problemlerin yerel optimumlarını karakterize etmektedir.
- İniş ve Newton-tipi yöntemler
- Gradyan, Newton ve yarı-Newton yöntemleri, iniş yönleri üretmekte ve durağan noktalara yakınsamak için çizgi aramaları veya güven bölgeleri kullanmaktadır; yarı-Newton güncellemeleri eğriliği daha düşük maliyetle yaklaşık olarak belirlemektedir.
- Kısıtlı optimizasyon algoritmaları
- Ceza, artırılmış Lagrange ve sıralı karesel programlama yöntemleri, kısıtlı problemleri daha basit problemler dizilerine dönüştürerek eşitlik ve eşitsizlik kısıtlamalarını sistematik olarak ele almaktadır.
Klinik önem
Doğrusal olmayan programlama, amaç fonksiyonlarının veya kısıtlamaların doğrusal olmadığı her yerde kullanılmaktadır; buna istatistiksel ve makine öğrenimi modellerinin model uyumu ve eğitimi, mühendislik tasarımı, optimal kontrol ve bilim dallarında parametre tahmini gibi alanlar dahildir.
Tarihçe
1951'de belirlenen ve 1939'da Karush tarafından öngörülen Karush-Kuhn-Tucker koşulları, Lagrange çarpanlarını eşitsizlik kısıtlamalarına genelleştirmiş ve kısıtlı doğrusal olmayan teorinin temelini atmıştır. Yarı-Newton yöntemleri, artırılmış Lagrange fonksiyonları ve sıralı karesel programlama, yirminci yüzyılın sonlarında standart hesaplama araç setine dönüşmüştür.
Öne çıkan isimler
- Harold Kuhn
- Albert Tucker
- Isaac Newton
- Magnus Hestenes
İlgili konular
Temel eserler
- nocedal2006
- bertsekas1999
Sıkça sorulan sorular
- Doğrusal olmayan programlama neden doğrusal programlamadan daha zordur?
- Doğrusal olmayan problemler, eğrisel uygunluk bölgelerine ve birden fazla yerel optimuma sahip olabilmektedir; bu nedenle, hesaplanan bir çözümün global olarak en iyi olduğuna dair genellikle bir garanti bulunmamaktadır ve optimumlar köşelerde yer almak zorunda değildir. Algoritmalar, gradyanlar ve eğrilik gibi yerel bilgilere dayanmak durumundadır.
- Yarı-Newton yöntemi nedir?
- Bu, tam ikinci türev matrisini hesaplamadan Newton adımını yaklaşık olarak belirleyen, ardışık gradyanlardan eğrilik bilgisini oluşturan yinelemeli bir yöntemdir. BFGS gibi yöntemler, kesin Newton adımlarına göre çok daha düşük maliyetle hızlı yakınsama sağlamaktadır.