Danskinsova věta - Danskins theorem - Wikipedia

v konvexní analýza, Danskinova věta je teorém který poskytuje informace o deriváty a funkce formuláře

${ displaystyle f (x) = max _ {z v Z} phi (x, z).}$

Věta má aplikace v optimalizace, kde se někdy používá k řešení minimax problémy. Původní věta JM Danskina, uvedená v jeho monografii z roku 1967 „The Theory of Max-Min and its Applications to Weapons Allocation Problems“, Springer, NY, poskytuje vzorec pro směrovou derivaci maxima (ne nutně konvexního) směrově diferencovatelná funkce. Když je tento vzorec přizpůsoben případu konvexní funkce, poskytuje následující větu uvedenou v poněkud obecnější formě jako Propozice A.22 v roce 1971 Ph.D. Diplomová práce D. P. Bertsekase, „Řízení nejistých systémů s popisem nejistoty v členství“. Důkaz o následující verzi lze najít v knize Bertsekas „Nelineární programování“ z roku 1999 (část B.5).

Prohlášení

Věta platí pro následující situaci. Předpokládat ${ displaystyle phi (x, z)}$ je spojitá funkce ze dvou argumentů,

${ displaystyle phi: { mathbb {R}} ^ {n} krát Z rightarrow { mathbb {R}}}$

kde ${ displaystyle Z podmnožina { mathbb {R}} ^ {m}}$ je kompaktní sada. Dále předpokládejme, že ${ displaystyle phi (x, z)}$ je konvexní v ${ displaystyle x}$ pro každého ${ displaystyle z v Z}$.

Za těchto podmínek poskytuje Danskinova věta závěry týkající se konvexity a rozlišitelnost funkce

${ displaystyle f (x) = max _ {z v Z} phi (x, z).}$

Pro vyjádření těchto výsledků definujeme množinu maximalizačních bodů ${ displaystyle Z_ {0} (x)}$ tak jako

${ displaystyle Z_ {0} (x) = left {{ overline {z}}: phi (x, { overline {z}}) = max _ {z in Z} phi (x , z) vpravo }.}$

Danskinova věta pak poskytuje následující výsledky.

Konvexnost

${ displaystyle f (x)}$ je konvexní.

Směrové deriváty

The směrový derivát z ${ displaystyle f (x)}$ ve směru ${ displaystyle y}$, označeno ${ displaystyle D_ {y} f (x)}$, darováno

${ displaystyle D_ {y} f (x) = max _ {z v Z_ {0} (x)} phi '(x, z; y),}$

kde ${ displaystyle phi '(x, z; y)}$ je směrový derivát funkce ${ displaystyle phi ( cdot, z)}$ na ${ displaystyle x}$ ve směru ${ displaystyle y}$.

Derivát

${ displaystyle f (x)}$ je rozlišitelný na ${ displaystyle x}$ -li ${ displaystyle Z_ {0} (x)}$ sestává z jediného prvku ${ displaystyle { overline {z}}}$. V tomto případě derivát z ${ displaystyle f (x)}$ (nebo spád z ${ displaystyle f (x)}$ -li ${ displaystyle x}$ je vektor) je dán vztahem

${ displaystyle { frac { částečné f} { částečné x}} = { frac { částečné phi (x, { overline {z}})} { částečné x}}.}$

Subdiferenciální

Li ${ displaystyle phi (x, z)}$ je diferencovatelné s ohledem na ${ displaystyle x}$ pro všechny ${ displaystyle z v Z}$, a pokud ${ displaystyle částečné phi / částečné x}$ je kontinuální s ohledem na ${ displaystyle z}$ pro všechny ${ displaystyle x}$, pak subdiferenciální z ${ displaystyle f (x)}$ darováno

${ displaystyle partial f (x) = mathrm {conv} left {{ frac { částečné phi (x, z)} { částečné x}}: z v Z_ {0} (x) že jo}}$

kde ${ displaystyle mathrm {conv}}$ označuje konvexní obal úkon.

Rozšíření

1971 Ph.D. Diplomová práce Bertsekase ^[1] (Návrh A.22) dokazuje obecnější výsledek, který to nevyžaduje ${ displaystyle phi ( cdot, z)}$ je rozlišitelný. Místo toho to předpokládá ${ displaystyle phi ( cdot, z)}$ je rozšířená uzavřená vlastní konvexní funkce se skutečnou hodnotou pro každou z nich ${ displaystyle z}$ v kompaktní sadě ${ displaystyle Z}$, že ${ displaystyle int (dom (f))}$, vnitřek efektivní domény ${ displaystyle f}$, je neprázdné, a to ${ displaystyle phi}$ je na scéně kontinuální ${ displaystyle int (dom (f)) krát Z}$. Pak pro všechny ${ displaystyle x}$ v ${ displaystyle int (dom (f))}$, subdiferenciál ${ displaystyle f}$ na ${ displaystyle x}$ darováno

${ displaystyle částečný f (x) = mathrm {conv} levý { částečný phi (x, z): z v Z_ {0} (x) pravý }}$

kde ${ displaystyle částečné phi (x, z)}$ je subdiferenciál ${ displaystyle phi ( cdot, z)}$ na ${ displaystyle x}$ pro všechny ${ displaystyle z}$ v ${ displaystyle Z}$.

Viz také

• Věta o maximu
• Věta o obálce
• Hotellings Lemma

Reference

• Danskin, John M. (1967). Teorie Max-Min a její aplikace na problémy s alokací zbraní. NY: Springer.
• Bertsekas, Dimitri P. (1971). Řízení nejistých systémů s popisem nejistoty v členství v sadě. Cambridge, MA: disertační práce, MIT.
• Bertsekas, Dimitri P. (1999). Nelineární programování. Belmont, MA: Athena Scientific. str.737. ISBN  1-886529-00-0.