OCVX: hyperplan d'appui

Rappels

• Hyperplan d'appui a une partie
  $A$ de
  ${\mathbb{R}}^n$ en un point
  $p\in A$, est un hyperplan affine de
  ${\mathbb{R}}^n$ qui laisse
  $A$ dans un des deux demi-espaces definis par
  $H$

Etant donne un vecteur normal

$\overrightarrow{\nu }$ definissant

$H\in {\mathbb{R}}^n$ et

$p$ un point dans

$H\cap A$ on a

$$\mathrm{\forall }x\in A;<\overrightarrow{\nu },x-p>\le 0$$

• On a definit par ailleurs la notion de gradient d'une fonction differentiable
  $f:{\mathbb{R}}^n\to \mathbb{R}$ en un point
  $a$, determinee par la relation:

$$\begin{gathered} \mathrm{\forall }h\text{ assez petit} \\ f(a+b)=f(a)+\mathrm{\nabla }f(a{)}^{T}h+\underset{\epsilon (h)\to 0 \\ h\to 0}{\underbrace{\epsilon (h)\Vert h\Vert }} \end{gathered}$$

Plan du cours

Objectif d'aujourd'hui

1. Etendre la notion de droite tangente au graphe d'une fonction
   $f:\mathbb{R}\to \mathbb{R}$
   1. Au cas des fonctions
      $\varphi :{\mathbb{R}}^n\to \mathbb{R}$
   2. au cas des parties de
      ${\mathbb{R}}^n$ decrites comme courbes de niveaux de fonctions
2. Utiliser le point 1. pour obtenir une lieuristique, permettant de construire des methodes iteratives d'optimisation

1. Revoir la notion de droite tangente dans le cas
   $\mathbb{R}$ (une dimension)
   • $f:\mathbb{R}\to \mathbb{R}$
   • Graphe
2. On va definir une maniere de generaliser la notion de droite tangente
   • $f:\mathbb{R}\to \mathbb{R}$
   • Graphe
3. On adapte cette definition au cas de courbes de niveaux
   • $g:{\mathbb{R}}^2\to \mathbb{R}$
   • zeros de
     $g$ (courbes de niveau de
     $g$)
4. Conclusion pour le cas general
   • $\varphi :{\mathbb{R}}^n\to \mathbb{R}$

Espace tangent

Le gradient en dimension 1 correspond a la notion de derivee, qui permet de definir la notion de droite tangente au graphe d'une fonction en un point. Dans ce contexte, l'interpretation geometrique de la notion de gradient est connue. En particulier le fait que vous soyez croissants ou decroissant vous est donne par le signe de votre gradient; cela vous permet de savoir dans quelle direction aller si vous cherchez des points ou votre fonction a des plus petite ou plus grandes valeurs.

Que signifie un nombre positif ou negatif pour un vecteur de

$\mathbb{R}$ ?
Si on est positif (resp. negatif), on est dans la moitie positive(resp. negative) de notre droite reelle.

$$Q:\underset{x\in \mathbb{R}}{min}f(x)$$
On cherche a minimiser la fonction

$f$

Dans ce dessin, le signe de la derivee vous dit que si vous voulez chercher des points

$x$ avec

$f(x)\le f(a)$, il faut aller dans le sens oppose a

$f^{\prime }(a)$.

La droite

$D_{f,p}$ est derivee parametriquement par

$$\begin{array}{rl}\mathbb{R}& {\to }^{\lambda }{\mathbb{R}}^2\\ t& \mapsto (a+t,f^{\prime }(a)t+f(a))\text{color}green=(a,f(a))+t(1,f^{\prime }(a))\text{color}red=P\end{array}$$

On est en train de dire que

$D_{f,p}$ est la droite passant par

$p$, de direction

$Vect((1,f^{\prime }(a)))$

Cette notion de droite tangente ne semble pas, telle quelle, facilement generalisable au cas de fonctions de

${\mathbb{R}}^n\to \mathbb{R}$

Definition
Soit

$A$ une partie de

${\mathbb{R}}^n$, soit

$p\in A$. On appelle

$$\text{color}red\text{germe d'une courbe (derivable) }\gamma :\underset{\epsilon >0}{\underbrace{]-\epsilon ,\epsilon [}}\to A\text{ tel que }\gamma (0)=p$$, la derivee de

$\gamma$ en

$0$

Cela correspond au vecteur vitesse en

$p$ d'un point materiel passant par

$p$ a l'instant 0, si

$\gamma$ decrit la position de ce point en fonction du temps

$t$.

L'ensemble des germes de courbes en

$p$ definit un sous-espace vectoriel de

${\mathbb{R}}^n$.

$\text{color}orange\text{On le note }{T}_{A,p}\text{, il s'appelle espace tangent a }A\text{ en }p$.

Que donne

$\text{color}orange{T}_{A,p}$ dans le cas du graphe de

$f$?

Si

$A$ est

${\mathrm{\Gamma }}_f$ (graphe de

$f$) toute courbe passant par

$p$

$\gamma :]-\epsilon ,\epsilon [\to {\mathrm{\Gamma }}_f$ est de la forme:

$$\gamma (t)=\underset{\text{color}orange\psi (t),\varphi (t)}{\underbrace{(\psi (t),f(\psi (t)))}}\text{pour }\psi :]-\epsilon ,\epsilon [\to \mathbb{R}$$
avec

$\psi (0)=a$

Si

$\gamma$ est derivable en 0:

$${\gamma }^{\prime }(0)=({\psi }^{\prime }(0),{\psi }^{\prime }(0)f^{\prime }(a))={\psi }^{\prime }(0)(1,f^{\prime }(a))$$

$$\Rightarrow {\gamma }^{\prime }(0)\in Vect((1,f^{\prime }(a)))\Rightarrow T_{A,p}\subseteq Vect((1,f^{\prime }(a)))$$

Conclusion

$$T_{A,p}=Vect((1,f^{\prime }(a)))$$

autrement dit:

$D_{f,p}=p+T_{A,p}$

Definition
Etant donne une partie

$A\subseteq {\mathbb{R}}^n$ et

$p\in A$, on appelle espace tangent a

$A$ en

$p$ l'espace vectoriel

$T_{A,p}$ compose des germes de courbes dans

$A$ passant par

$p$.

Remarque: Geometriquement, on represente souvent

$p+T_{A,p}$ et non

$T_{A,p}$

Notre prochaine etape est de reinterpreter

$p+T_{A,p}$ de maniere implicite de facon a faire apparaitre la notion de gradient d'une fonction

${\mathbb{R}}^n\to \mathbb{R}$.

On a

$D_{f,p}:(a,f(a))+t(1,f^{\prime }(a))$ pour

$t\in \mathbb{R}$.

Comment obtenir une ecriture implicite de

$D_{f,p}$ ?
Si

$(x,y)\in D_{f,p}$ alors

$$\{\begin{array}{l}x=a+t\\ y=f(a)+f^{\prime }(a)t\end{array}\iff f^{\prime }(a)(x-a)=y-f(a)$$

Questions

1. Comment ecrit-on
   ${\mathrm{\Gamma }}_f$ comme zeros d'une fonction ?
2. Quel est le gradient de cette fonction au point
   $p$ ?
3. Quel est
   $\perp$ de ce gradient au point
   $p$ ?

Premiere question

${\mathrm{\Gamma }}_f$ est zeros de la fonction:

$$\begin{gathered} \begin{array}{rl}\varphi :{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto f(x)-y\end{array} \\ \begin{array}{rl}z(\varphi )=\{(x,y)|f(x)-y=0\}& =\{(x,y)|f(x)=y\}\\ & =\{(x,f(x))|x\in \mathbb{R}\}\\ & ={\mathrm{\Gamma }}_f\end{array} \end{gathered}$$

Deuxieme question

$$\begin{gathered} \mathrm{\nabla }\varphi ((a,f(a)))=\left(\begin{array}{c}\frac{\partial \varphi }{\partial x}(a,f(a))\\ \frac{\partial \varphi }{\partial y}(a,f(a))\end{array}\right)=\left(\begin{array}{c}{f}^{\prime }(a)\\ -1\end{array}\right) \\ \varphi (x,y)=f(x)-y \end{gathered}$$

Ce qui genere notre droite tangente c'est

$(1,f^{\prime }(a))$ et on a obtenu le vecteur

$(f^{\prime }(a),-1)$.

On a obtenu un vecteur orthogonal a notre droite tangente

Troisieme question

L'orthogonal a

$\mathrm{\nabla }\varphi (p)$ au point

$p$:

$$\mathrm{\nabla }\varphi (p{)}^T\left(\begin{array}{c}x-a\\ y-f(a)\end{array}\right)=\left(\begin{array}{c}{f}^{\prime }(a)\\ -1\end{array}\right)\left(\begin{array}{c}x-a\\ y-f(a)\end{array}\right)=f^{\prime }(a)(x-a)-(y-f(a))$$

$\perp \mathrm{\nabla }\varphi (p):f^{\prime }(a)(x-a)=y-f(a)$ (

$\perp$ passant par

$p$)

"Vectorialise":

$f^{\prime }(a)x=y\iff \mathrm{\nabla }\varphi (p{)}^T\left(\begin{array}{c}x\\ y\end{array}\right)=0$

$\mathrm{\nabla }\varphi (p)$ nous donne

$T_{{\mathrm{\Gamma }}_{f,p}}$, Autrement dit:

$$D_{f,p}:p+\underset{\text{color}orange{T}_{{\mathrm{\Gamma }}_{f,p}}}{\underbrace{\mathrm{\nabla }\varphi (p{)}^{\perp }}}$$

Prop
Soit

$f:{\mathbb{R}}^n\to \mathbb{R}$ une fonction differentiable en un point

$p\in {\mathcal{C}}_{f,r}$. L'espace tangent a

${\mathcal{C}}_{f,r}$ au point

$p$ est donne par l'hyperplan orthogonal (

$\perp$) a

$\mathrm{\nabla }f(p)$.

Question: Calculer l'espace tangent au point

$(1,1)$ de

${\mathcal{C}}_{f,r}$ pour

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

$$\begin{array}{rl}\mathrm{\nabla }f(x,y)=\left(\begin{array}{c}2x\\ 2y\end{array}\right);\mathrm{\nabla }f(1,1{)}^T\left(\begin{array}{c}x\\ y\end{array}\right)& =0\\ \iff 2x+2y& =0\\ \iff x+y& =0\end{array}$$

Apport de la convexite

Rappel

Une fonction

$f:{\mathbb{R}}^n\to \mathbb{R}$, differentiable, est convexe si

$\mathrm{\forall }x,y\in {\mathbb{R}}^n$

$$f(y)-f(x)\ge \mathrm{\nabla }f(x{)}^T(y-x)\text{(E)}$$

Hypothese

Hypothese

$f:{\mathbb{R}}^n\to \mathbb{R}$ une fonction convexe

Dans ce cas

$\mathrm{\forall }r\in \mathbb{R}$,

${\mathcal{C}}_{f\le r}$ est convexe

$\subseteq {\mathbb{R}}^n$

Ici,

$$\mathrm{\forall }y\in {\mathcal{C}}_{f_1\le v}$$,

$\mathrm{\nabla }f(x{)}^T(y-a)\le 0$. Donc

$x+\mathrm{\nabla }f(x{)}^{\perp }$ est un hyperplan d'appui a

$${\mathcal{C}}_{f_1\le v}$$

Convexite:

$f(y)-f(x)\ge \mathrm{\nabla }f(x{)}^T(y-x)$

Donc le demi-espace positif est a exclure si l'on souhaite chercher un point

$x^{+}$ tel que

$f(x^{+})\le f(x)$

On vient d'eliminier toute une partie de l'espace de nos recherches.

Question: Dans quelle direction chercher ?

Prop
Soit

$f:U\subset {\mathbb{R}}^n\to \mathbb{R}$ une fonction differentiable. Soit

$x\in {\mathcal{C}}_{f,r}$, si

$\mathrm{\nabla }f(x)\ne 0$

$\mathrm{\exists }{x}^{+}=x+\mathrm{\Delta }x$ tel que

$f(x)\ge f(x^{+})$ detour, par un deplacement

$\mathrm{\Delta }x$ a l'oppose de la direction de

$\mathrm{\nabla }f(x)$

Remarques

1. On ne connait pas a priori l'amplitude par laquelle on doit additioner
   $\mathrm{\nabla }f(x)$ a
   $x$, pour obtenir
   $x^{+}$
2. Ce resultat est vrai meme si
   $f$ n'est pas convexe, on ne garantit plus la recherche d'un minimum global

Question: Il se passe quoi si

$\mathrm{\nabla }f(x)=0$ ?

Questions des eleves

J'ai pas compris la particule a une vitese constante sur x? Comment on défini la "vitesse"?

Tu images que la courbe gamma représente le déplacement de la particule le long de la courbe A -> gamma(t) = abscisse de la particule le long de la courbe. Avec en t=0, ta particule qui passe par le point p

La vitesse instantanée = dérivée de la position. Vitesse instantanée de la particule en p = dérivée de gamma en 0

Ta particule peut adopter plusieurs profils de vitesse le long de la courbe (accélérer, décélérer, etc), mais elle est contrainte de suivre le profile de la courbe

Donc la valeur du vecteur vitesse gamma'(0) peut effectivement varier selon le profil de vitesse

Mais la direction de ce vecteur vitesse sera toujours la même, et c'est ce qui défini l'espace tangent (en dim 1)

Mais du coup on fait tout ça juste pour trouver un vecteur qui appartient a l'espace tangent?

En fait cette idée est très générale, et indépendante de la dimension de l'espace dans lequel on travaille.
En dim 1, ça peut paraître un peu overkill de faire tout ça "juste" pour avoir la direction de la tangente.
Mais quand on va passer sur des dimensions supérieurs (donc des surfaces, etc), là tu auras plusieurs directions possibles de te balader sur la surface et d'approcher ton point p. Imagine

$f(x,y)=x^2+y^2$, donc une surface en forme de bol. En (0,0), tu as plusieurs directions pour approcher (0,0) en restant sur la surface. Pour chacune de ces courbes possibles, tu vas avoir un vecteur vitesse associé. Et c'est l'ensemble de ces vecteurs vitesse (enfin, l'espace généré par ces vecteurs vitesse) qui va définir le plan tangent

J'ai encore du mal à voir en quoi c'est différent d'une différentielle

Il y a effectivement un lien entre les deux notions, mais ce ne sont pas du tout les mêmes objets : une différentielle est une application linéaire, un espace tangent est une sous-partie de ton espace de travail.