Konvexní konjugát - Convex conjugate

v matematika a matematická optimalizace, konvexní konjugát funkce je zobecněním Legendární transformace což platí pro nekonvexní funkce. Je také známý jako Legendre – Fenchelova transformace, Fenchelova transformacenebo Fenchelův konjugát (po Adrien-Marie Legendre a Werner Fenchel ). Umožňuje zejména dalekosáhlé zobecnění Lagrangeovy duality.

Definice

Nechat ${ displaystyle X}$ být nemovitý topologický vektorový prostor a nechte ${ displaystyle X ^ {*}}$ být dvojí prostor na ${ displaystyle X}$. Označte dvojité párování podle

${ displaystyle langle cdot, cdot rangle: X ^ {*} krát X to mathbb {R}.}$

Pro funkci

${ displaystyle f: X až mathbb {R} pohár {- infty, + infty }}$

brát hodnoty na prodloužená řada reálných čísel, konvexní konjugát

${ displaystyle f ^ {*}: X ^ {*} to mathbb {R} cup {- infty, + infty }}$

je definována z hlediska supremum podle

${ displaystyle f ^ {*} left (x ^ {*} right): = sup left { left. left langle x ^ {*}, x right rangle -f left ( x right) right | x in X right },}$

nebo ekvivalentně z hlediska infimum podle

${ displaystyle f ^ {*} left (x ^ {*} right): = - inf left { left.f left (x right) - left langle x ^ {*}, x right rangle right | x in X right }.}$

Tuto definici lze interpretovat jako kódování konvexní obal funkce epigraf pokud jde o jeho podpůrné hyperplány.^[1][2]

Příklady

Další příklady viz § Tabulka vybraných konvexních konjugátů.

• Konvexní konjugát z afinní funkce ${ displaystyle f (x) = levý langle a, x pravý rangle -b}$ je

${ displaystyle f ^ {*} left (x ^ {*} right) = { begin {cases} b, & x ^ {*} = a + infty, & x ^ {*} neq a. end {případy}}}$

• Konvexní konjugát a funkce napájení ${ displaystyle f (x) = { frac {1} {p}} | x | ^ {p}, 1$

  je

${ displaystyle f ^ {*} left (x ^ {*} right) = { frac {1} {q}} | x ^ {*} | ^ {q}, 1$

• Konvexní konjugát absolutní hodnota funkce ${ displaystyle f (x) = vlevo | x vpravo |}$ je

${ displaystyle f ^ {*} left (x ^ {*} right) = { begin {cases} 0, & left | x ^ {*} right | leq 1 infty, & left | x ^ {*} right |> 1. end {cases}}}$

• Konvexní konjugát exponenciální funkce ${ displaystyle f (x) = e ^ {x}}$ je

${ displaystyle f ^ {*} left (x ^ {*} right) = { begin {cases} x ^ {*} ln x ^ {*} - x ^ {*}, & x ^ {*} > 0 0, & x ^ {*} = 0 infty, & x ^ {*} <0. end {cases}}}$

Konvexní konjugát a Legendreova transformace exponenciální funkce se shodují kromě toho, že doména konvexního konjugátu je přísně větší, protože Legendreova transformace je definována pouze pro kladná reálná čísla.

Souvislost s očekávaným schodkem (průměrná hodnota v riziku)

Vidět například tento článek.

Nechat F označit a kumulativní distribuční funkce a náhodná proměnná  X. Pak (integrace po částech),

${ displaystyle f (x): = int _ {- infty} ^ {x} F (u) , du = operatorname {E} left [ max (0, xX) right] = x- operatorname {E} left [ min (x, X) right]}$

má konvexní konjugát

${ displaystyle f ^ {*} (p) = int _ {0} ^ {p} F ^ {- 1} (q) , dq = (p-1) F ^ {- 1} (p) + operatorname {E} left [ min (F ^ {- 1} (p), X) right] = pF ^ {- 1} (p) - operatorname {E} left [ max (0, F ^ {- 1} (p) -X) vpravo].}$

Objednávání

Transformace má určitou interpretaci

${ displaystyle f ^ { text {inc}} (x): = arg sup _ {t} t cdot x- int _ {0} ^ {1} max {tf (u), 0 } , du,}$

protože se jedná o neklesající přeskupení počáteční funkce f; zejména, ${ displaystyle f ^ { text {inc}} = f}$ pro ƒ neklesající.

Vlastnosti

Konvexní konjugát a uzavřená konvexní funkce je opět uzavřená konvexní funkce. Konvexní konjugát a polyedrická konvexní funkce (konvexní funkce s mnohostěnný epigraf ) je opět polyedrická konvexní funkce.

Obrácení objednávky

Konvexní konjugace je reverzní objednávka: pokud ${ displaystyle f leq g}$ pak ${ displaystyle f ^ {*} geq g ^ {*}}$. Tady

${ Displaystyle (f leq g): iff ( forall x, f (x) leq g (x)).}$

Pro rodinu funkcí ${ displaystyle left (f _ { alpha} right) _ { alpha}}$ vyplývá ze skutečnosti, že supremum lze zaměnit

${ displaystyle left ( inf _ { alpha} f _ { alpha} right) ^ {*} (x ^ {*}) = sup _ { alpha} f _ { alpha} ^ {*} ( x ^ {*}),}$

a od max – min nerovnost že

${ displaystyle left ( sup _ { alpha} f _ { alpha} right) ^ {*} (x ^ {*}) leq inf _ { alpha} f _ { alpha} ^ {*} (x ^ {*}).}$

Biconjugate

Konvexní konjugát funkce je vždy nižší polokontinuální. The biconjugate ${ displaystyle f ^ {**}}$ (konvexní konjugát konvexního konjugátu) je také uzavřený konvexní trup, tj. největší nižší polokontinuální konvexní funkce s ${ displaystyle f ^ {**} leq f}$. Pro správné funkce F,

${ displaystyle f = f ^ {**}}$ kdyby a jen kdyby F je konvexní a spodní polokontinuální Fenchel – Moreauova věta.

Fenchelova nerovnost

Pro jakoukoli funkci F a jeho konvexní konjugát F *, Fenchelova nerovnost (také známý jako Fenchel – Mladá nerovnost) platí pro všechny X ∈ X a str ∈ X * :

${ displaystyle left langle p, x right rangle leq f (x) + f ^ {*} (p).}$

Důkaz bezprostředně vyplývá z definice konvexního konjugátu: ${ displaystyle f ^ {*} (p) = sup _ { tilde {x}} { langle p, { tilde {x}} rangle -f ({ tilde {x}}) } geq langle p, x rangle -f (x)}$.

Konvexnost

Pro dvě funkce ${ displaystyle f_ {0}}$ a ${ displaystyle f_ {1}}$ a číslo ${ displaystyle 0 leq lambda leq 1}$ vztah konvexity

${ displaystyle left ((1- lambda) f_ {0} + lambda f_ {1} right) ^ {*} leq (1- lambda) f_ {0} ^ {*} + lambda f_ {1} ^ {*}}$

drží. The ${ displaystyle {*}}$ operace je konvexní mapování samotné.

Infimální konvoluce

The infimální konvoluce (nebo epi-součet) dvou funkcí F a G je definován jako

${ displaystyle left (f operatorname { Box} g right) (x) = inf left {f (xy) + g (y) mid y in mathbb {R} ^ {n} že jo}.}$

Nechat F₁, …, F_m být správné, konvexní a nižší polokontinuální funkce zapnuty Rⁿ. Potom je infimální konvoluce konvexní a nižší polokontinuální (ale ne nutně správná),^[3] a uspokojuje

${ displaystyle left (f_ {1} operatorname { Box} cdots operatorname { Box} f_ {m} right) ^ {*} = f_ {1} ^ {*} + cdots + f_ { m} ^ {*}.}$

Infimální konvoluce dvou funkcí má geometrický výklad: (přísný) epigraf infimální konvoluce dvou funkcí je Minkowského součet (přísných) epigrafů těchto funkcí.^[4]

Maximalizace argumentu

Pokud je funkce ${ displaystyle f}$ je diferencovatelný, pak je jeho derivací maximalizační argument při výpočtu konvexního konjugátu:

${ displaystyle f ^ { prime} (x) = x ^ {*} (x): = arg sup _ {x ^ {*}} { langle x, x ^ {*} rangle} -f ^ {*} (x ^ {*})}$ a

${ displaystyle f ^ {{*} prime} (x ^ {*}) = x (x ^ {*}): = arg sup _ {x} { langle x, x ^ {*} rangle } -f (x);}$

odkud

${ displaystyle x = nabla f ^ {*} ( nabla f (x)),}$

${ displaystyle x ^ {*} = nabla f ( nabla f ^ {*} (x ^ {*})),}$

a navíc

${ displaystyle f ^ { prime prime} (x) cdot f ^ {{*} prime prime} (x ^ {*} (x)) = 1,}$

${ displaystyle f ^ {{*} prime prime} (x ^ {*}) cdot f ^ { prime prime} (x (x ^ {*})) = 1.}$

Vlastnosti změny měřítka

Pokud pro některé ${ displaystyle gamma> 0}$, ${ displaystyle g (x) = alpha + beta x + gamma cdot f ( lambda x + delta)}$, pak

${ displaystyle g ^ {*} (x ^ {*}) = - alpha - delta { frac {x ^ {*} - beta} { lambda}} + gamma cdot f ^ {*} left ({ frac {x ^ {*} - beta} { lambda gamma}} right).}$

Chování při lineárních transformacích

Nechat A být ohraničený lineární operátor z X na Y. Pro jakoukoli konvexní funkci F na X, jeden má

${ displaystyle left (Af right) ^ {*} = f ^ {*} A ^ {*}}$

kde

${ displaystyle (Af) (y) = inf {f (x): x v X, Ax = y }}$

je předobrazem F w.r.t. A a A^* je operátor adjoint z A.^[5]

Uzavřená konvexní funkce F je symetrický vzhledem k dané množině G z ortogonální lineární transformace,

${ Displaystyle f left (Ax right) = f (x), ; pro všechny x, ; pro všechny A v G}$

právě když je jeho konvexní konjugát F^* je symetrický vzhledem k G.

Tabulka vybraných konvexních konjugátů

Následující tabulka poskytuje transformace Legendre pro mnoho běžných funkcí a také několik užitečných vlastností.^[6]

${ displaystyle g (x)}$	${ displaystyle operatorname {dom} (g)}$	${ displaystyle g ^ {*} (x ^ {*})}$	${ displaystyle operatorname {dom} (g ^ {*})}$
${ displaystyle f (sekera)}$ (kde ${ displaystyle a neq 0}$)	${ displaystyle X}$	${ displaystyle f ^ {*} vlevo ({ frac {x ^ {*}} {a}} vpravo)}$	${ displaystyle X ^ {*}}$
${ displaystyle f (x + b)}$	${ displaystyle X}$	${ displaystyle f ^ {*} (x ^ {*}) - langle b, x ^ {*} rangle}$	${ displaystyle X ^ {*}}$
${ displaystyle af (x)}$ (kde ${ displaystyle a> 0}$)	${ displaystyle X}$	${ displaystyle af ^ {*} vlevo ({ frac {x ^ {*}} {a}} vpravo)}$	${ displaystyle X ^ {*}}$
${ displaystyle alpha + beta x + gamma cdot f ( lambda x + delta)}$	${ displaystyle X}$	${ displaystyle - alpha - delta { frac {x ^ {*} - beta} { lambda}} + gamma cdot f ^ {*} left ({ frac {x ^ {*} - beta} { gamma lambda}} right) quad ( gamma> 0)}$	${ displaystyle X ^ {*}}$
${ displaystyle { frac {| x | ^ {p}} {p}}}$ (kde ${ displaystyle p> 1}$)	${ displaystyle mathbb {R}}$	${ displaystyle { frac {| x ^ {*} | ^ {q}} {q}}}$ (kde ${ displaystyle { frac {1} {p}} + { frac {1} {q}} = 1}$)	${ displaystyle mathbb {R}}$
${ displaystyle { frac {-x ^ {p}} {p}}}$ (kde ${ displaystyle 0$ )	${ displaystyle mathbb {R} _ {+}}$	${ displaystyle { frac {- (- x ^ {*}) ^ {q}} {q}}}$ (kde ${ displaystyle { frac {1} {p}} + { frac {1} {q}} = 1}$)	${ displaystyle mathbb {R} _ {-}}$
${ displaystyle { sqrt {1 + x ^ {2}}}}$	${ displaystyle mathbb {R}}$	${ displaystyle - { sqrt {1- (x ^ {*}) ^ {2}}}}$	${ displaystyle [-1,1]}$
${ displaystyle - log (x)}$	${ displaystyle mathbb {R} _ {++}}$	${ displaystyle - (1+ log (-x ^ {*}))}$	${ displaystyle mathbb {R} _ {-}}$
${ displaystyle e ^ {x}}$	${ displaystyle mathbb {R}}$	${ displaystyle { begin {cases} x ^ {*} log (x ^ {*}) - x ^ {*} & { text {if}} x ^ {*}> 0 0 & { text {if}} x ^ {*} = 0 end {cases}}}$	${ displaystyle mathbb {R} _ {+}}$
${ displaystyle log left (1 + e ^ {x} right)}$	${ displaystyle mathbb {R}}$	${ displaystyle { begin {cases} x ^ {*} log (x ^ {*}) + (1-x ^ {*}) log (1-x ^ {*}) & { text {pokud }} 0$	${ displaystyle [0,1]}$
${ displaystyle - log left (1-e ^ {x} right)}$	${ displaystyle mathbb {R} _ {-}}$	${ displaystyle { begin {cases} x ^ {*} log (x ^ {*}) - (1 + x ^ {*}) log (1 + x ^ {*}) & { text {pokud }} x ^ {*}> 0 0 & { text {if}} x ^ {*} = 0 end {cases}}}$	${ displaystyle mathbb {R} _ {+}}$

Viz také

• Duální problém
• Fenchelova věta o dualitě
• Legendární transformace
• Youngova nerovnost pro výrobky

Reference

• Arnol'd, Vladimir Igorevič (1989). Matematické metody klasické mechaniky (Druhé vydání.). Springer. ISBN  0-387-96890-3. PAN  0997295.
• Rockafellar, R. Tyrell (1970). Konvexní analýza. Princeton: Princeton University Press. ISBN  0-691-01586-4. PAN  0274683.

Další čtení

• Touchette, Hugo (2014-10-16). „Legendre-Fenchel se transformuje v kostce“ (PDF). Archivovány od originál (PDF) dne 2017-04-07. Citováno 2017-01-09.

• Touchette, Hugo (2006-11-21). "Prvky konvexní analýzy" (PDF). Archivovány od originál (PDF) dne 2015-05-26. Citováno 2008-03-26.

• „Legendre a Legendre-Fenchel se transformují v podrobném vysvětlení“. Citováno 2013-05-18.

• Ellerman, David Patterson (1995-03-21). „Kapitola 12: Paralelní sčítání, paralelní dualita série a finanční matematika“. Intelektuální překračování jako způsob života: Pokusy o filozofii, ekonomii a matematiku (PDF). Světská filozofie: studium v ​​průsečíku filozofie a ekonomiky. G - Série referenčních, informačních a interdisciplinárních předmětů (ilustrované vydání). Rowman & Littlefield Publishers, Inc. 237–268. ISBN  0-8476-7932-2. Archivováno (PDF) z původního dne 2016-03-05. Citováno 2019-08-09. [1] (271 stránek)

• Ellerman, David Patterson (Květen 2004) [1995-03-21]. „Úvod do sériově paralelní duality“ (PDF). Kalifornská univerzita v Riverside. CiteSeerX  10.1.1.90.3666. Archivováno od originálu 10. 8. 2019. Citováno 2019-08-09. [2] (24 stránek)