مسابقة دكتوراه 2021 — Université Mohamed El Bachir El Ibrahimi

التمرين 1

Exercice 1 — Coercivité et points critiques d'une fonction sur R²

#optimization#coercivity#critical-points#convexity

On considère la fonction $f$ définie sur $\mathbb{R}^2$ par :

f(x,y) = x^2 + y^2 + 4\left(x^2 + y^2 - 1 - \frac{1}{6}\right)^2 + 2xy.

(2 pts) Montrer qu'il existe $(\alpha, \beta) \in \mathbb{R}_+^2$ tels que $f(x,y) \geq \alpha \|(x,y)\|^2 + \beta$ pour tous $(x,y) \in \mathbb{R}^2$ et déduire que $f$ est coercive.
(2 pts) Déterminer les points critiques et la nature de chacun.
(1 pt) La fonction $f$ est-elle convexe ?

◀الحل

1.

On développe : $f(x,y) = x^2+y^2+2xy + 4(x^2+y^2-7/6)^2$ . Le terme $4(x^2+y^2-7/6)^2 \geq 0$ . Par ailleurs $x^2+y^2+2xy = (x+y)^2 \geq 0$ , mais on a aussi $x^2+y^2 \geq (x+y)^2/2$ . Pour la coercivité : quand $\|x,y\| \to \infty$ , le terme quartique $4(x^2+y^2)^2$ domine. Donc $f(x,y) \to +\infty$ .

2.

$\nabla f = 0$ donne un système. Les points critiques se trouvent en résolvant les équations $\partial f/\partial x = 0$ et $\partial f/\partial y = 0$ .

3.

La matrice hessienne contient des termes quartiques, donc $f$ n'est pas quadratique. On vérifie si $H_f$ est semi-définie positive partout. Le terme $4(x^2+y^2-7/6)^2$ rend la hessienne non constante. En général, $f$ n'est pas convexe (à cause de la structure du polynôme de degré 4).

التمرين 2

Exercice 2 — Opérateur proximal et minimisation convexe

#proximal-operator#convex-optimization#projection#l1-norm

On considère $\mathbb{R}^n$ muni de la norme euclidienne. Soit $C \subset \mathbb{R}^n$ un ensemble convexe fermé non vide et $f : \mathbb{R}^n \to \mathbb{R}$ une fonction convexe. Pour $x \in \mathbb{R}^n$ on définit

\forall y \in \mathbb{R}^n, \quad \Phi_{f,x}(y) = f(y) + \frac{1}{2}\|x - y\|^2.

Montrer qu'il existe $x^* \in C$ unique tel que $\Phi_{f,x}(x^*) = \inf\{\Phi_{f,x}(y), y \in C\}$ . On note $\text{Prox}_f(x) = x^*$ .
À quoi correspond $\text{Prox}_f$ lorsque $f(x) = 0$ pour tout $x \in C$ ?
Calculer $\text{Prox}_f$ lorsque $C = \mathbb{R}^n$ et $f(x) = \|x\|_1$ .
Montrer que si $\bar{x} \in C$ est un minimiseur de $f$ sur $C$ , alors $\text{Prox}_f(\bar{x}) = \bar{x}$ .
On suppose $f = g + h$ avec $g$ convexe différentiable et $h$ convexe continue. Si $\bar{x}$ minimise $f$ sur $C$ , alors $\bar{x} = \text{Prox}_{\tau h}(\bar{x} - \tau \nabla g(\bar{x}))$ pour tout $\tau \gt 0$ .

◀الحل

1.

$\Phi_{f,x}$ est strictement convexe (car $\frac{1}{2}\|x-y\|^2$ est strictement convexe) et coercive. Donc elle admet un unique minimum sur $C$ (fermé convexe).

2.

Si $f \equiv 0$ : $\text{Prox}_f(x) = \arg\min_{y \in C} \frac{1}{2}\|x-y\|^2 = P_C(x)$ , la projection orthogonale sur $C$ .

\boxed{\text{Prox}_0 = P_C \text{ (projection sur } C)}

3.

Avec $C = \mathbb{R}^n$ et $f = \|\cdot\|_1$ : on minimise $\sum|y_i| + \frac{1}{2}\sum(x_i-y_i)^2$ composante par composante. La solution est le seuillage doux :

\boxed{(\text{Prox}_{\|\cdot\|_1}(x))_i = \text{sign}(x_i)\max(|x_i|-1, 0)}

4.

$\bar{x}$ minimise $f$ sur $C$ , donc $f(\bar{x}) \leq f(y)$ pour tout $y \in C$ . Alors $\Phi_{f,\bar{x}}(\bar{x}) = f(\bar{x}) \leq f(y) \leq f(y) + \frac{1}{2}\|\bar{x}-y\|^2 = \Phi_{f,\bar{x}}(y)$ .

5.

La condition d'optimalité de $\bar{x}$ pour $f = g+h$ s'écrit $0 \in \nabla g(\bar{x}) + \partial h(\bar{x}) + N_C(\bar{x})$ . Cela équivaut à $\bar{x} = \text{Prox}_{\tau h}(\bar{x} - \tau\nabla g(\bar{x}))$ (point fixe de l'itération forward-backward).