Dışbükey optimizasyon - Convex optimization

Bu makalenin birden çok sorunu var. Lütfen yardım et onu geliştir veya bu konuları konuşma sayfası. (Bu şablon mesajların nasıl ve ne zaman kaldırılacağını öğrenin) Bu makale çoğu okuyucunun anlayamayacağı kadar teknik olabilir. Lütfen geliştirmeye yardım et -e uzman olmayanlar için anlaşılır hale getirinteknik detayları kaldırmadan. (Haziran 2013) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (2012 Şubat) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Dışbükey optimizasyon alt alanı matematiksel optimizasyon küçültme sorununu inceleyen dışbükey fonksiyonlar bitmiş dışbükey kümeler. Birçok dışbükey optimizasyon problemi sınıfı, polinom zaman algoritmalarını kabul eder,^[1] matematiksel optimizasyon genel olarak NP-zor.^[2][3][4]

Dışbükey optimizasyon, otomatik gibi çok çeşitli disiplinlerde uygulamalara sahiptir. kontrol sistemleri, tahmin ve sinyal işleme, iletişim ve ağlar, elektronik Devre tasarımı,^[5] veri analizi ve modelleme, finans, İstatistik (optimal deneysel tasarım ),^[6] ve yapısal optimizasyon yaklaşım kavramının verimli olduğu kanıtlanmıştır.^[7][8] Bilgi işlem alanındaki son gelişmeler ve optimizasyon algoritmaları dışbükey programlama neredeyse olduğu kadar basittir. doğrusal programlama.^[9]

Tanım

Dışbükey optimizasyon problemi, optimizasyon sorunu Amaç fonksiyonun bir dışbükey işlev ve uygulanabilir set bir dışbükey küme. Bir işlev ${ displaystyle f}$ bazı alt kümelerini eşlemek ${ displaystyle mathbb {R} ^ {n}}$içine ${ displaystyle mathbb {R} cup { pm infty }}$ Etki alanı dışbükeyse ve herkes için dışbükeydir ${ displaystyle theta in [0,1]}$ ve tüm ${ displaystyle x, y}$ kendi alanında aşağıdaki koşul geçerlidir: ${ Displaystyle f ( theta x + (1- theta) y) leq theta f (x) + (1- theta) f (y)}$. Tüm üyeler için bir S kümesi dışbükeydir ${ displaystyle x, y S’de}$ ve tüm ${ displaystyle theta in [0,1]}$bizde var $S içinde { displaystyle theta x + (1- theta) y }$.

Somut olarak, bir dışbükey optimizasyon problemi, bazılarını bulma problemidir. $C} dilinde { displaystyle mathbf {x ^ { ast}}$ ulaşmak

${ displaystyle inf {f ( mathbf {x}): mathbf {x} C }}$,

amaç işlevi nerede ${ displaystyle f: { mathcal {D}} subseteq mathbb {R} ^ {n} to mathbb {R}}$ uygun set olduğu gibi dışbükeydir ${ displaystyle C}$.^[10][11] Böyle bir nokta varsa, buna bir optimal nokta veya çözüm; tüm optimal noktalar kümesine optimum set. Eğer ${ displaystyle f}$ aşağıda sınırsızdır ${ displaystyle C}$ veya en üst düzeye ulaşılmazsa, optimizasyon sorununun sınırsız. Aksi takdirde, eğer ${ displaystyle C}$ set boşsa, sorunun şu olduğu söylenir: olurlu.^[12]

Standart biçim

Dışbükey optimizasyon sorunu var standart biçim olarak yazılırsa

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

nerede $mathbb {R} ^ {n}} içinde { displaystyle mathbf {x}$ optimizasyon değişkeni, işlev ${ displaystyle f: { mathcal {D}} subseteq mathbb {R} ^ {n} to mathbb {R}}$ dışbükey ${ displaystyle g_ {i}: mathbb {R} ^ {n} - mathbb {R}}$, ${ displaystyle i = 1, ldots, m}$, dışbükeydir ve ${ displaystyle h_ {i}: mathbb {R} ^ {n} - mathbb {R}}$, ${ displaystyle i = 1, ldots, p}$, vardır afin.^[12] Bu gösterim, bulma sorununu açıklar $mathbb {R} ^ {n}} içinde { displaystyle mathbf {x}$ en aza indiren ${ displaystyle f ( mathbf {x})}$ hepsinin arasından ${ displaystyle mathbf {x}}$ doyurucu ${ displaystyle g_ {i} ( mathbf {x}) leq 0}$, ${ displaystyle i = 1, ldots, m}$ ve ${ displaystyle h_ {i} ( mathbf {x}) = 0}$, ${ displaystyle i = 1, ldots, p}$. İşlev ${ displaystyle f}$ sorunun nesnel işlevi ve işlevleri ${ displaystyle g_ {i}}$ ve ${ displaystyle h_ {i}}$ kısıtlama fonksiyonlarıdır.

Uygulanabilir set ${ displaystyle C}$ optimizasyon probleminin tamamı tüm noktalardan oluşur ${ mathcal {D}}} içinde { displaystyle mathbf {x}$ kısıtlamaları karşılamak. Bu set dışbükeydir çünkü ${ displaystyle { mathcal {D}}}$ dışbükey alt düzey kümeleri Dışbükey fonksiyonlar dışbükeydir, afin kümeler dışbükeydir ve dışbükey kümelerin kesişimi dışbükeydir.^[13]

Dışbükey optimizasyon problemine çözüm herhangi bir noktadır ${ displaystyle mathbf {x} C}$ ulaşmak ${ displaystyle inf {f ( mathbf {x}): mathbf {x} C }}$. Genel olarak, bir dışbükey optimizasyon probleminin sıfır, bir veya birçok çözümü olabilir.

Birçok optimizasyon problemi, bu standart formda eşdeğer şekilde formüle edilebilir. Örneğin, en üst düzeye çıkarma sorunu içbükey işlev ${ displaystyle f}$ dışbükey işlevi en aza indirme sorunu olarak eşdeğer şekilde yeniden formüle edilebilir ${ displaystyle -f}$. Bir dışbükey küme üzerinde bir içbükey işlevi maksimize etme problemi, genellikle bir dışbükey optimizasyon problemi olarak adlandırılır.

Özellikleri

Aşağıdakiler, dışbükey optimizasyon problemlerinin kullanışlı özellikleridir:^[14][12]

• her yerel minimum bir küresel minimum;
• optimum küme dışbükeydir;
• amaç işlevi ise kesinlikle konveks ise, problemin en fazla bir optimal noktası vardır.

Bu sonuçlar, dışbükey minimizasyon teorisi tarafından geometrik kavramlarla birlikte kullanılır. fonksiyonel Analiz (Hilbert boşluklarında) gibi Hilbert projeksiyon teoremi, hiper düzlem teoremini ayırma, ve Farkas 'lemma.

Belirsizlik Analizi

Ben-Hain ve Elishakoff^[15] (1990), Elishakoff et al.^[16] (1994) dışbükey analizi uyguladı model belirsizliği.

Örnekler

Aşağıdaki problem sınıflarının tümü dışbükey optimizasyon problemleridir veya basit dönüşümlerle konveks optimizasyon problemlerine indirgenebilir:^[12][17]

Dışbükey optimizasyon problemleri hiyerarşisi. (LP: doğrusal program, QP: ikinci dereceden program, SOCP ikinci dereceden koni programı, SDP: yarı sonsuz program, CP: koni programı.)

• En küçük kareler
• Doğrusal programlama
• Dışbükey ikinci dereceden küçültme doğrusal kısıtlamalarla
• Dışbükey ikinci dereceden kısıtlamalarla ikinci dereceden küçültme
• Konik optimizasyon
• Geometrik programlama
• İkinci dereceden koni programlama
• Yarı belirsiz programlama
• Entropi maksimizasyonu uygun kısıtlamalarla

Lagrange çarpanları

Bir maliyet fonksiyonu tarafından standart formda verilen bir dışbükey küçültme problemini düşünün ${ displaystyle f (x)}$ ve eşitsizlik kısıtlamaları ${ displaystyle g_ {i} (x) leq 0}$ için ${ displaystyle 1 leq i leq m}$. Sonra alan ${ displaystyle { mathcal {X}}}$ dır-dir:

${ displaystyle { mathcal {X}} = sol {x in X vert g_ {1} (x), ldots, g_ {m} (x) leq 0 sağ }.}$

Sorunun Lagrangian işlevi

${ displaystyle L (x, lambda _ {0}, lambda _ {1}, ldots, lambda _ {m}) = lambda _ {0} f (x) + lambda _ {1} g_ {1} (x) + cdots + lambda _ {m} g_ {m} (x).}$

Her nokta için ${ displaystyle x}$ içinde ${ displaystyle X}$ en aza indiren ${ displaystyle f}$ bitmiş ${ displaystyle X}$gerçek sayılar var ${ displaystyle lambda _ {0}, lambda _ {1}, ldots, lambda _ {m},}$ aranan Lagrange çarpanları, bu koşulları aynı anda karşılayan:

1. ${ displaystyle x}$ küçültür ${ displaystyle L (y, lambda _ {0}, lambda _ {1}, ldots, lambda _ {m})}$ her şeyden önce $X'te { displaystyle y ,}$
2. ${ displaystyle lambda _ {0}, lambda _ {1}, ldots, lambda _ {m} geq 0,}$ en az biriyle ${ displaystyle lambda _ {k}> 0,}$
3. ${ displaystyle lambda _ {1} g_ {1} (x) = cdots = lambda _ {m} g_ {m} (x) = 0}$ (tamamlayıcı gevşeklik).

"Kesinlikle uygulanabilir bir nokta", yani bir nokta varsa ${ displaystyle z}$ doyurucu

${ displaystyle g_ {1} (z), ldots, g_ {m} (z) <0,}$

daha sonra yukarıdaki ifade bunu gerektirecek şekilde güçlendirilebilir ${ displaystyle lambda _ {0} = 1}$.

Tersine, eğer bazıları ${ displaystyle x}$ içinde ${ displaystyle X}$ (1) - (3) 'ü karşılar skaler ${ displaystyle lambda _ {0}, ldots, lambda _ {m}}$ ile ${ displaystyle lambda _ {0} = 1}$ sonra ${ displaystyle x}$ minimize edeceği kesindir ${ displaystyle f}$ bitmiş ${ displaystyle X}$.

Algoritmalar

Dışbükey optimizasyon problemleri aşağıdaki çağdaş yöntemlerle çözülebilir:^[18]

• Paket yöntemleri (Wolfe, Lemaréchal, Kiwiel) ve
• Alt gradyan projeksiyonu yöntemler (Polyak),
• İç nokta yöntemleri,^[1] kullanan kendi kendine uyumlu bariyer fonksiyonları ^[19] ve kendi kendini düzenleyen bariyer fonksiyonları.^[20]
• Kesme düzlemi yöntemleri
• Elipsoid yöntemi
• Alt gradyan yöntemi
• İkili alt gradyanlar ve drift-plus-ceza yöntemi

Alt gradyan yöntemleri basitçe uygulanabilir ve bu nedenle yaygın olarak kullanılır.^[21] İkili alt gradyan yöntemleri, bir ikili problem. drift-plus-ceza yöntem ikili alt gradyan yöntemine benzer, ancak birincil değişkenlerin bir zaman ortalamasını alır.

Uzantılar

Dışbükey optimizasyonun uzantıları aşağıdakilerin optimizasyonunu içerir: bikonveks, sözde dışbükey, ve yarı konveks fonksiyonlar. Teorisinin uzantıları dışbükey analiz ve konveks olmayan minimizasyon problemlerini yaklaşık olarak çözmek için yinelemeli yöntemler genelleştirilmiş dışbükeylik, soyut dışbükey analiz olarak da bilinir.

Ayrıca bakınız

• Dualite
• Karush – Kuhn – Tucker koşulları
• Optimizasyon sorunu
• Proksimal gradyan yöntemi

Notlar

Referanslar

• Bertsekas, Dimitri P .; Nedic, Angelia; Özdağlar, Asuman (2003). Konveks Analiz ve Optimizasyon. Belmont, MA.: Athena Scientific. ISBN  978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Konveks Optimizasyon Teorisi. Belmont, MA.: Athena Scientific. ISBN  978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Konveks Optimizasyon Algoritmaları. Belmont, MA.: Athena Scientific. ISBN  978-1-886529-28-1.

• Boyd, Stephen P .; Vandenberghe, Lieven (2004). Dışbükey Optimizasyon (PDF). Cambridge University Press. ISBN  978-0-521-83378-3. Alındı 15 Ekim 2011.

• Borwein, Jonathan ve Lewis, Adrian. (2000). Konveks Analiz ve Doğrusal Olmayan Optimizasyon. Springer.
• Christensen, Peter W .; Anders Klarbring (2008). Yapısal optimizasyona giriş. 153. Springer Science & Business Media. ISBN  9781402086663.

• Hiriart-Urruty, Jean-Baptiste ve Lemaréchal, Claude. (2004). Konveks analizin temelleri. Berlin: Springer.
• 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 İlkeleri]. 305. Berlin: Springer-Verlag. s. xviii + 417. ISBN  978-3-540-56850-6. BAY  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konveks analiz ve minimizasyon algoritmaları, Cilt II: Gelişmiş teori ve paket yöntemleri. Grundlehren der Mathematischen Wissenschaften [Matematik Bilimlerinin Temel İlkeleri]. 306. Berlin: Springer-Verlag. s. xviii + 346. ISBN  978-3-540-56852-0. BAY  1295240.
• Kiwiel, Krzysztof C. (1985). Farklılaşamayan Optimizasyon için Alçalma Yöntemleri. Matematikte Ders Notları. New York: Springer-Verlag. ISBN  978-3-540-15642-0.
• Lemaréchal, Claude (2001). "Lagrange rahatlaması". Michael Jünger ve Denis Naddef'de (ed.). Hesaplamalı kombinatoryal optimizasyon: Schloß Dagstuhl'da düzenlenen Bahar Okulundan makaleler, 15–19 Mayıs 2000. Bilgisayar Bilimlerinde Ders Notları. 2241. Berlin: Springer-Verlag. s. 112–156. doi:10.1007/3-540-45586-8_4. ISBN  978-3-540-42877-0. BAY  1900016. S2CID  9048698.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Konveks Programlamada İç Nokta Polinom Yöntemleri. SIAM.
• Nesterov, Yurii. (2004). Dışbükey Optimizasyona Giriş Dersleri, Kluwer Academic Publishers
• Rockafellar, R. T. (1970). Dışbükey analiz. Princeton: Princeton Üniversitesi Yayınları.

• Ruszczyński, Andrzej (2006). Doğrusal Olmayan Optimizasyon. Princeton University Press.
• Schmit, L.A .; Fleury, C. 1980: Yaklaşım kavramlarını ve ikili yöntemleri birleştirerek yapısal sentez. J. Amer. Inst. Balon pilotu. Astronot 18, 1252-1260

Dış bağlantılar

• EE364a: Dışbükey Optimizasyon I ve EE364b: Dışbükey Optimizasyon II Stanford kursu ana sayfaları
• 6.253: Konveks Analiz ve Optimizasyon, bir MIT OCW kursu ana sayfası
• Brian Borchers, Dışbükey optimizasyon yazılımına genel bakış