Doğrusal Olmayan Programlama
- Ortaya koyan
- Jorge Nocedal & Stephen Wright
- Yıl
- 2006
- Tür
- Continuous mathematical optimization
- Aile
- Mathematical programming
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Doğrusal olmayan programlama (NLP), amaç fonksiyonunun veya en az bir kısıtlamanın doğrusal olmadığı optimizasyon problemlerini ilgilendiren matematiksel optimizasyonun bir dalıdır.
Jorge Nocedal ve Stephen Wright tarafından 2006 tarihli temel metinlerinde kapsamlı bir şekilde biçimlendirilen NLP, mühendislik, ekonomi ve fizik bilimlerinde ortaya çıkan sürekli karar problemlerine yerel veya küresel optimal çözümler bulmak için sıralı kuadratik programlama (SQP), iç nokta yöntemleri ve yarı-Newton yaklaşımları dahil olmak üzere gradyan tabanlı algoritmaları kapsar.
Yöntemin mantığı
Sisle kaplı tepelik bir arazide, çitle çevrili bir bölge içinde kalırken aşağı indiğinizi hayal edin. Tüm araziyi göremiyorsunuz, bu yüzden ayaklarınızın altındaki eğimi (gradyan) hissediyor, adım yönünüzü yokuş aşağı gitmek için ayarlıyor ve her harekette çiti geçmediğinizi kontrol ediyorsunuz (kısıtlamalar). Çit bükülürse veya tepeler üst üste gelirse, basit düz çizgili yollar işe yaramaz - yolunuzu eğmeniz gerekir. Doğrusal olmayan programlama tam olarak bu süreci biçimlendirir, sezgisel tepe yürüyüşünü matematiksel olarak titiz adım boyu ve yön kurallarıyla değiştirir.
Tarih
Doğrusal olmayan programlamanın teorik temelleri, Karush (1939) ve Kuhn ile Tucker (1951) tarafından türetilen KKT koşullarına dayanmaktadır. Pratik algoritmalar, SQP yöntemlerinin, artırılmış Lagrange yaklaşımlarının ve BFGS (1970) dahil olmak üzere yarı-Newton güncellemelerinin geliştirilmesiyle 1960'lar-1980'lerde hızlandı. Nocedal ve Wright'ın 2006 tarihli Sayısal Optimizasyon adlı ikinci baskısı, yakınsama teorisini, çizgi arama ve güven bölgesi çerçevelerini ve iç nokta yöntemlerini tutarlı bir modern incelemede sentezleyen kesin bir referans haline geldi.
Ne zaman kullanılır?
Amaç fonksiyonu veya kısıtlamalar, doğrulukta önemli bir kayıp olmadan doğrusallaştırılamadığında ve karar değişkenleri sürekli olduğunda doğrusal olmayan programlamayı kullanın. Tipik ayarlar arasında fiziksel yasa kısıtlamalarına sahip mühendislik tasarımı, doğrusal olmayan risk ölçütlerine sahip portföy optimizasyonu ve doğrusal olmayan model formlarına sahip regresyon yer alır. Temel varsayımlar, f ve c'nin en az iki kez sürekli olarak türevlenebilir olması (gradyan tabanlı çözücüler için) ve kısıtlama yeterliliklerinin geçerli olmasıdır. Değişkenler tamsayı değerli olduğunda, karışık tamsayılı doğrusal olmayan programlama (MINLP) uzantıları geçerlidir. Dışbükey problemler için iç nokta yöntemleri küresel optimalliği garanti eder; dışbükey olmayan problemler için yalnızca yerel garantiler mevcuttur.
Sınırlar ve dikkat edilmesi gerekenler
- Dışbükey olmayan problemler yalnızca yerel optimallik garantileri sunar; küresel çözümler ek küresel arama stratejileri gerektirir.
- Amaç fonksiyonu ve kısıtlamaların pürüzsüz olmasını gerektirir (en azından türevlenebilir); pürüzlü problemler özel alt diferansiyel yöntemler gerektirir.
- Kesin Hessian değerlendirmesi gerektiğinde hesaplama maliyeti, problem boyutuyla önemli ölçüde artar.
- Kısıtlama yeterlilikleri başarısız olabilir (örneğin, dejeneratif fizibil noktalarda), bu da KKT koşullarının teorik temelini kaybetmesine neden olur.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Doğrusal veya kuadratik yaklaşımların yetersiz olduğu geniş bir gerçek dünya problemi sınıfını ele alır.
- Dışbükey örnekler için iyi incelenmiş yakınsama garantilerine sahip olgun algoritmik teori.
- Verimli gradyan tabanlı çözücüler (SQP, iç nokta) pratikte binlerce değişkene ölçeklenir.
- Birleştirilmiş Lagrange çerçevesi, karışık eşitlik ve eşitsizlik kısıtlamalarını doğal olarak barındırır.
Uygulama alanları
- Yapısal ve havacılık mühendisliği: gerilme ve sapma kısıtlamalarına tabi olarak ağırlığı en aza indirme.
- Portföy yönetimi: doğrusal olmayan bir varyans (risk) bütçesine tabi olarak beklenen getiriyi en üst düzeye çıkarma.
- Kimyasal proses tasarımı: termodinamik ve güvenlik kısıtlamalarına tabi olarak reaktör verimini optimize etme.
- Makine öğrenmesi: doğrusal olmayan veya kısıtlanmamış NLP çözücüleri aracılığıyla sinir ağlarını ve çekirdek modellerini eğitme.
- Enerji sistemleri: doğrusal olmayan fiziksel kısıtlamalarla elektrik şebekesi sevkiyatında optimal güç akışı problemleri.
Nasıl çalışır?
Nasıl çalışır?
Analist, R^n'deki karar değişkenleri x üzerinde en aza indirmek veya en üst düzeye çıkarmak için skaler bir amaç fonksiyonu f(x) tanımlar, buna eşitlik kısıtlamaları c_i(x) = 0 ve eşitsizlik kısıtlamaları c_j(x) >= 0 eşlik eder. Aday bir çözeltide hangi kısıtlamaların aktif olduğunu ve düzenlilik koşullarının (kısıtlama yeterlilikleri) geçerli olup olmadığını belirlemek bu aşamada kritiktir ve hangi optimallik teorisinin geçerli olduğunu belirler.
Formül
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}Karush-Kuhn-Tucker (KKT) koşulları, yerel bir optimum için birinci dereceden gerekli koşulları sağlar. Lagrange'ın durağanlığını, eşitsizlik çarpanları için tamamlayıcı gevşekliği (lambda_j c_j = 0), çift fizibiliteyi (lambda_j >= 0) ve birincil fizibiliteyi gerektirirler. Algoritmalar, bu koşulları giderek daha sıkı bir şekilde karşılayan iterasyonlar oluşturur ve ikinci dereceden yeterlilik koşulları, durağan bir noktanın gerçekten yerel bir minimum olduğunu doğrular.
Formül
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}Her iterasyon k'da bir algoritma, tipik olarak Hessian'ın (örneğin, BFGS) bir yarı-Newton yaklaşımı B_k veya kesin bir ikinci türev sistemi aracılığıyla bir arama yönü p_k ve Wolfe veya Armijo koşullarını sağlayan bir adım uzunluğu alpha_k hesaplar. SQP yöntemleri p_k için kuadratik bir alt problem çözerken, iç nokta yöntemleri eşitsizlik kısıtlamalarını ele almak ve iterasyonları fizibil iç kısma doğru yönlendirmek için bariyer terimleri ekler.
Formül
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)Sonlandırma, hem Lagrange'ın gradyan normu hem de maksimum kısıtlama ihlali önceden belirlenmiş toleransların (epsilon ve delta) altına düştüğünde gerçekleşir. NLP genellikle dışbükey olmadığı için, algoritmalar yerel optimumlara yakınsayabilir; küresel optimallik gerektiğinde farklı başlangıç noktalarından birden fazla yeniden başlatma veya küresel arama stratejileri (dal-sınır, çoklu başlangıç) önerilir.
Formül
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaSık yapılan hatalar
- Kısıtlama yeterliliklerini göz ardı etmek ve dejeneratif veya fizibil olmayan noktalarda KKT koşullarını körü körüne uygulamak, sahte çözümlere yol açar.
- Kötü ölçeklenmiş değişkenlerin kullanılması, kötü koşullandırılmış Hessian yaklaşımlarına ve yavaş veya başarısız yakınsamaya neden olur.
- Dışbükey olmayan ayarlarda birden fazla yeniden başlatma olmadan bulunan ilk yerel minimumu kabul etmek, küresel optimumu önemli ölçüde kaçırabilir.
- Sonlu fark gradyan yaklaşımları sayısal hata üretir; analitik veya otomatik farklılaştırma şiddetle tercih edilir.
Sık sorulan sorular
Her doğrusal program aynı zamanda doğrusal olmayan bir program mıdır?
Evet. Doğrusal programlama, hem amaç fonksiyonunun hem de tüm kısıtlamaların afin olduğu NLP'nin özel bir durumudur. Ancak, LP doğrusallıktan yararlanan ve genel NLP çözücülerinden çok daha verimli olan simpleks ve iç nokta algoritmalarına izin verir; bir LP için genel bir NLP çözücüsü kullanmak israftır ancak matematiksel olarak geçerlidir.
Bir KKT noktasının küresel bir minimum olduğuna ne zaman güvenebilirim?
NLP dışbükey olduğunda - yani f dışbükey ve fizibil küme dışbükey bir küme olduğunda - herhangi bir KKT noktası küresel bir minimumdur. Dışbükey olmayan problemler için bu garanti geçerli değildir ve bir KKT noktası yalnızca yerel bir minimumdur (ikinci dereceden yeterlilik koşulları altında). Aksi takdirde dal-sınır veya dışbükey gevşetmeler gibi küresel optimizasyon yöntemleri gereklidir.
SQP ve iç nokta yöntemleri arasındaki fark nedir?
SQP, NLP'yi yerel olarak yaklaştıran kuadratik programlama alt problemlerini iteratif olarak çözer ve genellikle birçok aktif kısıtlamaya sahip küçük ila orta ölçekli problemler için tercih edilir. İç nokta (bariyer) yöntemleri, fizibil bölgenin içinde kesinlikle kalır ve büyük seyrek problemler için daha iyi ölçeklenir. Her ikisi de uygun düzenlilik koşulları altında süperlineer yakınsar.
İlgili yöntemler
Kaynaklar
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Kopyalandı.