İçeriğe atla
Arama sonuçlarına dön

Sağlam Optimizasyon — En Kötü Durum Matematiksel Programlama

Ortaya koyan
Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
Yıl
1970s theoretical roots; modern tractable form from late 1990s–2004
Tür
Mathematical programming framework

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Sağlam optimizasyon, parametre değerlerinin tam olarak bilindiğini varsaymak yerine, önceden tanımlanmış bir belirsizlik kümesi içindeki her senaryoda kabul edilebilir şekilde performans gösteren kararlar bulan, 1990'ların sonlarında Ben-Tal ve Nemirovski tarafından biçimlendirilen ve Bertsimas ve Sim (2004) tarafından geniş ölçüde çözülebilir hale getirilen bir matematiksel programlama çerçevesidir.

Tek bir beklenen sonuç için optimizasyon yapmak yerine, belirsiz verilerin tüm olası gerçekleşmeleri üzerinden en kötü durum hedefini en aza indirir.

Yöntemin mantığı

Sıradan optimizasyon size verdiğiniz sayılara güvenir. Sağlam optimizasyon şunu sorar: ya bu sayılar yanlışsa — belirli bir sınırlı aralıkta? Bu aralık içindeki en kötü olası girdiyi doğa seçtiğinde en az zarar veren kararı bulur. Bunu, ortalama yüke değil, en ağır güvenilir yüke dayanacak bir köprü tasarlamak gibi düşünün; kötü durumda bir garanti karşılığında tipik durumda mütevazı bir performans maliyetini kabul eder.

Tarih

Sağlam optimizasyonun teorik kökleri Soyster'a (1971) ve Wald'ın (1945) minimax karar teorisine dayanmaktadır. Alan, 1997'den itibaren bir dizi makalede Arkadi Nemirovski ve Aharon Ben-Tal tarafından modern, çözülebilir bir temel üzerine oturtulmuş ve 2009'daki El Ghaoui ile birlikte yazdıkları monograflarıyla doruğa ulaşmıştır. Dimitris Bertsimas ve Melvyn Sim (2004), nominal problemin doğrusalığını koruyan bütçe-belirsizlik (polihedral) formülasyonunu tanıtmış ve sağlam doğrusal programlamayı geniş çapta erişilebilir hale getirmiştir. O zamandan beri, sağlam optimizasyon tamsayı programlarını, iki aşamalı formülasyonları ve geçmiş gözlemlerden türetilen veri odaklı belirsizlik kümelerini kapsayacak şekilde genişlemiştir.

Ne zaman kullanılır?

Sağlam optimizasyon, parametre belirsizliği sınırlı ancak dağılımı bilinmeyen veya güvenilmez olduğunda, en kötü durum garantilerinin gerektiği durumlarda (güvenlik-kritik veya düzenleyici bağlamlar) ve stokastik programlamadaki gibi bir politika dağılımı yerine uygulanabilir tek bir karar gerektiğinde uygundur. Sürekli karar değişkenleriyle çalışır. Minimum örneklem boyutu gereksinimi yoktur — belirsizlik kümesi analitik olarak tanımlanır, verilerden tahmin edilmez. Belirsizlik sınırsız olduğunda, belirsiz parametreler için bir olasılık dağılımı mevcut ve doğru olduğunda (bunun yerine stokastik optimizasyon kullanın) veya senaryo tabanlı doğrulama için yaklaşık 1.000 senaryo değerlendirmesinden daha azı mümkün olduğunda uygun değildir.

Sınırlar ve dikkat edilmesi gerekenler

  • Çözüm zorunlu olarak nominal optimumdan daha tutucudur; belirsizlik kümesi büyük olduğunda sağlamlığın fiyatı önemli olabilir.
  • Gerçekçi bir belirsizlik kümesi tanımlamak alan bilgisi gerektirir; kötü seçilmiş bir küme ya çok tutucu olabilir ya da gerçek pertürbasyonları kapsamayabilir.
  • Dışbükey olmayan problemler veya genel karma tamsayı programları için, sağlam yeniden formülasyonlar NP-zor olabilir ve özel ayrıştırma algoritmaları gerektirebilir.
  • Sağlam optimizasyon olasılık bilgisini içermez; güvenilir bir dağılım mevcut olduğunda, stokastik programlama daha yüksek beklenen performans sağlayabilir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Belirsiz parametreler için bir olasılık dağılımı gerektirmeden deterministik en kötü durum garantileri sağlar.
  • Dışbükey belirsizlik kümeleri için yeniden formülasyonlar genellikle nominal problem kadar çözülebilirdir — ek hesaplama patlaması olmaz.
  • Tutuculuk seviyesi, belirsizlik kümesinin boyutu ve şekli aracılığıyla doğrudan kontrol edilebilir, bu da sağlamlık-performans ödünleşimini açık ve şeffaf hale getirir.
  • Çeşitli alanlarda uygulanabilir — tedarik zinciri, finans, mühendislik tasarımı, enerji sistemleri — sınırlı parametre belirsizliğinin olduğu her yerde.

Uygulama alanları

  • Belirsiz talep ve teslim süreleri altında tedarik zinciri ve lojistik ağ tasarımı.
  • Varlık getirilerindeki belirsizlik altında portföy optimizasyonu — sağlam ortalama-varyans sınırı.
  • İmalat toleranslarının parametre belirsizliği yarattığı mühendislik tasarımı (yapısal, mekanik, havacılık).
  • Belirsiz yenilenebilir üretim ve yakıt fiyatları altında enerji sistemleri planlaması.
  • İşlem sürelerinin veya seyahat sürelerinin tam olarak bilinmediği çizelgeleme ve rotalama problemleri.

Nasıl çalışır?

Nasıl çalışır?

1

Analist bir belirsizlik kümesi belirtir — nominal parametre değerleri etrafındaki olası pertürbasyonların bölgesi. Yaygın şekiller arasında kutu (her parametre bir aralıkta bağımsız olarak değişir), elipsoidal (pertürbasyonlar Öklid normunda sınırlıdır), polihedral ve bütçe kısıtlı (Bertsimas-Sim) kümeler bulunur. Seçim, belirsizliğin ne kadar ilişkili ve şiddetli olabileceğine dair bir varsayımı kodlar ve sonuçta ortaya çıkan çözümün tutuculuğunu doğrudan kontrol eder.

2

Optimizasyon problemi minimax biçiminde ifade edilir: kararlar üzerinden, düşmanca belirsizliğin empoze edebileceği maksimum maliyeti en aza indirme. Biçimsel olarak, hedef, belirsizlik kümesi U'daki tüm u'lar için geçerli olması gereken kısıtlamalar altında min_x max_{u in U} f(x, u) olur. Bu iç maksimizasyon, doğanın belirsiz parametrelerin en kötü gerçekleşmesini seçmesini modeller.

3

Dışbükey belirsizlik kümeleri için minimax problemi analitik olarak deterministik bir dışbükey programa eşdeğerdir — elipsoidal kümeler için genellikle ikinci dereceden konik program veya polihedral kümeler için doğrusal program. Bu çözülebilir yeniden formülasyon, Ben-Tal ve Nemirovski'nin temel anlayışıdır: birçok klasik problemin sağlam karşılıkları, nominal problemi çözmekten daha zor değildir. Dışbükey olmayan yapılar için Benders ayrıştırması, problemi ustabaşı ve düşmanca alt problem olarak böler ve bunları iteratif olarak çözer.

4

Yeniden formüle edilen deterministik program standart bir dışbükey veya karma tamsayı çözücüye iletilir. Yeniden formülasyon tipik olarak konik veya doğrusal bir program olduğundan, hazır çözücüler bunu verimli bir şekilde işler. Çözücü, belirsizlik kümesindeki tüm senaryolarda geçerli ve tama yakın bir çözüm olan tek bir karar vektörü — sağlam optimal çözüm — döndürür.

5

Analist, sağlamlığın fiyatını inceler: nominal optimal hedef değer (belirsizlik yok) ile sağlam optimal değer arasındaki fark. Sıkı bir belirsizlik kümesi küçük bir fark ancak daha zayıf garantiler verir; büyük bir küme tipik durumda daha yüksek performans maliyetiyle güçlü en kötü durum koruması sağlar. Belirsizlik kümesi boyutuna ilişkin duyarlılık analizi, tutuculuk seviyesinin nihai seçimini yönlendirir.

Sık yapılan hatalar

  • Aşırı büyük bir belirsizlik kümesi seçmek, pratik olarak işe yaramaz derecede tutucu çözümler üretir — küme boyutunu alan bilgisi veya geçmiş değişkenlik sınırlarına göre ayarlayın.
  • Sağlam optimizasyonu stokastik optimizasyonla karıştırmak: belirsiz parametreler için bir olasılık dağılımı iyi kurulmuş ve güveniliyorsa, stokastik programlama muhtemelen daha uygundur.
  • Belirsizliğin gerçekten sınırsız olduğu durumlarda sağlam optimizasyon uygulamak en kötü durum garantisini geçersiz kılar — sağlam optimizasyon sınırlı pertürbasyonları varsayar.
  • Çözümden sonra sağlamlığın fiyatını incelemeyi ihmal etmek: nominal ve sağlam hedefler arasındaki büyük fark, belirsizlik kümesinin gerçekçi olmayan bir şekilde geniş olabileceğini ve yeniden gözden geçirilmesi gerektiğini gösterir.

Sık sorulan sorular

Sağlam optimizasyon stokastik programlamadan nasıl farklıdır?

Sağlam optimizasyon, bu senaryolar üzerinde herhangi bir olasılık dağılımı varsaymadan, sınırlı bir belirsizlik kümesindeki her senaryo için geçerli ve tama yakın tek bir karar arar. Stokastik programlama, beklenen performansı optimize etmek için bilinen (veya tahmin edilen) bir olasılık dağılımı kullanır, tipik olarak tek bir sabit çözüm yerine bir politika veya geri çağrı eylemleri üretir. En kötü durum garantilerinin önemli olduğu ve güvenilir bir dağılımın mevcut olmadığı durumlarda sağlam optimizasyonu; iyi bir dağılımın bilindiği ve ortalama performansın birincil kriter olduğu durumlarda stokastik programlamayı seçin.

Sağlamlığın fiyatı nedir?

Sağlamlığın fiyatı, belirsizliği hesaba katmadan elde edilen nominal optimal çözüme kıyasla (bir minimizasyon problemi için) hedef değerdeki artıştır. Bertsimas ve Sim (2004), kendi bütçe-belirsizlik formülasyonları için bu fiyatın yalnızca belirsiz parametre sayısının karekökü olarak büyüdüğünü göstermişlerdir, bu da onu pratikte mütevazı kılmaktadır. Çözümden sonra bu farkı incelemek esastır: eğer çok büyükse, belirsizlik kümesi muhtemelen aşırı tutucudur ve yeniden gözden geçirilmelidir.

Hangi belirsizlik kümesi şeklini seçmeliyim?

Kutu kümeleri en basit ve en tutucusudur — her parametre bağımsız olarak değişir. Elipsoidal kümeler (Ben-Tal & Nemirovski), Öklid normunda sınırlı ilişkili pertürbasyonları modeller ve ikinci dereceden konik programlara yol açar. Polihedral / bütçe kısıtlı kümeler (Bertsimas & Sim), aynı anda sapabilecek parametre sayısını kontrol eder, doğrusalığı korur ve tutuculuğu azaltır. Pertürbasyonların nasıl birlikte ortaya çıktığına dair alan bilgisine ve hangi çözücü sınıfının mevcut olduğuna göre seçin.

Sağlam optimizasyon tamsayı karar değişkenlerini işleyebilir mi?

Evet, ancak sağlam tamsayı ve karma tamsayı programlama önemli ölçüde daha zordur. Karma tamsayı doğrusal programların sağlam karşılıkları genellikle en kötü durumda NP-zor'dur. Benders ayrıştırması ve sütun-ve-kısıtlama üretme algoritmaları standart yaklaşımlardır, ancak problem boyutu ve belirsizlik kümesi karmaşıklığı yönetilebilir tutulmalıdır.

İlgili yöntemler

Kaynaklar

  1. Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.

    ISBN: 9780691143682
    Kopyalandı.
  2. Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.

    DOI kaynağını aç
    Kopyalandı.