Maths C

# ENS – Concours d'admission 2020 — Mathématiques C (ULCR) — Filière MP

## En-tête

**Thème.**

Minimisation d'une fonction $f:\mathbb R^n\to\mathbb R$ sur un sous-domaine $K\subset\mathbb R^n$, et conditions nécessaires d'optimalité en optimisation convexe.

Le fil directeur part des caractérisations de la convexité par le gradient (Partie I), établit existence et unicité d'un minimum sur un convexe fermé via la $\alpha$-convexité et la projection, puis décline trois approches : la **pénalisation** (II), le **théorème de Karush–Kuhn–Tucker** appuyé sur le **lemme de Farkas** (III), et l'étude du **problème dual** culminant avec l'**algorithme d'Uzawa** (IV). Les outils mobilisés relèvent de la topologie des espaces normés de dimension finie, du calcul différentiel et de l'analyse réelle au programme MP.

## Carte stratégique

- **Statistiques (rapport).**

Notes de $0$ à $20$, moyenne $9{,}03$, écart-type $3{,}81$.

Aucune copie complète ; « une poignée » a traité I, II, III en quasi-totalité ; la partie IV « n'a été abordée que par 8% des candidats ».
- **Barème annoncé.** « Répondre correctement aux questions de la première partie permettait déjà d'atteindre une note supérieure à la moyenne. » Y ajouter une deuxième partie « parfaite » donnait « une excellente note ». « Aborder avec succès deux tiers des questions de la troisième partie assurait alors d'avoir la note maximale. »
- **Ordre de traitement conseillé.** I → II → III, dans l'ordre du sujet (les dépendances sont I ⟶ {II, III ⟶ IV}). Ne pas « se cantonner aux questions les plus simples » : le jury prévient que ce parti « n'a guère été récompensé ».
- **Questions discriminantes.** I.4, I.5, I.6.b–c (existence/unicité, projection), II.3, II.5.a, II.6 (rigueur sur les suites et la coercivité), III.1.c, III.3, III.7 (lemme de Farkas et son application). C'est là que se gagnent les points décisifs.
- **Exigence transversale.** Le jury « a lourdement sanctionné les réponses imprécises ou incomplètes » et insiste sur la mise en évidence des résultats.

---

# Partie I — Préliminaires

## Question I.1.a

**Stratégie.**

On exprime la convexité de $f$ via la définition appliquée à des points de la forme $x+t(y-x)=(1-\lambda)a+\lambda b$.

Les deux implications sont des réécritures directes.

**Rédaction.**

Soit $x,y\in\mathbb R^n$ et $\varphi=\varphi_{x,y}$.

($\Rightarrow$) Supposons $f$ convexe.

Soient $s,t\in\mathbb R$, $\lambda\in[0,1]$.

Posons $a=x+s(y-x)$, $b=x+t(y-x)$.

Alors $$x+\big((1-\lambda)s+\lambda t\big)(y-x)=(1-\lambda)a+\lambda b,$$ d'où, par convexité de $f$, $$\varphi\big((1-\lambda)s+\lambda t\big)=f\big((1-\lambda)a+\lambda b\big)\le (1-\lambda)f(a)+\lambda f(b)=(1-\lambda)\varphi(s)+\lambda\varphi(t).$$
Donc $\varphi$ est convexe.

($\Leftarrow$) Supposons $\varphi_{x,y}$ convexe pour tous $x,y$.

Pour $\lambda\in[0,1]$, $$f\big((1-\lambda)x+\lambda y\big)=\varphi_{x,y}(\lambda)=\varphi_{x,y}\big((1-\lambda)\cdot0+\lambda\cdot1\big)\le(1-\lambda)\varphi_{x,y}(0)+\lambda\varphi_{x,y}(1)=(1-\lambda)f(x)+\lambda f(y).$$
Donc $f$ est convexe. $\square$

**Commentaire du correcteur.** Question « en général bien traitée » selon le rapport. Le seul soin réel : bien identifier $(1-\lambda)a+\lambda b$, c'est-à-dire vérifier que la combinaison de paramètres se traduit en combinaison de points.

## Question I.1.b

**Stratégie.** $\varphi_{x,y}=f\circ\gamma$ où $\gamma(t)=x+t(y-x)$ est affine.

On compose la différentielle de $f$ avec $\gamma'$, en rappelant la définition du gradient $\mathrm df(a)(h)=\langle\nabla f(a),h\rangle$.

**Rédaction.**

L'arc $\gamma:t\mapsto x+t(y-x)$ est de classe $\mathcal C^1$ sur $\mathbb R$, de dérivée constante $\gamma'(t)=y-x$.

Comme $f$ est différentiable sur $\mathbb R^n$, la composée $\varphi_{x,y}=f\circ\gamma$ est dérivable et, par la règle de dérivation d'une fonction composée le long d'un arc, $$\varphi_{x,y}'(t)=\mathrm df\big(\gamma(t)\big)\big(\gamma'(t)\big)=\big\langle\nabla f\big(x+t(y-x)\big),\,y-x\big\rangle. \qquad\square$$

**Commentaire du correcteur.** Le jury s'est dit « particulièrement attentif au niveau de compréhension de la notion de différentielle et de gradient » et a sanctionné « les raisonnements trop rapides ou trop vagues ». Il faut donc nommer la composition différentielle/arc et l'identité $\mathrm df(a)(h)=\langle\nabla f(a),h\rangle$, et non écrire le résultat sans justification.

## Question I.1.c

**Stratégie.**

Sens direct : $f$ convexe $\Rightarrow\varphi$ convexe (I.1.a), et une fonction convexe dérivable d'une variable est au-dessus de ses tangentes.

Sens réciproque (le point délicat) : on n'utilise pas $\varphi$, mais on applique l'inégalité de tangence aux deux extrémités depuis le point intermédiaire $z=(1-\lambda)x+\lambda y$.

**Rédaction.** ($\Rightarrow$) Soit $f$ convexe ; par I.1.a, $\varphi=\varphi_{x,y}$ est convexe et dérivable sur $\mathbb R$.

Une fonction convexe dérivable est au-dessus de ses tangentes : $$\varphi(1)\ge\varphi(0)+\varphi'(0)(1-0).$$
Or $\varphi(1)=f(y)$, $\varphi(0)=f(x)$ et, par I.1.b, $\varphi'(0)=\langle\nabla f(x),y-x\rangle$.

D'où $f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle$.

($\Leftarrow$) Supposons l'inégalité vraie pour tous points.

Soient $x,y\in\mathbb R^n$, $\lambda\in[0,1]$ et $z=(1-\lambda)x+\lambda y$.

En appliquant l'hypothèse au couple $(z,x)$ puis $(z,y)$ : $$f(x)\ge f(z)+\langle\nabla f(z),x-z\rangle,\qquad f(y)\ge f(z)+\langle\nabla f(z),y-z\rangle.$$
On multiplie la première par $(1-\lambda)\ge0$, la seconde par $\lambda\ge0$, et on ajoute : $$(1-\lambda)f(x)+\lambda f(y)\ge f(z)+\big\langle\nabla f(z),\,(1-\lambda)(x-z)+\lambda(y-z)\big\rangle.$$
Or $(1-\lambda)(x-z)+\lambda(y-z)=(1-\lambda)x+\lambda y-z=z-z=0$.

Donc $(1-\lambda)f(x)+\lambda f(y)\ge f(z)$, ce qui est la convexité de $f$. $\square$

**Commentaire du correcteur.** « Le sens direct a été en général bien montré, mais le sens réciproque a posé beaucoup de difficultés. » L'astuce gagnante est d'évaluer l'inégalité de sous-gradient **au point intermédiaire** $z$ et de combiner : on évite ainsi tout recours à la monotonie du gradient.

## Question I.1.d

**Stratégie.**

Sens direct : on additionne les deux inégalités de I.1.c écrites en $(x,y)$ et $(y,x)$ — une addition d'inégalités licite.

Sens réciproque : la monotonie du gradient fait croître $\varphi'$, donc $\varphi$ convexe (I.1.a).

Le rapport recommande explicitement de **ne pas** raisonner par équivalence.

**Rédaction.** ($\Rightarrow$) Soit $f$ convexe.

Par I.1.c, $$f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle,\qquad f(x)\ge f(y)+\langle\nabla f(y),x-y\rangle.$$
En ajoutant ces deux inégalités (somme membre à membre de deux inégalités de même sens), $f(x)+f(y)$ se simplifie et il vient $$0\ge\langle\nabla f(x),y-x\rangle+\langle\nabla f(y),x-y\rangle=-\langle\nabla f(y)-\nabla f(x),y-x\rangle,$$ soit $\langle\nabla f(y)-\nabla f(x),y-x\rangle\ge0$.

($\Leftarrow$) Supposons cette monotonie.

Fixons $x,y$ et posons $\varphi=\varphi_{x,y}$, dérivable de dérivée $\varphi'(t)=\langle\nabla f(x+t(y-x)),y-x\rangle$ (I.1.b).

Pour $s<t$, posons $a=x+s(y-x)$, $b=x+t(y-x)$, de sorte que $b-a=(t-s)(y-x)$, donc $y-x=\tfrac{1}{t-s}(b-a)$.

Alors $$\varphi'(t)-\varphi'(s)=\big\langle\nabla f(b)-\nabla f(a),\,y-x\big\rangle=\frac{1}{t-s}\big\langle\nabla f(b)-\nabla f(a),\,b-a\big\rangle\ge0$$ par hypothèse (et $t-s>0$).

Ainsi $\varphi'$ est croissante, donc $\varphi$ est convexe ; par I.1.a, $f$ est convexe. $\square$

**Commentaire du correcteur.** Le jury « a été étonné » que des candidats croient à l'équivalence $(a_1\le a_2\text{ et }a_3\le a_4)\Leftrightarrow a_1+a_2\le a_3+a_4$. L'addition d'inégalités de même sens est une **implication** valable (et c'est tout ce dont on a besoin ici) ; la réciproque est fausse. D'où la consigne de séparer les deux sens.

## Question I.2

**Stratégie.** Application immédiate de la caractérisation I.1.c en $x=x^\star$.

**Rédaction.**

Soit $f$ convexe différentiable avec $\nabla f(x^\star)=0$.

Par I.1.c, pour tout $y\in\mathbb R^n$, $$f(y)\ge f(x^\star)+\langle\nabla f(x^\star),y-x^\star\rangle=f(x^\star).$$
Donc $f$ admet un minimum global en $x^\star$. $\square$

**Commentaire du correcteur.** « Correctement traitée, sauf dans les copies les plus faibles. »

## Question I.3.a

**Stratégie.**

Calcul du gradient de $x\mapsto\tfrac{\alpha}{2}\|x\|^2$, puis traduction de la convexité de $g_\alpha$ par I.1.c et identification avec la définition de la $\alpha$-convexité grâce à l'identité $\|y\|^2-\|x\|^2-2\langle x,y-x\rangle=\|y-x\|^2$.

**Rédaction.**

Comme $\nabla(\|\cdot\|^2)(x)=2x$, on a $\nabla g_\alpha(x)=\nabla f(x)-\alpha x$.

La fonction $g_\alpha$ est différentiable ; par I.1.c, $g_\alpha$ est convexe si et seulement si, pour tous $x,y$, $$g_\alpha(y)-g_\alpha(x)-\langle\nabla g_\alpha(x),y-x\rangle\ge0.$$
Or

$$g_\alpha(y)-g_\alpha(x)-\langle\nabla g_\alpha(x),y-x\rangle
=\big[f(y)-f(x)-\langle\nabla f(x),y-x\rangle\big]-\frac\alpha2\|y\|^2+\frac\alpha2\|x\|^2+\alpha\langle x,y-x\rangle.$$

Le regroupement des termes en $\alpha$ donne $$-\frac\alpha2\|y\|^2+\frac\alpha2\|x\|^2+\alpha\langle x,y-x\rangle=-\frac\alpha2\big(\|y\|^2+\|x\|^2-2\langle x,y\rangle\big)=-\frac\alpha2\|y-x\|^2.$$
Ainsi $$g_\alpha(y)-g_\alpha(x)-\langle\nabla g_\alpha(x),y-x\rangle=\big[f(y)-f(x)-\langle\nabla f(x),y-x\rangle\big]-\frac\alpha2\|y-x\|^2.$$
Cette quantité est $\ge0$ pour tous $x,y$ si et seulement si $f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\tfrac\alpha2\|y-x\|^2$ pour tous $x,y$, c'est-à-dire si et seulement si $f$ est $\alpha$-convexe.

Donc $f$ est $\alpha$-convexe $\iff g_\alpha$ convexe. $\square$

**Commentaire du correcteur.** « Correctement traitée. » Veiller à invoquer I.1.c pour $g_\alpha$ (donc à signaler que $g_\alpha$ est différentiable).

## Question I.3.b

**Stratégie.**

Combiner I.3.a (réduction à $g_\alpha$ convexe) et la caractérisation monotone I.1.d appliquée à $g_\alpha$.

**Rédaction.**

Par I.3.a, $f$ est $\alpha$-convexe $\iff g_\alpha$ convexe.

Par I.1.d, $g_\alpha$ convexe $\iff$ pour tous $x,y$, $\langle\nabla g_\alpha(y)-\nabla g_\alpha(x),y-x\rangle\ge0$.

Comme $\nabla g_\alpha(y)-\nabla g_\alpha(x)=\nabla f(y)-\nabla f(x)-\alpha(y-x)$, $$\langle\nabla g_\alpha(y)-\nabla g_\alpha(x),y-x\rangle=\langle\nabla f(y)-\nabla f(x),y-x\rangle-\alpha\|y-x\|^2.$$
Cette quantité est $\ge0$ si et seulement si $\langle\nabla f(y)-\nabla f(x),y-x\rangle\ge\alpha\|y-x\|^2$.

D'où l'équivalence annoncée. $\square$

**Commentaire du correcteur.** Question d'enchaînement, bien réussie quand I.3.a et I.1.d sont acquises.

## Question I.4

**Stratégie.** On localise le problème dans une boule fermée bien choisie.

Il faut sélectionner $M$ dans la coercivité **à partir d'une valeur de $f$ en un point de $K$** (pour que la boule contienne un point de $K$) et constater que l'on travaille sur un compact non vide.

La continuité y assure l'existence du minimum.

**Rédaction.** $K$ est non vide : fixons $a\in K$.

Posons $M=|f(a)|+1>0$.

Par coercivité, il existe $R>0$ tel que $\|x\|>R\Rightarrow f(x)>M>f(a)$.

Quitte à agrandir $R$, supposons $R\ge\|a\|$.

L'ensemble $B=K\cap\overline B(0,R)$ est fermé (intersection de fermés) et borné, donc compact (dimension finie) ; il est non vide car $a\in B$.

La fonction $f$ étant continue sur le compact $B$, le théorème des bornes atteintes fournit $x^\star\in B$ tel que $f(x^\star)=\min_{B}f\le f(a)$.

Soit $x\in K$ : si $\|x\|\le R$ alors $x\in B$ et $f(x)\ge f(x^\star)$ ; si $\|x\|>R$ alors $f(x)>f(a)\ge f(x^\star)$.

Dans tous les cas $f(x)\ge f(x^\star)$, donc $$f(x^\star)=\inf_{x\in K}f(x),$$ et cet infimum est fini, atteint en $x^\star\in K$. $\square$

**Commentaire du correcteur.** « Nettement plus discriminante. » Deux écueils signalés : choisir $M$ à l'aveugle (« ne pas se contenter de prendre $M=1$ ou $M=f(0)$ puisqu'il n'y a aucune raison que $0$ soit dans $K$ ») et oublier que « a priori $\inf_{x\in K}f(x)=-\infty$ ».

Le passage par un **compact non vide** lève les deux : il garantit à la fois l'existence d'un minorant et l'atteinte de la borne.

## Question I.5

**Stratégie.** Existence : montrer que la $\alpha$-convexité entraîne la coercivité, puis appliquer I.4.

Unicité : exploiter l'inégalité de convexité forte avec terme quadratique strict au point milieu — surtout **ne pas** invoquer $\nabla f=0$, car $K$ n'est pas ouvert.

**Rédaction.** *Existence.*

Par $\alpha$-convexité (définition, avec $x=0$), pour tout $y$, $$f(y)\ge f(0)+\langle\nabla f(0),y\rangle+\frac\alpha2\|y\|^2\ge f(0)-\|\nabla f(0)\|\,\|y\|+\frac\alpha2\|y\|^2\xrightarrow[\|y\|\to+\infty]{}+\infty,$$ le terme quadratique l'emportant : $f$ est coercive.

Elle est continue (différentiable) et $K$ est convexe fermé non vide.

Par I.4, $f$ atteint son minimum sur $K$ en un point $x^\star$.

*Unicité.*

De $g_\alpha$ convexe (I.3.a) on tire, pour $x,y$ et $\lambda\in[0,1]$, $g_\alpha((1-\lambda)x+\lambda y)\le(1-\lambda)g_\alpha(x)+\lambda g_\alpha(y)$, ce qui, en reportant $g_\alpha=f-\tfrac\alpha2\|\cdot\|^2$ et l'identité $(1-\lambda)\|x\|^2+\lambda\|y\|^2-\|(1-\lambda)x+\lambda y\|^2=\lambda(1-\lambda)\|x-y\|^2$, donne $$f\big((1-\lambda)x+\lambda y\big)\le(1-\lambda)f(x)+\lambda f(y)-\frac\alpha2\lambda(1-\lambda)\|x-y\|^2. \tag{$\ast$}$$
Soient $x_1,x_2\in K$ deux minimiseurs, de valeur commune $m$.

Le point $z=\tfrac12(x_1+x_2)$ appartient à $K$ (convexité).

Avec $\lambda=\tfrac12$ dans $(\ast)$ : $$f(z)\le m-\frac\alpha8\|x_1-x_2\|^2.$$
Si $x_1\ne x_2$, alors $f(z)<m$, contredisant la minimalité de $m$.

Donc $x_1=x_2$ : le minimum est unique. $\square$

**Commentaire du correcteur.** « En général mal traitée. » Le rapport rappelle que la **coercivité de $f$ était attendue** pour l'existence, et met en garde : « le théorème affirmant qu'un extremum d'une fonction différentiable vérifie $\nabla f=0$ est valable si $f$ est définie sur un **ouvert** de $\mathbb R^n$ ».

Sur $K$ quelconque, l'argument correct pour l'unicité est la **stricte** décroissance fournie par le terme $\tfrac\alpha8\|x_1-x_2\|^2$.

## Question I.6.a

**Stratégie.**

Le carré de la distance $y\mapsto\|y-x\|^2$ est $2$-convexe ; on applique le théorème d'existence-unicité I.5 sur le convexe fermé non vide $C$.

**Rédaction.**

Posons $\phi:y\mapsto\|y-x\|^2$, différentiable, de gradient $\nabla\phi(y)=2(y-x)$.

Alors $$\langle\nabla\phi(y)-\nabla\phi(y'),y-y'\rangle=2\|y-y'\|^2\ge 2\|y-y'\|^2,$$ donc $\phi$ est $2$-convexe (I.3.b).

Comme $C$ est convexe fermé non vide, I.5 assure que $\phi$ admet un **unique** minimum sur $C$, en un point noté $P_C(x)$.

Minimiser $\|y-x\|^2$ ou $\|y-x\|$ sur $C$ revient au même (la fonction $t\mapsto\sqrt t$ est strictement croissante sur $\mathbb R^+$).

Donc $P_C(x)$ est l'unique point de $C$ tel que $\|P_C(x)-x\|=\inf_{y\in C}\|y-x\|$. $\square$

**Commentaire du correcteur.**

Le jury « a particulièrement apprécié » les candidats utilisant la $2$-convexité de $y\mapsto\|y-x\|^2$ (voie ci-dessus) ou la coercivité de $y\mapsto\|y-x\|$.

Les deux sont admises.

## Question I.6.b

**Stratégie.**

On étudie $\psi_y(t)=\|x-(\bar x+t(y-\bar x))\|^2$, polynôme de degré $2$ en $t$.

La caractérisation s'obtient en traduisant la minimalité de $t=0$ par le signe de $\psi_y'(0)$, et réciproquement par développement direct.

**Rédaction.**

Pour $y\in C$ et $t\in[0,1]$, le point $\bar x+t(y-\bar x)$ appartient à $C$ (convexité).

On a
$$\psi_y(t)=\|x-\bar x\|^2-2t\langle x-\bar x,y-\bar x\rangle+t^2\|y-\bar x\|^2,\qquad \psi_y'(0)=-2\langle x-\bar x,y-\bar x\rangle.$$

($\Rightarrow$) Si $\bar x=P_C(x)$, alors pour tout $y\in C$ et tout $t\in[0,1]$, $\bar x+t(y-\bar x)\in C$ donne $\psi_y(t)\ge\psi_y(0)$.

Ainsi $\psi_y$ a un minimum en $0$ sur $[0,1]$, donc sa dérivée à droite est $\ge0$ : $\psi_y'(0)\ge0$, soit $\langle x-\bar x,y-\bar x\rangle\le0$.

($\Leftarrow$) Supposons $\langle x-\bar x,y-\bar x\rangle\le0$ pour tout $y\in C$.

Pour $y\in C$, $$\|x-y\|^2=\|(x-\bar x)+(\bar x-y)\|^2=\|x-\bar x\|^2-2\langle x-\bar x,y-\bar x\rangle+\|\bar x-y\|^2\ge\|x-\bar x\|^2,$$ les deux derniers termes étant $\ge0$.

Donc $\bar x$ minimise la distance, $\bar x=P_C(x)$. $\square$

[Figure : $C$ convexe, $x$ extérieur, $\bar x=P_C(x)$ sur le bord ; le vecteur $x-\bar x$ fait un angle obtus avec tout $y-\bar x$, $y\in C$.]

**Commentaire du correcteur.** Question « relativement classique » mais qui « a posé beaucoup de difficultés malgré les indications ».

L'indication du sujet (fonction $\psi_y$) mène directement au calcul : il faut traduire la minimalité de $t=0$ par $\psi_y'(0)\ge0$.

## Question I.6.c

**Stratégie.**

Écrire l'inégalité de I.6.b en $a=P_C(x)$ et $b=P_C(y)$ (chacune testée sur l'autre point), les additionner, puis Cauchy–Schwarz.

**Rédaction.**

Posons $a=P_C(x)$, $b=P_C(y)$.

Par I.6.b appliqué à $a$ (avec $z=b\in C$) puis à $b$ (avec $z=a\in C$) : $$\langle x-a,\,b-a\rangle\le0,\qquad \langle y-b,\,a-b\rangle\le0.$$
La somme donne $\langle x-a,b-a\rangle-\langle y-b,b-a\rangle\le0$, soit $$\langle (x-y)+(b-a),\,b-a\rangle\le0\ \Longrightarrow\ \|b-a\|^2\le\langle y-x,\,b-a\rangle\le\|y-x\|\,\|b-a\|$$ par Cauchy–Schwarz.

Si $\|b-a\|=0$ l'inégalité $\|P_C(y)-P_C(x)\|\le\|y-x\|$ est triviale ; sinon on divise par $\|b-a\|>0$ et on obtient $\|b-a\|\le\|y-x\|$. $\square$

**Commentaire du correcteur.** Même remarque que I.6.b : classique, mais peu réussie. La projection sur un convexe fermé est donc $1$-lipschitzienne, propriété cruciale pour Uzawa (IV.6.d).

## Question I.7

**Stratégie.**

Si $x$ est intérieur, une petite boule autour de $x$ est dans $K$ ; tout $h$ est admissible avec une suite $(t_k)$ tendant vers $0$ assez vite et $h_k=h$.

**Rédaction.**

Soit $x\in\overset{\circ}K$ : il existe $r>0$ tel que $B(x,r)\subset K$.

Soit $h\in\mathbb R^n$.

Posons, pour $k\in\mathbb N$, $$t_k=\frac{r}{(k+2)(\|h\|+1)}>0,\qquad h_k=h.$$
Alors $t_k\to0$, $h_k\to h$, et $t_k\|h\|<r$ donne $x+t_k h\in B(x,r)\subset K$ pour tout $k$.

Donc $h\in\mathcal A_K(x)$.

Comme $\mathcal A_K(x)\subset\mathbb R^n$ trivialement, $$\boxed{\mathcal A_K(x)=\mathbb R^n.}$$ $\square$

**Commentaire du correcteur.** « Très souvent correctement traitée. » Mises en garde du rapport : ne pas diviser par $\|h\|$ quand $h=0$ (ici on a ajouté $+1$ pour l'éviter), et signaler que la définition du cône admissible est inchangée si l'on n'exige les inclusions qu'à partir d'un certain rang (ce que respecte notre choix valable pour tout $k$).

## Question I.8

**Stratégie.**

Combiner la minimalité locale et le développement de Taylor à l'ordre $1$ le long de $x^\star+t_kh_k$, puis diviser par $t_k>0$ et passer à la limite.

**Rédaction.**

Soit $h\in\mathcal A_K(x^\star)$, avec $(t_k)$ réels $>0$, $t_k\to0$, $h_k\to h$ et $x^\star+t_kh_k\in K$.

Comme $t_kh_k\to0$ et que $f$ admet un minimum **local** sur $K$ en $x^\star$, on a $f(x^\star+t_kh_k)\ge f(x^\star)$ pour $k$ assez grand.

La différentiabilité de $f$ en $x^\star$ s'écrit $f(x^\star+u)-f(x^\star)=\langle\nabla f(x^\star),u\rangle+\|u\|\,\varepsilon(u)$ avec $\varepsilon(u)\to0$ quand $u\to0$.

Avec $u=t_kh_k$ ($\|u\|=t_k\|h_k\|$) : $$0\le f(x^\star+t_kh_k)-f(x^\star)=t_k\langle\nabla f(x^\star),h_k\rangle+t_k\|h_k\|\,\varepsilon(t_kh_k).$$
On divise par $t_k>0$ : $\langle\nabla f(x^\star),h_k\rangle+\|h_k\|\,\varepsilon(t_kh_k)\ge0$.

Quand $k\to+\infty$, $h_k\to h$ (donc $\langle\nabla f(x^\star),h_k\rangle\to\langle\nabla f(x^\star),h\rangle$ et $\|h_k\|$ borné) et $\varepsilon(t_kh_k)\to0$.

Ainsi
$$\langle\nabla f(x^\star),h\rangle\ge0.$$

*Cas $x^\star$ intérieur.*

Par I.7, $\mathcal A_K(x^\star)=\mathbb R^n$, donc l'inégalité vaut pour $h$ et $-h$ : $\langle\nabla f(x^\star),h\rangle=0$ pour tout $h$, soit $\nabla f(x^\star)=0$.

On retrouve la condition d'Euler classique de stationnarité en un minimum intérieur. $\square$

**Commentaire du correcteur.** « Souvent manqué de précision, en particulier dans l'application du développement de Taylor. » Le point délicat est le terme de reste : l'écrire $\|u\|\,\varepsilon(u)$ avec $\|u\|=t_k\|h_k\|$ permet la division par $t_k$ sans perdre le contrôle du reste.

---

# Partie II — Pénalisation

Dans toute la partie, $f$ est $\alpha$-convexe différentiable et $K=\{g_1\le0,\dots,g_p\le0\}$ avec $g_i$ convexes différentiables, $K\neq\varnothing$.

## Question II.1

**Stratégie.** Vérifier que $K$ est convexe fermé non vide, puis appliquer I.5.

**Rédaction.**

Chaque $g_i$ est convexe, donc $\{g_i\le0\}$ est convexe ; chaque $g_i$ est continue, donc $\{g_i\le0\}=g_i^{-1}(]-\infty,0])$ est fermé.

Ainsi $K=\bigcap_{i=1}^p\{g_i\le0\}$ est convexe fermé, et non vide par hypothèse.

Comme $f$ est $\alpha$-convexe différentiable, I.5 fournit l'existence et l'unicité de $x^\star\in K$ tel que $f(x^\star)=\inf_{x\in K}f(x)$. $\square$

**Commentaire du correcteur.** « N'a pas posé de problème particulier. »

## Question II.2

**Stratégie.**

Distinguer $x\in K$ (où $\Psi(x)=0$) et $x\notin K$ (où $\Psi(x)>0$).

**Rédaction.** $\Psi(x)=\sum_{i=1}^p\max(0,g_i(x))^2\ge0$, et $f_k(x)=f(x)+k\Psi(x)$.

- Si $x\in K$ : $g_i(x)\le0$ pour tout $i$, donc $\max(0,g_i(x))=0$ et $\Psi(x)=0$ ; alors $f_k(x)=f(x)$ pour tout $k$, donc $\lim_{k}f_k(x)=f(x)$.

- Si $x\notin K$ : il existe $j$ avec $g_j(x)>0$, donc $\Psi(x)\ge g_j(x)^2>0$ et $f_k(x)=f(x)+k\Psi(x)\xrightarrow[k\to\infty]{}+\infty$.

$$\lim_{k\to\infty}f_k(x)=\begin{cases}f(x)&\text{si }x\in K,\\[1mm]+\infty&\text{si }x\notin K.\end{cases}\qquad\square$$

**Commentaire du correcteur.** « N'a pas posé de problème particulier. »

## Question II.3

**Stratégie.**

Établir l'indication (composée d'une convexe par une convexe croissante), en déduire que $\Psi$ est convexe et **différentiable**, donc que $f_k$ est $\alpha$-convexe différentiable, et conclure par I.5 sur $K=\mathbb R^n$.

**Rédaction.** *Lemme (indication).*

Soient $g:\mathbb R^n\to\mathbb R$ convexe et $h:\mathbb R\to\mathbb R$ convexe croissante.

Pour $x,y$, $\lambda\in[0,1]$ : $g((1-\lambda)x+\lambda y)\le(1-\lambda)g(x)+\lambda g(y)$ ; $h$ croissante puis $h$ convexe donnent $$h\big(g((1-\lambda)x+\lambda y)\big)\le h\big((1-\lambda)g(x)+\lambda g(y)\big)\le(1-\lambda)h(g(x))+\lambda h(g(y)).$$
Donc $h\circ g$ est convexe.

*Application.*

La fonction $h:t\mapsto\max(0,t)^2$ vaut $0$ sur $\mathbb R^-$ et $t^2$ sur $\mathbb R^+$ ; elle est de classe $\mathcal C^1$ de dérivée $h'(t)=2\max(0,t)$, qui est croissante ($\ge0$) — donc $h$ est convexe et croissante.

Chaque $g_i$ étant convexe, $h\circ g_i=\max(0,g_i)^2$ est convexe (lemme) et différentiable, de gradient $2\max(0,g_i(x))\,\nabla g_i(x)$.

Par somme, $\Psi$ est convexe et différentiable.

Pour $k\in\mathbb N$, $f_k=f+k\Psi$ est différentiable, et $\alpha$-convexe : pour tous $x,y$, $$f_k(y)=f(y)+k\Psi(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac\alpha2\|y-x\|^2+k\big(\Psi(x)+\langle\nabla\Psi(x),y-x\rangle\big)$$ (la $\alpha$-convexité de $f$ et la convexité de $\Psi$ via I.1.c), soit $f_k(y)\ge f_k(x)+\langle\nabla f_k(x),y-x\rangle+\tfrac\alpha2\|y-x\|^2$.

Donc $f_k$ est $\alpha$-convexe différentiable.

Par I.5 (avec $K=\mathbb R^n$, convexe fermé non vide), $f_k$ admet un unique minimiseur $x_k$ sur $\mathbb R^n$. $\square$

**Commentaire du correcteur.** « Peu de succès au-delà du résultat suggéré. » Le rapport insiste : il fallait montrer « la convexité de $\Psi$, puis la forte convexité de $f_k$ », et surtout « la différentiabilité de $f_k$ était nécessaire pour appliquer I.5, ce que la majorité n'ont pas vu ».

C'est précisément le point qui transforme un argument incomplet en preuve.

## Question II.4

**Stratégie.**

Comparer $f_k(x_k)$ et $f_k(x^\star)$ ; sur $K$, $\Psi$ s'annule.

**Rédaction.**

Par minimalité de $x_k$ : $f_k(x_k)\le f_k(x^\star)$.

Or $x^\star\in K$ donne $\Psi(x^\star)=0$, donc $f_k(x^\star)=f(x^\star)$.

Par ailleurs $f_k(x_k)=f(x_k)+k\Psi(x_k)\ge f(x_k)$. D'où
$$f(x_k)\le f_k(x_k)\le f(x^\star).\qquad\square$$

**Commentaire du correcteur.** « Pas de difficulté et généralement bien traitée. » L'encadrement $f(x_k)\le f_k(x_k)\le f(x^\star)$ resservira en II.7.

## Question II.5.a

**Stratégie.**

Borner $k\Psi(x_k)$ en utilisant que $f$, coercive, est minorée sur $\mathbb R^n$.

On en déduit $\Psi(x_k)\to0$, puis $\Psi(\bar x)=0$ par continuité, soit $\bar x\in K$.

**Rédaction.** $f$ est $\alpha$-convexe donc coercive (cf. I.5) et continue ; par I.4 (avec $K=\mathbb R^n$), $f$ admet un minimum global $m_0=\min_{\mathbb R^n}f$, fini.

Pour $k\ge1$, $$k\Psi(x_k)=f_k(x_k)-f(x_k)\le f(x^\star)-f(x_k)\le f(x^\star)-m_0=:C,$$ en utilisant $f_k(x_k)\le f(x^\star)$ (II.4) et $f(x_k)\ge m_0$.

Donc $0\le\Psi(x_k)\le C/k$.

Le long de la sous-suite, $\Psi(x_{\varphi(k)})\le C/\varphi(k)\to0$ ($\varphi(k)\to\infty$).

Comme $\Psi$ est continue et $x_{\varphi(k)}\to\bar x$, $$\Psi(\bar x)=\lim_{k}\Psi(x_{\varphi(k)})=0.$$
Or $\Psi(\bar x)=\sum_i\max(0,g_i(\bar x))^2=0$ impose $g_i(\bar x)\le0$ pour tout $i$, donc $\bar x\in K$. $\square$

**Commentaire du correcteur.** « Un peu plus difficile. » Le rapport relève deux fautes : croire que $\bar x\notin K\Rightarrow\lim_k f_k(x_k)=+\infty$ (« ce qu'on ne peut pas déduire directement »), et « admettre sans démonstration la convergence de $(f_{\varphi(k)}(x_{\varphi(k)}))$ », « sévèrement sanctionné ».

La voie sûre est de **majorer $\Psi(x_k)$** via la minoration de $f$, puis d'utiliser la continuité de $\Psi$.

## Question II.5.b

**Stratégie.**

Passer à la limite dans $f(x_{\varphi(k)})\le f(x^\star)$, puis utiliser que $\bar x\in K$ et que $x^\star$ est l'unique minimiseur sur $K$.

**Rédaction.**

Par continuité de $f$ et $x_{\varphi(k)}\to\bar x$, on a $f(x_{\varphi(k)})\to f(\bar x)$.

Or $f(x_{\varphi(k)})\le f(x^\star)$ (II.4), d'où $f(\bar x)\le f(x^\star)$.

Comme $\bar x\in K$ (II.5.a) et $x^\star$ réalise $\inf_K f$, on a aussi $f(\bar x)\ge f(x^\star)$.

Donc $f(\bar x)=f(x^\star)=\inf_K f$, et par unicité du minimiseur (II.1), $\bar x=x^\star$. $\square$

**Commentaire du correcteur.** « Beaucoup mieux réussie. »

## Question II.6

**Stratégie.**

Montrer que $(x_k)$ est bornée (via la coercivité de $f$), puis qu'elle n'a que $x^\star$ pour valeur d'adhérence ; une suite bornée en dimension finie à valeur d'adhérence unique converge.

**Rédaction.** *Bornitude.*

On a $f(x_k)\le f(x^\star)$ (II.4). $f$ étant coercive, il existe $R>0$ tel que $\|x\|>R\Rightarrow f(x)>f(x^\star)$.

Donc nécessairement $\|x_k\|\le R$ pour tout $k$ : $(x_k)$ est bornée.

*Conclusion.* $(x_k)$ vit dans le compact $\overline B(0,R)$.

Toute sous-suite convergente a une limite qui, par II.5.a–b, vaut $x^\star$ : $(x_k)$ admet $x^\star$ comme **unique** valeur d'adhérence.

Une suite **bornée** d'un espace de dimension finie n'ayant qu'une seule valeur d'adhérence converge vers celle-ci.

Donc $x_k\to x^\star$. $\square$

**Commentaire du correcteur.** « Souvent abordée, mais plus rarement de manière satisfaisante. » Le rapport rappelle qu'« une suite qui n'admet qu'une seule valeur d'adhérence ne converge pas nécessairement » — c'est faux sans bornitude. D'où l'usage de la coercivité pour borner $(x_k)$.

## Question II.7

**Stratégie.**

Encadrer $f_k(x_k)$ entre $f(x_k)$ et $f(x^\star)$ et passer à la limite.

**Rédaction.** D'après II.4, $f(x_k)\le f_k(x_k)\le f(x^\star)$.

Comme $x_k\to x^\star$ (II.6) et $f$ continue, $f(x_k)\to f(x^\star)$.

Par le théorème d'encadrement,
$$f_k(x_k)\xrightarrow[k\to\infty]{}f(x^\star).\qquad\square$$

**Commentaire du correcteur.** « Pouvait être résolue presque immédiatement en exploitant l'encadrement $f(x_k)\le f_k(x_k)\le f(x^\star)$. »

---

# Partie III — Théorème de Karush–Kuhn–Tucker

## Lemme de Farkas

### Question III.1.a

**Stratégie.** Stabilité de l'ensemble des combinaisons à coefficients positifs par combinaison convexe.

**Rédaction.**

Soient $a=\sum_i\mu_iu_i$, $b=\sum_i\nu_iu_i$ avec $\mu_i,\nu_i\ge0$, et $\lambda\in[0,1]$.

Alors $$(1-\lambda)a+\lambda b=\sum_{i=1}^m\big((1-\lambda)\mu_i+\lambda\nu_i\big)u_i,$$ et $(1-\lambda)\mu_i+\lambda\nu_i\ge0$.

Donc $(1-\lambda)a+\lambda b\in C$ : $C$ est convexe (et non vide, $0\in C$). $\square$

**Commentaire du correcteur.** « Aucune difficulté … correctement traitée par un très grand nombre de candidats. »

### Question III.1.b

**Stratégie.**

Si la famille est libre, l'application linéaire $\Phi:\mu\mapsto\sum\mu_iu_i$ est injective, donc un isomorphisme sur son image $F$ (sous-espace fermé) ; $\Phi^{-1}$ est continue, ce qui transporte la fermeture de $\mathbb R^m_+$.

**Rédaction.** Soit $\Phi:\mathbb R^m\to\mathbb R^n,\ \Phi(\mu)=\sum_i\mu_iu_i$, linéaire.

La liberté de $(u_1,\dots,u_m)$ équivaut à l'injectivité de $\Phi$ ; son image $F=\mathrm{Vect}(u_1,\dots,u_m)$ est un sous-espace de dimension finie, donc fermé.

L'application $\Phi:\mathbb R^m\to F$ est un isomorphisme entre espaces de dimension finie, donc $\Phi^{-1}:F\to\mathbb R^m$ est continue.

Soit $(a^{(j)})$ une suite de $C$ convergeant vers $a\in\mathbb R^n$ ; écrivons $a^{(j)}=\Phi(\mu^{(j)})$, $\mu^{(j)}\in\mathbb R^m_+$.

Comme $a^{(j)}\in F$ et $F$ fermé, $a\in F$.

Alors $\mu^{(j)}=\Phi^{-1}(a^{(j)})\to\Phi^{-1}(a)=:\mu$ par continuité de $\Phi^{-1}$.

Chaque $\mu^{(j)}\ge0$ et $\mathbb R^m_+$ est fermé, donc $\mu\ge0$.

Ainsi $a=\Phi(\mu)\in C$ : $C$ est fermé. $\square$

**Commentaire du correcteur.** « De nombreuses copies … déduisent directement la convergence coordonnée par coordonnée … sans relier ce résultat à la liberté de la famille. Les candidats ayant omis de justifier la convergence ont été sanctionnés. » La justification clé est la **continuité de $\Phi^{-1}$**, qui n'a lieu que parce que la famille est libre.

### Question III.1.c

**Stratégie.** Inclusion $\supseteq$ immédiate. Pour $\subseteq$, partir d'une représentation positive à **support minimal** : si la sous-famille du support était liée, on ferait baisser le support en conservant la positivité, contradiction. Union finie de fermés.

**Rédaction.** $\supseteq$ : pour tout $I$, $C_I\subset C$ (compléter par des coefficients nuls).

$\subseteq$ : soit $a\in C$.

Parmi toutes les écritures $a=\sum_{i=1}^m\mu_iu_i$ avec $\mu_i\ge0$, choisissons-en une dont le support $S=\{i:\mu_i>0\}$ est de **cardinal minimal**.

Montrons que $(u_i)_{i\in S}$ est libre.

Sinon, il existe $(\lambda_i)_{i\in S}$ non tous nuls avec $\sum_{i\in S}\lambda_iu_i=0$ ; quitte à changer de signe, on peut supposer qu'au moins un $\lambda_i>0$.

Pour $t\ge0$ posons $\mu_i(t)=\mu_i-t\lambda_i$ ($i\in S$).

En $t=0$ tous sont $>0$ ; soit $t^\star=\min\{\mu_i/\lambda_i:\ \lambda_i>0\}>0$.

Alors $\mu_i(t^\star)\ge0$ pour tout $i\in S$, au moins un est nul, et $$\sum_{i\in S}\mu_i(t^\star)u_i=\sum_{i\in S}\mu_iu_i-t^\star\sum_{i\in S}\lambda_iu_i=a-0=a.$$
On a donc une écriture positive de $a$ à support strictement plus petit, contredisant la minimalité.

Donc $(u_i)_{i\in S}$ est libre et $a\in C_S$, avec $S$ d'indices libres.

D'où $C=\bigcup_{I\text{ libre}}C_I$.

Chaque $C_I$ (famille $(u_i)_{i\in I}$ libre) est fermé par III.1.b. L'union porte sur un nombre **fini** de parties $I\subset\llbracket1,m\rrbracket$, donc $C$ est une union finie de fermés : $C$ est fermé. $\square$

**Commentaire du correcteur.** « Beaucoup plus discriminante … correctement traitée que dans quelques copies. » Le rapport pointe exactement l'erreur à éviter : « il ne suffisait pas de considérer une sous-famille libre, car on ne pouvait plus garantir que les coordonnées restent positives ». L'argument de **support minimal** (qui maintient $\mu_i(t^\star)\ge0$) est la bonne réponse.

### Question III.2.a

**Stratégie.** $C$ est un cône convexe fermé contenant $0$.

Tester la caractérisation I.6.b en $y=0$ et $y=2P_C(v)$.

**Rédaction.** $C$ est convexe (III.1.a), fermé (III.1.c) et non vide ($0\in C$) ; $P_C(v)$ est donc bien défini (I.6.a).

De plus $C$ est un cône : pour $z=\sum_i\mu_iu_i\in C$ et $t\ge0$, $tz=\sum_i(t\mu_i)u_i\in C$.

En particulier $0\in C$ et $2P_C(v)\in C$.

Notons $z=P_C(v)$.

Par I.6.b, $\langle v-z,y-z\rangle\le0$ pour tout $y\in C$.

Avec $y=0$ : $\langle v-z,-z\rangle\le0$, soit $\langle v-z,z\rangle\ge0$.

Avec $y=2z$ : $\langle v-z,2z-z\rangle=\langle v-z,z\rangle\le0$.

Donc $\langle v-z,z\rangle=0$, c'est-à-dire $$\langle P_C(v),\,P_C(v)-v\rangle=-\langle v-z,z\rangle=0.\qquad\square$$

**Commentaire du correcteur.** « L'autre inégalité a posé plus de problèmes.

Certains candidats ont su exploiter que $2P_C(v)\in C$. » C'est bien le caractère de **cône** de $C$ (testé en $0$ et $2z$) qui force l'égalité.

### Question III.2.b

**Stratégie.**

Pour $\langle v,w\rangle$, développer avec III.2.a. Pour $\langle u_i,w\rangle$, tester I.6.b en $y=z+u_i\in C$.

**Rédaction.**

Posons $w=z-v$ avec $z=P_C(v)$.

$\bullet$ $\langle v,w\rangle=\langle v,z-v\rangle=\langle v-z,z-v\rangle+\langle z,z-v\rangle=-\|z-v\|^2+0$ (par III.2.a, $\langle z,z-v\rangle=0$).

Comme $v\notin C$ et $z\in C$, $z\neq v$, donc $\langle v,w\rangle=-\|z-v\|^2<0$.

$\bullet$ Pour $i\in\llbracket1,m\rrbracket$, $u_i\in C$ et, $C$ étant un cône stable par addition, $z+u_i\in C$.

Par I.6.b avec $y=z+u_i$ : $\langle v-z,(z+u_i)-z\rangle\le0$, soit $\langle v-z,u_i\rangle\le0$, d'où $\langle u_i,w\rangle=\langle u_i,z-v\rangle\ge0$.

Ainsi $\langle v,w\rangle<0$ et $\langle u_i,w\rangle\ge0$ pour tout $i$. $\square$

**Commentaire du correcteur.** « Très accessible, beaucoup mieux réussie. » La seconde inégalité « peut aisément se déduire de I.6.b » avec $y=z+u_i$ : ne pas l'oublier.

### Question III.3

**Stratégie.**

Réunir l'implication « $v\notin C\Rightarrow$ (ii) » (III.2) et son complément « $v\in C\Rightarrow$ (i) », **puis** prouver l'exclusion mutuelle de (i) et (ii).

**Rédaction.** *Au moins une des assertions.* Si $v\in C$, (i) est vraie.

Si $v\notin C$, le vecteur $w=P_C(v)-v$ vérifie (ii) (III.2.b).

*Exclusion mutuelle.* Supposons (i) et (ii) simultanément.

Par (i), $v=\sum_i\mu_iu_i$, $\mu_i\ge0$ ; par (ii), il existe $w$ avec $\langle v,w\rangle<0$ et $\langle u_i,w\rangle\ge0$.

Alors $$\langle v,w\rangle=\sum_{i=1}^m\mu_i\langle u_i,w\rangle\ge0,$$ contredisant $\langle v,w\rangle<0$.

Donc (i) et (ii) ne peuvent être vraies ensemble.

Conclusion : exactement une des deux assertions (i), (ii) est vérifiée. $\square$

**Commentaire du correcteur.** « Assez simple, a pourtant tendu un piège : de nombreux candidats … ont omis de montrer que les assertions s'excluaient mutuellement. » L'énoncé du lemme étant un *ou exclusif*, l'exclusion mutuelle fait partie intégrante de la preuve.

## Condition nécessaire d'optimalité

### Question III.4

**Stratégie.**

Développer chaque contrainte active $g_i$ ($i\in I_x$) à l'ordre $1$ le long de $x+t_kh_k\in K$, exactement comme en I.8.

**Rédaction.**

Soit $h\in\mathcal A_K(x)$, avec $(t_k)$ réels $>0$, $t_k\to0$, $h_k\to h$ et $x+t_kh_k\in K$.

Pour $i\in I_x$, on a $g_i(x)=0$ et $g_i(x+t_kh_k)\le0$.

Par différentiabilité de $g_i$, $$0\ge g_i(x+t_kh_k)=g_i(x)+t_k\langle\nabla g_i(x),h_k\rangle+t_k\|h_k\|\,\varepsilon_k=t_k\langle\nabla g_i(x),h_k\rangle+t_k\|h_k\|\,\varepsilon_k,$$ avec $\varepsilon_k\to0$.

On divise par $t_k>0$ : $\langle\nabla g_i(x),h_k\rangle+\|h_k\|\varepsilon_k\le0$.

Quand $k\to+\infty$, $\langle\nabla g_i(x),h\rangle\le0$.

Donc
$$\mathcal A_K(x)\subset\{h\in\mathbb R^n:\ \forall i\in I_x,\ \langle\nabla g_i(x),h\rangle\le0\}.\qquad\square$$

**Commentaire du correcteur.** « Pouvait être traitée directement ou en utilisant I.8. Elle n'a été abordée que par peu de candidats. » La voie directe (Taylor à l'ordre $1$) est la plus rapide.

### Question III.5

**Stratégie.** L'inclusion $\subset$ est III.4.

Pour $\supset$, montrer d'abord que tout $h'$ vérifiant des inégalités **strictes** est admissible, puis approcher $h$ par $h+\tfrac1k v$ (qui rend les inégalités strictes grâce à (H)) et construire la suite admissible par diagonalisation.

**Rédaction.** L'inclusion $\subset$ découle de III.4. Montrons $\supset$.

*Étape 1.*

Soit $h'$ tel que $\langle\nabla g_i(x^\star),h'\rangle<0$ pour tout $i\in I_{x^\star}$.

Montrons $h'\in\mathcal A_K(x^\star)$. Pour $t>0$ :

- si $i\in I_{x^\star}$ : $g_i(x^\star+th')=t\langle\nabla g_i(x^\star),h'\rangle+o(t)<0$ pour $t$ assez petit ;

- si $i\notin I_{x^\star}$ : $g_i(x^\star)<0$ et $g_i$ continue, donc $g_i(x^\star+th')<0$ pour $t$ assez petit.

Les indices étant en nombre fini, il existe $\tau>0$ tel que pour $0<t<\tau$, $x^\star+th'\in K$.

Avec $t_k=\tfrac{\tau}{k+2}$ et $h_k=h'$, on obtient $h'\in\mathcal A_K(x^\star)$.

*Étape 2.*

Soit $h$ tel que $\langle\nabla g_i(x^\star),h\rangle\le0$ pour tout $i\in I_{x^\star}$.

Pour $k\ge1$ posons $h^{(k)}=h+\tfrac1k v$.

Par (H), pour $i\in I_{x^\star}$, $$\langle\nabla g_i(x^\star),h^{(k)}\rangle=\langle\nabla g_i(x^\star),h\rangle+\frac1k\underbrace{\langle\nabla g_i(x^\star),v\rangle}_{<0}<0.$$
Par l'étape 1, $h^{(k)}\in\mathcal A_K(x^\star)$ : il existe $\tau_k>0$ tel que $x^\star+t\,h^{(k)}\in K$ pour $0<t<\tau_k$.

*Diagonalisation.*

Posons $H_k=h^{(k)}\to h$ et $t_k=\tfrac12\min(\tau_k,\tfrac1k)>0$, de sorte que $t_k\le\tfrac1{2k}\to0$ et $t_k<\tau_k$, donc $x^\star+t_kH_k\in K$.

Ainsi $h\in\mathcal A_K(x^\star)$.

D'où l'égalité $\mathcal A_K(x^\star)=\{h:\ \forall i\in I_{x^\star},\ \langle\nabla g_i(x^\star),h\rangle\le0\}$. $\square$

**Commentaire du correcteur.**

Le rapport souligne que la question « demandait un soin particulier pour construire les suites $(t_k)$ et $(h_k)$, ce qui a été insuffisamment fait ».

L'argument en deux temps (inégalités strictes admissibles, puis perturbation $h+\tfrac1k v$ et diagonale) est la rédaction propre attendue.

### Question III.6

**Stratégie.**

Si la famille des gradients actifs est libre, l'application linéaire $v\mapsto(\langle\nabla g_i(x^\star),v\rangle)_{i\in I_{x^\star}}$ est surjective ; choisir un antécédent du vecteur $(-1,\dots,-1)$.

**Rédaction.** Si $I_{x^\star}=\varnothing$, (H) est vraie de manière vide.

Sinon, notons $r=|I_{x^\star}|$ et considérons $L:\mathbb R^n\to\mathbb R^r,\ L(v)=(\langle\nabla g_i(x^\star),v\rangle)_{i\in I_{x^\star}}$, linéaire.

Sa matrice (dans la base canonique, lignes $\nabla g_i(x^\star)^{\mathsf T}$) a ses $r$ lignes formant une famille libre, donc est de rang $r$ : $L$ est surjective.

Il existe ainsi $v\in\mathbb R^n$ tel que $L(v)=(-1,\dots,-1)$, c'est-à-dire $\langle\nabla g_i(x^\star),v\rangle=-1<0$ pour tout $i\in I_{x^\star}$.

L'hypothèse (H) est vérifiée. $\square$

**Commentaire du correcteur.** « Bien qu'accessible, la question 6 n'a presque pas été abordée. » Le ressort est la surjectivité d'une application linéaire de rang plein.

### Question III.7

**Stratégie.**

Par I.8 et III.5, $x^\star$ vérifie $\langle\nabla f(x^\star),h\rangle\ge0$ sur le cône $\{h:\langle\nabla g_i(x^\star),h\rangle\le0,\ i\in I_{x^\star}\}$.

Appliquer le lemme de Farkas à $v=-\nabla f(x^\star)$ et $u_i=\nabla g_i(x^\star)$ : l'alternative (ii) est exclue, donc $-\nabla f(x^\star)$ est dans le cône engendré.

**Rédaction.**

Comme $f$ admet un minimum local sur $K$ en $x^\star$ et $f$ est différentiable, I.8 donne $\langle\nabla f(x^\star),h\rangle\ge0$ pour tout $h\in\mathcal A_K(x^\star)$.

Par (H) et III.5,
$$\mathcal A_K(x^\star)=\{h:\ \forall i\in I_{x^\star},\ \langle\nabla g_i(x^\star),h\rangle\le0\}.\tag{$\star$}$$

Posons $u_i=\nabla g_i(x^\star)$ ($i\in I_{x^\star}$), $C=\{\sum_{i\in I_{x^\star}}\mu_iu_i,\ \mu_i\ge0\}$ et $v=-\nabla f(x^\star)$.

Appliquons le lemme de Farkas (III.3) à $v$ :

- Si l'assertion (ii) était vraie, il existerait $w$ avec $\langle v,w\rangle<0$ et $\langle u_i,w\rangle\ge0$.

Alors $h:=-w$ vérifie $\langle\nabla g_i(x^\star),h\rangle=-\langle u_i,w\rangle\le0$, donc $h\in\mathcal A_K(x^\star)$ par $(\star)$, d'où $\langle\nabla f(x^\star),h\rangle\ge0$, soit $\langle\nabla f(x^\star),-w\rangle\ge0$, i.e. $\langle v,w\rangle=\langle-\nabla f(x^\star),w\rangle\ge0$ — contradiction.

- Donc (i) est vraie : $-\nabla f(x^\star)\in C$, soit $-\nabla f(x^\star)=\sum_{i\in I_{x^\star}}\mu_i^\star\nabla g_i(x^\star)$ avec $\mu_i^\star\ge0$.

Posons $\mu_i^\star=0$ pour $i\notin I_{x^\star}$.

Alors $$\nabla f(x^\star)+\sum_{i=1}^p\mu_i^\star\nabla g_i(x^\star)=0,$$ et pour tout $i$ : si $i\in I_{x^\star}$, $g_i(x^\star)=0$ ; si $i\notin I_{x^\star}$, $\mu_i^\star=0$ ; dans les deux cas $\mu_i^\star g_i(x^\star)=0$.

Le système (1) est satisfait. $\square$

**Commentaire du correcteur.** « La question 7 demandait d'appliquer le lemme de Farkas aux vecteurs $\nabla f(x^\star)$ et $\nabla g_i(x^\star)$.

Peu de candidats l'ont vu et ont su mener le raisonnement jusqu'au bout. » C'est le cœur de la partie : reconnaître que la condition de I.8 sur le cône $(\star)$ est exactement la négation de l'alternative (ii) de Farkas.

### Question III.8

**Stratégie.**

Réciproque dans le cas convexe : introduire $\phi=f+\sum_i\mu_i^\star g_i$, convexe avec $\nabla\phi(x^\star)=0$, donc de minimum global en $x^\star$ (I.2) ; conclure sur $K$ par les conditions de complémentarité.

**Rédaction.** Posons $\phi(x)=f(x)+\sum_{i=1}^p\mu_i^\star g_i(x)$.

Comme $f$ et les $g_i$ sont convexes et $\mu_i^\star\ge0$, $\phi$ est convexe (somme de convexes), et différentiable.

Par (1), $\nabla\phi(x^\star)=\nabla f(x^\star)+\sum_i\mu_i^\star\nabla g_i(x^\star)=0$.

Par I.2, $\phi$ admet un minimum global en $x^\star$ : pour tout $x$, $\phi(x)\ge\phi(x^\star)$.

Soit $x\in K$.

Alors $g_i(x)\le0$ et $\mu_i^\star\ge0$, donc $\sum_i\mu_i^\star g_i(x)\le0$, d'où $$f(x)\ge f(x)+\sum_i\mu_i^\star g_i(x)=\phi(x)\ge\phi(x^\star)=f(x^\star)+\sum_i\underbrace{\mu_i^\star g_i(x^\star)}_{=0}=f(x^\star).$$
Donc $f(x)\ge f(x^\star)$ pour tout $x\in K$ : $f$ admet en $x^\star$ un minimum global sur $K$. $\square$

**Commentaire du correcteur.** « Il s'agissait de se ramener à la minimisation de la fonction $x\mapsto f(x)+\sum_i g_i(x)$, convexe également. » La complémentarité $\mu_i^\star g_i(x^\star)=0$ et la négativité de $\sum_i\mu_i^\star g_i$ sur $K$ ferment l'argument.

---

# Partie IV — Étude du problème dual

Ici $p\in\llbracket1,n\rrbracket$, $f$ est $\alpha$-convexe différentiable, les $g_i$ sont convexes différentiables, $K=\{g_1\le0,\dots,g_p\le0\}\neq\varnothing$, et $\mathcal L(x,\mu)=f(x)+\sum_i\mu_ig_i(x)$.

## Question IV.1

**Stratégie.**

Calculer $\sup_{\mu\in\mathbb R^p_+}\mathcal L(x,\mu)$ : il vaut $f(x)$ sur $K$ et $+\infty$ hors de $K$.

**Rédaction.**

Pour $x$ fixé, $\sup_{\mu\in\mathbb R^p_+}\mathcal L(x,\mu)=f(x)+\sup_{\mu\ge0}\sum_i\mu_ig_i(x)$.

- Si $x\in K$ : $g_i(x)\le0$, donc $\sum_i\mu_ig_i(x)\le0$ pour $\mu\ge0$, le sup étant atteint en $\mu=0$ ; ainsi $\sup_\mu\mathcal L(x,\mu)=f(x)$.

- Si $x\notin K$ : il existe $j$ avec $g_j(x)>0$ ; pour $\mu=t\,e_j$, $\sum_i\mu_ig_i(x)=t\,g_j(x)\to+\infty$, donc $\sup_\mu\mathcal L(x,\mu)=+\infty$.

Par conséquent, $K$ étant non vide, $$\inf_{x\in\mathbb R^n}\sup_{\mu\in\mathbb R^p_+}\mathcal L(x,\mu)=\inf_{x\in K}f(x).\qquad\square$$

**Commentaire du correcteur.** La partie IV « n'a été abordée que par 8% des candidats, qui pour la plupart se sont contentés de traiter la première question ». Cette question est en effet la plus accessible : un simple calcul de borne supérieure.

## Question IV.2

**Stratégie.** $\mathcal L(\cdot,\mu)$ est $\alpha$-convexe différentiable ; appliquer I.5 sur $\mathbb R^n$.

**Rédaction.**

Pour $\mu\in\mathbb R^p_+$, $\mathcal L(\cdot,\mu)=f+\sum_i\mu_ig_i$ est différentiable, et $\alpha$-convexe (somme de la fonction $\alpha$-convexe $f$ et des fonctions convexes $\mu_ig_i$, $\mu_i\ge0$ ; même calcul qu'en II.3).

Par I.5 avec $K=\mathbb R^n$ (convexe fermé non vide), elle admet un unique minimiseur $x_\mu\in\mathbb R^n$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas spécifiquement cette question.

Piège à signaler : ne pas oublier de justifier que $\mathcal L(\cdot,\mu)$ reste $\alpha$-convexe (et non seulement convexe), ce qui garantit l'unicité via I.5.

## Question IV.3.a

**Stratégie.**

Le caractère fini de $\sup_\mu\mathcal L(\bar x,\mu)$ force $\bar x\in K$ ; puis comparer via les deux conditions du point selle.

**Rédaction.**

Comme $\sup_\mu\mathcal L(\bar x,\mu)=\mathcal L(\bar x,\bar\mu)$ est fini, l'analyse de IV.1 impose $\bar x\in K$, et alors $\sup_\mu\mathcal L(\bar x,\mu)=f(\bar x)$, donc $\mathcal L(\bar x,\bar\mu)=f(\bar x)$.

Soit $x\in K$. Par IV.1, $f(x)=\sup_\mu\mathcal L(x,\mu)\ge\mathcal L(x,\bar\mu)$. Par la première condition de point selle, $\mathcal L(x,\bar\mu)\ge\inf_{x'}\mathcal L(x',\bar\mu)=\mathcal L(\bar x,\bar\mu)=f(\bar x)$.

Donc $f(x)\ge f(\bar x)$ pour tout $x\in K$, avec $\bar x\in K$ : $\bar x$ est solution de (P). $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

Veiller à justifier $\bar x\in K$ avant d'identifier $\sup_\mu\mathcal L(\bar x,\mu)=f(\bar x)$.

## Question IV.3.b

**Stratégie.** Symétrique : utiliser la seconde condition de point selle.

**Rédaction.** $G(\bar\mu)=\inf_x\mathcal L(x,\bar\mu)=\mathcal L(\bar x,\bar\mu)$.

Pour tout $\mu\in\mathbb R^p_+$, $$G(\mu)=\inf_x\mathcal L(x,\mu)\le\mathcal L(\bar x,\mu)\le\sup_{\mu'}\mathcal L(\bar x,\mu')=\mathcal L(\bar x,\bar\mu)=G(\bar\mu),$$ la dernière majoration étant la seconde condition de point selle.

Donc $\bar\mu$ maximise $G$ sur $\mathbb R^p_+$ : $\bar\mu$ est solution de (Q). $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question. C'est l'exact miroir de IV.3.a.

## Question IV.3.c

**Stratégie.** Dualité faible (toujours vraie) $\sup\inf\le\inf\sup$, et inégalité inverse fournie par le point selle.

**Rédaction.** *Dualité faible.*

Pour tous $x_0,\mu_0$ : $\inf_x\mathcal L(x,\mu_0)\le\mathcal L(x_0,\mu_0)\le\sup_\mu\mathcal L(x_0,\mu)$.

En prenant le sup sur $\mu_0$ (membre de gauche indépendant de $x_0$) puis l'inf sur $x_0$, $$\sup_{\mu}\inf_{x}\mathcal L(x,\mu)\le\inf_{x}\sup_{\mu}\mathcal L(x,\mu).$$

*Inégalité inverse (point selle).*
$$\inf_x\sup_\mu\mathcal L(x,\mu)\le\sup_\mu\mathcal L(\bar x,\mu)=\mathcal L(\bar x,\bar\mu)=\inf_x\mathcal L(x,\bar\mu)\le\sup_\mu\inf_x\mathcal L(x,\mu).$$

Les deux inégalités donnent l'égalité $\inf_x\sup_\mu\mathcal L=\sup_\mu\inf_x\mathcal L$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question. Bien démontrer la dualité faible (et ne pas la « supposer connue ») : c'est le seul point susceptible d'être attaqué.

## Question IV.4

**Stratégie.**

Les conditions KKT de III.7 font de $x^\star$ le minimiseur de $\mathcal L(\cdot,\mu^\star)$, donc $G(\mu^\star)=f(x^\star)$ ; majorer $G(\mu)$ par $\mathcal L(x^\star,\mu)\le f(x^\star)$.

**Rédaction.** $x^\star$ étant solution de (P) avec (H), III.7 fournit $\mu^\star\in\mathbb R^p_+$ tel que $\nabla f(x^\star)+\sum_i\mu_i^\star\nabla g_i(x^\star)=0$ et $\mu_i^\star g_i(x^\star)=0$.

La fonction $\mathcal L(\cdot,\mu^\star)$ est $\alpha$-convexe différentiable, de gradient nul en $x^\star$ ; par I.2 elle y atteint son minimum global, donc $x_{\mu^\star}=x^\star$ et $$G(\mu^\star)=\mathcal L(x^\star,\mu^\star)=f(x^\star)+\sum_i\mu_i^\star g_i(x^\star)=f(x^\star).$$
Pour tout $\mu\in\mathbb R^p_+$, $$G(\mu)=\inf_x\mathcal L(x,\mu)\le\mathcal L(x^\star,\mu)=f(x^\star)+\sum_i\mu_ig_i(x^\star)\le f(x^\star)=G(\mu^\star),$$ puisque $\mu_i\ge0$ et $g_i(x^\star)\le0$.

Donc $\mu^\star$ maximise $G$ : $\mu^\star$ est solution de (Q). $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

Point à surveiller : justifier que $x^\star$ minimise $\mathcal L(\cdot,\mu^\star)$ (via $\nabla_x\mathcal L(x^\star,\mu^\star)=0$ et la convexité), ce qui donne la valeur $G(\mu^\star)=f(x^\star)$.

## Question IV.5.a

**Stratégie.**

Convexité de $\mathbb R^p_+$ pour le segment ; encadrer le taux d'accroissement de $G$ entre $\langle g(x_{\mu+t\xi}),\xi\rangle$ et $\langle g(x_\mu),\xi\rangle$, puis passer à la limite par continuité de $\mu\mapsto x_\mu$.

**Rédaction.** $\mu+t\xi=(1-t)\mu+t(\mu+\xi)$ avec $\mu,\mu+\xi\in\mathbb R^p_+$ et $t\in[0,1]$ : c'est une combinaison convexe d'éléments de $\mathbb R^p_+$, donc $\mu+t\xi\in\mathbb R^p_+$.

Écrivons $\mathcal L(x,\mu)=f(x)+\langle\mu,g(x)\rangle$. Pour $t>0$ :

- minoration : $G(\mu)=\inf_x\mathcal L(x,\mu)\le\mathcal L(x_{\mu+t\xi},\mu)=f(x_{\mu+t\xi})+\langle\mu,g(x_{\mu+t\xi})\rangle$, d'où $$G(\mu+t\xi)-G(\mu)\ge\big[f(x_{\mu+t\xi})+\langle\mu+t\xi,g(x_{\mu+t\xi})\rangle\big]-\big[f(x_{\mu+t\xi})+\langle\mu,g(x_{\mu+t\xi})\rangle\big]=t\langle g(x_{\mu+t\xi}),\xi\rangle;$$

- majoration : $G(\mu+t\xi)\le\mathcal L(x_\mu,\mu+t\xi)=f(x_\mu)+\langle\mu+t\xi,g(x_\mu)\rangle=G(\mu)+t\langle g(x_\mu),\xi\rangle$.

D'où l'encadrement $$\langle g(x_{\mu+t\xi}),\xi\rangle\le\frac{G(\mu+t\xi)-G(\mu)}{t}\le\langle g(x_\mu),\xi\rangle.$$
Quand $t\to0^+$, $\mu+t\xi\to\mu$ ; par continuité de $\mu\mapsto x_\mu$ (hypothèse) et de $g$, $g(x_{\mu+t\xi})\to g(x_\mu)$.

Le théorème d'encadrement donne
$$\lim_{t\to0^+}\frac{G(\mu+t\xi)-G(\mu)}{t}=\langle g(x_\mu),\xi\rangle.$$

*Conséquence.* $\bar\mu$ étant solution de (Q), $G(\bar\mu)\ge G(\mu')$ pour tout $\mu'\in\mathbb R^p_+$.

Soit $\mu\in\mathbb R^p_+$ et $\xi=\mu-\bar\mu$ ; alors $\bar\mu+\xi=\mu\in\mathbb R^p_+$, et pour $t\in(0,1]$, $G(\bar\mu+t\xi)\le G(\bar\mu)$, donc $\frac{G(\bar\mu+t\xi)-G(\bar\mu)}{t}\le0$.

À la limite $t\to0^+$, $\langle g(x_{\bar\mu}),\mu-\bar\mu\rangle\le0$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question (partie très peu traitée).

Piège : l'encadrement utilise deux choix différents de point d'évaluation ($x_\mu$ et $x_{\mu+t\xi}$) — c'est l'inf qui permet de tester en n'importe quel point.

La continuité $\mu\mapsto x_\mu$ est indispensable pour conclure.

## Question IV.5.b

**Stratégie.**

De $\langle g(x_{\bar\mu}),\mu-\bar\mu\rangle\le0$, déduire $g(x_{\bar\mu})\le0$ (donc $x_{\bar\mu}\in K$) puis la complémentarité $\langle g(x_{\bar\mu}),\bar\mu\rangle=0$ ; comme $\nabla_x\mathcal L(x_{\bar\mu},\bar\mu)=0$, appliquer III.8.

**Rédaction.** $x_{\bar\mu}$ minimise $\mathcal L(\cdot,\bar\mu)$, d'où $\nabla f(x_{\bar\mu})+\sum_i\bar\mu_i\nabla g_i(x_{\bar\mu})=0$.

*$x_{\bar\mu}\in K$.*

Si $g_j(x_{\bar\mu})>0$ pour un $j$, prendre $\mu=\bar\mu+s\,e_j\in\mathbb R^p_+$ ($s>0$) donne $\langle g(x_{\bar\mu}),\mu-\bar\mu\rangle=s\,g_j(x_{\bar\mu})>0$, contredisant IV.5.a. Donc $g_j(x_{\bar\mu})\le0$ pour tout $j$ : $x_{\bar\mu}\in K$.

*Complémentarité.*

Avec $\mu=0\in\mathbb R^p_+$ : $\langle g(x_{\bar\mu}),-\bar\mu\rangle\le0$, soit $\langle g(x_{\bar\mu}),\bar\mu\rangle\ge0$.

Mais $\bar\mu\ge0$ et $g(x_{\bar\mu})\le0$ donnent $\langle g(x_{\bar\mu}),\bar\mu\rangle\le0$.

Donc $\langle g(x_{\bar\mu}),\bar\mu\rangle=\sum_i\bar\mu_ig_i(x_{\bar\mu})=0$, chaque terme étant $\le0$, d'où $\bar\mu_ig_i(x_{\bar\mu})=0$ pour tout $i$.

Ainsi $x_{\bar\mu}\in K$, $\bar\mu\ge0$ et le système (1) est vérifié au point $x_{\bar\mu}$.

Les fonctions $f$ ($\alpha$-convexe donc convexe) et $g_i$ étant convexes, III.8 assure que $x_{\bar\mu}$ est minimum global de $f$ sur $K$ : $x_{\bar\mu}$ est solution de (P). $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question. La logique est : la condition variationnelle de IV.5.a fournit exactement la faisabilité primale et la complémentarité, transformant $x_{\bar\mu}$ en point KKT, auquel III.8 (cas convexe) s'applique.

## Question IV.6.a

**Stratégie.** Annuler $\nabla_x\mathcal L(\cdot,\mu)$ au minimiseur. La continuité (mieux, le caractère lipschitzien) de $\mu\mapsto x_\mu$ s'obtient par la monotonie forte du gradient (I.3.b).

**Rédaction.**

Ici $g(x)=Ax+b$, donc $\mathcal L(x,\mu)=f(x)+\langle\mu,Ax+b\rangle=f(x)+\langle{}^{\mathsf t}A\mu,x\rangle+\langle\mu,b\rangle$ et $\nabla_x\mathcal L(x,\mu)=\nabla f(x)+{}^{\mathsf t}A\mu$.

Comme $x_\mu$ minimise $\mathcal L(\cdot,\mu)$, $\alpha$-convexe différentiable sur l'ouvert $\mathbb R^n$, on a $\nabla_x\mathcal L(x_\mu,\mu)=0$, soit $$\nabla f(x_\mu)=-{}^{\mathsf t}A\mu.$$

*Continuité.*

Soit $C>0$ tel que $\|Ax\|\le C\|x\|$ pour tout $x$ (continuité de $A$).

Pour $\mu,\mu'\in\mathbb R^p_+$, posons $\delta x=x_\mu-x_{\mu'}$.

Par I.3.b ($f$ $\alpha$-convexe) et $\nabla f(x_\mu)-\nabla f(x_{\mu'})=-{}^{\mathsf t}A(\mu-\mu')$ : $$\alpha\|\delta x\|^2\le\langle\nabla f(x_\mu)-\nabla f(x_{\mu'}),\delta x\rangle=-\langle{}^{\mathsf t}A(\mu-\mu'),\delta x\rangle=-\langle\mu-\mu',A\,\delta x\rangle\le\|\mu-\mu'\|\,\|A\,\delta x\|\le C\|\mu-\mu'\|\,\|\delta x\|.$$
Si $\delta x\ne0$, on divise : $\|x_\mu-x_{\mu'}\|\le\frac{C}{\alpha}\|\mu-\mu'\|$ (inégalité triviale si $\delta x=0$).

Donc $\mu\mapsto x_\mu$ est $\frac{C}{\alpha}$-lipschitzienne, en particulier continue sur $\mathbb R^p_+$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

C'est la monotonie forte $\langle\nabla f(y)-\nabla f(x),y-x\rangle\ge\alpha\|y-x\|^2$ (I.3.b) qui rend l'application $\mu\mapsto x_\mu$ lipschitzienne ; cette continuité est l'hypothèse exigée pour IV.5.

## Question IV.6.b

**Stratégie.** Existence/unicité primale par I.5.

Existence duale via III.6/III.7/IV.4 (les gradients actifs, lignes de $A$, sont libres car $A$ est de rang $p$).

Unicité duale via l'injectivité de ${}^{\mathsf t}A$.

**Rédaction.** *(P).* $K$ est convexe fermé non vide (les $\{g_i\le0\}$ sont des demi-espaces) et $f$ est $\alpha$-convexe ; par I.5, (P) admet une unique solution $x^\star$.

*Existence de (Q).*

Les contraintes sont affines : $\nabla g_i(x^\star)$ est la $i$-ème ligne de $A$ (vue comme vecteur). $A$ étant de rang $p$, ses $p$ lignes sont libres, donc toute sous-famille $(\nabla g_i(x^\star))_{i\in I_{x^\star}}$ est libre.

Par III.6, (H) est vérifiée en $x^\star$ ; par III.7, il existe $\mu^\star\in\mathbb R^p_+$ vérifiant (1) ; par IV.4, $\mu^\star$ est solution de (Q).

*Unicité de (Q).* Soit $\bar\mu$ une solution de (Q).

Par IV.6.a, $\mu\mapsto x_\mu$ est continue, donc IV.5.b s'applique : $x_{\bar\mu}$ est solution de (P), d'où $x_{\bar\mu}=x^\star$ (unicité primale).

Alors $\nabla f(x^\star)=\nabla f(x_{\bar\mu})=-{}^{\mathsf t}A\bar\mu$.

Toute solution $\mu'$ de (Q) vérifie de même $\nabla f(x^\star)=-{}^{\mathsf t}A\mu'$, donc ${}^{\mathsf t}A(\bar\mu-\mu')=0$.

Or $A$ de rang $p$ entraîne ${}^{\mathsf t}A$ injective ($\mathrm{rg}\,{}^{\mathsf t}A=p$ = nombre de colonnes), donc $\bar\mu=\mu'$ : (Q) admet une unique solution $\mu^\star$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

L'unicité duale repose sur l'injectivité de ${}^{\mathsf t}A$, conséquence du rang plein $p$ de $A$.

## Question IV.6.c

**Stratégie.** $\mu^\star$ solution de (Q) donne $\langle g(x_{\mu^\star}),\mu-\mu^\star\rangle\le0$ (IV.5.a) ; reconnaître la caractérisation I.6.b de la projection sur $\mathbb R^p_+$.

**Rédaction.**

Par IV.5.a appliqué à $\bar\mu=\mu^\star$ : pour tout $\mu\in\mathbb R^p_+$, $\langle g(x_{\mu^\star}),\mu-\mu^\star\rangle\le0$.

Pour $\rho>0$, $$\big\langle(\mu^\star+\rho\,g(x_{\mu^\star}))-\mu^\star,\ \mu-\mu^\star\big\rangle=\rho\langle g(x_{\mu^\star}),\mu-\mu^\star\rangle\le0\qquad\forall\mu\in\mathbb R^p_+.$$
Comme $\mu^\star\in\mathbb R^p_+$ et $\mathbb R^p_+$ est convexe fermé, la caractérisation I.6.b de la projection donne $$\mu^\star=P_{\mathbb R^p_+}\big(\mu^\star+\rho\,g(x_{\mu^\star})\big).\qquad\square$$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

C'est le « point fixe » de l'itération d'Uzawa : $\mu^\star$ est invariant par l'opérateur $\mu\mapsto P_{\mathbb R^p_+}(\mu+\rho\,g(x_\mu))$.

## Question IV.6.d

**Stratégie.**

Comparer $\mu_{k+1}$ et $\mu^\star$ via la non-expansivité de $P_{\mathbb R^p_+}$ (I.6.c), puis exploiter la monotonie forte de $\nabla f$ et l'hypothèse $\|Ax\|\le\sqrt{\alpha/\rho}\,\|x\|$ pour faire apparaître une décroissance avec terme en $\|x_{\mu_k}-x^\star\|^2$.

**Rédaction.**

Rappelons $x_{\mu^\star}=x^\star$ (IV.6.b) et $\mu^\star=P_{\mathbb R^p_+}(\mu^\star+\rho g(x_{\mu^\star}))$ (IV.6.c).

Posons $\delta\mu_k=\mu_k-\mu^\star$ et $\delta x_k=x_{\mu_k}-x^\star$.

Comme $P_{\mathbb R^p_+}$ est $1$-lipschitzienne (I.6.c), $$\|\mu_{k+1}-\mu^\star\|^2\le\big\|(\mu_k+\rho g(x_{\mu_k}))-(\mu^\star+\rho g(x^\star))\big\|^2=\big\|\delta\mu_k+\rho A\,\delta x_k\big\|^2,$$ en utilisant $g(x_{\mu_k})-g(x^\star)=A\,\delta x_k$.

Donc $$\|\mu_{k+1}-\mu^\star\|^2\le\|\delta\mu_k\|^2+2\rho\langle\delta\mu_k,A\,\delta x_k\rangle+\rho^2\|A\,\delta x_k\|^2.$$
Or $\langle\delta\mu_k,A\,\delta x_k\rangle=\langle{}^{\mathsf t}A\,\delta\mu_k,\delta x_k\rangle$, et ${}^{\mathsf t}A\,\delta\mu_k=-(\nabla f(x_{\mu_k})-\nabla f(x^\star))$ (IV.6.a).

Par I.3.b, $$\langle\delta\mu_k,A\,\delta x_k\rangle=-\langle\nabla f(x_{\mu_k})-\nabla f(x^\star),\delta x_k\rangle\le-\alpha\|\delta x_k\|^2.$$
Avec l'hypothèse $\|A\,\delta x_k\|^2\le\frac{\alpha}{\rho}\|\delta x_k\|^2$, on obtient $\rho^2\|A\,\delta x_k\|^2\le\rho\alpha\|\delta x_k\|^2$, d'où $$\|\mu_{k+1}-\mu^\star\|^2\le\|\mu_k-\mu^\star\|^2-2\rho\alpha\|\delta x_k\|^2+\rho\alpha\|\delta x_k\|^2=\|\mu_k-\mu^\star\|^2-\rho\alpha\|x_{\mu_k}-x^\star\|^2.\tag{$\dagger$}$$
La suite $(\|\mu_k-\mu^\star\|^2)$ est décroissante et minorée par $0$, donc convergente.

En sommant $(\dagger)$ de $0$ à $N$, $$\rho\alpha\sum_{k=0}^{N}\|x_{\mu_k}-x^\star\|^2\le\|\mu_0-\mu^\star\|^2-\|\mu_{N+1}-\mu^\star\|^2\le\|\mu_0-\mu^\star\|^2.$$
La série $\sum_k\|x_{\mu_k}-x^\star\|^2$ converge ($\rho\alpha>0$), donc son terme général tend vers $0$ : $x_{\mu_k}\to x^\star$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

La condition $\|Ax\|\le\sqrt{\alpha/\rho}\,\|x\|$ est exactement calibrée pour que le terme dissipatif $-2\rho\alpha\|\delta x_k\|^2$ domine le terme parasite $\rho^2\|A\delta x_k\|^2$ et laisse une décroissance nette $-\rho\alpha\|\delta x_k\|^2$.

## Question IV.6.e

**Stratégie.**

Transférer la convergence $x_{\mu_k}\to x^\star$ aux multiplicateurs via $\nabla f(x_{\mu_k})=-{}^{\mathsf t}A\mu_k$ et la minoration $\|{}^{\mathsf t}A\nu\|\ge c\|\nu\|$ (injectivité de ${}^{\mathsf t}A$).

**Rédaction.**

Par IV.6.a, ${}^{\mathsf t}A\mu_k=-\nabla f(x_{\mu_k})$ et ${}^{\mathsf t}A\mu^\star=-\nabla f(x^\star)$.

Comme $\nabla f$ est continue et $x_{\mu_k}\to x^\star$ (IV.6.d), $${}^{\mathsf t}A(\mu_k-\mu^\star)=-\big(\nabla f(x_{\mu_k})-\nabla f(x^\star)\big)\xrightarrow[k\to\infty]{}0.$$
Or $A$ est de rang $p$, donc ${}^{\mathsf t}A$ est injective : $\nu\mapsto\|{}^{\mathsf t}A\nu\|$ est une norme sur $\mathbb R^p$.

En dimension finie toutes les normes sont équivalentes, donc il existe $c>0$ tel que $\|{}^{\mathsf t}A\nu\|\ge c\|\nu\|$ pour tout $\nu\in\mathbb R^p$.

Ainsi $$\|\mu_k-\mu^\star\|\le\frac1c\,\|{}^{\mathsf t}A(\mu_k-\mu^\star)\|\xrightarrow[k\to\infty]{}0,$$ d'où $\mu_k\to\mu^\star$. $\square$

**Commentaire du correcteur.** Le rapport ne commente pas cette question.

L'argument final repose à nouveau sur l'injectivité de ${}^{\mathsf t}A$ (rang plein), qui fournit la minoration $\|{}^{\mathsf t}A\nu\|\ge c\|\nu\|$ par équivalence des normes — point à énoncer explicitement plutôt que sous-entendu.

---

*Fin du corrigé.*