Funcția asimptotică

În matematică și mai precis în analiza convexă , funcția asimptotică (sau funcția de recesiune ) este o funcție asociată cu o funcție convexă și definită din aceasta, care are ca scop descrierea comportamentului său la infinit. De multe ori îl observăm . Definim funcția asimptotică prin epigraful său, care este conul asimptotic al epigrafului din . f{\ displaystyle f}f∞{\ displaystyle f ^ {\ infty}}f∞{\ displaystyle f ^ {\ infty}}f{\ displaystyle f}

Calculul și examinarea funcției asimptotice pot spune uneori dacă o funcție convexă are un set neimplic și delimitat de minimizatoare; pot fi stabilite într-adevăr condiții necesare și suficiente în ceea ce privește funcția asimptotică.

Noțiunea de funcție asimptotică poate fi definită și pentru funcțiile neconvexe.

Notări și definiție

Presupunem în acest articol că este un spațiu vectorial real de dimensiune finită . Observăm E{\ displaystyle E}

• VSonuv¯⁡(E){\ displaystyle \ operatorname {C {\ overline {onv}}} (E)}setul de funcții ale lui in ℝ care sunt convexe (adică epigraful convex ), propriu-zis (adică să nu ia valoarea și să nu fie identic egal cu ) și „închis” (adică semi-continuu inferior , sau din nou, de epigraf închis ).E{\ displaystyle E}-∞{\ displaystyle - \ infty} +∞{\ displaystyle + \ infty}

Epigraful unei funcții este un convex închis ne-gol al lui . Prin urmare, putem lua în considerare conul său asimptotic . Putem arăta că acesta este epigraful unei funcții care este, prin definiție, funcția asimptotică a . urechef{\ displaystyle \ operatorname {epi} \, f}f∈VSonuv¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}E×R{\ displaystyle E \ times \ mathbb {R}}(urechef)∞{\ displaystyle (\ operatorname {epi} \, f) ^ {\ infty}}f{\ displaystyle f}

Funcția asimptotică  -  Funcția asimptotică a unei funcții este funcția definită de f∈VSonuv¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}f∞∈VSonuv¯⁡(E){\ displaystyle f ^ {\ infty} \ in \ operatorname {C {\ overline {onv}}} (E)}

ureche(f∞)=(urechef)∞.{\ displaystyle \ operatorname {epi} \, (f ^ {\ infty}) = (\ operatorname {epi} \, f) ^ {\ infty}.}

Unii autori definesc funcția asimptotică a funcțiilor convexe care nu sunt neapărat închise; această ușoară extensie are o utilitate marginală.

Proprietăți

Definiția funcției asimptotice ne spune puțin despre cum să calculăm această funcție și semnificația acesteia. Următoarea proprietate face legătura între , pentru și coeficientul diferențial f∞(d){\ displaystyle f ^ {\ infty} (d)}d∈E{\ displaystyle d \ in E}

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

Știm că, dacă este convex, crește și că limita de când este derivata direcțională , uneori numită în sensul lui Dini . Următorul rezultat ne învață, în special, că limita de când este valoarea funcției asimptotice. 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}

Funcția asimptotică  -  Fie . Asa de f∈VSonuv¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}

1. ∀X∈{\ displaystyle \ forall \, x \ in}dom și :f{\ displaystyle f}∀d∈E{\ displaystyle \ forall \, d \ in 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} \ subset (\ operatorname {dom} \, f) ^ {\ infty}},
3. f∞{\ displaystyle f ^ {\ infty}}este subliniar .

Câteva observații cu privire la acest rezultat.

• De asemenea, se scrie și formula punctului 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}},}cu un coeficient care, spre deosebire de coeficientul diferențial, nu este neapărat monoton în .f(X+td)/t{\ displaystyle f (x + td) / t}t{\ displaystyle t}
• Folosirea formulei de la punctul 1 sau cea discutată mai sus este adesea cea mai rapidă modalitate de a calcula valoarea funcției asimptotice într-o singură direcție . Să insistăm asupra faptului că limita coeficientului diferențial nu depinde de punctul ales în domeniul .d{\ displaystyle d}X{\ displaystyle x}f{\ displaystyle f}
• Formula anterioară arată că dacă are o asimptotă în direcție , este panta. În caz contrar ,.f{\ displaystyle f}d{\ displaystyle d}f∞(d){\ displaystyle f ^ {\ infty} (d)}f∞(d)=+∞{\ displaystyle f ^ {\ infty} (d) = + \ infty}
• Dacă pentru unul , va fi așa pentru toate , astfel încât, în acest caz ,. Această observație, o consecință a punctului 1, este, de asemenea, o consecință a punctului 2, deoarece direcția luată în considerare nu este în și, prin urmare, nu în .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}}
• Nu avem neapărat o egalitate la punctul 2 al propoziției anterioare. De exemplu, dacă este funcția exponențială , avem , atunci asta .f:R→R{\ displaystyle f: \ mathbb {R} \ to \ mathbb {R}}domf∞=R-{\ displaystyle \ operatorname {dom} \, f ^ {\ infty} = \ mathbb {R} _ {-}}(domf)∞=R∞=R{\ displaystyle (\ operatorname {dom} \, f) ^ {\ infty} = \ mathbb {R} ^ {\ infty} = \ mathbb {R}}

După aceste precizări privind funcția asimptotică, iată un rezultat care arată utilitatea conceptului pentru a determina existența unui set neimpresor și delimitat de minimizatoare. Notăm setul de subnivele ale unei funcții după cum urmează: ν∈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 \ in E \ mid f (x) \ leqslant \ nu \}.}

Este un set convex, când este convex. Următorul rezultat arată că, pentru funcțiile , aceste seturi de sub-nivel au toate același con asimptotic (dacă nu sunt goale). În special, dacă unul dintre ei este delimitat non-gol, toate sunt delimitate (posibil goale). Unul dintre aceste seturi de subnivele este setul minimizatorilor săi: f{\ displaystyle f}VSonuv¯⁡(E){\ displaystyle \ operatorname {C {\ overline {onv}}} (E)}

argminf: ={X∈E∣f(X)⩽f(X′),  ∀X′∈E}=Sinff(f).{\ displaystyle f: = \ {x \ in E \ mid f (x) \ leqslant f (x '), ~~ \ forall \, x' \ in E \} = S _ {\ inf f} (f) .}

Funcția asimptotică face posibilă acordarea condițiilor necesare și suficiente pentru ca acest set să nu fie gol și delimitat.

Seturi de sub-nivel ale unei funcții convexe  -  Let . Deci, pentru tot ceea ce avem, avem f∈VSonuv¯⁡(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 \ in E \ mid f ^ {\ infty} (d) \ leqslant 0 \}.}

În special, următoarele proprietăți sunt echivalente:

1. ∃ν∈R{\ displaystyle \ există \ nu \ în \ mathbb {R}}care nu este gol și delimitat,Sν(f){\ displaystyle S _ {\ nu} (f)}
2. argminf{\ displaystyle \ operatorname {argmin} \, f} nu este gol și delimitat,
3. ∀ν∈R{\ displaystyle \ forall \ nu \ in \ mathbb {R}}, este delimitat,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}.

În practică, pentru a arăta că un non-gol și delimitate minimizers (punctul 2), punctul 4 se utilizează: indiferent de managementul de zero , . La fel de des în analiza convexă, obținem o proprietate globală (limita setului de minimizatoare) din proprietăți unidirecționale (pozitivitatea strictă a funcției asimptotice în toate direcțiile non-zero). f{\ displaystyle f}d{\ displaystyle d}f∞(d)>0{\ displaystyle f ^ {\ infty} (d)> 0}

Aspecte computaționale

Iată un rezultat care face posibilă calcularea, în anumite cazuri, a funcției asimptotice a unei compoziții convexe a funcțiilor convexe: regula amintește cea a derivării lanțului .

Compoziția funcțiilor  -  Să presupunem că sunt date două funcții și astfel încât . Presupunem că crește și se menține . Deci și pentru toate , avem f∈VSonuv¯⁡(E){\ displaystyle f \ in \ operatorname {C {\ overline {onv}}} (E)}g∈VSonuv¯⁡(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)∈VSonuv¯⁡(E){\ displaystyle (g \ circ f) \ in \ operatorname {C {\ overline {onv}}} (E)}d∈E{\ displaystyle d \ in E}

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

În acest rezultat, am adoptat următoarele convenții: dacă și dacă . 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}}

Exemple

Funcția de barieră în jurnal

Luați în considerare funcția barieră-log definită la alin X∈R+nu{\ displaystyle x \ in \ mathbb {R} _ {+} ^ {n}}

lb⁡(X)={-∑eu=1nuButuruga⁡Xeudacă X>0+∞dacă nu.{\ displaystyle \ operatorname {l \! b} (x) = \ left \ {{\ begin {array} {ll} - \ sum _ {i = 1} ^ {n} \ log x_ {i} & {\ mbox {si}} ~ x> 0 \\ + \ infty & {\ mbox {altfel.}} \ end {array}} \ right.}

Știm asta . Avem lb∈VSonuv¯⁡(Rnu){\ displaystyle \ operatorname {l \! b} \ in \ operatorname {C {\ overline {onv}}} (\ mathbb {R} ^ {n})}

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

în cazul în care este indicatorul de . EuR+nu{\ displaystyle {\ mathcal {I}} _ {\ mathbb {R} _ {+} ^ {n}}}R+nu{\ displaystyle \ mathbb {R} _ {+} ^ {n}}

Funcția log-determinantă

Pe spațiul vectorial de matrici simetrice reale de ordine , considerăm că funcția-log determinant definit în prin Snu{\ displaystyle {\ mathcal {S}} ^ {n}}nu{\ displaystyle n}X∈Snu{\ displaystyle X \ in {\ mathcal {S}} ^ {n}}

ld⁡(X)={-ButurugadetXdacă X≻0+∞dacă nu,{\ displaystyle \ operatorname {l \! d} (X) = \ left \ {{\ begin {array} {ll} - \ log \, \ det X & {\ mbox {si}} ~ X \ succ 0 \ \ + \ infty & {\ mbox {în caz contrar,}} \ end {array}} \ right.}

unde notația înseamnă că este pozitiv definit . Știm asta . Avem X≻0{\ displaystyle X \ succ 0}X{\ displaystyle X}ld∈VSonuv¯⁡(Snu){\ displaystyle \ operatorname {l \! d} \ in \ operatorname {C {\ overline {onv}}} ({\ mathcal {S}} ^ {n})}

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

unde este indicatorul conului convex al matricilor semidefinite pozitive . EuS+nu{\ displaystyle {\ mathcal {I}} _ {{\ mathcal {S}} _ {+} ^ {n}}} S+nu{\ displaystyle {\ mathcal {S}} _ {+} ^ {n}}

Anexe

Note

1. Auslender și Teboulle 2003 , p.  48.
2. Acesta este cazul Rockafellar 1970 , nu cel al lui Hiriart-Urruty și Lemaréchal 1993 .
3. (în) A. Auslender, R. și M. Cominetti Haddou, "  Analiza asimptotică pentru metodele de penalizare și barieră în programarea convexă și liniară  " , Matematica cercetării operaționale , Vol.  22,1997, p.  43-62.

Articol asociat

Comparație asimptotică

Bibliografie

• (ro) A. Auslender și M. Teboulle, Conuri asimptotice și funcții în optimizare și inegalități variaționale , New York, Springer , col.  „Monografii Springer în matematică”,2003( citește online )
• (ro) JM Borwein și AS Lewis, Convex Analysis and Nonlinear Optimization , New York, Springer,2006, A 2 -a  ed. ( 1 st  ed. 2000) ( linia de citit )
• (en) Jean-Baptiste Hiriart-Urruty și Claude Lemaréchal, Convex Analysis and Minimization Algorithms I: Fundamentals , Springer, col.  „  Grund. matematica. Wiss.  "( N o  305),1993( citește online )
• (en) Jean-Baptiste Hiriart-Urruty și Claude Lemaréchal, Fundamentals of Convex Analysis , Berlin, Springer,2004( 1 st  ed. 2001) ( citit on - line )
• (ro) R. Tyrrell Rockafellar , Convex Analysis , Princeton, NJ, Princeton University Press , col.  „Seria matematică Princeton” ( nr .  28),1970( citește online )

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