Asymptotická funkce

V matematice a přesněji v konvexní analýze je asymptotická funkce (nebo funkce recese ) funkce spojená s konvexní funkcí a definovaná z ní, jejímž cílem je popsat její chování do nekonečna. Často si toho všimneme . Asymptotickou funkci definujeme jejím epigrafem, který je asymptotickým kuželem epigrafu . F{\ displaystyle f}F∞{\ displaystyle f ^ {\ infty}}F∞{\ displaystyle f ^ {\ infty}}F{\ displaystyle f}

Výpočet a zkoumání asymptotické funkce může někdy zjistit, zda má konvexní funkce neprázdnou a omezenou sadu minimalizátorů; lze skutečně stanovit nezbytné a dostatečné podmínky, pokud jde o asymptotickou funkci.

Pojem asymptotické funkce lze definovat také pro nekonvexní funkce.

Zápisy a definice

V tomto článku předpokládáme, že jde o skutečný vektorový prostor konečné dimenze . Všimli jsme si E{\ displaystyle E}

• VSÓneproti¯⁡(E){\ displaystyle \ operatorname {C {\ overline {onv}}} (E)}množina funkcí in ℝ, které jsou konvexní (tj. konvexní epigraf ), vlastní (tj. neberou hodnotu a nejsou identicky stejné ) a „uzavřené“ (tj. polokontinuální v horším směru , nebo znovu uzavřeného epigrafu ).E{\ displaystyle E}-∞{\ displaystyle - \ infty} +∞{\ displaystyle + \ infty}

Epigraf funkce je uzavřený neprázdný konvex . Můžeme tedy uvažovat o jeho asymptotickém kuželu . Můžeme ukázat, že se jedná o epigraf funkce, která je podle definice asymptotickou funkcí . uchoF{\ displaystyle \ operatorname {epi} \, f}F∈VSÓneproti¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}E×R{\ displaystyle E \ times \ mathbb {R}}(uchoF)∞{\ displaystyle (\ operatorname {epi} \, f) ^ {\ infty}}F{\ displaystyle f}

Asymptotická funkce  -  Asymptotická funkce funkce je funkce definovaná symbolem F∈VSÓneproti¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}F∞∈VSÓneproti¯⁡(E){\ displaystyle f ^ {\ infty} \ v \ operatorname {C {\ overline {onv}}} (E)}

ucho(F∞)=(uchoF)∞.{\ displaystyle \ operatorname {epi} \, (f ^ {\ infty}) = (\ operatorname {epi} \, f) ^ {\ infty}.}

Někteří autoři definují asymptotickou funkci konvexních funkcí, které nemusí být nutně uzavřeny; toto mírné rozšíření má okrajovou užitečnost.

Vlastnosti

Definice asymptotické funkce nám říká málo o tom, jak vypočítat tuto funkci a její význam. Následující vlastnost umožňuje propojení mezi , pro a diferenciální kvocient F∞(d){\ displaystyle f ^ {\ infty} (d)}d∈E{\ displaystyle d \ v E}

q(t): =F(X+td)-F(X)t.{\ displaystyle q (t): = {\ frac {f (x + td) -f (x)} {t}}.}

Víme, že pokud je konvexní, zvyšuje se a že hranice, kdy je směrovou derivací , někdy nazývanou ve smyslu Diniho . Následující výsledek nás učí zejména, že limitem kdy je hodnota asymptotické funkce. F{\ displaystyle f}t∈]0,∞[↦q(t){\ displaystyle t \ in {] 0, \ infty [} \ mapsto q (t)}q{\ displaystyle q}t↓0{\ displaystyle t \ downarrow 0} F′(X;d){\ displaystyle f '(x; d)}q{\ displaystyle q}t→∞{\ displaystyle t \ to \ infty}d{\ displaystyle d}

Asymptotická funkce  -  Buď . Tak F∈VSÓneproti¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}

1. ∀X∈{\ displaystyle \ forall \, x \ in}dom a :F{\ displaystyle f}∀d∈E{\ displaystyle \ forall \, d \ v E}F∞(d)=limt→+∞F(X+td)-F(X)t,{\ displaystyle f ^ {\ infty} (d) = \ lim _ {t \ to + \ infty} {\ frac {f (x + td) -f (x)} {t}},}
2. domF∞⊂(domF)∞{\ displaystyle \ operatorname {dom} \, f ^ {\ infty} \ podmnožina (\ operatorname {dom} \, f) ^ {\ infty}},
3. F∞{\ displaystyle f ^ {\ infty}}je podmořský .

Několik poznámek k tomuto výsledku.

• Protože je také napsán vzorec z bodu 1F(X)∈R{\ displaystyle f (x) \ in \ mathbb {R}}F∞(d)=limt→+∞F(X+td)t,{\ displaystyle f ^ {\ infty} (d) = \ lim _ {t \ to + \ infty} {\ frac {f (x + td)} {t}},}s kvocientem, který na rozdíl od rozdílového kvocientu nemusí být nutně monotónní .F(X+td)/t{\ displaystyle f (x + td) / t}t{\ displaystyle t}
• Použití vzorce z bodu 1 nebo výše diskutovaného je často nejrychlejší způsob, jak vypočítat hodnotu asymptotické funkce v jednom směru . Trvejme na tom, že limit diferenciálního kvocientu nezávisí na bodě zvoleném v doméně .d{\ displaystyle d}X{\ displaystyle x}F{\ displaystyle f}
• Předchozí vzorec ukazuje, že pokud má ve směru asymptotu , je sklon. Jinak .F{\ displaystyle f}d{\ displaystyle d}F∞(d){\ displaystyle f ^ {\ infty} (d)}F∞(d)=+∞{\ displaystyle f ^ {\ infty} (d) = + \ infty}
• V případě jednoho , bude to za všechno , takže v tomto případě ,. Toto pozorování, důsledek bodu 1, je také důsledkem bodu 2, protože uvažovaný směr není v , a tedy ani v .X+t1d∉domF{\ displaystyle x + t_ {1} d \ notin \ operatorname {dom} \, f}t1>0{\ displaystyle t_ {1}> 0}t⩾t1{\ displaystyle t \ geqslant t_ {1}}F∞(d)=+∞{\ displaystyle f ^ {\ infty} (d) = + \ infty}d{\ displaystyle d}(domF)∞{\ displaystyle (\ operatorname {dom} \, f) ^ {\ infty}}domF∞{\ displaystyle \ operatorname {dom} \, f ^ {\ infty}}
• V bodě 2 předchozího návrhu nutně nemáme remízu. Například pokud je exponenciální funkce , máme , pak to .F:R→R{\ displaystyle f: \ mathbb {R} \ do \ mathbb {R}}domF∞=R-{\ displaystyle \ operatorname {dom} \, f ^ {\ infty} = \ mathbb {R} _ {-}}(domF)∞=R∞=R{\ displaystyle (\ operatorname {dom} \, f) ^ {\ infty} = \ mathbb {R} ^ {\ infty} = \ mathbb {R}}

Po těchto upřesněních na asymptotickou funkci je zde výsledek, který ukazuje užitečnost konceptu k určení existence neprázdné a omezené sady minimalizátorů. Množinu podúrovní funkce označíme takto: ν∈R{\ displaystyle \ nu \ in \ mathbb {R}}F:E→R¯{\ displaystyle f: E \ to {\ overline {\ mathbb {R}}}}

Sν(F): ={X∈E∣F(X)⩽ν}.{\ displaystyle S _ {\ nu} (f): = \ {x \ v E \ mid f (x) \ leqslant \ nu \}.}

Je to konvexní množina, když je konvexní. Následující výsledek ukazuje, že pro funkce těchto mají všechny sady podúrovní stejný asymptotický kužel (pokud nejsou prázdné). Zejména pokud je jeden z nich ohraničen, není prázdný, jsou všechny ohraničené (možná prázdné). Jednou z těchto sad podúrovní je sada jejích minimalizátorů: F{\ displaystyle f}VSÓneproti¯⁡(E){\ displaystyle \ operatorname {C {\ overline {onv}}} (E)}

argminF: ={X∈E∣F(X)⩽F(X′),  ∀X′∈E}=SinfF(F).{\ displaystyle f: = \ {x \ v E \ mid f (x) \ leqslant f (x '), ~~ \ forall \, x' \ v E \} = S _ {\ inf f} (f) .}

Asymptotická funkce poté umožňuje dát nezbytné a dostatečné podmínky pro to, aby tato množina byla neprázdná a ohraničená.

Sady podúrovní konvexní funkce  -  Let . Takže pro všechno , co máme, máme F∈VSÓneproti¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}ν∈R{\ displaystyle \ nu \ in \ mathbb {R}}Sν(F)≠∅{\ displaystyle S _ {\ nu} (f) \ neq \ varnothing}

(Sν(F))∞={d∈E∣F∞(d)⩽0}.{\ displaystyle (S _ {\ nu} (f)) ^ {\ infty} = \ {d \ v E \ mid f ^ {\ infty} (d) \ leqslant 0 \}.}

Ekvivalentní jsou zejména následující vlastnosti:

1. ∃ν∈R{\ displaystyle \ existuje \ nu \ v \ mathbb {R}}takové, které je neprázdné a ohraničené,Sν(F){\ displaystyle S _ {\ nu} (f)}
2. argminF{\ displaystyle \ operatorname {argmin} \, f} je neprázdný a ohraničený,
3. ∀ν∈R{\ displaystyle \ forall \ nu \ in \ mathbb {R}}, je ohraničený,Sν(F){\ displaystyle S _ {\ nu} (f)}
4. ∀d∈E∖{0}F∞(d)>0{\ displaystyle \ forall d \ in E \ setminus \ {0 \} \ quad f ^ {\ infty} (d)> 0}.

V praxi se ukazuje, že neprázdný a ohraničené minimizers (bod 2), bod 4 se používá: bez ohledu na řízení nenulový , . Jak často v konvexní analýze získáme globální vlastnost (ohraničenost množiny minimalizátorů) z jednosměrných vlastností (přísná pozitivita asymptotické funkce ve všech nenulových směrech). F{\ displaystyle f}d{\ displaystyle d}F∞(d)>0{\ displaystyle f ^ {\ infty} (d)> 0}

Výpočtové aspekty

Zde je výsledek, který umožňuje v určitých případech vypočítat asymptotickou funkci konvexního složení konvexních funkcí: pravidlo připomíná derivaci řetězce .

Složení funkcí  -  Předpokládejme dané dvě funkce a takové . Předpokládáme, že se to zvyšuje a platí . Takže a na všechno máme F∈VSÓneproti¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}G∈VSÓneproti¯⁡(R){\ displaystyle g \ in \ operatorname {C {\ overline {onv}}} (\ mathbb {R})}(domG)∩F(E)≠∅{\ displaystyle (\ operatorname {dom} \, g) \ cap f (E) \ neq \ varnothing}G{\ displaystyle g}G∞(1)>0{\ displaystyle g ^ {\ infty} (1)> 0}(G∘F)∈VSÓneproti¯⁡(E){\ displaystyle (g \ circ f) \ in \ operatorname {C {\ overline {onv}}} (E)}d∈E{\ displaystyle d \ v E}

(G∘F)∞(d)=G∞(F∞(d)).{\ displaystyle (g \ circ f) ^ {\ infty} (d) = g ^ {\ infty} (f ^ {\ infty} (d)).}

V tomto výsledku jsme přijali následující konvence: if and if . G(F(X))=+∞{\ displaystyle g (f (x)) = + \ infty}X∉domF{\ displaystyle x \ notin \ operatorname {dom} \, f}G∞(F∞(d))=+∞{\ displaystyle g ^ {\ infty} (f ^ {\ infty} (d)) = + \ infty}d∉domF∞{\ displaystyle d \ notin \ operatorname {dom} \, f ^ {\ infty}}

Příklady

Funkce bariéry protokolu

Zvažte funkci bariéry protokolu definovanou v par X∈R+ne{\ displaystyle x \ in \ mathbb {R} _ {+} ^ {n}}

lb⁡(X)={-∑i=1nelog⁡Xi-li X>0+∞Pokud ne.{\ displaystyle \ operatorname {l \! b} (x) = \ left \ {{\ begin {pole} {ll} - \ sum _ {i = 1} ^ {n} \ log x_ {i} & {\ mbox {si}} ~ x> 0 \\ + \ infty & {\ mbox {jinak.}} \ end {pole}} \ vpravo.}

Víme to . My máme lb∈VSÓneproti¯⁡(Rne){\ displaystyle \ operatorname {l \! b} \ v \ operatorname {C {\ overline {onv}}} (\ mathbb {R} ^ {n})}

lb∞=JáR+ne,{\ displaystyle \ operatorname {l \! b} ^ {\ infty} = {\ mathcal {I}} _ {\ mathbb {R} _ {+} ^ {n}},}

kde je indikátor z . JáR+ne{\ displaystyle {\ mathcal {I}} _ {\ mathbb {R} _ {+} ^ {n}}}R+ne{\ displaystyle \ mathbb {R} _ {+} ^ {n}}

Funkce určující log

Na vektorový prostor všech reálných symetrických matic od objednávky , považujeme funkce log-determinant je definováno v podle Sne{\ displaystyle {\ mathcal {S}} ^ {n}}ne{\ displaystyle n}X∈Sne{\ displaystyle X \ v {\ mathcal {S}} ^ {n}}

ld⁡(X)={-logdetX-li X≻0+∞Pokud ne,{\ displaystyle \ operatorname {l \! d} (X) = \ left \ {{\ begin {pole} {ll} - \ log \, \ det X & {\ mbox {si}} ~ X \ succ 0 \ \ + \ infty & {\ mbox {jinak,}} \ end {pole}} \ vpravo.}

kde notace znamená, že je pozitivní definitivní . Víme to . My máme X≻0{\ displaystyle X \ succ 0}X{\ displaystyle X}ld∈VSÓneproti¯⁡(Sne){\ displaystyle \ operatorname {l \! d} \ v \ operatorname {C {\ overline {onv}}} ({\ mathcal {S}} ^ {n})}

ld∞=JáS+ne,{\ displaystyle \ operatorname {l \! d} ^ {\ infty} = {\ mathcal {I}} _ {{\ mathcal {S}} _ {+} ^ {n}},}

kde je indikatrix z konvexního kužele z pozitivních polotovarů definované matice . JáS+ne{\ displaystyle {\ mathcal {I}} _ {{\ mathcal {S}} _ {+} ^ {n}}} S+ne{\ displaystyle {\ mathcal {S}} _ {+} ^ {n}}

Dodatky

Poznámky

1. Auslender a Teboulle 2003 , s.  48.
2. Toto je případ Rockafellar 1970 , nikoli případ Hiriart-Urruty a Lemaréchal 1993 .
3. (in) A. Auslender, R. a M. Cominetti Haddou, „  Asymptotická analýza pro trestné a bariérové ​​metody v konvexním a lineárním programování  “ , Mathematics of Operations Research , sv.  22,1997, str.  43-62.

Související článek

Asymptotické srovnání

Bibliografie

• (en) A. Auslender a M. Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalitites , New York, Springer , coll.  "Springer Monografie z matematiky",2003( číst online )
• (en) JM Borwein a AS Lewis, Konvexní analýza a nelineární optimalizace , New York, Springer,2006, 2 nd  ed. ( 1 st  ed. , 2000) ( číst řádek )
• (en) Jean-Baptiste Hiriart-Urruty a Claude Lemaréchal, Konvexní analýza a minimalizační algoritmy I: Fundamentals , Springer, kol.  "  Grundi." matematika. Wiss.  „( N O  305),1993( číst online )
• (en) Jean-Baptiste Hiriart-Urruty a Claude Lemaréchal, Základy konvexní analýzy , Berlín, Springer,2004( 1 st  ed. 2001) ( číst on-line )
• (en) R. Tyrrell Rockafellar , Convex Analysis , Princeton, NJ, Princeton University Press , kol.  "Princeton Mathematical Series" ( n o  28),1970( číst online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">