Konikni optimallashtirish - Conic optimization

Ushbu maqola umumiy ro'yxatini o'z ichiga oladi ma'lumotnomalar, lekin bu asosan tasdiqlanmagan bo'lib qolmoqda, chunki unga mos keladigan etishmayapti satrda keltirilgan. Iltimos yordam bering takomillashtirish tomonidan ushbu maqola tanishtirish aniqroq iqtiboslar. (2011 yil oktyabr) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Konikni optimallashtirish ning subfildidir qavariq optimallashtirish minimallashtirishdan iborat muammolarni o'rganadigan konveks funktsiyasi an chorrahasi ustida affin subspace va a qavariq konus.

Konusni optimallashtirish muammolari sinfiga eng yaxshi ma'lum bo'lgan konveks optimallashtirish muammolari sinflari kiradi chiziqli va semidefinite dasturlash.

Ta'rif

Berilgan haqiqiy vektor maydoni X, a qavariq, haqiqiy qadrli funktsiya

${displaystyle f: C o mathbb {R}}$

a da aniqlangan qavariq konus ${displaystyle Csubset X}$va affin subspace ${displaystyle {mathcal {H}}}$ to'plami bilan belgilanadi afine cheklovlar ${displaystyle h_ {i} (x) = 0}$, konusni optimallashtirish muammosi nuqta topishdir ${displaystyle x}$ yilda ${displaystyle Ccap {mathcal {H}}}$ buning uchun raqam ${displaystyle f (x)}$ eng kichigi.

Misollari ${displaystyle C}$ ijobiyni o'z ichiga oladi orthant ${displaystyle mathbb {R} _ {+} ^ {n} = left {xin mathbb {R} ^ {n} :, xgeq mathbf {0} ight}}$, ijobiy yarim cheksiz matritsalar ${displaystyle mathbb {S} _ {+} ^ {n}}$, va ikkinchi darajali konus ${displaystyle left {(x, t) in mathbb {R} ^ {n} imes mathbb {R}: lVert xVert leq tight}}$. Ko'pincha ${displaystyle f}$ chiziqli funktsiya bo'lib, u holda konusni optimallashtirish muammosi a ga kamayadi chiziqli dastur, a semidefinite dasturi va a ikkinchi darajali konus dasturi navbati bilan.

Ikkilik

Konusni optimallashtirish muammolarining ayrim maxsus holatlarida ularning ikki tomonlama muammolarining sezilarli yopiq ifodalari mavjud.

Konik LP

Konusning chiziqli dasturining duali

minimallashtirish ${displaystyle c ^ {T} x}$

uchun mavzu ${displaystyle Ax = b, xin C}$

bu

maksimal darajaga ko'tarish ${displaystyle b ^ {T} y}$

uchun mavzu ${displaystyle A ^ {T} y + s = c, sin C ^ {*}}$

qayerda ${displaystyle C ^ {*}}$ belgisini bildiradi ikkita konus ning ${displaystyle C}$.

Konusning chiziqli dasturlashida zaif ikkilik mavjud bo'lsa-da, kuchli ikkilik shart emas.^[1]

Semidefinite dasturi

Yarimfinitli dasturning tengsizlik ko'rinishidagi duali

minimallashtirish ${displaystyle c ^ {T} x}$

uchun mavzu ${displaystyle x_ {1} F_ {1} + cdots + x_ {n} F_ {n} + Gleq 0}$

tomonidan berilgan

maksimal darajaga ko'tarish ${displaystyle mathrm {tr} (GZ)}$

uchun mavzu ${displaystyle mathrm {tr} (F_ {i} Z) + c_ {i} = 0, to'rtlik i = 1, nuqta, n}$

${displaystyle Zgeq 0}$

Adabiyotlar

Tashqi havolalar

• Boyd, Stiven P.; Vandenberghe, Liven (2004). Qavariq optimallashtirish (pdf). Kembrij universiteti matbuoti. ISBN  978-0-521-83378-3. Olingan 15 oktyabr, 2011.
• MOSEK Konusni optimallashtirish muammolarini hal qilishga qodir dasturiy ta'minot.