Exercices corrigés — Optimisation

Points critiques : $\nabla f=(2x-4,\,2y-6)=\vec0$.

Hessienne $H=\begin{pmatrix}2&0\\0&2\end{pmatrix}$ (constante).

Calculer $rt-s^2$ et le signe de $r$.

$f_x=2x-4=0$, $f_y=2y-6=0\Rightarrow(x,y)=(2,3)$.

$r=2,\ t=2,\ s=0$ : $rt-s^2=4>0$ et $r>0\Rightarrow$ minimum local. Valeur $f(2,3)=0$.

$f=(x-2)^2+(y-3)^2\ge0$ : le minimum est global, atteint en $(2,3)$.

$\nabla f=(2x,-2y)=\vec0\Rightarrow(0,0)$.

$H=\begin{pmatrix}2&0\\0&-2\end{pmatrix}$.

$rt-s^2<0$ caractérise un col.

$f_x=2x=0$, $f_y=-2y=0\Rightarrow(0,0)$.

$r=2,\ t=-2,\ s=0$ : $rt-s^2=-4<0\Rightarrow$ point col. Les valeurs propres $2$ et $-2$ sont de signes opposés : $f$ croît selon $x$, décroît selon $y$.

$\nabla f=(3x^2-3,\,2y)=\vec0$.

$3x^2-3=0\Rightarrow x=\pm1$, et $y=0$.

$H=\begin{pmatrix}6x&0\\0&2\end{pmatrix}$ dépend de $x$.

$x=\pm1$, $y=0$ : deux points $(1,0)$ et $(-1,0)$.

$r=6,\ t=2,\ s=0$ : $rt-s^2=12>0$, $r>0\Rightarrow$ minimum local, $f(1,0)=-2$.

$r=-6,\ t=2$ : $rt-s^2=-12<0\Rightarrow$ point col.

$\nabla f=(3x^2-3y,\,3y^2-3x)=\vec0\Rightarrow y=x^2$ et $x=y^2$.

$x=x^4\Rightarrow x\in\{0,1\}$ (racines réelles).

$H=\begin{pmatrix}6x&-3\\-3&6y\end{pmatrix}$.

$y=x^2,\ x=y^2\Rightarrow x^4=x\Rightarrow x=0$ ou $x=1$ : $(0,0)$ et $(1,1)$.

$H=\begin{pmatrix}0&-3\\-3&0\end{pmatrix}$, $rt-s^2=-9<0\Rightarrow$ col.

$H=\begin{pmatrix}6&-3\\-3&6\end{pmatrix}$, $rt-s^2=36-9=27>0$, $r>0\Rightarrow$ minimum local, $f(1,1)=-1$.

$\nabla f=(4x^3-4y,\,4y^3-4x)=\vec0\Rightarrow y=x^3$ et $x=y^3$.

$x=x^9\Rightarrow x\in\{0,1,-1\}$.

$H=\begin{pmatrix}12x^2&-4\\-4&12y^2\end{pmatrix}$.

$y=x^3,\ x=y^3\Rightarrow x^9=x\Rightarrow x\in\{0,1,-1\}$ : $(0,0),(1,1),(-1,-1)$.

$H=\begin{pmatrix}0&-4\\-4&0\end{pmatrix}$, $rt-s^2=-16<0\Rightarrow$ col.

$H=\begin{pmatrix}12&-4\\-4&12\end{pmatrix}$, $rt-s^2=144-16=128>0$, $r>0\Rightarrow$ minimum, $f(1,1)=f(-1,-1)=-2$.

$\nabla f=(4x^3,4y^3)=\vec0\Rightarrow(0,0)$.

Calculer la Hessienne en $(0,0)$.

Quand le test échoue, raisonner directement sur le signe de $f$.

$H=\begin{pmatrix}12x^2&0\\0&12y^2\end{pmatrix}$, donc en $(0,0)$ : $H=0$, $rt-s^2=0\Rightarrow$ cas douteux.

$f(x,y)=x^4+y^4\ge0=f(0,0)$ pour tout $(x,y)$ : c'est un minimum global, malgré l'échec du test.

$g(x,y)=x+y-10=0$.

$\nabla f=(y,x)$, $\nabla g=(1,1)$ ; poser $\nabla f=\lambda\nabla g$.

$y=\lambda$ et $x=\lambda\Rightarrow x=y$.

$y=\lambda$, $x=\lambda\Rightarrow x=y$ ; avec $x+y=10$ : $x=y=5$.

Aire $=xy=25$. Le rectangle optimal est le carré $5\times5$.

Minimiser le carré de la distance évite la racine.

$\nabla f=(2x,2y)=\lambda(1,1)\Rightarrow x=y$.

Reporter dans la contrainte.

$2x=\lambda$, $2y=\lambda\Rightarrow x=y$ ; $x+y=1\Rightarrow x=y=\tfrac12$.

$x^2+y^2=\tfrac14+\tfrac14=\tfrac12$ : distance minimale $\tfrac1{\sqrt2}$.

$\nabla f=(1,1)=\lambda(2x,2y)\Rightarrow x=y$.

$2x^2=1\Rightarrow x=\pm\tfrac1{\sqrt2}$.

Évaluer $f$ en chaque point.

$1=2\lambda x$, $1=2\lambda y\Rightarrow x=y$ ; $2x^2=1\Rightarrow x=y=\pm\tfrac1{\sqrt2}$.

$f\left(\tfrac1{\sqrt2},\tfrac1{\sqrt2}\right)=\sqrt2$ (max) ; $f\left(-\tfrac1{\sqrt2},-\tfrac1{\sqrt2}\right)=-\sqrt2$ (min).

$\nabla f=(y,x)=\lambda(2x,2y)$.

$y=2\lambda x$ et $x=2\lambda y\Rightarrow x^2=y^2$.

Avec $x^2+y^2=1$ : $x^2=y^2=\tfrac12$.

$y=2\lambda x$, $x=2\lambda y\Rightarrow x^2=y^2=\tfrac12$.

$xy=\pm\tfrac12$ : max $\tfrac12$ (si $x,y$ de même signe), min $-\tfrac12$ (signes opposés).

$\nabla f=(yz,xz,xy)=\lambda(1,1,1)$.

$yz=xz=xy\Rightarrow x=y=z$.

Reporter dans la contrainte.

$yz=xz\Rightarrow x=y$ (car $z>0$), de même $y=z$ : $x=y=z$ ; $x+y+z=3\Rightarrow x=y=z=1$.

$f(1,1,1)=1$. (Les points de bord $(3,0,0),\dots$ donnent $f=0$, ce ne sont pas des maxima intérieurs.)

$\nabla f=(2x,2y,2z)=\lambda(1,2,3)$.

$x=\tfrac\lambda2,\ y=\lambda,\ z=\tfrac{3\lambda}2$.

Reporter dans la contrainte.

$2x=\lambda,\ 2y=2\lambda,\ 2z=3\lambda\Rightarrow x=\tfrac\lambda2,\ y=\lambda,\ z=\tfrac{3\lambda}2$.

$\tfrac\lambda2+2\lambda+\tfrac{9\lambda}2=7\lambda=14\Rightarrow\lambda=2$, d'où $(x,y,z)=(1,2,3)$.

$d^2=1+4+9=14$, donc $d=\sqrt{14}$.

Calculer la Hessienne (constante).

Convexité $\Leftrightarrow$ Hessienne $\succeq0$ (vp $\ge0$).

Le point critique d'une fonction convexe est le min global.

$H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$, valeurs propres $1$ et $3$, toutes $>0\Rightarrow$ strictement convexe.

$\nabla f=(2x+y,\,x+2y)=\vec0\Rightarrow x=y=0$ ; convexité $\Rightarrow$ minimum global, $f(0,0)=0$.

$H=\begin{pmatrix}2&a\\a&2\end{pmatrix}$.

Convexe $\Leftrightarrow H\succeq0\Leftrightarrow\det H\ge0$ et diagonale $\ge0$.

$\det H=4-a^2$.

$\det H=4-a^2$. La diagonale ($2>0$) est toujours positive.

$H\succeq0\Leftrightarrow4-a^2\ge0\Leftrightarrow|a|\le2$. Strictement convexe ssi $|a|<2$.

$f'(x)=2x$, donc $x_{n+1}=x_n-\alpha\cdot2x_n=(1-2\alpha)x_n$.

Itérer avec $\alpha=0{,}1$.

Convergence vers $0$ ssi $|1-2\alpha|<1$.

$x_{n+1}=(1-2\cdot0{,}1)x_n=0{,}8\,x_n$ : $x_1=0{,}8$, $x_2=0{,}64$, $x_3=0{,}512$.

$x_n=(1-2\alpha)^n\to0$ ssi $|1-2\alpha|<1\Leftrightarrow0<\alpha<1$. Pour $\alpha=\tfrac12$ : un seul pas atteint $0$ (pas optimal) ; $\alpha\ge1$ diverge.

$\nabla f=(2x,20y)$, donc $x_{n+1}=(1-2\alpha)x_n$ et $y_{n+1}=(1-20\alpha)y_n$.

Chaque composante est stable ssi son facteur est $<1$ en module.

La plus grande courbure ($20$) impose le pas.

La composante $y$ : $y_{n+1}=(1-20\alpha)y_n$ stable ssi $|1-20\alpha|<1\Leftrightarrow0<\alpha<\tfrac1{10}$.

Avec $\alpha<\tfrac1{10}$ imposé par $y$, la composante $x$ décroît au facteur $1-2\alpha>0{,}8$ : lent. Le conditionnement $\kappa=\tfrac{20}2=10$ mesure cette disparité (vallée étirée $\Rightarrow$ zig-zags).

$S$ est une quadratique convexe en $(a,b)$ : son minimum est en $\nabla S=\vec0$.

$\partial_a S=0$ et $\partial_b S=0$ donnent les équations normales.

$\bar x=2{,}5$, $\bar y=2$.

$\partial_b S=0\Rightarrow b=\bar y-a\bar x$ ; $\partial_a S=0\Rightarrow a=\dfrac{\sum(x_i-\bar x)(y_i-\bar y)}{\sum(x_i-\bar x)^2}$.

$\sum(x_i-\bar x)(y_i-\bar y)=3$, $\sum(x_i-\bar x)^2=5$ : $a=\tfrac35=0{,}6$, $b=2-0{,}6\cdot2{,}5=0{,}5$.

Convexité : $f(\vec y)\ge f(\vec x)+\nabla f(\vec x)\cdot(\vec y-\vec x)$.

En un point critique $\vec x^\star$, $\nabla f(\vec x^\star)=\vec0$.

Substituer.

En $\vec x^\star$ critique : $f(\vec y)\ge f(\vec x^\star)+\vec0\cdot(\vec y-\vec x^\star)=f(\vec x^\star)$ pour tout $\vec y$ : minimum global.

$f=x^2+y^2-4x-6y+13$ a $H=2I\succ0$ (convexe) ; son point critique $(2,3)$ est donc le minimum global, $f=0$ — ce que confirmait $f=(x-2)^2+(y-3)^2$.