OCVX - Norme

Norme:

$$\begin{array}{rl}\Vert .\Vert .{\mathbb{R}}^n& \to {\mathbb{R}}^1\\ x& \mapsto \Vert x\Vert \end{array}$$

• separation:
  $\Vert x\Vert =0\Rightarrow x=0$
• homogeneite:
  $\Vert \lambda x\Vert =|\lambda |\Vert x\Vert$
• inegalite triangulaire:
  $\mathrm{\forall }x,y\in {\mathbb{R}}^n,\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$
• inegalite triangulaire inversee:
  $\mathrm{\forall }x,y\in {\mathbb{R}}^n,|\Vert x\Vert -\Vert y\Vert |\le \Vert x-y\Vert$

$$\begin{gathered} \Vert x\Vert =\Vert x+y-y\Vert \le \Vert x-y\Vert +\Vert y\Vert \\ \iff \Vert x\Vert -\Vert y\Vert \le \Vert x-y\Vert \\ \Vert y\Vert =\Vert y-x+x\Vert \le \underset{\Vert x-y\Vert }{\underbrace{\Vert y-x\Vert }}+\Vert x\Vert =\Vert x-y\Vert +\Vert x\Vert \\ \iff \Vert y\Vert -\Vert x\Vert \le \Vert x-y\Vert \\ \Rightarrow |\Vert x\Vert -\Vert y\Vert |\le \Vert x-y\Vert \end{gathered}$$

A partir d'une norme, on peut definir une distance

$$d_{\Vert .\Vert }=\Vert x.y\Vert$$

Tout produit scalaire permet de definir une norme

$$\Vert x\Vert =\sqrt{<x.x>}$$

En particulier:

• $p=1$,
  $\Vert x{\Vert }_1=\sum _{i=1}^n|x_i|$
• $p=2$,
  $\Vert x{\Vert }_2=\sqrt{\sum _{i=1}^n{x}_i^2}$
• $p=\mathrm{\infty }$,
  $$\Vert x{\Vert }_{\mathrm{\infty }}=\underset{i=1,...,n}{max}|x|$$

Question 3.30

$$\begin{array}{rl}\Vert x-y{\Vert }_1& =|x_1.y_1|+|x_2.y_2|\\ & =|1-3|+|2-1|\\ d_{\Vert .{\Vert }_1}(xy)& =3\end{array}$$
Distance de Manhattan

$$\begin{array}{rl}\Vert x-y{\Vert }_2& =\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2}\\ d_{\Vert .{\Vert }_2}& =\sqrt{4+1}\\ & =5\end{array}$$

$$d_{\Vert .{\Vert }_{\mathrm{\infty }}}=\Vert x-y{\Vert }_{\mathrm{\infty }}=max(2,1)=2$$

Notion de voisinage

Notion de voisinnage/boule ouverte

$\to$ generalise la notion d'intervallle pour

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

$n\ge 2$
Boule ouverte centree sur un point

$x_0$ de rayon

$r$

$${\mathcal{B}}_{\Vert \Vert }(x_0,\epsilon )=\{y\in {\mathbb{R}}^n|\Vert x_0-y\Vert \le \epsilon \}\text{ boule ouverte}$$

$${\overline{\mathcal{B}}}_{\Vert \Vert }(x_0,\epsilon )=\{y\in {\mathbb{R}}^n,\Vert x_0-y\Vert \le \epsilon \}\text{ boule fermee}$$

Voisinnage de

$x_0$:

$$\begin{gathered} \mathcal{V}(x_0)\subseteq {\mathbb{R}}^n\text{ tq }\mathrm{\exists }\epsilon >0 \\ {\mathcal{B}}_{\Vert \Vert }(x_0,\epsilon )\in \mathcal{V}(x_0) \end{gathered}$$

Question 3.31

$$\begin{gathered} {\overline{\mathcal{B}}}_{\mathcal{2}}(0,1): \\ x\in (\delta {\mathcal{B}}_2(0,1)) \\ \{x\in {\mathbb{R}}^1,\underset{x_1^2+x_2^2=1}{\underbrace{\Vert x{\Vert }_1=1\}}} \end{gathered}$$

$$\begin{gathered} {\overline{\mathcal{B}}}_{\mathcal{1}}(0,1): \\ x\in \delta {\mathcal{B}}_1(0,1) \\ \{x\in {\mathbb{R}}^2,\underset{|x_1|+|x_2|=1}{\underbrace{\Vert x{\Vert }_2=1}}\} \end{gathered}$$

Si

$x_1>0$,

$x_2>0$,

$x_2=1-x_1$

$$\begin{gathered} {\overline{\mathcal{B}}}_{\mathrm{\infty }}: \\ x\in \delta {\mathcal{B}}_{infty}(0,1) \\ \{x\in {\mathbb{R}}^2,max(|x_1|,|x_2|)=1\} \end{gathered}$$

Nos formes s'emboitent:

$0<p<1?$

$\Vert .{\Vert }_p$ est une quasi norme

$\to$ inegalite triangulaire

$p=0?$

$\Vert x{\Vert }_0=$ nombre de coordonnees non nulles du vecteur

$x$

${\mathcal{B}}_p(0,1)$ convexe ?

$A$ convexe:

$\mathrm{\forall }x,y\in A,\mathrm{\forall }t\in [0,1]$,

$tx+(1-ty)\in A$

$$\begin{gathered} x,y\in {\mathbb{B}}_p(0,1)\iff \Vert x{\Vert }_p-\Vert y{\Vert }_p<1 \\ \begin{array}{rl}t\in [0,1],\Vert \underset{\in {\mathbb{B}}_p(0,1)}{\underbrace{tx+(1-t)y}}{\Vert }_p& \le \Vert tx{\Vert }_p+\Vert (1-t)y\Vert \text{ inegalite triangulaire}\\ & \le t\underset{\le 1}{\underbrace{\Vert x{\Vert }_p}}+(1-t)\underset{\le 1}{\underbrace{\Vert y{\Vert }_p}}\\ & \le t+(1-t)\\ & \le 1\end{array} \end{gathered}$$

${\mathcal{B}}_p(0,1)={\mathcal{C}}_{<1}\Vert .{\Vert }_p=$ lien de sous niveau (strict) 1.
Donc si

$\Vert .{\Vert }_p:x\mapsto \Vert x{\Vert }_p$ est une fonction convexe,

${\mathcal{B}}_p(0,1)={\mathcal{C}}_{<1}\Vert .{\Vert }_p$ est une partie convexe.

$\to (1-t)y\le tf(x)+(1-t)f(y)$

Continuite d'une fonction de

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

$f$ continue en

$a$

$$\mathrm{\forall }\epsilon >0,\mathrm{\exists }\eta >0,|x-a|<\eta \Rightarrow |f(x)-f(a)|<\epsilon$$

Continuite d'une fonction de

$\stackrel{\Vert .{\Vert }_n}{\overbrace{{\mathbb{R}}^n}}\to \stackrel{\Vert .{\Vert }_p}{\overbrace{{\mathbb{R}}^p}}$

$f$ continue en

$a$

$\iff$

$$\mathrm{\forall }\epsilon >0,\mathrm{\exists }\eta >0,\underset{x\in {\mathcal{B}}_{\alpha }(a,\eta )}{\underbrace{\Vert x-a\Vert \mathrm{\_}\alpha lt\eta }}\Rightarrow \underset{x\in {\mathcal{B}}_{\beta }(f(a),\epsilon )}{\underbrace{\Vert f(x)-f(a){\Vert }_{\beta }<\epsilon }}$$

Equation de normes

$\Vert .{\Vert }_{\alpha }$ et

$\Vert .{\Vert }_{\beta }$ sont equivalentes ssi

$\mathrm{\exists }A,B>0$ tels que

$$\mathrm{\forall }x\in {\mathbb{R}}^n,A\Vert x{\Vert }_{\beta }\le \Vert x{\Vert }_T\le B\Vert x{\Vert }_{\beta }$$

Theoreme
Toutes les normes sont equivalentes en dimension finie

Fonctions lipschitzienne

Definition: Fonctions lipschitzienne
Une fonction est

$K-$lipschitzienne s'il existe

$K>0$ tel que

$$\mathrm{\forall }x,y\in {\mathbb{R}}^n,\Vert f(x)-f(y)\Vert \le K\Vert x-y\Vert$$

Theoreme
Toute fonction lipschitzienne est continue.

Exemple

$$\begin{gathered} \begin{array}{rl}f:{\mathbb{R}}^2& \to \mathbb{R}\\ x=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)& \mapsto x_1+x_2\end{array} \\ \begin{array}{rl}\{\begin{array}{l}x\in {\mathbb{R}}^2\\ y\in {\mathbb{R}}^2\end{array}\Vert f(x)-f(y)\Vert & =|(x_1+x_2)-(y_1+y_2)|\\ & =|(x_1-y_1)+(x_2-y_2)|\le |x_1-y_1|+|x_2-y_2|\end{array} \\ \Vert x-y\Vert =\Vert \left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)-\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\Vert =\Vert \left(\begin{array}{c}{x}_1-y_1\\ x_2-y_2\end{array}\right){\Vert }_1=|x_1-y_1|+|x_2-y_2| \end{gathered}$$

Fonctions continues

• Toutes les fonctions polynomiales sont continues.
• Toutes les fractions rationnelles
  $\frac{f(x)}{g(x)},x\in {\mathbb{R}}^n$ sont continues partout ou
  $g(x)\ne 0$
• Si
  $f:{\mathbb{R}}^n\to {\mathbb{R}}^p$ continue,
  $g:{\mathbb{R}}^n\to {\mathbb{R}}^p$ continue,
  $\lambda ,\mu \in \mathbb{R}$ alors
  $\lambda f-\mu g$ continue.
• Si
  $p=1$,
  $fg$ continue,
  $\frac{f}{g}$ continue partout ou
  $g$ ne s'annule pas.
• Si
  $f:{\mathbb{R}}^n\to {\mathbb{R}}^p$ continue,
  $f:{\mathbb{R}}^p\to {\mathbb{R}}^n$ continue, alors
  $g\circ f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ continue

Exemple

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

Est-ce que

$x\mapsto f(x,0)$ et

$y\mapsto f(0,y)$ continues

$\Rightarrow$

$f$ continue ?
Bah non ca sera trop beau.

$$\begin{gathered} \underset{f\circ g(t)\text{ avec }g:t\mapsto (t,0)}{\underbrace{x\mapsto f(x,0)}} \\ \begin{array}{rl}f:{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto \{\begin{array}{ll}\frac{xy}{x^2+y^2}& (x,y)+(0,0)\\ 0& (x,y)=(0,0)\end{array}\end{array} \end{gathered}$$

• Si
  $g:t\to (t,0)$,
  $f\circ g(t)=0$
  $\mathrm{\forall }t\in \mathbb{R}$
• Si
  $g:t\to (0,t)$,
  $f\circ g(t)=0$
  $\mathrm{\forall }t\in \mathbb{R}$
• Si
  $g:t\to (t,t)$,

$$f\circ g(t)=\{\begin{array}{ll}\frac{1}{2}& t\ne 0\\ 0& t=0\end{array}\mathrm{\forall }t\in \mathbb{R}$$

Exercice 3.34

Rappel

$$\begin{gathered} \Vert x{\Vert }_1=\sum _{i=1}^n|x| \\ \Vert x{\Vert }_2=\sqrt{\sum _{i=1}^n{x}^2} \\ \Vert x{\Vert }_{\mathrm{\infty }}=\underset{i=1,..,n}{max}|x_i| \end{gathered}$$

$$\begin{gathered} \Vert x{\Vert }_1=\Vert x{\Vert }_{\mathrm{\infty }}+\sum |\underset{\ge 0}{\underbrace{\text{toutes les valeurs qui ne sont pas le max}}}| \\ \Vert x{\Vert }_{\mathrm{\infty }}\le \Vert x{\Vert }_1\le n\Vert x{\Vert }_{\mathrm{\infty }} \\ \begin{array}{rl}\Vert x{\Vert }_2\le \Vert x{\Vert }_1\Vert x{\Vert }_2^2& =\sum _{i=1}^n{x}_i^2=\sum _{i=1}^n|x_i{|}^2\\ \Vert x{\Vert }_1^2& =(\sum _{i=1}^n|x_i|{)}^2=\sum _{i=1}^n|x_i{|}^2+2\sum _{1\le i\le j\le n}|x_i||x_j|\end{array} \\ \begin{array}{rl}\Vert x{\Vert }_{\mathrm{\infty }}& =\underset{i}{max}|x_i|=|x_{\underset{\text{index ou le max est atteint}}{\underbrace{j}}}|\\ & =\sqrt{x_j^2}\\ \Vert x{\Vert }_2& =\sqrt{\sum _{i=1}^n{x}_i^2}\\ & =\sqrt{x_j^2+\underset{\ge 0}{\underbrace{\sum _{i\ne j}{x}_i^2}}}\\ & \ge \sqrt{x_j^2}\\ & \ge |x_j|\\ & \ge \Vert x{\Vert }_{\mathrm{\infty }}\end{array} \end{gathered}$$

$$\Vert \mathrm{\infty }\Vert \le \Vert x{\Vert }_2\le \Vert x{\Vert }_1\le n\Vert x{\Vert }_{\mathrm{\infty }}$$