OCVX - parties de

$\mathbb{R}$ et convexite

Rappels de la seance precedente

• description des sous espaces affine de
  ${\mathbb{R}}^n$
• sous espaces vectoriels de
  ${\mathbb{R}}^n$
  • $E\subset {\mathbb{R}}^n$
  • $0_{{\mathbb{R}}^n}\in E$
• Sous espace affine
  $A=x_0+E$,
  $E$ sous espace vectoriel et
  $x\in {\mathbb{R}}^n$

Un sous-espace affine n'est pas un sous-espace vectoriel.
Un sous-espace vectoriel est un sous-espace affine.

$$\begin{array}{rl}(D)& =\{x\in {\mathbb{R}}^n,X_0+\lambda \overrightarrow{u},\lambda \in \mathbb{R}\}\\ & =X_0+\{\lambda \overrightarrow{u},\lambda \in \mathbb{R}\}\to \text{description parametrique}\end{array}$$

Description implicite

Description implicite: ensemble des points qui verifient une certaine equation

$$\begin{array}{rl}(D)=dx\text{ tel que }<& x,n>=0\\ & x^{T}n=0\end{array}$$

$$\begin{gathered} \{x\text{ tel que }<x,n>=b\} \\ \text{si je sais que }{x}_0\in (D),<x_0,n>=b \\ \begin{array}{rl}\{x\text{ tel que }<x,n>=b=<x_0,n>& \}\\ <x,n>-<x_0,n>=0& \}\\ <x-x_0,n>=0& \}\end{array} \end{gathered}$$

Description de parties de

${\mathbb{R}}^n$

Ecriture implicite

On se donne une fonction

$$\begin{gathered} \begin{array}{rl}f:{\mathbb{R}}^n& \to \mathbb{R}\\ x=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)& \mapsto f(x)\end{array} \\ \begin{array}{rl}& {\mathcal{C}}_0=\{x\in {\mathbb{R}}^n|f(x)=0\}\\ & {\mathcal{C}}_x=\{x\in {\mathbb{R}}^n|\underset{g(x)=f(x)-r,{\mathcal{C}}_r(f)={\mathcal{C}}_0(g)}{\underbrace{f(x)=x}}\}\text{ courbe de niveau }x\end{array} \end{gathered}$$

Lieu de sous niveau

$${\mathcal{C}}_{\le r}(f)=\{x\in {\mathbb{R}}^n|f(x)\le r\}$$

Exemple

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

Question 3-10

$$\begin{gathered} \begin{array}{rl}f:{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto x^2+y^2\end{array} \\ \begin{array}{rl}{\mathcal{C}}_0(f)& =\{(0,0)\}\\ {\mathcal{C}}_1(f)& =\{(x,y)\in {\mathbb{R}}^2\text{ tel que }{x}^2+y^2=1\}\Rightarrow \text{ cercle de rayon }1\\ {\mathcal{C}}_2(f)& =\text{ cercle de rayon }\sqrt{2}\end{array} \end{gathered}$$

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

Equation d'une ellipse de demi grand axe

$a$ et demi petit axe

$b$

$$\{(x,y)\in {\mathbb{R}}^2\text{ tel que }(\frac{x}{a}{)}^2+(\frac{y}{b}{)}^2=1\}$$

$$\begin{gathered} a=b=r \\ (\frac{x}{a}{)}^2+(\frac{y}{b}{)}^2=1\iff x^2+y^2=r^2 \end{gathered}$$

$$\begin{array}{rl}{\mathcal{C}}_0(g)& =\{(0,0)\}\\ {\mathcal{C}}_1(g)& =\{(x,y)\in {\mathbb{R}}^2\text{ tel que }\underset{(\frac{x}{1}{)}^2+(\frac{y}{\frac{1}{2}}{)}^2=1}{\underbrace{x^2+4y^2=1}}\}\\ {\mathcal{C}}_2(g)& =\text{ de meme que }{\mathcal{C}}_1\end{array}$$

Question 3-11

Surface definie apr les 2 branches d'une hyperbole

$y\mapsto \frac{1}{x}$

$$\begin{gathered} \{(x,y)\in {\mathbb{R}}^2,\underset{xy=1}{\underbrace{y=\frac{1}{x}}}\} \\ \begin{array}{rl}g:{\mathbb{R}}^2& \to \mathbb{R}\\ (x,y)& \mapsto xy\end{array} \\ y\le \frac{1}{x}\iff yx\le 1 \end{gathered}$$

Donc pour la decrire:

$$\{(x,y)\in {\mathbb{R}}^2,xy\le 1\}={\mathcal{C}}_{\le 1}(g)$$

Ecriture parametrique

Exemples

$$\begin{gathered} \begin{array}{rl}f:\mathbb{R}& \to \mathbb{R}\\ t& \mapsto f(t)\end{array} \\ graph(f)\subset {\mathbb{R}}^2 \\ \{(t,f(t)),t\in \mathbb{R}\}\to \text{ ecriture parametrique} \end{gathered}$$

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

Definition

Soit

$$\begin{gathered} \begin{array}{rl}f:{\mathbb{R}}^n& \to \mathbb{R}\\ t& \mapsto f(t)\end{array} \\ graph(f)=\{(t,f(t)),t\in {\mathbb{R}}^n\} \end{gathered}$$

Avec une ecriture parametrique, on peut se ramener a une ecriture implicite

$$\begin{gathered} y=f(x)\iff f(x)-y=0 \\ graph(f)=\{(x,f(t)),x\in \mathbb{R}\} \\ \begin{array}{rl}graph(f)& =\{(x,y),x\in \mathbb{R},y=f(x)\}\\ & =\{(x,y),x\in \mathbb{R}\underset{g(x,y)}{\underbrace{f(x)-y}}=0\}\\ & =\{(x,y),g(x,y)=0\}={\mathcal{C}}_0(g)\end{array} \end{gathered}$$

Epigraphe (au-dessus du graphe) d'une fonction

$f$

$$Epi(f)=\{(x,t),t\ge f(x)\}$$

Convexite dans

${\mathbb{R}}^n$

Parties convexes de

${\mathbb{R}}^n$

On va dessiner des patates et des haricots

Quelle forme est convexe ?

Si on prend 2 points quelconque de

$A$ et qu'on trace ce segment, alors le segment est inclut dans

$A$

$A$ est convexe et

$B$ ne l'est pas.

Pour un segment entre

$x$ et

$y$, n'importe quel point de ce segments est une proportion du segment

$$\begin{gathered} tx+(1-t)y,t\in [0;1] \\ \begin{array}{rl}t& =0\to y\\ t& =1\to x\\ t& =\frac{1}{2}\to \text{milieu de }[x,y]\end{array} \end{gathered}$$

A CONNAITRE

Definition: Une partie

$A\subseteq {\mathbb{R}}^n$ est convexe si, et seulement si

$$\begin{gathered} \mathrm{\forall }x,y\in A \\ \mathrm{\forall }t\in [0;1] \\ tx+(1-t)y\in A \end{gathered}$$

:::

Proprietes

• tout intervall de
  $\mathbb{R}$ est convexe
• les sous espaces affines/les demi espaces sont convexes

On a

$A$ et

$B$ convexes

• $A\cap B\to$ convexe
• $A\cup B\to$ en general pas convexe

Enveloppe convexe d'une partie

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

Si on a une forme non-convexe, on "bouche les trous" pour rendre la forme convexe et on obtient

$conv(A)$

Intersection de tous les convexes qui

$\supseteq$

$A$.

• plus petit convexe qui
  $\supseteq$
  $A$

Soit

$A$ une partie de

${\mathbb{R}}^n$

$x$ un point du bord si

$\mathrm{\forall }\epsilon >0,B(x,\epsilon )\cap A\ne \mathrm{\varnothing }$

$\to$ bord/frontiere

$\delta A$

On appelle:

• adherence de
  $A$,
  $\overline{A}=A\cup \delta A$
• interieur de
  $A$,
  $\dot{A}=A\setminus \delta A$

$$A=[0;1[\to \{\begin{array}{l}\delta A=\{\{0\};\{1\}\}\\ \overline{A}=[0;1]\\ \dot{A}=]0;1[\end{array}$$

Hyperplan d'appui

$A$ admet un hyperplan d'appui en

$x\in \delta A$
Si on peut definir un hyperplan qui separe l'espace en deux demi espaces tels que

$A$ tombe integralement dans l'un des deux.

$A$ admet un hyperplan d'appui de normale

$\overrightarrow{n}$ en

$x\in \delta A$ si, et seulement si,

$$\mathrm{\forall }y\in A,<y-x,n>\le 0$$

Question 3-20

• N’ayant pas d’hyperplan d’appui en un point donné de son bord:

Haricots

$\to$ pas d'hyperplan d'appui en certains points de son bord.

• Ayant plus d’un hyperplan d’appui en un même point: il faut un angle

Point anguleux

$\to$ plusieurs hyperplan d'appuis en ce point la

• N’ayant aucun hyperplan d’appui:

Pas d'hyperplan d'appui pour tous les points de bord.

• Ayant un hyperplan d'appui en tous les points de son bord:

Pour tous les convexes

Une partie est convexe ssi on peut definir un hyperplan d'appui en tout point de son bord.

Fonction convexes

A CONNAITRE

Une fonction

$f:{\mathbb{R}}^n\to \mathbb{R}$ est convexe ssi:

• $Domf$ est convexe
• $\mathrm{\forall }x,y\in Domf$,
  $\mathrm{\forall }t\in [0;1]$
  • $f(tx+(1-t)y\le tf(x)+(1-t)f(y))$

:::

$f$ concave si

$-f$ convexe.

Les droites affines sont les seules fonctions concaves ET convexes

Petit bestiaire de fonctions convexes:

• $ax+b$
• $e^{\alpha x},\mathrm{\forall }\alpha \in \mathbb{R}$
• $a{x}^2+bx+c$,
  $a\ge 0$
• $-\log (x)=\log (\frac{1}{x})$
• $\sqrt{x}$
• $x^n$,
  $n$ pair

La somme ponderee positivement de fonctions convexes est une fonction convexe

$$\begin{gathered} f_{i_{i\ge 0}},i=1,...,N\text{convexes} \\ f=\sum _{i=1}^N{\omega }_i{f}_i \end{gathered}$$

Demonstration

$$Domf=\cap Dom{f}_i\to \text{ convexe}$$

Soit

$x,y\in Domf$ et

$t\in [0;1]$

$$\begin{array}{rl}f(tx+(1-t)y)& =\sum _{i=1}^N{\omega }_i\underset{\le t{f}_i(x)+(1-t)f_i(y)\text{ car }f\text{ convexe}}{\underbrace{f_i(tx+(1-t)y)}}\\ & \le \sum _{i=1}^N{\omega }_{i}t{f}_i(x)+\sum _{i=1}^N{\omega }_i(1-t)f_i(y)\\ & \le t\underset{f(x)}{\underbrace{\sum _{i=1}^N{\omega }_i{f}_i(x)}}+(1-t)\underset{f(y)}{\underbrace{\sum _{i=1}^N{\omega }_i{f}_i(y)}}\\ f(tx+(1-t)y)& \le tf(x)+(1-t)f(y)\end{array}$$

• $f=\underset{i=1,...,n}{max}{f}_i$ est convexe
• la composition d'une fonction convexe
  $f$ avec
  $g$ affine croissant
  $g\circ f$ est convexe

Lien entre partie convexe et fonction convexe:

• L'epigraphe d'une fonction convexe est une partie convexe

• Tous les lieux de sous niveaux d'une fonction convexe sont des parties convexes

En dimension 1: