Dualite (optimizasyon) - Duality (optimization)

İçinde matematiksel optimizasyon teori ikilik ya da dualite ilkesi ilke optimizasyon sorunları iki perspektiften birinden görülebilir, ilk sorun ya da ikili problem. İkili sorunun çözümü, ilkel (minimizasyon) sorunun çözümüne daha düşük bir sınır sağlar.^[1] Bununla birlikte, genel olarak, birincil ve ikili problemlerin optimal değerlerinin eşit olması gerekmez. Farklarına dualite boşluğu. İçin dışbükey optimizasyon problemler, dualite açığı a altında sıfırdır kısıtlama yeterliliği şart.

İkili sorun

Genellikle "ikili problem" terimi, Lagrange ikili problemi ancak diğer ikili problemler kullanılır - örneğin, Wolfe ikili sorunu ve Fenchel ikili problemi. Lagrange dual problemi, Lagrange negatif olmayan kullanarak bir minimizasyon probleminin Lagrange çarpanları kısıtlamaları amaç fonksiyonuna eklemek ve ardından orijinal amaç fonksiyonunu en aza indiren ilk değişken değerleri için çözmek. Bu çözüm, ilk değişkenleri, ikili değişkenler olarak adlandırılan Lagrange çarpanlarının fonksiyonları olarak verir, böylece yeni problem, ikili değişkenler üzerindeki türetilmiş kısıtlamalar altında (en azından nonnegativite dahil) ikili değişkenlere göre amaç fonksiyonunu maksimize etmektir. kısıtlamalar).

Genel olarak iki verilir çift ​​çiftler nın-nin ayrılmış yerel dışbükey boşluklar ${ displaystyle sol (X, X ^ {*} sağ)}$ ve ${ displaystyle sol (Y, Y ^ {*} sağ)}$ ve işlev ${ displaystyle f: X - mathbb {R} cup {+ infty }}$, temel problemi bulmak olarak tanımlayabiliriz ${ displaystyle { şapka {x}}}$ öyle ki ${ displaystyle f ({ hat {x}}) = inf _ {x in X} f (x). ,}$Başka bir deyişle, eğer ${ displaystyle { şapka {x}}}$ var, ${ displaystyle f ({ şapka {x}})}$ ... minimum fonksiyonun ${ displaystyle f}$ ve infimum fonksiyonun (en büyük alt sınırı) elde edilir.

Kısıtlama koşulları varsa, bunlar işlevin içine yerleştirilebilir ${ displaystyle f}$ izin vererek ${ displaystyle { tilde {f}} = f + I _ { mathrm {kısıtlamalar}}}$ nerede ${ displaystyle I _ { mathrm {kısıtlamalar}}}$ uygun bir işlevdir ${ displaystyle X}$ kısıtlamalarda minimum 0 olan ve bunu kanıtlayabilen ${ displaystyle inf _ {x X'te} { tilde {f}} (x) = inf _ {x mathrm {kısıtlı}} f (x)}$. İkinci koşul, önemsiz bir şekilde, ancak her zaman uygun şekilde değil, karakteristik fonksiyon (yani ${ displaystyle I _ { mathrm {kısıtlamalar}} (x) = 0}$ için ${ displaystyle x}$ kısıtlamaları karşılamak ve ${ displaystyle I _ { mathrm {kısıtlamalar}} (x) = infty}$ aksi takdirde). Sonra uzat ${ displaystyle { tilde {f}}}$ bir tedirginlik işlevi ${ displaystyle F: X times Y - mathbb {R} cup {+ infty }}$ öyle ki ${ displaystyle F (x, 0) = { tilde {f}} (x)}$.^[2]

dualite boşluğu eşitsizliğin sağ ve sol taraflarının farkı

${ displaystyle sup _ {y ^ {*} , Y ^ {*}} - F ^ {*} (0, y ^ {*}) leq inf _ {x , X} F (x, 0), ,}$

nerede ${ displaystyle F ^ {*}}$ ... dışbükey eşlenik hem değişkenlerde hem de ${ displaystyle sup}$ gösterir üstünlük (en az üst sınır).^[2][3][4]

Dualite boşluğu

İkilik boşluğu, herhangi bir ilkel çözümün değerleri ile herhangi bir ikili çözüm arasındaki farktır. Eğer ${ displaystyle d ^ {*}}$ optimal ikili değerdir ve ${ displaystyle p ^ {*}}$ optimal birincil değerdir, bu durumda dualite boşluğu eşittir ${ displaystyle p ^ {*} - d ^ {*}}$. Bu değer her zaman 0'dan büyük veya 0'a eşittir. Dualite boşluğu sıfırdır ancak ve ancak güçlü ikilik tutar. Aksi takdirde boşluk kesinlikle olumludur ve zayıf ikilik tutar.^[5]

Hesaplamalı optimizasyonda, genellikle herhangi bir ikili çözüm ile birincil problem için uygulanabilir ancak yetersiz bir yinelemenin değeri arasındaki değer farkı olan başka bir "ikilik açığı" rapor edilir. Bu alternatif "ikilik açığı", birincil problem için mevcut uygulanabilir ancak yetersiz yinelemenin değeri ile ikili problemin değeri arasındaki tutarsızlığı nicelendirir; ikili problemin değeri, düzenlilik koşulları altında, değerin değerine eşittir. dışbükey gevşeme İlk sorunun çözümü: Dışbükey gevşeme, dışbükey olmayan uygulanabilir bir setin kapalı olanla değiştirilmesinden kaynaklanan problemdir. dışbükey örtü ve dışbükey olmayan bir işlevi dışbükey ile değiştirerek kapatma bu, sahip olan işlevdir kitabesi bu, orijinal birincil amaç fonksiyonunun kapalı dışbükey gövdesidir.^{[6][7][8][9][10][11][12][13][14][15][16]}

Doğrusal durum

Doğrusal programlama sorunlar optimizasyon hangi problemler amaç fonksiyonu ve kısıtlamalar hepsi doğrusal. Primal problemde, amaç fonksiyonu aşağıdakilerin doğrusal bir kombinasyonudur: n değişkenler. Var m kısıtlamalar, her biri bir üst sınırın doğrusal kombinasyonuna yerleştirilir. n değişkenler. Amaç, kısıtlamalara tabi olarak amaç fonksiyonunun değerini maksimize etmektir. Bir çözüm bir vektör (bir liste) n Amaç işlevi için maksimum değere ulaşan değerler.

İkili problemde, amaç işlevi aşağıdakilerin doğrusal bir kombinasyonudur: m sınırlar olan değerler m birincil problemin kısıtlamaları. Var n Her biri doğrusal bir kombinasyona bir alt sınır koyan ikili kısıtlamalar m çift ​​değişkenler.

İlkel problem ve ikili problem arasındaki ilişki

Doğrusal durumda, ilk problemde, tüm kısıtlamaları karşılayan her alt optimal noktadan, bir yön veya alt uzay Hedef işlevi artıran hareket yönleri. Herhangi bir yönde hareket etmenin, arasındaki boşluğu giderdiği söylenir. aday çözüm ve bir veya daha fazla kısıtlama. Bir olurlu Aday çözümün değeri, bir veya daha fazla kısıtlamayı aşan değerdir.

İkili problemde, ikili vektör, ilkeldeki kısıtların konumlarını belirleyen kısıtlamaları çarpar. Dual problemde dual vektörü değiştirmek, ilk problemdeki üst sınırları revize etmeye eşdeğerdir. En düşük üst sınır aranır. Yani, kısıtlamaların aday konumları ile gerçek optimum arasındaki boşluğu gidermek için ikili vektör en aza indirilir. İkili vektörün uygulanabilir olmayan bir değeri, çok düşük olanıdır. Bir veya daha fazla kısıtlamanın aday konumlarını, gerçek optimum olanı dışlayan bir konuma ayarlar.

Bu sezgi, aşağıdaki denklemler tarafından biçimlendirilir: Doğrusal programlama: Dualite.

Doğrusal olmayan durum

İçinde doğrusal olmayan programlama kısıtlamalar mutlaka doğrusal değildir. Bununla birlikte, aynı ilkelerin çoğu geçerlidir.

Doğrusal olmayan bir sorunun küresel maksimumunun kolayca tanımlanabilmesini sağlamak için, problem formülasyonu genellikle işlevlerin dışbükey olmasını ve kompakt alt düzey kümelere sahip olmasını gerektirir.

Bu önemi Karush – Kuhn – Tucker koşulları. Doğrusal olmayan programlama problemlerinin yerel optimizasyonunu belirlemek için gerekli koşulları sağlarlar. Bir yönün tanımlanmasının mümkün olması için gerekli olan ek koşullar (kısıtlama nitelikleri) vardır. en uygun çözüm. Optimal bir çözüm, yerel bir optimum olan ancak muhtemelen global bir optimum olmayan çözümdür.

Güçlü Lagrange prensibi: Lagrange ikiliği

Verilen bir doğrusal olmayan programlama standart biçimde sorun

${ displaystyle { başla {hizalı} { text {küçült}} & f_ {0} (x) { text {konu}} & f_ {i} (x) leq 0, i in sol {1, ldots, m right } & h_ {i} (x) = 0, i in left {1, ldots, p right } end {hizalı}}}$

etki alanı ile ${ displaystyle { mathcal {D}} alt küme mathbb {R} ^ {n}}$ içi boş olmayan Lagrange işlevi ${ displaystyle Lambda: mathbb {R} ^ {n} times mathbb {R} ^ {m} times mathbb {R} ^ {p} to mathbb {R}}$ olarak tanımlanır

${ displaystyle Lambda (x, lambda, nu) = f_ {0} (x) + toplamı _ {i = 1} ^ {m} lambda _ {i} f_ {i} (x) + toplam _ {i = 1} ^ {p} nu _ {i} h_ {i} (x).}$

Vektörler ${ displaystyle lambda}$ ve ${ displaystyle nu}$ denir ikili değişkenler veya Lagrange çarpanı vektörleri sorunla ilişkili. Lagrange ikili işlevi ${ displaystyle g: mathbb {R} ^ {m} times mathbb {R} ^ {p} - mathbb {R}}$ olarak tanımlanır

${ displaystyle g ( lambda, nu) = inf _ {x in { mathcal {D}}} Lambda (x, lambda, nu) = inf _ {x { mathcal { D}}} left (f_ {0} (x) + sum _ {i = 1} ^ {m} lambda _ {i} f_ {i} (x) + sum _ {i = 1} ^ {p} nu _ {i} h_ {i} (x) sağ).}$

İkili işlev g başlangıç ​​problemi dışbükey olmadığında bile içbükeydir, çünkü bu, nokta bazında afin fonksiyonların bir sonsuzudur. İkili işlev, optimum değerde daha düşük sınırlar verir ${ displaystyle p ^ {*}}$ ilk sorunun; herhangi ${ displaystyle lambda geq 0}$ Ve herhangi biri ${ displaystyle nu}$ sahibiz ${ displaystyle g ( lambda, nu) leq p ^ {*}}$.

Eğer bir kısıtlama yeterliliği gibi Slater'in durumu tutar ve asıl sorun dışbükeydir, o zaman elimizde güçlü ikilik yani ${ displaystyle d ^ {*} = max _ { lambda geq 0, nu} g ( lambda, nu) = inf f_ {0} = p ^ {*}}$.

Dışbükey problemler

Eşitsizlik kısıtlamaları olan bir dışbükey minimizasyon problemi için,

${ displaystyle { begin {align} & { underet {x} { operatorname {minimize}}} && f (x) & operatorname {subject ; to} && g_ {i} (x) leq 0, quad i = 1, ldots, m end {hizalı}}}$

Lagrange ikili problemi

${ displaystyle { begin {align} & { underet {u} { operatorname {maximize}}} && inf _ {x} left (f (x) + sum _ {j = 1} ^ {m } u_ {j} g_ {j} (x) sağ) & operatöradı {konu ; to} && u_ {i} geq 0, quad i = 1, ldots, m end {hizalı}} }$

Amaç işlevin Lagrange ikili işlevi olduğu. İşlevlerin ${ displaystyle f}$ ve ${ displaystyle g_ {1}, ldots, g_ {m}}$ sürekli türevlenebilir, en düşük, gradyan sıfıra eşit olduğunda gerçekleşir. Sorun

${ displaystyle { begin {align} & { underet {x, u} { operatorname {maximize}}} && f (x) + sum _ {j = 1} ^ {m} u_ {j} g_ {j } (x) & operatöradı {konu ; kime} && nabla f (x) + sum _ {j = 1} ^ {m} u_ {j} nabla g_ {j} (x) = 0 &&& u_ {i} geq 0, quad i = 1, ldots, m end {hizalı}}}$

Wolfe ikili problemi olarak adlandırılır. Bu problemin sayısal olarak ele alınması zor olabilir, çünkü amaç fonksiyonu ortak değişkenlerde içbükey değildir. ${ displaystyle (u, x)}$. Ayrıca eşitlik kısıtı ${ displaystyle nabla f (x) + toplamı _ {j = 1} ^ {m} u_ {j} nabla g_ {j} (x)}$ genel olarak doğrusal değildir, dolayısıyla Wolfe ikili problemi tipik olarak bir konveks olmayan optimizasyon problemidir. Her halükârda, zayıf ikilik tutar.^[17]

Tarih

Göre George Dantzig doğrusal optimizasyon için dualite teoremi tarafından varsayılmıştır John von Neumann Dantzig doğrusal programlama problemini sunduktan hemen sonra. Von Neumann, kendisinden aldığı bilgileri kullandığını kaydetti. oyun Teorisi ve iki kişilik sıfır toplamlı matris oyununun doğrusal programlamaya eşdeğer olduğunu varsaydı. Titiz kanıtlar ilk olarak 1948'de Albert W. Tucker ve grubu. (Dantzig'in Nering ve Tucker'a önsözü, 1993)

Ayrıca bakınız

• Konveks dualite
• Dualite
• Gevşeme (yaklaşım)

Notlar

Referanslar

Kitabın

• Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Ağ Akışları: Teori, Algoritmalar ve Uygulamalar. Prentice Hall. ISBN  0-13-617549-X.
• Bertsekas, Dimitri; Nedic, Angelia; Özdağlar, Asuman (2003). Konveks Analiz ve Optimizasyon. Athena Scientific. ISBN  1-886529-45-0.
• Bertsekas, Dimitri P. (1999). Doğrusal Olmayan Programlama (2. baskı). Athena Scientific. ISBN  1-886529-00-0.
• Bertsekas, Dimitri P. (2009). Konveks Optimizasyon Teorisi. Athena Scientific. ISBN  978-1-886529-31-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Sayısal optimizasyon: Teorik ve pratik yönler. Universitext (1997 Fransızca baskısının ikinci gözden geçirilmiş baskısı). Berlin: Springer-Verlag. s. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN  3-540-35445-X. BAY  2265882.CS1 bakimi: ref = harv (bağlantı)
• Aşçı, William J.; Cunningham, William H .; Pulleyblank, William R.; Schrijver, İskender (12 Kasım 1997). Kombinatoryal Optimizasyon (1. baskı). John Wiley & Sons. ISBN  0-471-55894-X.
• Dantzig, George B. (1963). Doğrusal Programlama ve Uzantılar. Princeton, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Dışbükey analiz ve minimizasyon algoritmaları, Cilt I: Temel Bilgiler. Grundlehren der Mathematischen Wissenschaften [Matematik Bilimlerinin Temel Prensipleri]. 305. Berlin: Springer-Verlag. s. xviii + 417. ISBN  3-540-56850-6. BAY  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Uygulayıcılar için "14 Dualite". Konveks analiz ve minimizasyon algoritmaları, Cilt II: Gelişmiş teori ve paket yöntemleri. Grundlehren der Mathematischen Wissenschaften [Matematik Bilimlerinin Temel Prensipleri]. 306. Berlin: Springer-Verlag. s. xviii + 346. ISBN  3-540-56852-2. BAY  1295240.
• Lasdon, Leon S. (2002) [1970 Macmillan'ın yeniden baskısı]. Büyük sistemler için optimizasyon teorisi. Mineola, New York: Dover Publications, Inc. s. Xiii + 523. ISBN  978-0-486-41999-2. BAY  1888251.CS1 bakimi: ref = harv (bağlantı)
• Lawler, Eugene (2001). "4.5. Max-Flow Min-Cut Teoreminin Kombinatoryal Etkileri, 4.6. Max-Flow Min-Cut Teoreminin Doğrusal Programlama Yorumu". Kombinatoryal Optimizasyon: Ağlar ve Matroidler. Dover. s. 117–120. ISBN  0-486-41453-1.
• Lemaréchal, Claude (2001). "Lagrange rahatlaması". Jünger'de Michael; Naddef, Denis (editörler). Hesaplamalı kombinatoryal optimizasyon: 15–19 Mayıs 2000'de Schloß Dagstuhl'da düzenlenen Bahar Okulu'ndan makaleler. Bilgisayar Bilimi Ders Notları (LNCS). 2241. Berlin: Springer-Verlag. s. 112–156. doi:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. BAY  1900016.CS1 bakimi: ref = harv (bağlantı)
• Minoux, Michel (1986). Matematiksel programlama: Teori ve algoritmalar. Egon Balas (forvet); Steven Vajda (trans) (1983 Paris: Dunod) Fransız. Chichester: Bir Wiley-Interscience Yayını. John Wiley & Sons, Ltd. s. Xxviii + 489. ISBN  0-471-90170-9. BAY  0868279. (2008 İkinci baskı, Fransızca: Programlama matematiği: Théorie ve algoritmalar, Éditions Tec & Doc, Paris, 2008. xxx + 711 s.)).CS1 bakimi: ref = harv (bağlantı)
• Nering, Evar D .; Tucker, Albert W. (1993). Doğrusal Programlama ve İlgili Sorunlar. Boston, MA: Academic Press. ISBN  978-0-12-515440-6.
• Papadimitriou, Christos H .; Steiglitz Kenneth (Temmuz 1998). Kombinatoryal Optimizasyon: Algoritmalar ve Karmaşıklık (Kısaltılmamış ed.). Dover. ISBN  0-486-40258-4.
• Ruszczyński, Andrzej (2006). Doğrusal Olmayan Optimizasyon. Princeton, NJ: Princeton University Press. sayfa xii + 454. ISBN  978-0691119151. BAY  2199043.

Nesne

• Everett, Hugh, III (1963). "Kaynakların optimum tahsisi ile ilgili problemleri çözmek için genelleştirilmiş Lagrange çarpanı yöntemi". Yöneylem Araştırması. 11 (3): 399–417. doi:10.1287 / opre.11.3.399. JSTOR  168028. BAY  0152360. Arşivlenen orijinal 2011-07-24 tarihinde.CS1 bakimi: ref = harv (bağlantı)
• Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (Ağustos 2007). "Ballstep alt gradyan yöntemleriyle Lagrange gevşemesi". Yöneylem Araştırması Matematiği. 32 (3): 669–686. doi:10.1287 / moor.1070.0261. BAY  2348241.CS1 bakimi: ref = harv (bağlantı)
• Doğrusal Programlamada Dualite Gary D. Knott