Doğrusal Olmayan Programlama

Doğrusal Olmayan Programlama (NLP) — matematiksel programlama ve yöneylem araştırmasının bir dalıdır; amaç fonksiyonunun ve/veya en az bir kısıtlamanın, karar değişkenlerinin doğrusal olmayan fonksiyonları olduğu optimizasyon problemleriyle ilgilenir.

NLP, doğrusal programlamanın bir genellemesidir ve değişkenler arasındaki ilişkilerin kesin olarak orantılı olmadığı (yani düz çizgilerle değil, eğrilerle tanımlanan) daha geniş bir gerçek sistem ve süreç sınıfının modellenmesine olanak tanır.

Konu ve Amaç

Doğrusal olmayan programlama, aşağıdaki durumlarda en uygun çözümlerin bulunmasında kullanılır:

• Yönetilen parametrelere bağlı hedef göstergenin (kâr, maliyet, verimlilik vb.) doğrusal olmayan bir ilişki sergilemesi (örneğin, ölçeğe göre azalan getiri, ikinci dereceden maliyetler).
• Kaynaklar veya teknolojik süreçler üzerindeki kısıtlamaların doğrusal olmayan bağıntılarla tanımlanması (örneğin, kimyasal reaksiyonlar, fizik yasaları, ekonomik bağımlılıklar).

NLP problemleri pek çok alanda ortaya çıkar:

• Mühendislik tasarımı (yapı ve süreç optimizasyonu).
• Ekonomi ve finans (riske göre portföy optimizasyonu, piyasa modellemesi).
• Kimya teknolojisi (reaktör çalışma koşullarının optimizasyonu).
• Machine Learning (sinir ağlarının eğitimi, destek vektör makineleri).
• Üretim süreçlerinin yönetimi. Lojistik (doğrusal olmayan maliyetler göz önünde bulundurularak).

NLP Probleminin Matematiksel Formülasyonu

Doğrusal olmayan programlamanın genel problemi şu şekilde ifade edilir:

Karar değişkenlerine ait, doğrusal olmayan amaç fonksiyonunu en büyükleyen veya en küçükleyen bir değer kümesi bulunması gerekmektedir. Bu değerlerin, eşitsizlikler (örneğin, "A büyüklüğü B'ye eşit veya küçük olmalıdır") ya da eşitlikler (örneğin, "C büyüklüğü D'ye tam olarak eşit olmalıdır") biçiminde ifade edilebilen bir kısıtlamalar sistemini sağlaması gerekmektedir. Önemli olan nokta, amacı veya kısıtlamaları tanımlayan fonksiyonlardan en az birinin doğrusal olmayan nitelik taşımasıdır. Genellikle değişkenlerin negatif olmama koşulu da eklenir; yani değerlerin sıfıra eşit veya sıfırdan büyük olması şartı aranır.

Kısıtlamaları sağlayan tüm değer kümelerinin oluşturduğu küme, uygulanabilir çözümler bölgesi (UCB) olarak adlandırılır.

Doğrusal Programlamadan Farkları

Doğrusal olmayan programlama, doğrusal programlamadan (DP) önemli ölçüde farklıdır:

• Doğrusal olmama: Amaç fonksiyonu veya kısıtlamalar (ya da her ikisi) doğrusal olmayan bağımlılıklar içerir.
• UCB'nin özellikleri: NLP'deki uygulanabilir çözümler bölgesi dışbükey olmayabilir (DP'den farklı olarak, DP'de UCB her zaman dışbükey bir çokyüzlüdür).
• Optimumun özellikleri: NLP'deki optimal çözüm, UCB'nin bir köşesinde yer almak zorunda değildir; bölgenin sınırında veya içinde olabilir. NLP'de global olmayan yerel optimumlar mevcut olabilir.
• Çözüm karmaşıklığı: NLP problemleri, genel olarak DP problemlerine kıyasla çok daha zordur. Tüm NLP problemleri için simpleks yöntemine benzer tek ve evrensel bir algoritma mevcut değildir.

NLP'nin Temel Güçlükleri ve Zorlukları

Doğrusal olmayan programlama problemlerinin çözümü bir dizi güçlükle birlikte gelir:

• Yerel ekstremumların varlığı: NLP yöntemlerinin büyük çoğunluğu yalnızca yerel bir optimumun (belirli bir komşulukta en iyi çözümün) bulunmasını garanti eder. Global optimumun (UCB'nin tamamında en iyi çözümün) aranması, özellikle dışbükey olmayan problemlerde zorlu bir görevdir.
• Dışbükeylik eksikliği: Problem dışbükey değilse (amaç fonksiyonu veya UCB dışbükey değilse), birden fazla yerel optimum bulunabilir ve standart gradyan yöntemleri bunlardan birinde "takılı" kalabilir.
• Hesaplama karmaşıklığı: NLP çözüm algoritmaları, DP'ye kıyasla genellikle çok daha fazla hesaplama kaynağı gerektirir.

NLP Problemlerinin Önemli Sınıfları

Genel karmaşıklığa karşın, etkin çözüm yöntemlerinin geliştirildiği önemli NLP alt sınıfları mevcuttur:

• Dışbükey programlama: Dışbükey bir küme üzerinde dışbükey bir fonksiyonu en küçükleme (veya içbükey bir fonksiyonu en büyükleme) problemi. Temel özellik: her yerel minimum aynı zamanda global minimumdur. Bu durum, optimal çözümün aranmasını önemli ölçüde kolaylaştırır.
• İkinci dereceden programlama: Amaç fonksiyonu ikinci dereceden, tüm kısıtlamalar ise doğrusaldır.
• Ayrılabilir programlama: Amaç fonksiyonu ve kısıtlamalar, her biri yalnızca tek bir değişkene bağlı fonksiyonların toplamı olarak ifade edilebilir.

NLP Problemlerinin Çözüm Yöntemleri

Doğrusal olmayan programlama (NLP) problemlerinin çözüm yöntemleri

I. Koşulsuz optimizasyon yöntemleri (kısıtlamasız optimizasyon):

• Gradyan yöntemleri (en dik iniş yöntemi, eşlenik gradyan yöntemi);
• Newton yöntemi ve yarı-Newton yöntemleri (örneğin, BFGS);
• Hessian yaklaşımı kullanan yöntemler.

II. Koşullu optimizasyon yöntemleri (kısıtlamalı optimizasyon):

• Dönüşüm yöntemleri:
  • Ceza fonksiyonu yöntemi (penalty methods);
  • Engel fonksiyonu yöntemi (barrier methods).
• Doğrudan yön arama yöntemleri:
  • Uygun yönler yöntemi.
• Optimallik koşullarına dayalı yöntemler:
  • Karush-Kuhn-Tucker yöntemleri (KKT koşulları);
  • Lagrange çarpanları yöntemi.
• Yinelemeli yöntemler:
  • Ardışık ikinci dereceden programlama (SQP);
  • İç nokta yöntemleri.

III. Global optimizasyon yöntemleri:

• Sezgisel ve meta-sezgisel yöntemler:
  • Genetik algoritmalar;
  • Benzetimli tavlama (simulated annealing);
  • Tabu arama (tabu search).
• Deterministik yöntemler:
  • Dal ve sınır (branch and bound);
  • Özel yapılı problemler için global optimizasyon algoritmaları.

Ayrıca bakınız

• Yöneylem araştırması
• Optimizasyon
• Doğrusal programlama
• Dışbükey programlama
• Amaç fonksiyonu
• Kısıtlamalar
• Uygulanabilir çözümler bölgesi

Kaynakça

• Bazara M., Şetti K. Doğrusal Olmayan Programlama. Teori ve Algoritmalar. — Moskova: Mir, 1982.
• Fiakko A., Mak-Kormik G. Doğrusal Olmayan Programlama. Ardışık Koşulsuz Minimizasyon Yöntemleri. — Moskova: Mir, 1972.
• Himmelblau D. Uygulamalı Doğrusal Olmayan Programlama. — Moskova: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)