Nicolas Bacaër
On s'intéresse au problème d'optimisation déterministe en temps discret à horizon infini sur un espace métrique compact avec un critère de coût moyen qui fait intervenir deux fonctions, le coût et le temps. On rassemble tout d'abord les différentes caractérisations de la valeur λ comme valeur propre max-plus et comme problème de programmation linéaire. Puis on prouve une borne sur l'erreur faite sur λ lorsque l'espace est discrétisé.
Mots clés : Optimisation en temps discret; Coût moyen; Programmation linéaire; Analyse numérique
On s'intéresse au problème d'optimisation déterministe en temps discret à horizon infini avec un critère de coût moyen \[\lambda = \max_{(x_n)\in X^\mathbb{N}} \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n, x_{n+1})}{\sum_{n=0}^{N-1} T(x_n, x_{n+1})}\, .\] X est un espace métrique compact. K et T sont des fonctions continues avec \(T > 0\). L'ensemble X est l'espace d'états. \(\,x_n\,\) est l'état du système au temps n. \(\,K(x_n,x_{n+1})\) est le coût. \(T(x_n,x_{n+1})\) est le temps associé à la transition de l'état \(x_n\to x_{n+1}\). Le problème est motivé par des exemples
L'objectif ici est double. Tout d'abord, on rassemble les différentes caractérisations de λ comme problème de valeur propre max-plus généralisé (aussi appelé équation d'optimalité de Bellman) \[\max_{y \in X} \{K(x,y)-\lambda T(x,y) + u(y)\} = u(x)\] et comme problème de programmation linéaire. Ces caractérisations semblent n'avoir été démontrées que dans le cas particulier où T=1 [7, 8, 13] ou d'un ensemble fini X [11, 14, 10, 4]. Deuxièmement, on démontre une borne pour l'erreur commise sur λ lorsque l'espace X est discrétisé. Ceci généralise un travail récent [2] qui supposait T=1.
Mentionnons quelques domaines de recherche liés à notre étude. Des problèmes de programmation linéaire en dimension infinie qui ressemblent beaucoup à l'équation (4) ci-dessous apparaissent dans le problème de transport de masse de Monge et Kantorovich et dans le problème de transbordement de Kantorovich et Rubinstein étudié dans [17]. Il y a naturellement aussi des analogues en temps continu de notre problème. Un analogue en temps continu de la formule (4) intervient par exemple dans l'étude des systèmes lagrangiens [12]. La propriété (7) est aussi un ingrédient de base de la théorie d'Aubry et Mather [5, 6]. Des problèmes de coût moyen se trouvent aussi dans le cadre de la théorie du contrôle stochastique [15, 16]. Ces études supposent que T=1 et ne couvrent donc pas notre travail. Notons qu'ici, il ne sera pas nécessaire d'utiliser les méthodes sophistiquées de la programmation linéaire en dimension infinie [1] (topologies faibles, théorème d'Alaoglu, théorème de séparation par un hyperplan) pour prouver la « dualité forte ».
Rappelons quelques définitions. Si X est une espace métrique compact, \(C^0(X)\,\) est l'espace des fonctions continues sur X à valeurs réelles. C'est un espace de Banach lorsqu'il est muni de la norme du suprémum. \(\,\mathcal{M}(X)\) est l'espace des formes linéaires continues sur \(C^0(X)\). Si ρ \(\in \mathcal{M}(X)\), ρ≥0 signifie que \(\langle u,\rho \rangle \geq 0\ \forall u\in C^0(X)\) avec \(u\geq 0\). Les crochets désignent le produit de dualité.
L'énoncé du premier théorème nécessite quelques notations spéciales. On définit \[\forall u\in C^0(X),\ \forall (x,y)\in X^2,\quad (Q_1u)(x,y)=u(x),\quad (Q_2u)(x,y)=u(y).\] Si ρ \(\in \mathcal{M}(X^2)\), on définit \(P_1\rho\) et \(P_2\rho \in \mathcal{M}(X)\) par \[\forall u\in C^0(X),\quad \langle u,P_1\rho \rangle= \langle Q_1 u,\rho \rangle,\quad \langle u,P_2\rho \rangle = \langle Q_2 u,\rho \rangle.\] Si E est un ensemble et \(\,f:E\to \mathbb{R}\), alors la notation \(x \in \mathrm{argmax}_{y \in E} f(y)\) signifie que \(x\in E\) et \(f(x)=\max \{f(y);\ y\in E\}\).
Théorème 1.
Soit X un espace métrique compact, \(\,K\in C^0(X^2)\) et \(T\in C^0(X^2)\). On suppose \(\,T(x,y) > 0\ \forall x,y \in X\). On a alors
\begin{equation}\tag{1}
\exists ! \lambda \in \mathbb{R},\quad \exists u\in C^0(X),\quad \forall x\in X,\quad \max_{y\in X} \{K(x,y)-\lambda T(x,y) + u(y) \} = u(x)\, .
\end{equation}
De plus,
\begin{align}
\lambda=&
\max_{(x_n)\in X^{\mathbb{N}}} \limsup_{N \to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})} \tag{2}\\
&= \min\{\mu;\ (\mu,v)\in \mathbb{R}\times C^0(X),\ K-\mu T+Q_2v\leq Q_1 v\} \tag{3}\\
&= \max \{\langle K,\rho\rangle ;\ \rho \in \mathcal{M}(X^2), \ \rho \geq 0, \langle T,\rho \rangle = 1,\ P_1\rho = P_2\rho \}. \tag{4}
\end{align}
Si on a (1), alors \((\lambda,u)\) atteignent le minimum dans (3). Si on a \(\,x_0 \in X\) et
\begin{equation}
\forall n\in \mathbb{N},\quad x_{n+1} \in \mathop{\mathrm{argmax}}_{y\in X} \{K(x_n,y)- \lambda T(x_n,y) + u(y)\} \tag{5}
\end{equation}
on a
On dit que l'unique nombre réel λ défini dans le théorème 1 est la valeur propre de (K,T). Une fonction \(\,u\,\) avec (1) est une « fonction propre » de (K,T). La proposition suivante concerne le problème transposé.
Proposition 1. Mêmes hypothèses que dans le théorème 1. On définit \[\forall x, y \in X,\quad K'(x,y) = K(y,x),\quad T'(x,y) = T(y,x).\] Soit λ la valeur propre de \((K,T)\) et \(\lambda'\) la valeur propre de \((K',T')\). On a alors \(\,\lambda=\lambda'\).
Le théorème suivant aborde la question de l'analyse numérique de (1). Rappelons qu'une fois discrétisé, il y a des algorithmes bien connus pour résoudre le problème fini qui en résulte, par exemple l'algorithme d'itération de [9].
Théorème 2. Soit (X,d) un espace métrique compact. \(\,K:X^2\to \mathbb{R}\) et \(T:X^2\to \mathbb{R}\) sont des fonctions lipschitziennes avec des constantes de Lipschitz \(C_K\) et \(C_T\) \begin{align*} \forall x,x',y,y' \in X,\quad &|K(x,y)-K(x',y')| \leq C_K \max\{d(x,x');d(y,y')\}\\ &|T(x,y)-T(x',y')| \leq C_T \max\{d(x,x');d(y,y')\}\, . \end{align*} On suppose \(T(x,y) > 0\ \forall x, y \in X\). Soit λ la valeur propre de \(\,(K,T)\). \((X_p)_{p\in \mathbb{N}}\,\) est une suite de sous-ensembles finis de X tels que \[h_p = \sup_{x\in X} \min_{y\in X_p} d(x,y) \mathop{\longrightarrow}_{p\to +\infty} 0.\] D'après le théorème 1, \[\forall p \in \mathbb{N},\quad \exists !\, \lambda_p \in \mathbb{R},\quad \exists u_p:X_p \to \mathbb{R}, \quad \forall x\in X_p,\ \max_{y\in X_p} \{K(x,y)-\lambda_p\, T(x,y)+u_p(y) \} = u_p(x)\, .\] On définit \(\,\delta_T=\min \{T(x,y);\, (x,y) \in X^2\}\) et \(\|K\|=\max \{|K(x,y)|;\, (x,y) \in X^2 \}\). On a alors \[\forall p\in \mathbb{N},\quad \lambda_p \leq \lambda \leq \lambda_p+ \left ( \frac{C_K}{\delta_T}+\frac{\|K\|\, C_T}{(\delta_T)^2} \right ) h_p \] et \(\lambda_p \to \lambda\) si \(p\to +\infty\).
Certains résultats utiles pour prouver la première partie du théorème 1 sont rappelés dans la section 3. Ces résultats se trouvent par exemple dans [2]. La preuve de la première partie du théorème 1 se trouve dans la section 4. On prouve la formule (2) et l'optimalité de \(\,(x_n)\) dans la section 5. On prouve les formules (3), (4) et l'optimalité de \((\lambda,u)\) et de \(\rho^*\,\) dans la section 6 en généralisant les preuves de [10]. On prouve la propriété (7) dans la section 7, la proposition 1 dans la section 8, le théorème 2 dans la section 9. Enfin, on propose dans la section 10 une preuve alternative de l'existence d'une solution (λ,u) de (1). La preuve repose sur un passage à la limite à partir d'un problème de coût actualisé. Un avantage de cette approche par rapport à celle de la section 4 est qu'elle n'utilise pas la proposition 4 ci-dessous (qui repose sur le théorème de point fixe de Schauder). Elle n'utilise que le théorème de point fixe de Banach.
Proposition 2. Soit X un espace métrique compact et \(\,K\in C^0(X)\). On a \[\exists !\, \lambda \in \mathbb{R},\quad \exists u\in C^0(X),\quad \forall x \in X,\ \max_{y\in X} \{K(x,y)+u(y) \} = \lambda + u(x)\, .\] De plus, \begin{equation}\tag{8} \lambda = \max_{(x_n) \in X^{\mathbb{N}}} \limsup_{N \to +\infty} \frac{1}{N} \sum_{n=0}^{N-1} K(x_n,x_{n+1})\, . \end{equation}
Proposition 3. Soit X un espace métrique compact. \(\forall \alpha \in \mathbb{R}, \ K_\alpha \in C^0(X)\). On suppose \(\forall x,y \in X\), \(\alpha \mapsto K_\alpha(x,y)\,\) est une fonction convexe. Pour tout α \(\in \mathbb{R}\,\), \(\,\lambda_\alpha\) est l'unique nombre réel de la proposition 2. On a alors \(\alpha \mapsto \lambda_\alpha\) de \(\mathbb{R}\to \mathbb{R}\) est une fonction convexe.
On définit \[\forall \lambda \in \mathbb{R},\quad \forall x, y \in X,\quad K_\lambda(x,y)=K(x,y)-\lambda T(x,y).\] D'après la proposition 2, \[\forall \lambda \in \mathbb{R},\quad \exists ! \Lambda(\lambda) \in \mathbb{R}, \quad \exists u_\lambda \in C^0(X), \quad \forall x\in X,\ \max_{y\in X} \{K_\lambda(x,y)+u_\lambda(y)\} = \Lambda(\lambda)+u_\lambda(x).\] Avec la formule (8), \begin{equation}\tag{9} \forall \lambda \in \mathbb{R}, \quad \Lambda(\lambda) = \max_{(x_n) \in X^{\mathbb{N}}} \limsup_{N \to +\infty} \frac{1}{N} \sum_{n=0}^{N-1} K_\lambda(x_n,x_{n+1})\, . \end{equation} Mais \(T\geq 0\). \(\,\lambda \mapsto K_\lambda=K-\lambda T\) de \(\mathbb{R}\to C^0(X)\,\) est donc une fonction décroissante. La formule (9) montre alors que \(\lambda \mapsto \Lambda(\lambda)\) de \(\mathbb{R}\to \mathbb{R}\,\) est aussi une fonction décroissante. \(K_\lambda\,\) est une fonction linéaire et donc convexe de λ. La proposition 3 montre que Λ est une fonction convexe, donc aussi une fonction continue.
On prend la suite stationnaire égale à \(x_0\) pour \((x_n)\in X^{\mathbb{N}}\,\) dans (9). On a alors \[\forall \lambda\in \mathbb{R}, \quad \Lambda(\lambda) \geq K_\lambda(x_0,x_0)=K(x_0,x_0)-\lambda T(x_0,x_0).\] Mais \(T(x_0,x_0) > 0\). On a donc \(\,K(x_0,x_0)-\lambda T(x_0,x_0) \to +\infty\) si \(\lambda \to -\infty\), et \(\Lambda(\lambda)\to +\infty\) si \(\lambda \to -\infty\).
Puisque X est compact et puisque la fonction T est continue et strictement positive, on a \[\delta_T=\min \{T(x,y);\, (x,y) \in X^2\} > 0.\] On définit \[\|K\|=\max \{|K(x,y)|;\, (x,y) \in X^2\}.\] Soit ε>0. On a \[\forall \lambda \geq (\|K\|+\varepsilon)/\delta_T,\quad \forall (x,y) \in X^2, \quad K_\lambda(x,y)=K(x,y)-\lambda T(x,y) \leq \|K\| - \lambda\, \delta_T \leq - \varepsilon.\] D'après la formule (9), \(\forall \lambda \geq (\|K\|+\varepsilon)/\delta_T, \ \Lambda(\lambda) \leq - \varepsilon\).
Comme la fonction continue Λ prend des valeurs positives et négatives, \(\exists\ \lambda^*\in \mathbb{R},\ \Lambda(\lambda^*)=0\). Enfin, \begin{align*} \forall x\in X,\quad u_{\lambda^*}(x)=&\Lambda(\lambda^*)+u_{\lambda^*}(x) = \max_{y\in X} \{K_{\lambda^*}(x,y)+u_{\lambda^*}(y)\}\\ =&\max_{y\in X} \{K(x,y)- \lambda^* T(x,y) + u_{\lambda^*}(y)\}. \end{align*} Cela prouve la partie existence du théorème 1. L'unicité résulte de la formule (2), qui est prouvée dans la prochaine section.
\(\bullet\) On choisit \((x_n) \in X^{\mathbb{N}}\). D'après (1), \[\forall n \in \mathbb{N},\quad u(x_n) \geq K(x_n,x_{n+1})-\lambda T(x_n,x_{n+1})+u(x_{n+1}).\] Additionnons les N premières inégalités. On obtient \[u(x_0) \geq \sum_{n=0}^{N-1} K(x_n,x_{n+1}) - \lambda \sum_{n=0}^{N-1} T(x_n,x_{n+1}) + u(x_N).\] Mais \(T > 0\). On a donc \[\lambda \geq \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1}) +u(x_N)-u(x_0)}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, .\] Parce que \(T\geq \delta_T > 0\), on a \(\sum_{n=0}^{N-1} T(x_n,x_{n+1})\geq N\delta_T \to +\infty\) si \(N\to +\infty\). \(\,u\,\) est une fonction borné. On obtient donc \[\lambda \geq \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, .\] Mais \((x_n)\in X^{\mathbb{N}}\,\) était arbitraire. On a donc \begin{equation}\tag{10} \lambda \geq \sup_{(x_n)\in X^{\mathbb{N}}} \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, . \end{equation} \(\bullet\) On choisit \((x_n) \in X^{\mathbb{N}}\) avec (5), \[\forall n\in \mathbb{N},\quad u(x_n)=K(x_n,x_{n+1})-\lambda T(x_n,x_{n+1})+u(x_{n+1}).\] On additionne ces équations et on obtient \[\forall N \in \mathbb{N},\quad \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})} = \lambda + \frac{u(x_0)-u(x_N)}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, .\] On a ainsi \[\lim_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})} = \lambda\, .\] Avec (10), cela prouve la formule (2) et le fait que \((x_n)\) atteigne le maximum.
On définit \[E=\{\rho \in \mathcal{M}(X^2);\ \rho \geq 0,\ \langle T,\rho \rangle =1,\ P_1\rho = P_2\rho \},\] \[\tilde{E}=\{(u,v) \in \mathbb{R} \times C^0(X);\ K-\mu T +Q_2 v \leq Q_1 v \}.\] On a \[\forall \rho \in E, \quad \forall (\mu,v) \in \tilde{E},\quad \langle K,\rho \rangle \leq \langle \mu T +Q_1 v - Q_2 v,\rho \rangle = \mu \langle T,\rho \rangle + \langle v,P_1\rho-P_2\rho \rangle =\mu\, .\] On a donc \[\sup \{\langle K,\rho\rangle;\ \rho \in E\} \leq \inf \{\mu; (\mu,v)\in \tilde{E}\}.\] Avec la première partie du théorème 1, on sait qu'il existe \((\lambda,u)\in \mathbb{R}\times C^0(X)\,\) avec (1). On a \( \forall x,y \in X,\quad K(x,y)-\lambda T(x,y)+u(y)\leq u(x).\) On a donc \((\lambda,u) \in \tilde{E}\) et \[\inf \{\mu;\ (\mu,v)\in \tilde{E} \} \leq \lambda.\] D'après (6), on voit facilement que \(\,\rho^*\in \mathcal{M}(X^2)\), \(\rho^*\geq 0\) et \(\langle T,\rho^* \rangle = 1\). On a \begin{align*} \forall u\in C^0(X),\quad &\langle u,P_1 \rho^* \rangle = \langle Q_1 u,\rho^* \rangle = \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} u(x_n)}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, ,\\ &\langle u,P_2 \rho^* \rangle = \langle Q_2 u,\rho^* \rangle = \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} u(x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, . \end{align*} On a donc \(\langle u,P_1 \rho^* \rangle = \langle u,P_2\rho^* \rangle\) (parce que \(u\) est borné), et \(P_1\rho^*=P_2\rho^*\). On a ainsi \(\,\rho^* \in E\). De plus, \[\langle K,\rho^* \rangle = \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}=\lambda \] parce que \((x_n)\,\) atteint le maximum dans (2). On a donc \[\sup \{ \langle K,\rho \rangle ;\ \rho \in E \} \geq \lambda \, .\] En conclusion, \[\lambda=\max \{ \langle K,\rho \rangle;\ \rho \in E \} = \min \{\mu ;\ (\mu,v) \in \tilde{E} \},\] \(\rho^*\) atteint le maximum et \((\lambda,u)\) atteint le minimum.
On suppose \(0\leq i < j\,\) et \(\,(y_n)\in X^{\mathbb{N}}\) avec \((x_i,x_j)=(y_i,y_j)\). On a \begin{align*} \forall i\leq n \leq j-1,\quad &K(x_n,x_{n+1})- \lambda\, T(x_n,x_{n+1})+u(x_{n+1})=u(x_n),\\ &K(y_n,y_{n+1})- \lambda\, T(y_n,y_{n+1})+u(y_{n+1})\leq u(y_n). \end{align*} On additionne ces équations et on utilise \((x_i,x_j)=(y_i,y_j)\). On obtient \begin{align*} \sum_{n=i}^{j-1} [K(y_n,y_{n+1})-\lambda\, T(y_n,y_{n+1})] &\leq u(y_i) -u(y_j)\\ &=u(x_i)-u(x_j)\\ &=\sum_{n=i}^{j-1} [K(x_n,x_{n+1})-\lambda\, T(x_n,x_{n+1})]. \end{align*}
On choisit une fonction propre \(u \in C^0(X)\) de \((K,T)\). On choisit une fonction propre \(u' \in C^0(X)\) de \((K',T')\). On choisit \(x_0 \in \mathrm{argmax}_{x\in X} \{u(x)+u'(x)\}\). Il existe \(\,x_1 \in X\) avec \[K(x_0,x_1)- \lambda T(x_0,x_1)+u(x_1)=u(x_0).\] Remarquons que \[K'(x_1,x_0)-\lambda' T'(x_1,x_0)+u'(x_0) \leq u'(x_1).\] Soustrayons ces deux lignes. On obtient \[(\lambda-\lambda') T(x_0,x_1) \leq u(x_1) +u'(x_1) - u(x_0) - u'(x_0) \leq 0 .\] On a donc \(\lambda-\lambda' \leq 0\) et \(\lambda \leq \lambda'\). Si l'on échange \(\,(K,T)\) et \((K',T')\), on obtient \(\lambda' \leq \lambda\). On a donc \(\,\lambda=\lambda'\).
On choisit p \(\in \mathbb{N}\). D'après la formule (2), \[\lambda=\max_{(x_n) \in X^{\mathbb{N}}} \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(x_n,x_{n+1})}{\sum_{n=0}^{N-1} T(x_n,x_{n+1})}\, ,\] \[\lambda_p=\max_{(y_n) \in X_p^{\mathbb{N}}} \limsup_{N\to +\infty} \frac{\sum_{n=0}^{N-1} K(y_n,y_{n+1})}{\sum_{n=0}^{N-1} T(y_n,y_{n+1})}\, .\] D'un côté, \(X_p \subset X\). Il est donc clair que \(\,\lambda \geq \lambda_p\). D'un autre côté, on choisit \(\,(x_n) \in X^{\mathbb{N}}\). D'après la définition de \(\,h_p\), \[\forall n\in \mathbb{N}, \quad \exists y_n \in X_p,\quad d(x_n,y_n) \leq h_p.\] Mais K et T sont des fonctions lipschitziennes \begin{align*} \forall n\in \mathbb{N},\quad &|K(x_n,x_{n+1})-K(y_n,y_{n+1})| \leq C_K h_p,\\ &|T(x_n,x_{n+1})-T(y_n,y_{n+1})| \leq C_T h_p. \end{align*} Pour simplifier, on définit \(x=(x_n)\), \(y=(y_n)\), \[K_N(x)=\sum_{n=0}^{N-1} K(x_n,x_{n+1})\] et de même pour \(T_N(x)\). On a alors \begin{align*} \forall N\geq 1,\quad \left |\frac{K_N(x)}{T_N(x)}-\frac{K_N(y)}{T_N(y)} \right | &= \left | \frac{[K_N(x)-K_N(y)]T_N(y)+K_N(y)[T_N(y)-T_N(x)]}{T_N(x) T_N(y)} \right |\\ &\leq \left | \frac{K_N(x)-K_N(y)}{T_N(x)} \right | + \left | \frac{K_N(y) [T_N(y)-T_N(x)]}{T_N(x) T_N(y)} \right |\\ &\leq \frac{N C_K h_p}{N \delta_T} + \frac{N \|K\| \times N C_T h_p}{(N\delta_T)^2}\, . \end{align*} On a ainsi \begin{align*} \limsup_{N\to +\infty} \frac{K_N(x)}{T_n(x)} &\leq \limsup_{N \to +\infty} \frac{K_N(y)}{T_N(y)} + \left ( \frac{C_K}{\delta_T} + \frac{\|K\| C_T}{(\delta_T)^2} \right ) h_p\\ &\leq \lambda_p + \left ( \frac{C_K}{\delta_T} + \frac{\|K\| C_T}{(\delta_T)^2} \right ) h_p\, . \end{align*} Mais \((x_n) \in X^{\mathbb{N}}\,\) était arbitraire. On obtient donc la seconde inégalité du théorème 3.
Lemme 1. \[\forall \alpha \in ]0,1[,\quad \forall \lambda \in \mathbb{R},\quad \exists v_{\alpha,\lambda}\in C^0(X),\quad \forall x\in X,\quad \max_{y \in X} \{K(x,y)-\lambda T(x,y) + \alpha\, v_{\alpha,\lambda}(y)\}= v_{\alpha,\lambda}(x)\, .\]
Preuve. Soit α \(\in ]0,1[\) et λ \(\in \mathbb{R}\). On définit \[\forall v \in C^0(X),\quad \forall x\in X,\quad (\mathcal{K}v)(x)=\max_{y \in X} \{ K(x,y)-\lambda T(x,y) + \alpha \, v(y) \}.\] Puisque K et T sont uniformément continus, \(\,\mathcal{K}(C^0(X)) \subset C^0(X)\). On a \begin{align*} \forall v_1,v_2 \in C^0(X), \quad \forall x\in X,\quad (\mathcal{K}v_1)(x)-(\mathcal{K}v_2)(x)&\leq \max_{y \in X} \{ K(x,y)-\lambda T(x,y) + \alpha (v_1(y)-v_2(y))+\alpha v_2(y) \} \\ &\quad - \max_{y \in X} \{ K(x,y)-\lambda T(x,y) + \alpha v_2(y)\}\\ &\leq \alpha \|v_1-v_2\|. \end{align*} Donc par symétrie, \(\|\mathcal{K}v_1-\mathcal{K}v_2\| \leq \alpha \|v_1-v_2\|\). Parce que α \(\in ]0,1[\), le théorème du point fixe de Banach montre \(\exists \ v_{\alpha,\lambda} \in C^0(X),\ \mathcal{K} v_{\alpha,\lambda}=v_{\alpha,\lambda}\).
Lemme 2. On choisit \(\,x_0 \in X\). On a \(\forall \alpha \in ]0,1[, \ \exists ! \ \lambda_\alpha \in \mathbb{R},\ \exists\, u_\alpha \in C^0(X),\ u_\alpha(x_0)=0\) et \begin{equation}\tag{11} \forall x \in X,\quad \max_{y \in X} \{K(x,y)-\lambda_\alpha T(x,y)+\alpha u_\alpha(y)\}=u_\alpha(x). \end{equation} De plus, \begin{equation}\tag{12} \lambda_\alpha = \max_{(x_n)_{n\geq 1}} \frac{\sum_{n=0}^\infty \alpha^n K(x_n,x_{n+1})}{\sum_{n=0}^\infty \alpha^n T(x_n,x_{n+1})}\, . \end{equation}
Preuve. Soit α \(\in ]0,1[\). Pour tout λ \(\in \mathbb{R}\), on choisit \(v_{\alpha,\lambda}\) comme dans le lemme 1 et on définit \[u_{\alpha,\lambda}=v_{\alpha,\lambda}-v_{\alpha,\lambda}(x_0),\quad r_{\alpha,\lambda}=(1-\alpha) \, v_{\alpha,\lambda}(x_0).\] D'après le lemme 1, \[\forall \lambda \in \mathbb{R},\quad \forall x\in X,\quad \max_{y\in X} \{K(x,y)-\lambda T(x,y)+\alpha\, u_{\alpha,\lambda}(y) \} = r_{\alpha,\lambda} + u_{\alpha,\lambda}(x).\] On a \begin{equation}\tag{13} \forall \lambda \in \mathbb{R},\quad r_{\alpha,\lambda}=(1-\alpha) \max_{(x_n)_{n\geq 1}} \left \{\sum_{n=0}^{+\infty} \alpha^n K(x_n,x_{n+1}) - \lambda \sum_{n=0}^{+\infty} \alpha^n T(x_n,x_{n+1}) \right \}. \end{equation} Pour le prouver, on a \begin{equation}\tag{14} \forall (x_n)_{n\geq 1},\quad \forall n\in \mathbb{N},\quad K(x_n,x_{n+1}) - \lambda T(x_n,x_{n+1})+\alpha \, u_{\alpha,\lambda}(x_{n+1}) \leq r_{\alpha,\lambda} + u_{\alpha,\lambda}(x_n)\, . \end{equation} On multiplie cette équation par \(\alpha^n\). On fait la somme et on utilise \(\,u_{\alpha,\lambda}(x_0)=0\). On obtient \begin{equation}\tag{15} \sum_{n=0}^{+\infty} \alpha^n K(x_n,x_{n+1}) - \lambda \sum_{n=0}^{+\infty} \alpha^n T(x_n,x_{n+1}) \leq \frac{r_{\alpha,\lambda}}{1-\alpha}\, . \end{equation} L'inégalité est une égalité s'il y a égalité dans (14) pour tout n. Ceci prouve (13).
D'après (13), \(\,\lambda \mapsto r_{\alpha,\lambda}\,\) est une fonction convexe (donc continue) et une fonction décroissante, puisque c'est l'enveloppe supérieure de fonctions linéaires décroissantes de λ. De plus,
Lemme 3. On choisit \(\,x_0 \in X\). On a : \(\exists \, \lambda \in \mathbb{R}, \ \exists u \in C^0(X),\) \begin{align} & u(x_0)=0,\nonumber\\ &\lim_{\alpha\to 1^-} \lambda_\alpha = \lambda, \nonumber\\ &\forall x \in X,\quad \max_{y \in X} \{K(x,y)-\lambda T(x,y) +u(y) \} = u(x). \tag{16} \end{align}
Preuve. Tout d'abord, la formule (12) implique que pour tout α \(\in ]0,1[\), \(|\lambda_\alpha| \leq \|K\|/\delta_T\). On va montrer : \((u_\alpha)_{\alpha \in (0,1)}\,\) est une famille équicontinue. Soit x\(\in X\) et ε \(\in \mathbb{R}_+^*\). Puisque les fonctions K et T sont uniformément continues, \[\exists \eta \in\mathbb{R}_+^*, \quad d(x,x')\leq \eta \Rightarrow \max_{y \in X} |K(x,y)-K(x',y)|\leq \varepsilon,\quad \max_{y \in X} |T(x,y)-T(x',y)|\leq \varepsilon.\] Avec \(d(x,x')\leq \eta\), on a \begin{align*} \forall \alpha \in ]0,1[,\quad u_\alpha(x)-u_\alpha(x')&=\max_{y \in X} \{K(x,y)-K(x',y)-\lambda_\alpha (T(x,y)-T(x',y))\\ &\quad +K(x',y)-\lambda_\alpha T(x',y) + \alpha\, u_\alpha(y) \}\\ &\quad - \max_{y\in X} \{K(x',y)-\lambda_\alpha T(x',y)+\alpha u_\alpha(y) \}\\ &\leq \varepsilon + \frac{\|K\|}{\delta_T}\, \varepsilon, \end{align*} et par symétrie, \(|u_\alpha(x)-u_\alpha(x')|\leq \varepsilon (1+\|K\|/\delta_T)\). \(\,(u_\alpha)_{\alpha \in ]0,1[}\,\) est donc une famille équicontinue.
On va montrer que \(\,(u_\alpha)_{\alpha \in ]1/2,1[}\,\) est une famille uniformément bornée. Avec (11), \[\forall \alpha \in ]1/2,1[, \ \forall y \in X,\quad K(x_0,y)-\lambda_\alpha T(x_0,y)+\alpha\, u_\alpha(y)\leq u_\alpha(x_0)=0.\] On a donc \(u_\alpha(y)\leq 2\|K\| (1+\|T\|/\delta_T)\). Avec (11), on a aussi \[ \forall x\in X,\quad u_\alpha(x) \geq K(x,x_0)-\lambda_\alpha\, T(x,x_0)+\alpha\, u_\alpha(x_0)=K(x,x_0)-\lambda_\alpha \, T(x,x_0)\, .\] On a donc \(u_\alpha(x) \geq -\|K\| (1+\|T\|/\delta_T)\) et \(\,(u_\alpha)_{\alpha \in ]1/2,1[}\,\) est uniformément borné.
On choisit \(\alpha_n\in ]1/2,1[\) avec \(\alpha_n\to 1^-\) si \(n\to +\infty\). D'après le théorème de \(\ \text{Bolzano}\) et le théorème d'Ascoli, \(\exists\ (\alpha_{\phi(n)})\), \(\exists \ \lambda\in \mathbb{R}\), \(\exists \ u\in C^0(X)\) avec