Problème de minimisation

sundae · January 2018

Bonjour,

Dans cet exercice, on note ||.|| la norme euclidienne standard sur R². On cherche à calculer la projection d'un point y=(y1,y2) dans R² sur l'ensemble C = { x=(x1,x2}, tel que x1²-x2 <=0 }

1) représenter C graphiquement.

2)Enoncer le théorème général sur la projection sur un convexe.

3)Montrer que C est un ensemble convexe fermé et en déduire que pour tout y da,s R le problème de projection sur C admet une solution unique y*

4. Dans cette question, on suppose que y appartient pas à C
.
(a) Montrer que y* minimise la fonction f(z) = ||z - y||² z = (z1, z2), sous la contrainte d’égalité z1² - z2 = 0.

(b) Appliquer la méthode des multiplicateurs de Lagrange au problème d’optimisation précédent, et donner le système d’équations satisfait parles coordonnées de y*(on ne cherchera pas à résoudre ce système dans le cas général).

(c) Calculer y* dans les cas suivants : y = (-1, 1/2) et y = (3, 0).

J'ai réussis à faire jusque la moitié de la 3) je ne sais pas comment déduire qu'il existe une unique projection sur C, s'agit-il d'un théorème ?

Pour la question 4) je ne comprend pas le mot minimisation, que veut - il dire ? Cherche les points critiques ? Ou bien autre choses ?
et que veux dire la mention "sous contrainte d'égalité z1²-z2" ?

Merci à vous tous chers lecteurs

LOU16 · January 2018

Bonjour,
Il me semble que dans un espace euclidien $E$, il est acquis que pour tout $x$ de $E$ et tout fermé $B$ convexe non vide de $E$, il existe un unique $x^*$ de $B$ tel que $\|x - x^*\| = d(x,\;B)$.
De plus si $x\notin B$ alors, $x^*$ est sur la frontière de $B$.
Ainsi si $y\notin C$ alors $y^*$ est l'unique point de $E$ qui minimise la fonction
$$f:\: (X,Y)\mapsto (X-y_1)^2 + (Y-y_2)^2$$ avec la condition d'appartenance à la parabole (frontière de $C$) $X^2 = Y$, et la "méthode des multiplicateurs de Lagrange" s'applique alors parfaitement.

Amicalement,

sundae · January 2018

Bonjour LOU16

Oulaaa, tout ce qui est "boule" nous ne l'avons pas abordé

Mais je vais essayer de comprendre tout de même.

Peux-tu me dire ce que veux dire "minimiser sous contrainte" ?

LOU16 · January 2018

Re,

Ici, la "contrainte" c' est "appartenir à la parabole":
On cherche le point de la parabole qui est le plus proche de $y$, c'est à dire parmi les couples $(X,Y)$ vérifiant
$X^2=Y$ (points de la parabole), ceux qui rendent la quantité $f(X,Y)$, qui est le carré de la distance de $y $ au point $(X,Y)$, la plus petite possible.

Amicalement,

NB: la notion de "boule" n'intervient à aucun moment dans mon propos.

gb · January 2018

Bonjour,

sundae a écrit:

J'ai réussis à faire jusque la moitié de la 3) je ne sais pas comment déduire qu'il existe une unique projection sur C, s'agit-il d'un théorème ?

Qu'as-tu répondu à la question 2 ?

sundae · January 2018

Bonjour,

Pour la question 2) : Soit (E,<.>) un espace de Hilbert et C inclus dans E un convexe fermé. Pour tout x dans E il existe un unique point de C noté z tel que pour tout y appartenant à C ||y-x||> ||z-x||

sundae · January 2018

Que veux dire " montrer que y minimise la fonction f(z)" ?
Que faut-il faire ? Calculer des points critiques ou bien autre chose :-(

gb · January 2018

Cela résout bien la question 3, pour l'existence et l'unicité de $y^*$, non ?

sundae · January 2018

Oui en effet gb, je pensais qu'il fallait faire des calculs pour le montrer :-D

Ca veut dire quoi montrer que y minimise tel ou tel fonction please

gb · January 2018

La question 3 est purement théorique, les calculs sont réservés à la question 4.

L'expression « $y^*$ minimise la fonction $f$ » signifie simplement que $f$ atteint son minimum en $y^*$.

Mais ici, la fonction $f$ est une fonction définie sur le plan $\mathbf{R}^2$, et on ne veut pas chercher un minimum global de cette fonction : ce serait bien évidemment 0 obtenu en $y$. On restreint $f$ au sous ensemble : $E = \lbrace z\in\mathbf{R}^2 \mathrel{;} z_1^2-z_2 \rbrace = \partial C$ défini par la « contrainte » (bien y réfléchir $E$ est la parabole qui limite le convexe $C$).

Sauf que, pour étudier les extrema de la restriction de $f$ à $E$, qui n'est pas un ouvert de $\mathbf{R}^2$ ($E$ est même d'intérieur vide), on ne peut pas utiliser la méthode usuelle avec les points critiques et on lui substitue la méthode des multiplicateurs de Lagrange que tu as dû voir en cours, sinon je ne sais pas comment tu pourrais répondre aux questions que l'on te pose.

sundae · January 2018

Super gb merci pour ces explications !

J'obtiens quelque chose, dîtes-moi si c'est bon.

J'applique le théorème sur les multiplicateurs de Lagrange. Soit k un réel, j'ai le système suivant

2*z₁-2*y₁ = 2*k*z₁
2*z₂-2*y₂ = -k

et ensuite pour la 4c) je remplace y₁ et y₂ par ce qu'on nous donne dans la question ?

sundae · January 2018

C'est correct ce que j'ai écris ?
Pour la 4c) je ne suis pas si sûr finalement :-D

[ Non. Le participe passé du verbe écrire est écrit (au féminin écrite, pas écrise.) ;-) AD]

AP · January 2018

Bonsoir

Tu cherches $z=(z_1,z_2) $ minimisant $||z-y||^2$ mais $z$ étant sur la parabole frontière de ton domaine
via le multiplicateur de Lagrange, tu as 3 dérivées partielles à annuler et donc tu vas obtenir trois conditions dont l'une est l'équation de la parabole : il te manque cette condition
ainsi tu as 3 équations avec 3 inconnues $k,z_1,z_2$
Et tu dois trouver que $z_1$ (abscisse) vérifie une équation de degré 3 qui sera facile à résoudre pour tes deux exemples numériques

gb · January 2018

Ton calcul est correct sauf que tu as oublié la contrainte. Tu dois résoudre le système de trois équations :
\[\left\lbrace \begin{array}{l} 2(z_1-y_1) = 2kz_1 \\ 2(z_2-y_2) = -k \\ z_1^2-z_2 = 0 \end{array} \right.\]
à trois inconnues $(z_1,z_2,k)$, mais où tu t'intéresses en fait aux seules inconnues $(z_1,z_2)$ qui sont les coordonnées de la projection $y^*$ de $y$ sur le convexe fermé $C$.

sundae · January 2018

Merci à vous tous !

Bonne année au passage

Problème de minimisation

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 29