Compléments des compléments de Calcul Différentiel

Subsection 4.1 Conditions d'ordre 2 pour les contraintes d'égalité

On prend une fonction objectif

et \(p\) contraintes:

toutes deux de classe \(\mathcal C^2\) sur l'ouvert \(U\) de \(\R^n\text{.}\)

Pour ne pas changer, on cherche les extrema de \(f\) parmi les points contraints par \(g\text{:}\)

où on note \(\Gamma=\{x\in U, g_1(x)=b_1,g_2(x)=b_2,...,g_p(x)=b_p\}\text{.}\)

Ce qu'on sait déjà, avec le Théorème des Extrema Liés, c'est que si \(x^*\) est une solution de \((\mathcal P)\) telle que l'application linéaire \(Dg(x^*)\in\L(\R^n,\R^p)\) est surjective, alors il existe \((\lambda^*_1,\ldots,\lambda^*_p)\) tels que

Autrement dit, une solution de \(x^*\) est un point critique de la fonction

Finalement, du coup, la condition nécessaire d'ordre 1 sous contrainte se ramène à la recherche de points critiques d'une nouvelle fonction qui tient compte à la fois de la fonction objectif \(f\) et des contraintes \(g_i\text{.}\)

Si on veut des conditions suffisantes, on pourrait tenter d'appliquer les conditions suffisantes d'ordre 2 à cette nouvelle fonction !

La seule difficulté, c'est le choix des \(\lambda_i^*\text{,}\) qui dépendent aux aussi de \(x^*\text{.}\)

On va donc les ajouter à la définition de notre nouvelle fonction. On introduit donc en fanfare:

que l'on appelle le lagrangien.

On introduit quelques notations un peu similaires à celles du TFI: pour \(\lambda \in \R^p,\) on notera

• \(\nabla_x \mathscr L(x,\lambda) \in \R^n\) le gradient de l'application \(x\in U \mapsto \mathscr L(x,\lambda)\in \R\)

• \(D_x\mathscr L(x,\lambda)\in \L(\R^n,\R)\) la différentielle de cette même application;

• et \(H_x\mathscr L(x,\lambda)\in\M_n(\R)\) sa hessienne.

En ces termes, ce que dit le théorème des extrema liés, c'est que si \(x^*\) est une solution locale de \((\mathcal P)\) telle que l'application linéaire \(Dg(x^*)\in\L(\R^n,\R^p)\) est surjective, alors il existe \(\lambda^*\in\R^p\) tel que

autrement dit, \(x^*\) est un point critique de \(x\mapsto \mathscr L(x,\lambda^*)\text{.}\)

Et de là, en continuant sur cette lancée, on va cherche des d'optimalité pour le problème contraint \((\mathcal P)\) en appliquant les conditions d'ordre 2 pour les problèmes sans contraintes au Lagrangien:

Exercice (CN2C) avec contraintes affines

Supposons dans un premier temps que \(g\) est une application affine: il existe alors une matrice \(M\in \M_{p,n}(\R)\) et \(b\in\R^p\) tels que

\begin{equation*} g:x\in\R^n \mapsto Mx-b \end{equation*}

1. Un peu de traduction.

Pour \(i=1,\ldots,n\text{,}\) on note \(\ell_i \in\R^n\) les lignes de \(M\text{.}\)

Exprimer \(D g(x)\) en fonction de \(M\text{.}\)

\(\leadsto\) Que devient l'hypothèse \(\rg Dg(x^*)=p\) ? Qu'est-ce que ça implique sur les \(\ell_i\) ?

Spoiler.

2.

Calculer \(\nabla_x \mathscr L(x,\lambda)\) et \(H_x\mathscr L(x,\lambda)\) dans ce cas particulier.

Spoiler.

3.

Montrer que, si \(u\in \Ker M\text{,}\) alors pour \(k\in\N^*\) suffisamment grand, \(x^*+\dfrac1k u\in \Gamma\text{.}\)

Spoiler.

4.

Montrer que

\begin{equation*} {}^tu\cdot Hf(x^*)u \geq 0 \end{equation*}

Indice.

Appliquer la formule de Taylor à l'ordre 2 à \(f\) en \(x^*\) (qui, rappelons-le, est un minimum local de \(f_{|\Gamma})\)), et utiliser allègrement les calculs qu'on a fait en 1. et en 2.

Spoiler.

5.

Obtenir majestueusement la conclusion souhaitée.

Dans un élan d'humilité, se souvenir que c'est le cas facile.

Spoiler.

Revenons maintenant au cas général: \(g\) est maintenant simplement une fonction \(\mathcal C^2\text{,}\) pas nécessairement affine, mais tout de même très fréquentable.

On suppose donc que \(x^*\in \Gamma=g^{-1}(\{0_{\R^p}\})\) est une solution (local) du problème

ce qui nous donne des multiplicateurs de Lagrange \(\lambda^* =(\lambda_1^*,...,\lambda_1^*)\in\R^p\) tels que

et ce qui nous remplirait de joie, ce serait que

soit une matrice symétrique positive sur \(\Ker Dg(x^*)\text{.}\)

On prend donc \(u\in Ker Dg(x^*)\) et on veut que

Exercice Interlude: Construction de suites noyautées

Nous interrompons notre programme pour céder à une subite envie de générer des suites de \(\Gamma\) qui tendent vers \(x^*\) et telles que \(Dg(x^*)(x^*-z_k)=0_{\R^p}\text{.}\)

Toute ressemblance avec la suite \(z_k=x^*+\frac1k u\) de la section précédente serait fortuite.

1.

Soit \(Z_1,Z_2\ldots\) une base de \(\Ker Dg(x^*)\text{:}\) on note \(Z\) la matrice dont les colonnes sont les vecteurs \(Z_j\text{.}\)

Quelle est la taille de \(Z\) ? Que donnent \(\rg Z\) et \(\Ker Z\) ?

Spoiler.

Puisqu'on a supposé que \(\rg Dg(x^*)=p\text{,}\) le théorème du rang nous dit que

\begin{equation*} \dim \Ker Dg(x^*) = \dim \R^n - \rg Dg(x^*)=n-p \end{equation*}

donc il y a \(n-p\) vecteurs \(Z_j\text{,}\) et ce sont des vecteurs de \(\R^n\text{,}\) ce qui nous donne une matrice \(Z\in\mathcal M_{n,n-p}(\R)\text{.}\)

On a, pour tout \(u=(u_1,\ldots, u_n)\in\R^{n-p},\)

\begin{equation*} Zu= \left(\begin{array}{c|c|c|c}\ Z_1\amp Z_2 \amp ... \amp Z_{n-p}\ \end{array}\right)\cdot \begin{pmatrix}u_1\\\vdots\\u_{n-p}\end{pmatrix} = u_1Z_1+\ldots+u_{n-p}Z_{n-p} \end{equation*}

donc \(\Image Z = \{Zu,u\in \R^{n-p}\}=\vect(Z_1,\ldots,Z_{n-p}).\)

Puisque \(\{Z_1,\ldots,Z_{n-p}\}\) est une base de \(\Ker Dg(x^*)\text{,}\) on a donc

\begin{equation*} \rg Z = \dim \Image Z = \dim \vect(Z_1,\ldots,Z_{n-p}) = n-p \end{equation*}

Enfin, si \(u=(u_1,\ldots, u_n)\in \Ker Z\text{,}\) le même calcul nous donne

\begin{equation*} 0_{\R^n}=Z\cdot u= = u_1Z_1+\ldots+u_{n-p}Z_{n-p} \end{equation*}

Or \(\{Z_1,\ldots,Z_{n-p}\}\) est une base, donc une famille libre, donc ceci implique

\begin{equation*} u_1=....=u_{n-p}=0,\text{ i.e. } u=0_{\R^{n-p}} \end{equation*}

Autrement dit, \(\Ker Z = \{0_{\R^{n-p}}\}.\text{.}\)

2.

Soit \(u\in \Ker Dg(x^*)\text{.}\) Montrer que \(u\in \Image(Z)\text{,}\) et en déduire que

\begin{equation*} \text{Si } {}^t Zu = 0_{\R^{n-p}} \text{ alors } u=0_{\R^n} \end{equation*}

Spoiler.

Puisque \(u\in \Ker Dg(x^*)=\vect(Z_1,...,Z_{n-p})\text{,}\) il existe des réels \(\mu_1,\ldots,\mu_{n-p}\) tels que

\begin{equation*} u=\mu_1Z_1+...+\mu_{n-p}Z_{n-p} = \left(\begin{array}{c|c|c|c}\ Z_1\amp Z_2 \amp ... \amp Z_{n-p}\ \end{array}\right)\cdot \begin{pmatrix}\mu_1\\\vdots\\\mu_{n-p}\end{pmatrix} = Z\mu \end{equation*}

en notant \(\mu\) le vecteur \({}^t(\mu_1,...,\mu_{n-p})\in\R^{n-p}\text{,}\) et donc \(u=Z\cdot \mu \in \Image Z\text{.}\)

Et du coup, si \({}^t Zu = 0_{\R^{n-p}}\text{,}\) on a

\begin{equation*} {}^t ZZ\mu = 0_{\R^{n-p}}\text{, donc } ( {}^t ZZ\mu) \cdot \mu =0 \end{equation*}

Or, \(( {}^t ZZ\mu) \cdot \mu = (Z\mu)\cdot (Z\mu) = \|Z\mu\|^2\text{,}\) donc

\begin{equation*} {}^t Zu = 0_{\R^{n-p}} \Rightarrow Z\mu=0_{\R^{n-p}} \Rightarrow \mu \in \Ker Z \end{equation*}

et on a trouvé que \(\Ker Z=\{0_{\R^{n-p}}\}\text{,}\) donc on en déduit que \(\mu=0_{\R^{n-p}}\) et donc

\begin{equation*} u=Z\cdot 0_{\R^{n-p}} = 0_{\R^n}. \end{equation*}

3.

Munis de cette splendide matrice, on introduit l'application

\begin{equation*} R:(z,t)\in U\times \R \mapsto (g(z),{}^tZ(z-x^*+tu))\in\R^p\times\R^{n-p} \end{equation*}

Calculer la \(\Jac R(z,t)\text{.}\) En déduire que la différentielle en \(x^*\) de l'application partielle

\begin{equation*} z\in U\mapsto R(z,0) \end{equation*}

est inversible.

Spoiler.

4.

Montrer qu'il existe un intervalle \(I\subset \R\) contenant \(0\) et une fonction \(C^1\) \(\varphi:I\rightarrow \R^n\) telle que, pour tout \(t\in I\text{,}\)

\begin{equation*} \varphi(t)\in \Gamma \text{ et } \varphi(t)-x^*-tu \in \Ker({}^tZ) \end{equation*}

Indice.

Tropisme des Flocons Ignifugés ?

Spoiler.

5.

Déterminer \(\varphi(0)\) et \(\varphi'(0)\text{.}\)

Spoiler.

6.

Soit \((t_k)\in \R_+^\N\) une suite positive qui tend vers 0. Montrer que \(z_k=\varphi(t_k)\in \Gamma\) pour \(k\) assez grand, et que \(z_k\rightarrow x^*\text{.}\)

Spoiler.

Exercice Reprise de la quête principale: (CN2C) avec contrainte \(\mathcal C^2\)

Equipés de notre suite \((z_k)_k\in\Gamma^\N\text{,}\) reprenons notre objectif initial: montrer que

\begin{equation*} {}^tu\, H_x\mathscr L(x^*,\lambda^*)\, u \geq 0 \end{equation*}

1.

Montrer que, pour tout \(k\in \N\text{,}\)

\begin{equation*} f(z_k) -f(x^*) = \frac{t_k^2}2\ {}^tu \cdot H_x\mathscr L(x^*,\lambda^*)\cdot u+t_k^2\varepsilon(t_k)^2 \end{equation*}

avec \(\varepsilon(s)\xrightarrow[s\rightarrow 0]{} 0\text{.}\)

Indice.

Appliquer la formule de Taylor à l'ordre 2 à une fonction dont le nom évoque une chanson de ZZ Top.

Spoiler.

2.

Supposons, par l'absurde, que \({}^tu\, H_x\mathscr L(x^*,\lambda^*)\, u \lt 0\) et cherchons l'erreur.

Montrer que, si c'est le cas, on peut trouver un point \(z\in \Gamma\) proche de \(x^*\) tel que

\begin{equation*} f(z) \lt f(x^*) \end{equation*}

Spoiler.

3.

Exterminer la contradiction et conclure.

Spoiler.

Tout ceci est positivement merveilleux, mais généralement, les extrema de la fonction objectif, on ne les a pas à l'avance: on les cherche.

Autrement dit, à la place d'un théorème qui nous dit que

"Si \(x^*\) est un extremum local, alors \(x^*\) est Truc"

on préfèrerait un théorème qui nous donne les extrema:

"Si \(x^*\) est Truc, alors \(x^*\) est un extremum local"

Autrement dit, une condition suffisante d'extrémitude.³

Et nos conditions nécessaires d'ordre 1 et d'ordre 2 ne sont pas suffisantes:

Appliquer les conditions nécessaires d'ordre 1 et 2 à la fonction

\begin{equation*} f:(x,y,z)\in\R^3\mapsto x^3+3y^2+z^2 \end{equation*}

sur l'ensemble \(\Gamma=\{(x,y,z)\in\R^3, z^4+z^2=1\}\text{.}\)

\(\leadsto\) Montrer que le lagrangien admet un unique point critique \(x^*\) et que \(H_x\mathscr L(x^*,\lambda^*)\) est positive sur \(\Ker Dg(x^*)\text{,}\) mais que \(x^*\) n'est pas un extremum local de \(f_{|\Gamma}\text{.}\)

Indice.

Spoiler.

Il nous faudrait donc une vraie condition suffisante.

Ca tombe bien, j'en ai une à vous vendre !

En reprenant les notations du théorème précédent:

Exercice (CS2C) avec contraintes affines

Commençons par l'échauffement: on va traiter le cas où \(g:x\in\R^n \mapsto Mx-b\) est une application affine, avec \(M\in \M_{p,n}(\R)\) et \(b\in\R^p\text{.}\)

1.

Pour \(i=1,\ldots,n\text{,}\) on note \(\ell_i \in\R^n\) les vecteurs correspondants aux lignes de \(M\text{.}\)

Premièrement, que sait-on ? Traduire les hypothèses 1,2,3 en fonction de \(M,\ell_i\) et \(Hf(x^*)\text{.}\)

Spoiler.

2.

Soit donc \(x^*\in \Gamma\) un point vérifiant ces trois hypothèses traduites, et soit \(\lambda^*\in\R^p\) les multiplicateurs de Lagrange associés.

Le but du jeu est de trouver un voisinage de \(x^*\text{,}\) disons une boule \(B(x^*,r)\) telle que pour tout \(x\in B(x^*,r)\cap \Gamma\text{,}\) on ait \(f(x)\geq f(x^*)\text{.}\)

Soit \(\rho \gt 0\) tq \(B(x^*,\rho)\subset U\) et soit \(x\in B(x^*,\rho)\cap \Gamma\text{.}\) Montrer qu'il existe \(c\in[0,1]\) et un vecteur \(u\in \Ker(M)\) tels que

\begin{equation*} f(x) = f(x^*) + \frac12\,{}^tu Hf(x^*+c(x-x^*))\,u \end{equation*}

Indice.

Remarquer que la fonction

\begin{equation*} \alpha:t\in[0,1]\mapsto \mathscr L(x^*+t(x-x^*))\in \R \end{equation*}

existe, déjà, et admet un développement du tailleur dans la grange, ou un proverbe du même genre.

Spoiler.

3.

Du coup, tout ce qui manque à notre béatitude, c'est un rayon \(r\gt 0\) tel que si \(x\in B(x^*,r)\cap \Gamma\) alors, pour tout \(u\in \Ker(M)\) et pour tout \(c\in[0,1]\text{,}\)

\begin{equation*} \frac12\,{}^tu Hf(x^*+c(x-x*))\,u \gt 0 \end{equation*}

Ce qui ressemble à l'hypothèse (3), mais pas tout à fait, car ce n'est pas \(Hf(x^*)\) qu'on utilise.

La question est donc: la Hessienne de \(f\) a-t-elle la politesse de rester définie positive sur \(\Ker(M)\) au voisinage de \(x^*\) ?

On aimerait donc, idéalement, minorer \({}^tu Hf(x^*+c(x-x^*))\,u\) par un truc positif. L'ennui, c'est que si \(u\in\Ker(M)\) est tout petit, alors \({}^tu Hf(y)\,u\) sera aussi tout petit, quelle que soit la matrice \(Hf(y)\text{,}\) même si elle est définie positive: ça ne pas être évident de trouver une minoration qui marche en général.

Petit détour par la sphère: On va donc commencer par regarder les aimables vecteurs de \(\Ker(M)\) qui sont de norme 1:

\begin{equation*} S=\{u\in \Ker(M), \|u\|=1\} \end{equation*}

et on s'intéresse à la fonction

\begin{equation*} \varphi:(u,y)\in S\times U \mapsto {}^tu Hf(y)\,u \in \R \end{equation*}

Justifier qu'il existe \(u_{min}\in S\) tel que, pour tout \(u \in S\text{,}\)

\begin{equation*} \varphi(u,x^*)\geq \varphi(u_{min},x^*)\gt 0 \end{equation*}

Indice.

Est-ce qu'il ne serait pas compact, \(S\text{,}\) par hasard ?

Si c'est le cas, Karl peut nous aider.⁸

Spoiler.

4.

On note \(m=\frac12 \varphi(u_{min},x^*)\text{.}\)

Montrer que pour tout \(u\in S\text{,}\) il existe un voisinage \(V_u\subset \Ker(M)\) de \(u\) et un voisinage \(W_u \subset U\) de \(x^*\) tels que

\begin{equation*} \text{Pour tout } v\in V_u, \text{ pour tout }x\in W_u,\varphi(v,x)\gt m \end{equation*}

Indice.

On aura \(\varphi(v,x)\gt m\) ssi \((v,x)\in\varphi^{-1}(\rbb m,+\infty\lbb)\) qui est l'image réciproque d'un ouvert par une fonction pas méchante.

Spoiler.

5.

Montrer qu'on n'a pas besoin de tous les \(V_u\) pour contenir les vecteurs de \(S\text{:}\) il y a une sous-famille finie d'ouverts \(V_{u_1},...,V_{u_m}\) qui vérifient à eux tous seuls

\begin{equation*} S\subset \left(V_{u_1}\, \cup \,...\, \cup\, V_{u_m}\right) \end{equation*}

Indice 1.

Heine

Indice 2.

Borel

Indice 3.

Lebesgue

Spoiler.

6.

A chacun des \(V_{u_k}\) correspond un \(W_{u_k}\text{.}\) On note \(W=W_{u_1}\cap....\cap W_{u_m}\text{.}\)

Montrer que pour tout \(u\in S\) et pour tout \(x\in W\text{,}\)

\begin{equation*} {}^t u Hf(x) u \gt m \end{equation*}

et en déduire que, pour tous \(v\in \Ker(M)\) et \(x\in W\)

\begin{equation*} {}^t v Hf(x) v \geq m\, \|v\|^2 \end{equation*}

Spoiler.

7.

Fin du détour: Aller prendre l'air, et recentrer ses chakras: qu'est-ce qu'on voulait montrer, déjà ?

Montrer, donc, qu'il existe \(r\gt 0\) tel que \(B(x^*,r)\subset U\) et

\begin{equation*} \text{Pour tout }x\in B(x^*,r), f(x)\geq f(x^*) \end{equation*}

et conclure affinement.

Spoiler.

Exercice Plat de résistance: (CS2C) avec contrainte \(\mathcal C^2\)

Cette fois, on suppose que \(g\) est une fonction \(\mathcal C^2\text{,}\) et donc, conformément au Tao du Calcul Différentiel, "pas affine, mais pas loin".

On prend donc \(x^* \in \Gamma\text{,}\)\(\lambda^*\in\R^p\) qui vérifient les conditions 1.,2. et 3. du théorème, et il s'agit de trouver un voisinage, disons une boule \(B(x^*,r)\text{,}\)telle que

\begin{equation*} \text{Pour tout }x\in B(x^*,r)\cap \Gamma,\ f(x)\geq f(x^*). \end{equation*}

On va faire plus précis: on va trouver un \(m\gt 0\) tel que, pour chaque \(\varepsilon \in \lbb 0,m \lbb\text{,}\) il existe un \(r_\varepsilon\gt 0\) tel que

\begin{equation*} \text{Pour tout }x\in B(x^*,r_\varepsilon)\cap \Gamma, f(x) \geq f(x^*)+\frac{\varepsilon}2 \|x-x^*\|^2 \end{equation*}

1.

En reprenant le raisonnement qu'on a fait dans le détour du cas affine, montrer qu'il existe \(m\gt 0\) tel que, pour tout \(v\in \Ker Dg(x^*)\text{,}\)

\begin{equation} {}^tv\,H_x\mathscr L(x^*) \,v \geq m\|v\|^2\tag{4.1} \end{equation}

Spoiler.

2.

On va obtenir ce qu'on a promis avec ce \(m\gt 0\text{:}\) on doit donc montrer que

Affirmation 4.6.

Pour chaque \(\varepsilon \in \lbb 0,m \lbb\text{,}\) il existe un \(r_\varepsilon\gt 0\) tel que tout \(x\in B(x^*,r_\varepsilon)\cap \Gamma\text{,}\)

\begin{equation*} f(x) \geq f(x^*)+\dfrac{\varepsilon}2 \|x-x^*\|^2 \end{equation*}

et on va faire ça par l'absurde. Supposons donc que l'Affirmation 4.6 est fausse.

Trouver un \(\varepsilon_0 \lt m\) et une suite \((x_k)_k\in \Gamma^\N\) tels que

1. \(\displaystyle x_k\xrightarrow[k\rightarrow\infty]{}x^*\)

2. Pour tout \(k\in\N^*\text{,}\)

   \begin{equation} f(x_k)\lt f(x^*) + \dfrac{\varepsilon_0}2 \|x_k-x^*\|^2\tag{4.2} \end{equation}

Spoiler.

3.

Justifier que la suite \(\left(\frac{x_k-x^*}{\|x_k-x^*\|}\right)_k\) admet une sous-suite convergente, disons \(\left(\frac{x_{\varphi(k)}-x^*}{\|x_{\varphi(k)}-x^*\|}\right)_k\text{.}\) On note \(z_k=x_{\varphi(k)}\) et \(u=\lim_{k\rightarrow\infty}\dfrac{z_k-x^*}{\|z_k-x^*\|}\text{.}\)

Montrer que \(u\in\Ker Dg(x^*)\text{.}\)

Indice.

Pour la sous-suite convergente, demander à Karl et Bernard⁹.

Ensuite, exprimer \(g(z_k)\) à l'aide d'un développement de Taylor de \(g\) en \(x^*\) et triturer la formule obtenue pour faire apparaître

\begin{equation*} Dg(x^*)\left(\frac{z_k-x^*}{\|z_k-x^*\|}\right) \end{equation*}

Spoiler.

4.

Montrer que, pour tout \(k\in\N\text{,}\)

\begin{equation*} f(z_k)=f(x^*)+\frac{\|z_k-x^*\|^2}{2}\,{}^tu\cdot H_x\mathcal L(x^*,\lambda^*)\cdot u + \|z_k-x^*\|^2R_k \end{equation*}

avec \(R_k\xrightarrow[k\rightarrow \infty]{}0\text{.}\)

Indice 1.

Utiliser un 150ème développement de Taylor, cette fois avec une fonction aux connotations agricoles, en \(z_k\text{.}\)

Se rappeler que \(z_k\in \Gamma\) et que \((x^*,\lambda^*)\) vérifie l'hypothèse 2.

Indice 2.

De plus,

\begin{equation*} z_k-x^*=\|z_k-x^*\|(u+\varepsilon_k),\text{ avec }\varepsilon_k\xrightarrow[k\rightarrow \infty]{}0_{\R^n}. \end{equation*}

Spoiler.

5.

En déduire une contradiction entre l'inégalité (4.1) que doit vérifier \(H_x\mathscr L(x^*,\lambda^*)\) et l'équation (4.2) (notre hypothèse par l'absurde).

Spoiler.

6.

Conclure optimalement.

Spoiler.

Subsection 4.2 Dépendance à un paramètre: le théorème de l'enveloppe

Supposons qu'on souhaite maximiser/minimiser une fonction qui dépend d'un paramètre \(\alpha\) (ou de plusieurs paramètres \(\alpha_1,\ldots,\alpha_p\)), et on aimerait comprendre comment les extrema de notre fonctions seront modifiés par une modification du paramètre.

Précisons un peu cette question.

Soient \(n>p\) et \(U\subset \R^n,V\subset \R^p\) deux ouverts. On va s'intéresser à une fonction \(C^2\) sur \(U\times V\) à valeurs réelles:

On pose, pour chaque \(\alpha_0\in V\text{,}\) \(f_{\alpha_0}: x\in U \mapsto f(x,\alpha)\text{.}\)

\(\leadsto\) Pour une valeur donnée \(\alpha_0\) des paramètres, on résoud le problème d'optimisation

et ce qu'on veut comprendre, c'est comment le point minimum de \(f_\alpha\) et la valeur minimale de \(f_\alpha\) dépendent de \(\alpha\text{.}\)

Soient \(\alpha_0\in V\) et \(x_0\in U\) tels que \(\nabla f_{\alpha_0}(x_0)=0_{\R^n}\) et \(Hf_{\alpha_0}(x_0)\) est symétrique définie positive. Ainsi, d'après la Condition Suffisante d'ordre 2, \(x_0\) est solution de \(\mathcal P(\alpha_0)\text{.}\)

Exercice TFI et optimisation paramétrée

1.

Soit \(S_n(\R)\) l'espace vectoriel des matrices symétriques de taille \(n\times n\text{.}\)

On note \(S_n^{++}\) le sous-ensemble des matrices définies positives.

Montrer que \(S_n^{++}\) est un ouvert.

Indice.

On note \(A_k\in\M_k(\R)\) la matrice obtenue en ne gardant que les \(k\) premières lignes et colonnes de \(A\) sont positifs.

et on considère pour chaque \(k\) l'application

\begin{equation*} d_k:A\in\S_n(\R)\mapsto \det(A_k) \end{equation*}

En utilisant le critère de Sylvester¹⁰, exprimer \(S_n^{++}\) en fonction des \(d_k\text{.}\)

Spoiler.

2.

Montrer qu'il existe \(r>0\) tel que

\begin{align*} B(x_0,r)\subset U,\ B(\alpha_0,r) \amp\subset V \text{ et }\\ \forall x\in B(x_0,r),\forall \alpha \in B(\alpha_0,r),\amp Hf_\alpha(x) \text{ définie positive.} \end{align*}

Indice 1.

Quelle est la relation entre \(Hf(x,\alpha)\) et \(Hf_\alpha(x)\) ?

Indice 2.

Utiliser le fait que \(f\) est \(\C^2\text{,}\) ce qui nous donne des informations sur \(Hf(x,\alpha)\) au voisinage de \(x_0,\alpha_0\text{.}\)

De là, montrer que \((x,\alpha)\mapsto Hf_\alpha(x)\) est continue.

Spoiler.

3.

Justifier qu'il existe un voisinage \(V_1\) de \(\alpha_0\text{,}\) un voisinage \(U_1\) de \(x_0\) et une fonction \(\varphi: V_1\rightarrow U_1\text{,}\) de classe \(C^1\) sur \(V_1\text{,}\) telle que

\begin{equation*} \begin{array}{ccc} (x,\alpha)\in U_1\times V_1\amp\iff\amp \alpha\in V_1\\ x \text{ point critique de } f_\alpha \amp\amp x=\varphi(\alpha) \end{array} \end{equation*}

Indice 1.

Ca ressemble furieusement au Théorème des Flans Immatériels, ou quelque chose comme ça.

La question est: avec quelle fonction ?

Indice 2.

Pour trouver des points critiques, quelle serait la fonction \(g\) dont on cherche les zéros au voisinage de \((x_0,\alpha_0)\) ? Quelle est sa jacobienne ?

Spoiler.

4.

Justifier qu'il existe \(s\in \lbb 0,r\rbb\) tel que \(B(\alpha_0,s)\subset V_1\text{,}\) et, pour tout \(\alpha\in B(\alpha_0,s)\text{,}\) \(\varphi(\alpha)\in B(x_0,r)\text{.}\)

Spoiler.

5.

Justifier que, pour tout \(\alpha\in B(\alpha_0,s)\text{,}\) pour tout \(x\in U_1\text{,}\) on a

\begin{equation*} f_\alpha(x) \geq f_\alpha(\varphi(\alpha)) \end{equation*}

Spoiler.

6.

On note \(v:\alpha\in B(\alpha_0,s) \in \R^p \mapsto f_\alpha(\varphi(\alpha)) \in\R\text{.}\) Déterminer \(\nabla v(\alpha)\text{.}\)

Spoiler.

Résumons nos résultats dans une belle enveloppe:

¹³

Regardons ce que ça donne pour une fonction vraiment simple:

\begin{equation*} f:(x,\alpha)\in\R\times \R_+^* \mapsto x^2-\alpha x \end{equation*}

Pour une valeur fixée du paramètre \(\alpha \gt 0\text{,}\) on calcule les points critiques de \(f_\alpha(x)=x^2-\alpha x\text{.}\)

On constate que \(f\) est une brave fonction polynomiale sur \(\R \times \R_+^*\text{,}\) elle est donc \(\mathcal C^2\) et on a

\begin{equation*} f_\alpha'(x)=\frac{\partial f}{\partial x}(x,\alpha)= 2x-\alpha \end{equation*}

\(\leadsto\) la fonction \(f_\alpha\) admet un point critique en \(x(\alpha)=\frac{\alpha}2\text{,}\) qui correspond à un minimum global sur \(\R\text{.}\)

Et d'un autre côté,

\begin{equation*} \frac{\partial f}{\partial \alpha}(x,\alpha)= -x \end{equation*}

Voyons maintenant comment la valeur minimale de \(f_\alpha\) varie en fonction de \(\alpha\text{:}\)

A la main: On calcule directement

\begin{equation*} v(\alpha) =f_\alpha(x(\alpha))=x(\alpha)^2-\alpha x(\alpha) \end{equation*}

donc

\begin{align*} \frac{\partial v}{\partial \alpha}(\alpha)\amp = 2\frac{\partial x}{\partial \alpha}(\alpha)x(\alpha) - \alpha \frac{\partial x}{\partial \alpha}(\alpha) - x(\alpha)\\ \amp= \underbrace{(2x(\alpha)-\alpha)}\frac{\partial x}{\partial \alpha}(\alpha) - x(\alpha)\\ \amp = \frac{\partial f_\alpha}{\partial x}(x(\alpha))\frac{\partial x}{\partial \alpha}(\alpha) - x(\alpha) \end{align*}

Or \(x(\alpha)\) est un point critique de \(f_\alpha\text{,}\) donc \(\frac{\partial f_\alpha}{\partial x}(x(\alpha))=0\text{.}\) Et donc au final:

\begin{equation*} \frac{\partial v}{\partial \alpha}(\alpha)= - x(\alpha) \end{equation*}

Avec le théorème de l'enveloppe: Ce qu'on a obtenu, c'est que

\begin{equation*} \frac{\partial v}{\partial \alpha}(\alpha) = \frac{\partial f}{\partial \alpha}(x(\alpha),\alpha) = -x(\alpha) \end{equation*}

Comme on avait trouvé à la main !

Au fait, pourquoi "enveloppe"?

Lorsqu'on a une famille de fonctions

dépendant d'un paramètre réel \(x \in J\text{,}\) on dit qu'une fonction

est l'enveloppe de la famille de fonctions \((f_x)_{x\in J}\text{,}\) si

• pour tout \(t_0\in I\text{,}\) il existe un \(x_{t_0}\in J\) tel que la courbe de \(f_{x_{t_0}}\) est tangente à celle de \(h\) en \(t_0\text{:}\)

  \begin{equation*} \forall t\in I \exists x_t \in J, f_{x_t}(t)=h(t) \text{ et } f'_{x_{t_0}}(t)=h'(t) \end{equation*}

• et d'un autre côté, si pour tout \(x_0\in J\text{,}\) il existe \(t_{x_0} \in I\) tel que la courbe de \(f_{x_0}\) est tangente à la courbe de \(h\) en \(t_{x_0}\text{:}\)

  \begin{equation*} \forall x \in J \exists t_x \in I , f_{x}(t_x)=h(t_x) \text{ et } f'_{x}(t_x)=h'(t_x) \end{equation*}

ce qui, graphiquement, correspond au fait que le graphe de \(h\) "enveloppe" celui des graphes de \(f_x\text{.}\)

On généralise cette notion aux fonctions définies sur \(\R^p\) dépendant d'un paramètre dans \(\R^n\text{,}\) en remplaçant les dérivées par des gradients:

Ce que nous donne le théorème de l'enveloppe, c'est que la fonction

est l'enveloppe de la famille de fonctions \(\alpha \mapsto f_x(\alpha)=f(x,\alpha)\) "paramétrée" par \(x\text{:}\) pour chaque point \(\alpha\text{,}\) il existe une valeur \(X(\alpha)\) du paramètre, telle que

et pour \(n=1, p=1\text{,}\) on retrouve bien cette idée graphique: par exemple dans l'exemple précédent:

Subsection 4.3 Dépendance au second membre d'une contrainte d'égalité

Pour \(b\in\R^p\text{,}\) intéressons-nous au problème d'optimisation

\begin{equation*} (\mathcal P_b) \begin{cases} \text{Minimiser } f(x)\\ g(x) =b\\ x\in U \end{cases} \end{equation*}

¹⁶, où \(f\) et \(g\) sont des fonctions \(\mathcal C^2\) sur un ouvert \(U\subset \R^n\text{.}\)

On note \(\Gamma_b=\{x\in\R^n,g(x)=b\}\text{.}\)

La question est: que deviennent les solutions du problème lorsque \(b\) varie ?

Plus précisément, en supposant qu'on a une solution \(x_{b_0}\in \Gamma_{b_0}\) de \((\mathcal P_{b_0})\text{,}\)

• Si on prend \(b\) près de \(b_0\text{,}\) le problème \((\mathcal P_b)\) admet-il une solution \(x_b\in \Gamma_b\) ?

• Si oui, que peut-on savoir de la fonction \(b\mapsto x_b\) ?

Exercice Variation du second membre

On suppose que \(p\lt n\) et qu'on a un \(b_0\in\R^p\) tel que \((\mathcal P_{b_0})\) admet une solution (locale) \(x_{b_0} \in \Gamma_{b_0}\text{,}\) telle que:

• \(\displaystyle \rg Dg(x_{b_0}) = p\)

• \(\leadsto\) On note \(\lambda_{b_0}\in\R^p\) les multiplicateurs de Lagrange donnés par le TEL, et on suppose de plus que

  \begin{equation*} \text{Pour tout } u\in\Ker(Dg(x_{b_0}))\setminus \{0_{\R^n}\},\ {}^tu\,H_x\mathscr L(x_{b_0},\lambda_{b_0})\,u \gt0 \end{equation*}

  ¹⁸

Ce qu'on veut savoir, c'est s'il existe un voisinage \(V\) de \(b_0\) dans \(\R^p\) tel que, pour tout \(b\in V\text{,}\) \((\mathcal P_b)\) admet aussi une solution \(x_b\text{.}\)

On va voir que la question est plus compliquée que prévue: on va donc se poser une question plus facile:

Existe-t-il un voisinage \(V\) de \(b_0\) dans \(\R^p\) tel que, pour chaque \(b\in V\text{,}\) on peut trouver un point \(x_b\) voisin de \(x_{b_0}\) qui vérifie la condition nécessaire d'ordre 1 pour les problèmes d'optimisaton à contrainte d'égalité ?

1.

Déterminer une fonction \(G:U\times\R^p\times \R^p \rightarrow\R^n\times \R^p\text{,}\) \(\mathcal C^1\) sur \(U\times \R^p\times \R^p\text{,}\) telle que, si \(x_b\) est solution de \((\mathcal P_b)\) et \(\lambda_b=(\lambda_{b,1},...,\lambda_{b,p})\in\R^p\) sont les multiplicateurs de Lagrange associés, alors

\begin{equation*} G(x_b,\lambda_b,b)=(0_{\R^n},0_{\R^p}) \end{equation*}

Indice.

Si c'est le cas, alors \(x_b\in \Gamma_b\text{,}\) autrement dit \(g(x_b)=b\text{,}\) et de plus il existe \(\lambda_b=(\lambda_{b,1},...,\lambda_{b,p})\in\R^p\) tels que

\begin{equation*} \nabla_x\mathscr L(x_b,\lambda_b) = 0_{\R^n},\text{ i.e. } \nabla f(x_b)=\lambda_{b,1}\nabla g_1(x_b)+...+\lambda_{b,p}\nabla g_p(x_b) \end{equation*}

Peut-on fabriquer une fonction \(G\) qui résume ces différentes conditions ?

Spoiler.

2.

Calculer la jacobienne de \(G\) en un point \((x,\lambda,b)\inU\times\R^p\times \R^p\text{.}\)

Spoiler.

3.

Montrer que la sous-matrice \(D_{x,\lambda} G(x_{b_0},\lambda_{b_0},b_0))\) est inversible.

Indice.

Puisque c'est une matrice carrée, il suffit de montrer que \(\Ker(D_{x,\lambda} G(x_{b_0},\lambda_{b_0},b_0)))=\{(0_{\R^n},0_{\R^p})\}\text{.}\)

Spoiler.

4.

En déduire qu'il existe un voisinage \(V \subset \R^p\) de \(b_0\text{,}\) un voisinage \(W=W_1\times W_2 \subset \R^n\times \R^p\) de \((x_{b_0},\lambda_{b_0})\) et une fonction \(\varphi: b\in V\mapsto (X(b),\Lambda(b))\in W_1\times W_2\) tels que

\begin{equation*} \begin{array}{ccc} (x,\lambda,b)\in W_1\times W_2 \times V\amp\iff \amp b\in V\\ x\in\Gamma_b\amp\amp x=X(b)\\ \nabla f(x) = \sum_k \lambda_k \nabla g_k(x)\amp\amp \lambda = \Lambda(b) \end{array} \end{equation*}

Indice.

Transmutation de la Flammèche en Incendie ?

Spoiler.

5.

Mais ça ne suffit pas pour conclure que \(X(b)\) est solution de \((\mathcal P_b)\text{:}\) tout ce qu'on a vérifié, c'est que \(X(b)\) vérifie la condition nécessaire d'ordre 1 !

Pour le moment, on va s'en contenter: pour chaque \(b\in V\text{,}\) on a trouvé un point candidat à l'extrémitude \(X(b)\) associé aux multiplicateurs de Lagrange \(\Lambda(b)=(\Lambda_1(b),...,\Lambda_p(b))\text{.}\)

Voyons maintenant ce qu'on peut dire de la valeur de \(f\) en ce point candidat.

On la note \(v(b)\text{:}\)

\begin{equation*} \forall b\in V', v(b)=f(X(b)) \end{equation*}

Montrer que, pour tout \(b\in V'\text{,}\)

\begin{equation*} \nabla v(b) = \Lambda(b) \end{equation*}

Spoiler.

Résumons nos trouvailles:

On est tombés par hasard sur une interprétation des multiplicateurs de Lagrange: on a obtenu que

autrement dit, le \(i\)-ième multiplicateur \(\lambda_i\) décrit la façon dont la valeur qu'on essaie d'optimiser va réagir si on change la valeur "autorisée" pour la \(i\)-ième contrainte \(g_i\text{.}\)

En économie, cette interprétation est particulièrement éclairante.

Théorie du consommateur: Supposons par exemple que la fonction objectif \(f(x)\) représente l'utilité donnée par la consommation d'un panier de biens contenant une quantité \(x_k\) du \(k\)-ième bien, et supposons qu'on ait une unique contrainte \(g\) représentant la contrainte budgétaire: typiquement de la forme

où \(I\) est le revenu et les \(p_k\) sont les prix des biens. On a alors obtenu que, si on considère le panier optimal \(x(I)\) en fonction du revenu \(I\text{,}\) alors sa valeur \(v(I)=f(x(I))\) vérifie (à l'ordre 1)

\(\leadsto\) \(\lambda\) décrit donc ici l'utilité marginale du revenu: à prix des biens constants, à quel point est-on plus content si on a plus à dépenser ?

Théorie du producteur: Supposons cette fois qu'un producteur cherche à minimiser sa fonction de coût \(f(x)\text{,}\) avec des contraintes \(g_i\) sur les ressources rares nécessaires à la production.

Dans ce cas, \(v(b+te_i)\simeq v(b)+t\lambda_i\) nous dit que, si la contrainte \(g_i\) sur la \(i\)-ème augmente ou diminie de \(t\text{,}\) alors le coût total pour le producteur augmentera ou diminuera de \(\lambda_i t\text{.}\)

\(\leadsto\) S'il était possible au producteur de payer un prix unitaire \(\pi_i\) pour que la contrainte se relâche sur la \(i\)-ème ressource, il aurait intérêt à le faire tant que \(\pi_i \leq \lambda_i\text{.}\)

\(\leadsto\) C'est pour cette raison que les multiplicateurs de Lagrange sont parfois appelés "shadow prices" ou "prix fictifs" dans la littérature économique.

Exercice Une version améliorée dans le cas de contraintes affines

Reprenons la question dans le cas où la contrainte est affine: on suppose donc que

\begin{equation*} g(x)=Mx,\text{ pour une matrice }M\in\mathcal M_{p,n}(\R) \end{equation*}

et on note \(\ell_1,\dots,\ell_n \in\R^n\) les vecteurs correspondants aux lignes de \(M\text{.}\)

Soit à nouveau \(x_{b_0}\in \R^n\) une solution de \((\mathcal P_{b_0})\) et \(\lambda_b=(\lambda_{b_0,1},...,\lambda_{b_0,p})\in\R^p\) le multiplicateurs de Lagrange associés. On suppose que :

On fait les mêmes suppositions que ci-dessus, adaptées à ce cas particulier (voir Exercise 4.1.1):

1. \(Mx_{b_0} = b_0\text{,}\) i.e. \(x_{b_0}\in \Gamma_{b_0}\text{;}\)

2. \(\rg M=p\text{;}\)

3. \(H f(x_{b_0})\) est définie positive sur \(\Ker M\)

On a donc, par le TFI, un voisinage \(V \subset \R^p\) de \(b_0\text{,}\) un voisinage \(W=W_1\times W_2 \subset \R^n\times \R^p\) de \((x_{b_0},\lambda_{b_0})\) et une fonction \(\varphi: b\in V\mapsto (X(b),\Lambda(b))\in W_1\times W_2\) tels que

\begin{equation*} \begin{array}{ccc} (x,\lambda,b)\in W_1\times W_2 \times V\amp\iff \amp b\in V\\ x\in\Gamma_b\amp\amp x=X(b)\\ \nabla f(x) = \sum_k \lambda_k \ell_k\amp\amp \lambda = \Lambda(b) \end{array} \end{equation*}

1.

En reprenant le trajet du petit détour de l'Exercice 4.1, montrer qu'il existe un voisinage \(V'\subset V\) de \(b\) tel que, pour tout \(b\in V'\text{,}\) \(H f (X(b))\) est définie positive sur \(\Ker M\text{.}\)

En déduire que, pour tout \(b\in V'\text{,}\) \(X(b)\) est solution du problème \((\mathcal P(b))\text{.}\)

Indice.

On a une condition suffisante qui nous permet de garantir que \(X(b)\) soit solution locale de \((\mathcal P(b))\text{:}\) il....suffit, dou coup, de trouver un voisinage \(V'\) de \(b_0\) tel que, pour tout \(b\in V'\text{,}\)

\begin{equation*} H_x\mathscr L(X(b),\Lambda(b)) = H_xf(X(b)) \text{ est définie positive sur }\Ker Dg(X(b))=\Ker(M) \end{equation*}

Spoiler.

2.

Qu'est-ce qui nous empêche de faire de même pour le cas général où \(g\) est une fonction \(\mathcal C^2\) sur \(U\) ?

Spoiler.

Subsection 4.4 Dépendance à un paramètre II: enveloppes contraintes

Nos deux derniers résultats, le théorème de l'enveloppe (pour un problème sans contrainte) et la sensibilité au second membre, rentrent dans une catégorie plus large: les problèmes d'optimisation à paramètre, du type

dépendant d'un paramètre \(\alpha\in\R^q\text{.}\)

On se pose les mêmes questions que précédemment:

Supposons que, pour une certaine valeur \(\alpha_0\in V\) du paramètre, on a une solution (locale) \(x_{\alpha_0}\in U\) de \((\mathcal P_{\alpha_0})\text{.}\)

• Si on choisit \(\alpha\) près de \(\alpha_0\text{,}\) le problème \((\mathcal P_\alpha)\) admet-il une solution \(x_\alpha\) proche de \(x_{\alpha_0}\) ?

• Si oui, comment la valeur minimale de \(f\) sur l'ensemble des points admissibles \(\Gamma_\alpha=\{x\in U,g(x,\alpha)=0_{\R^p}\}\) dépend-elle de \(\alpha\) ?

  Autrement dit, que sait-on de la fonction \(\alpha\mapsto f(x_\alpha)\) ?

Comme pour le cas de la variation du second membre, puisque la contrainte \(g_\alpha\) dépend de \(\alpha\text{,}\) on ne pourra pas garantir l'existence d'une solution en vérifiant la condition suffisante d'ordre 2.

Tout ceci considéré, on peut montrer le théorème de l'enveloppe dans toute sa splendide généralité postale:

Exercice Challenge final

Démontrer le théorème du colis recommandé !