# 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$

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


$$
\begin{aligned}
(D) &= \{x\in\mathbb R^n, X_0+\lambda\vec u,\lambda\in\mathbb R\}\\
&= X_0+\{\lambda\vec u,\lambda\in\mathbb R\}\rightarrow\text{description parametrique}
\end{aligned}
$$


## Description implicite

:::info
**Description implicite**: ensemble des points qui verifient une certaine equation
:::

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

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

# Description de parties de $\mathbb R^n$
## Ecriture implicite
On se donne une fonction
$$
\begin{aligned}
f:\mathbb R^n&\to\mathbb R\\
x=\begin{pmatrix}
x_1\\
\vdots\\
x_n
\end{pmatrix}&\mapsto f(x)
\end{aligned}\\
\begin{aligned}
&\mathcal C_0=\{x\in\mathbb R^n\vert f(x)=0\}\\
&\mathcal C_x=\{x\in\mathbb R^n\vert \underbrace{f(x)=x}_{g(x)=f(x)-r, \mathcal C_r(f)=\mathcal C_0(g)}\}\text{ courbe de niveau }x
\end{aligned}
$$

Lieu de sous niveau
$$
\mathcal C_{\le r}(f)=\{x\in\mathbb R^n\vert f(x)\le r\}
$$

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


## Question 3-10
$$
\begin{aligned}
f:\mathbb R^2&\to\mathbb R\\
(x,y)&\mapsto x^2+y^2
\end{aligned}\\
\begin{aligned}
\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{aligned}
$$


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

:::warning
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\}
$$

:::

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

$$
\begin{aligned}
\mathcal C_0(g)&=\{(0,0)\}\\
\mathcal C_1(g)&=\{(x,y)\in\mathbb R^2 \text{ tel que } \underbrace{x^2+4y^2=1}_{(\frac{x}{1})^2+(\frac{y}{\frac{1}{2}})^2=1}\}\\
\mathcal C_2(g)&=\text{ de meme que }\mathcal C_1
\end{aligned}
$$

## Question 3-11
Surface definie apr les 2 branches d'une hyperbole $y\mapsto\frac{1}{x}$


$$
\{(x,y)\in\mathbb R^2, \underbrace{y=\frac{1}{x}}_{xy=1}\}\\
\begin{aligned}
g:\mathbb R^2&\to\mathbb R\\
(x,y)&\mapsto xy
\end{aligned}\\
y\le\frac{1}{x}\Leftrightarrow yx\le1
$$


:::success
Donc pour la decrire:

$$
\{(x,y)\in\mathbb R^2, xy\le1\}=\mathcal C_{\le1}(g)
$$
:::

## Ecriture parametrique
### Exemples
$$
\begin{aligned}
f:\mathbb R&\to\mathbb R\\
t&\mapsto f(t)
\end{aligned}\\
graph(f)\subset\mathbb R^2\\
\{(t,f(t)),t\in\mathbb R\}\rightarrow\text{ ecriture parametrique}
$$


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


### Definition
:::info
Soit
$$
\begin{aligned}
f:\mathbb R^n&\to\mathbb R\\
t&\mapsto f(t)
\end{aligned}\\
graph(f)=\{(t,f(t)),t\in\mathbb R^n\}
$$
:::

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


$$
y=f(x)\Leftrightarrow f(x)-y=0\\
graph(f)=\{(x,f(t)),x\in\mathbb R\}\\
\begin{aligned}
graph(f) &= \{(x,y),x\in\mathbb R,y=f(x)\}\\
&= \{(x,y), x\in\mathbb R\,\underbrace{f(x)-y}_{g(x,y)}=0\}\\
&=\{(x,y), g(x,y)=0\}=\mathcal C_0(g)
\end{aligned}
$$

## 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 ?*

:::danger
Si on prend 2 points quelconque de $A$ et qu'on trace ce segment, alors le segment est **inclut** dans $A$
:::


:::success
$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

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

:::danger
**A CONNAITRE**
:::info
**Definition**: Une partie $A\subseteq\mathbb R^n$ est convexe si, et seulement si
$$
\forall x,y\in A\\
\forall t\in[0;1]\\
tx+(1-t)y\in A
$$
:::

:::

### 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)$

:::info
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 $\forall\varepsilon\gt0, B(x,\varepsilon)\cap A\neq \emptyset$ $\to$ bord/frontiere $\delta A$

:::info
On appelle:
- adherence de $A$, $\bar A=A\cup \delta A$
- interieur de $A$, $\dot A=A \setminus\delta A$
:::

$$
A=[0;1[\to\begin{cases}
\delta A = \{\{0\};\{1\}\}\\
\bar A = [0;1]\\
\dot A = ]0;1[
\end{cases}
$$

## Hyperplan d'appui

:::info
$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.

:::

:::warning
$A$ admet un hyperplan d'appui de normale $\vec n$ en $x\in\delta A$ si, et seulement si,
$$
\forall y\in A, <y-x,n>\le0
$$


:::

## 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

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

## Fonction convexes

:::danger
**A CONNAITRE**
:::info
Une fonction $f:\mathbb R^n\to\mathbb R$ est convexe ssi:
- $Dom f$ est convexe
- $\forall x,y\in Dom f$, $\forall t\in[0;1]$
- $f(tx+(1-t)y\le tf(x)+(1-t)f(y))$


:::
:::

:::warning
$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}, \forall\alpha\in\mathbb R$
- $ax^2+bx+c$, $a\ge0$
- $-\log(x)=\log(\frac{1}{x})$
- $\sqrt{x}$
- $x^n$, $n$ pair


:::warning
La somme ponderee positivement de fonctions convexes est une fonction convexe

$$
f_{i_{i\ge 0}},i=1,...,N\text{convexes}\\
f=\sum_{i=1}^N\omega_if_i\\
$$
:::

### Demonstration
$$
Dom f=\cap Dom f_i\to\text{ convexe}
$$

Soit $x,y\in Dom f$ et $t\in[0;1]$

$$
\begin{aligned}
f(tx+(1-t)y)&=\sum_{i=1}^N\omega_i\underbrace{f_i(tx+(1-t)y)}_{\le tf_i(x)+(1-t)f_i(y)\text{ car } f \text{ convexe}}\\
&\le \sum_{i=1}^N\omega_itf_i(x) + \sum_{i=1}^N\omega_i(1-t)f_i(y)\\
&\le t\underbrace{\sum_{i=1}^N\omega_if_i(x)}_{f(x)} + (1-t)\underbrace{\sum_{i=1}^N\omega_if_i(y)}_{f(y)}\\
f(tx+(1-t)y)&\le tf(x)+(1-t)f(y)
\end{aligned}
$$
- $f=\max_{i=1,...,n}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: