OCVX2: Approche lineaire

Exercice 1

On considere la fonction differentiable

$$\begin{array}{rl}f:{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto 3x^2+y^2\end{array}$$

1. Representer les courbes de niveaux 2 et 4 de
   $f$ dans le plan euclidien
2. A quel lieu correspond la condition
   $f(x,y)\le 4$
3. On s'interesse au probleme d'optimisation
   $(P)$ minimiser
   $f_0(x,y)=2x+y$ sujet a
   $3x^2+y^2\le 4$. Representer la courbe de niveau de la fonction objectif qui correspond a la valeur optimale de
   $(P)$
4. Comment trouver le point optimal correspondant a
   $(P)$? Faire le calcul

Solution

$$\begin{gathered} f(x,y)=3x^2+y^2 \\ \begin{array}{rl}{\mathcal{C}}_2& =\{3x^2+y^2=2\}\\ & =\{\frac{3}{2}{x}^2+\frac{1}{2}{y}^2=1\}\end{array} \end{gathered}$$

Il s'agit de l'equation d'une elipse de:

• demi grand axe
  $a$
• demi petit axe
  $b$

$$(\frac{x}{a}{)}^2+(\frac{y}{b}{)}^2=1$$

Rappel

$$\begin{gathered} 2\pi r\to \pi (a+b) \\ \pi r^2\to \pi ab \end{gathered}$$

$${\mathcal{C}}_2(f)=\{3x^2+y^2=2\}$$

Ellipse de:

• demi grand axe
  $\sqrt{2}$ sur
  $O_y$
• demi petit axe
  $\sqrt{\frac{2}{3}}$ sur
  $O_x$

$${\mathcal{C}}_4(f)=\{3x^2+y^2=4\}$$

Ellipse de:

• demi grand axe
  $2$ sur
  $O_y$
• demi petit axe
  $\frac{2}{\sqrt{3}}$ sur
  $O_y$

Zoli dessin

$$\begin{array}{rl}(P)\text{min}{f}_0(x,y)& =2x+y\\ 3x^2+y^2& \le 4\iff {\mathcal{C}}_{\le 4}(f)\end{array}$$

$$\begin{gathered} {\mathcal{C}}_0=\{2x+y=0\} \\ \overrightarrow{u}=(\genfrac{}{}{0ex}{}{-1}{2}) \\ \overrightarrow{n}=(\genfrac{}{}{0ex}{}{2}{1}) \end{gathered}$$

Pour minimiser, on part dans le sens inverse du vecteur normal.

Notre point optimal:

$p^{\text{*}}=(x^{\text{*}},y^{\text{*}})$

$$\begin{gathered} p\ast \in {\mathcal{C}}_4(f)\iff 3x^{{\ast }^2}+y^{{\ast }^2}=4 \\ p\ast \in {\mathcal{C}}_{f_0^{\ast }}\iff 2x^{\ast }+y^{\ast }=f_0^{\ast } \end{gathered}$$

Le gradient d'une fonction en un point donne est orthogonal a la courbe de niveau qui passe par ce point la.

En

$p^{\ast }$:

$$\begin{gathered} \mathrm{\nabla }\overrightarrow{f}(p^{\ast })=\lambda \overrightarrow{n} \\ \mathrm{\nabla }\overrightarrow{f}(p^{\ast })+\lambda \overrightarrow{n}=0\lambda >0 \end{gathered}$$

$$\begin{gathered} f(x,y)=3x^2+y^2 \\ \mathrm{\nabla }f=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})=(6x,2y) \\ \begin{array}{rl}\mathrm{\nabla }f(p^{\ast }=(x^{\ast },y^{\ast }))=(6x^{\ast },2y^{\ast })=\lambda (\genfrac{}{}{0ex}{}{2}{1})& \iff \{\begin{array}{l}6x^{\ast }=2\lambda \\ 2y^{\ast }=\lambda \end{array}\\ & \iff 6x^{\ast }=4y^{\ast }\\ & \iff \text{color}green\boxed{{\displaystyle y^{\ast }=\frac{3}{2}{x}^{\ast }}}\end{array} \\ \begin{array}{rl}3x^{{\ast }^2}+y^{{\ast }^2}=4\Rightarrow 3x^{{\ast }^2}+(\frac{3}{2}{x}^{\ast }{)}^2& =4\\ 3x^{{\ast }^2}+\frac{9}{4}{x}^{{\ast }^2}& =4\\ \frac{21}{4}{x}^{{\ast }^2}& =4\\ x^{{\ast }^2}& =\frac{16}{21}\end{array} \end{gathered}$$

Donc:

$$\begin{gathered} x^{\ast }=\frac{4}{\sqrt{21}}\text{ou}\text{color}green\boxed{{\displaystyle -\frac{4}{21}}} \\ \text{et}\text{color}green\boxed{{\displaystyle y^{\ast }=-\frac{6}{\sqrt{21}}}} \end{gathered}$$

:::

Exercice 2

On considere le probleme d'optimisation

$(P)$ minimiser

$f_0(x,y)=x+y$ sujet a

$x+2y\le 3,x\in B$ avec

$B\in {\mathbb{R}}^2$ l'intersection de l'epigraphe de

$x\mapsto -\sqrt{x}$.

1. Dessiner le lieu admissible de
   $(P)$
2. Representer la courbe de niveau
   $f_0$ qui realise le minimum de
   $(P)$
3. Calculer le point optimal ainsi que la valeur optimale de
   $(P)$

Solution

Rappel: Epigraphe

Tout ce qu'il y a au-dessus du graphe de la fonction

$$\text{epi}(f)=\{(x,t)|t\ge f(x)\}$$

$$\begin{gathered} x+2y-3=0(D) \\ (3,0)\in D \\ \overrightarrow{u}=(\genfrac{}{}{0ex}{}{-2}{1}) \\ \overrightarrow{n}=(\genfrac{}{}{0ex}{}{1}{2}) \end{gathered}$$

Avec la courbe

${\mathcal{C}}_0$:

Avec

$p^{\text{*}}=(x^{\text{*}},y^{\text{*}})$:

Le vecteur normal au graphe va etre colineaire au vecteur normal de notre courbe de niveau.

Gradient de quoi ?

On est sur le graphe et pas la ligne de niveau

Est-ce qu'on peut exprimer le graphe comme ligne de niveau ?

Toutes les representations parametriques peuvent s'ecrire en representation implicite (l'inverse n'etant pas vrai)

Notre graphe de

$y\mapsto -\sqrt{x}$ est:

$$\begin{gathered} \{(x,y)\text{ tq }y=-\sqrt{x}\} \\ \{(x,y)\text{ tq }\sqrt{x}+y=0\} \\ ={\mathcal{C}}_0(g) \end{gathered}$$
Avec:

$$\begin{array}{rl}g:{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto \sqrt{x}+y\end{array}$$

Condition d'optimalite: en

$p^{\text{*}}=(x^{\text{*}},y^{\text{*}})$,

$$\begin{gathered} \mathrm{\nabla }g(p^{\ast })=\lambda {\overrightarrow{n}}_0 \\ \begin{array}{rl}\mathrm{\nabla }g(x,y)& =(\frac{\partial g}{\partial x},\frac{\partial g}{\partial y})\\ & =(\frac{1}{2\sqrt{x}},1)\end{array} \end{gathered}$$

En

$p^{\text{*}}$:

$$\begin{array}{rl}& \{\begin{array}{l}\frac{1}{2\sqrt{x^{\ast }}}=\lambda \\ 1=\lambda \end{array}\\ & \iff \{\begin{array}{l}\lambda =1\\ \frac{1}{2\sqrt{x^{\ast }}}=1\end{array}\\ & \iff \{\begin{array}{l}{x}^{\ast }=\frac{1}{4}\\ y^{\ast }=-\frac{1}{2}\end{array}\end{array}$$

Valeur optimale:

$$x^{\ast }+y^{\ast }=\frac{1}{4}-\frac{1}{2}=\text{color}green\boxed{{\displaystyle -\frac{1}{4}}}$$

:::