Fonction asymptotique

En mathématiques, et plus précisément en analyse convexe, la fonction asymptotique (ou fonction de récession) est une fonction associée à une fonction convexe f et définie à partir d'elle, qui a pour but de décrire son comportement à l'infini. On la note souvent $f^\infty$. On définit la fonction asymptotique $f^\infty$ par son épigraphe qui est le cône asymptotique de l'épigraphe de f.

Le calcul et l'examen de la fonction asymptotique permet parfois de dire si une fonction convexe a un ensemble non vide et borné de minimiseurs ; des conditions nécessaires et suffisantes en termes de la fonction asymptotique pour cela se produise peuvent en effet être établies.

La notion de fonction asymptotique peut aussi se définir pour des fonctions non convexes^[1].

Connaissances supposées : les bases de l'analyse et de l'analyse convexe (en particulier la notion de cône asymptotique).

Notations et définition

On suppose dans cet article que $\mathbb{E}$ est un espace vectoriel réel (les scalaires sont les éléments de $\R$) de dimension finie. On note

• $\operatorname{C\overline{onv}}(\mathbb{E})$ l'ensemble des fonctions définies sur $\mathbb{E}$ à valeurs dans $\bar{\R}:=\R\cup\{-\infty,+\infty\}$ qui sont convexes (i.e., leur épigraphe est convexe), propres (i.e., elles ne prennent pas la valeur $-\infty$ et ne sont pas identiquement égales à $+\infty$) et fermées (i.e., leur épigraphe est fermé).

L'épigraphe $\operatorname{epi}\,f$ d'une fonction $f\in\operatorname{C\overline{onv}}(\mathbb{E})$ est un convexe fermé non vide de $\mathbb{E}\times\R$. On peut donc considérer son cône asymptotique $(\operatorname{epi}\,f)^\infty$. On peut montrer que celui-ci est l'épigraphe d'une fonction qui est, par définition, la fonction asymptotique de f.

Fonction asymptotique — La fonction asymptotique d'une fonction $f\in\operatorname{C\overline{onv}}(\mathbb{E})$ est la fonction $f^\infty\in\operatorname{C\overline{onv}}(\mathbb{E})$ définie par

$\operatorname{epi}\,(f^\infty)=(\operatorname{epi}\,f)^\infty.$

Certains auteurs^[2] définissent la fonction asymptotique de fonctions convexes non nécessairement fermées ; cette légère extension est d'une utilité marginale.

Propriétés

La définition de la fonction asymptotique nous apprend peu de chose sur la manière de calculer cette fonction et sur sa signification. La propriété suivante fait le lien entre $f^\infty(d)$, pour $d\in\mathbb{E}$, et le quotient différentiel

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

On sait que, si f est convexe, $t\in{]0,\infty[}\mapsto q(t)$ est croissante et que la limite de q lorsque $t\downarrow0$ est la dérivée directionnelle f'(x;d), parfois dite au sens de Dini. Le résultat suivant nous apprend, en particulier, que la limite de q lorsque $t\to\infty$ est la valeur en d de la fonction asymptotique.

Fonction asymptotique — Soit $f\in\operatorname{C\overline{onv}}(\mathbb{E})$. Alors

1. $\forall\,x\in\operatorname{dom}\, f$ et $\forall\,d\in \mathbb{E}$ : $f^\infty(d) =\lim_{t\to+\infty}\frac{f(x+td)-f(x)}{t},$
2. $\operatorname{dom}\,f^\infty\subset(\operatorname{dom}\, f)^\infty$,
3. $f^\infty\in\operatorname{C\overline{onv}}(\mathbb{E})$ et est sous-linéaire.

Quelques remarques sur ce résultat.

• Comme $f(x)\in\R$, la formule du point 1 s'écrit aussi $f^\infty(d) =\lim_{t\to+\infty}\frac{f(x+td)}{t},$ avec un quotient f(x + td) / t qui, contrairement au quotient différentiel, n'est pas nécessairement monotone en t.
• L'utilisation de formule du point 1 ou de celle exposée ci-dessus est souvent le moyen le plus rapide de calculer la valeur de la fonction asymptotique en une direction d. Insistons sur le fait que la limite du quotient différentiel ne dépend pas du point x choisi dans le domaine de f.
• La formule précédente montre que si f a une asymptote dans la direction d, $f^\infty(d)$ en est la pente. Dans le cas contraire, $f^\infty(d)=+\infty$.
• Si $x+t_1d\notin\operatorname{dom}\,f$ pour un t₁ > 0, il en sera ainsi pour tout $t\geqslant t_1$, si bien que dans ce cas, $f^\infty(d)=+\infty$. Cette observation, conséquence du point 1, est aussi une conséquence du point 2, car la direction d considérée n'est pas dans $(\operatorname{dom}\, f)^\infty$, donc pas non plus dans $\operatorname{dom}\, f^\infty$, c'est-à-dire $f^\infty(d)$.
• On n'a pas nécessairement égalité au point 2 de la proposition précédente. En effet, si $f:\R\to\R$ est l'exponentielle, on a $f^\infty(1)=+\infty$. Donc $1\notin\operatorname{dom}\,f^\infty$, alors que $1\in(\operatorname{dom}\,f)^\infty=(\R)^\infty=\R$.

Après ces précisions sur la fonction asymptotique, voici un résultat qui montre l'utilité du concept pour déterminer l'existence d'un ensemble non vide et borné de minimiseurs. On note l'ensemble de sous-niveau $\nu\in\R$ d'une fonction $f:\mathbb{E}\to\bar{R}$ de la manière suivante :

$N_\nu(f):=\{x\in \mathbb{E}:f(x)\leqslant\nu\}.$

C'est un ensemble convexe, lorsque f est convexe. Le résultat suivant montre que, pour les fonctions de $\operatorname{C\overline{onv}}(\mathbb{E})$, ces ensembles de sous-niveau ont tous le même cône asymptotique (s'ils sont non vides). En particulier, si l'un d'eux est borné non vide, ils sont tous bornés (éventuellement vides). Un de ces ensembles de sous-niveau est l'ensemble de ses minimiseurs :

$\operatorname{argmin}\, f:= \{x\in \mathbb{E}: f(x)\leqslant f(x'),~~\forall\, x'\in \mathbb{E}\}=N_{\inf f}(f).$

La fonction asymptotique permet alors de donner des conditions nécessaires et suffisantes pour que cet ensemble soit non vide et borné.

Ensembles de sous-niveau d’une fonction convexe — Soit $f\in\operatorname{C\overline{onv}}(\mathbb{E})$. Alors, pour tout $\nu\in\R$ tel que $N_\nu(f)\ne\varnothing$, on a

$(N_\nu(f))^\infty=\{d\in \mathbb{E}:f^\infty(d)\leqslant 0\}.$

En particulier, les propriétés suivantes sont équivalentes :

1. $\exists\,\nu\in\R$ tel que N_ν(f) est non vide et borné,
2. $\operatorname{argmin}\, f$ est non vide et borné,
3. $\forall\,\nu\in\R$, N_ν(f) est borné,
4. $\forall\, d\in \mathbb{E}\setminus\{0\}$, $f^\infty(d)>0$.

En pratique, pour montrer que f a un ensemble non vide et borné de minimiseurs (point 2), on utilise le point 4 : quelle que soit la direction non nulle d, $f^\infty(d)>0$. Comme souvent en analyse convexe, on obtient une propriété globale (la bornitude de l'ensemble des minimiseurs) à partir de propriétés unidirectionnelles (la stricte positivité de la fonction asymptotique dans toutes les directions non nulles).

Aspects calculatoires

Voici un résultat permettant de calculer, dans certains cas, la fonction asymptotique d'une composition convexe de fonctions convexes^[3] : la règle rappelle celle de la dérivation en chaîne.

Composition de fonctions — Supposons données deux fonctions $f\in\operatorname{C\overline{onv}}(\mathbb{E})$ et $g\in\operatorname{C\overline{onv}}(\R)$ telles que $(\operatorname{dom}\, g)\cap f(\mathbb{E})\ne\varnothing$. On suppose que g est croissante et vérifie $g^\infty(1)>0$. Alors $(g\circ f)\in\operatorname{C\overline{onv}}(\mathbb{E})$ et pour tout $d\in \mathbb{E}$, on a

$(g\circ f)^\infty(d)=g^\infty(f^\infty(d)).$

Dans ce résultat, on a adopté les conventions suivantes : $g(f(x))=+\infty$ si $x\notin\operatorname{dom}\, f$ et $g^\infty(f^\infty(d))=+\infty$ si $d\notin\operatorname{dom}\,f^\infty$.

Exemples

Fonction log-barrière

Considérons la fonction log-barrière définie en $x\in\R^n_+$ par

$\operatorname{l\!b}(x)=\left\{\begin{array}{ll} -\sum_{i=1}^n\log x_i & \mbox{si}~x>0\\ +\infty & \mbox{sinon.} \end{array}\right.$

On vérifie que $\operatorname{l\!b}\in\operatorname{C\overline{onv}}(\R^n)$ et qu'en $d\in\R^n$, on a

$\operatorname{l\!b}^\infty(d)=\left\{\begin{array}{ll} 0 & \mbox{si}~x\geqslant 0\\ +\infty & \mbox{sinon.} \end{array}\right.$

Fonction log-déterminant

Soient

• $\mathcal{S}^n$ l'espace vectoriel des matrices réelles symétriques d'ordre n,
• $\mathcal{S}^n_+$ le cône de $\mathcal{S}^n$ formé par les matrices semi-définies positives et
• $\mathcal{S}^n_{++}$ le cône de $\mathcal{S}^n$ formé par les matrices définies positives.

On considère la fonction log-déterminant définie en $X\in\mathcal{S}^n$ par

$\operatorname{l\!d}(X)=\left\{\begin{array}{ll} -\log\,\det X & \mbox{si}~X\succ0\\ +\infty & \mbox{sinon,} \end{array}\right.$

où la notation $X\succ0$ signifie que $X\in\mathcal{S}^n_{++}$. On vérifie que $\operatorname{l\!d}\in\operatorname{C\overline{onv}}(\mathcal{S}^n)$ et qu'en $D\in\mathcal{S}^n$, on a

$\operatorname{l\!d}^\infty(D)=\left\{\begin{array}{ll} 0 & \mbox{si}~D\succcurlyeq0\\ +\infty & \mbox{sinon,} \end{array}\right.$

où la notation $X\succcurlyeq0$ signifie que $X\in\mathcal{S}^n_+$.

Annexes

Notes

1. ↑ Voir Auslender et Teboulle (2003).
2. ↑ C'est le cas de Rockafellar (1970), pas celui de Hiriart-Urruty et Lemaréchal (1993).
3. ↑ (en) A. Auslender, R. Cominetti, M. Haddou (1997). Asymptotic analysis for penalty and barrier methods in convex and linear programming. Mathematics of Operations Research, 22, 43–62.

Articles connexes

• Asymptote
• Comparaison asymptotique
• Cône asymptotique

Bibliographie

• (en) A. Auslender, M. Teboulle (2003). Asymptotic Cones and Functions in Optimization and Variational Inequalitites. Springer Monographs in Mathematics. Springer, New York.
• (en) J. M. Borwein, A. S. Lewis (2000). Convex Analysis and Nonlinear Optimization. Springer, New York.
• (en) J.-B. Hiriart-Urruty, C. Lemaréchal (1993). Convex Analysis and Minimization Algorithms. Grundlehren der mathematischen Wissenschaften, 305-306. Springer-Verlag.
• (en) J.-B. Hiriart-Urruty, C. Lemaréchal (2001). Fundamentals of convex analysis. Springer-Verlag, Berlin.
• (en) R.T. Rockafellar (1970). Convex Analysis. Princeton Mathematics Ser. 28. Princeton University Press, Princeton, New Jersey.