# OCVX

# Introduction
L’optimisation fait partie des missions historiques de l’ingénierie. Elle naît avec l’ère industrielle: une fois un concept élaboré il s’agit de réduire les coups, minimiser les risques de défauts de livraisons ou étendre le scope d’action ...

Les techniques mathématiques qui permettent de résoudre une partie de ces problèmes d’optimisation balayent un large spectre des thématiques mathématiques que vous avez pu aborder jusque là; l’algèbre linéaire, le calcul différentielle et un peu de géométrie. Le cours d’OCVX a pour objectif de vous donner le bon degré de confort pour manipuler ces techniques.

## De quoi on parle ?
Voici quelques exemples qu’on pourrait croiser lorsqu’on s’intéresse à l’optimisation.
- Chercher le plus court/rapide chemin entre deux coordonnées GPS.
- Décider des meilleures routes aériennes qui minimisent le prix d’approvisionnement en kérosène.
- Identifier des images d’IRM qui correspondent à des malformations du cerveau.
- Chercher des patterns dans la population d’étudiants intégrants Epita
- Décider d’achat/vente d’assets prenant en compte l’historique disponible.

# Probleme d'optimisation
## Definition formelle
On écrit en général un problème d’optimisation $(P)$ sous la forme standard

$$
\begin{aligned}
&\text{minimiser} &f_0(x) &\\
&\text{sujet a } &f_i(x)\le0, &\forall i\in\{1,...,p\}\\
& &h_j(x)=0, &\forall i\in\{1,...,m\}
\end{aligned}
$$

où $f_0$, les $f_i$ et les $h_j$ sont des applications de $\mathbb R^n$ vers R. La fonction $f_0$ est dite _**fonction objectif**_ ; suivant le contexte ce sera une fonction de _**coût**_ ou _**d’erreur**_. Les inégalités sont qualifiées de _**contraintes d’inégalités**_ et les égalités de _**contraintes d’égalités**_.

:::warning
**Tentative**
Vous pouvez chercher à formuler les problèmes énumérés sous forme d’un problème d’optimisation, ce n’est pas toujours évident.
:::

Un probleme d'optimisation du type de $(P)$ est dit
- differentiable si toutes les fonctions en jeux le sont;
- _**non-contraint**_ s'il n'a aucune contraintes d'inegalites ou egalites
- _**convexe**_ si l'ensemble des fonctions en jeu sont convexes, les contraintes d'egalites etant de plus affines

Sous la première hypothèse on a une série d’outils mathématiques qui nous permettront d’apporter un éclairage riche sur $(P)$. Si l’on rajoute la seconde on est en mesure de construire des procédés itératifs efficaces en état de *résoudre* ces problèmes. La dernière nous garantie de trouver *la* solution optimale.

:::danger
**Fake news**
Les éléments en italiques sont là pour marquer le fait que nos assertions à ce stade sont encore un peu fausses. L’image est un peu moins idyllique.
:::

## Lexique
Étant donné un problème d’optimisation $(P)$ on appelle:
- _**point admissible**_ de $(P)$ tout point de $R^n$ satisfaisant toutes les contraintes. L’ensemble de tous les points admissibles est appelé **lieu admissible** de $(P)$.
- _**valeur objectif**_ d’un point admissible la valeur que prend la fonction objectif en celui-ci.
- _**valeur optimale**_ de $(P)$ la meilleure borne inférieure sur la fonction objectif.
- _**point optimal**_ de $(P)$ tout point admissible dont la valeur objectif est la valeur optimale.

## Premieres remarques qualitatives
Comme est le cas de tout système d’équations, il est utile de se poser le type de questions suivantes:
- y a-t-il au moins une solution?
- s’il y a au moins une solution combien?
- peut-on toujours décrire l’ensemble des solutions?
- y a-t-il moyen d’approcher des solutions?

:::warning
**Question**
Chercher un problème d’optimisation qui:
- a un lieu admissible est vide;
- a plus d’un seul point optimal;
- n’a pas de valeur optimale mais a un lieu admissible non vide \;
- a une valeur optimale mais pas de point optimal.
:::

# Cadre de la premiere UE d'OCVX
## Contours du cours
On se limite au cours du premier semestre de majeure au cas des problèmes d’optimisations **_sans contraintes_**.
- C’est un cadre suffisant pour les premières applications des techniques d’optimisations à un premier niveau de ML ; il recouvre le cas des différentes régressions, de l’entraînement d’un réseau de neurones ainsi que les cas des algos de classification standards
- Il représente un premier niveau à atteindre qui permet de fixer votre attitude vis-à-vis d’un problème d’optimisation, sans s’encombrer de concepts plus abstraits à concevoir.
- Il ne recouvre pas le cas des Support Vector Machines

# Regression mon amie
## Map Fitting
:::info
Une famille différentiable d’applications $f_{\alpha} : \mathbb R^n \to \mathbb R$ indexées par $\alpha\in \mathbb R^k$ est une famille de fonctions pour laquelle l’application $\phi : \mathbb R^k \times\mathbb R^n → \mathbb R$ qui envoie $(\alpha, x)$ sur $f_{\alpha}(x)$ est différentiable.

:::

:::danger
On considère un ensemble de couples $(X_i, y_i) \in\mathbb R^n \times\mathbb R$ pour $i \in \{1, . . . , p\}$ et une famille différentiable d’applications $\{f_{\alpha}\},\alpha\in\mathbb R^k$ . Le problème de *map fitting* relatif aux données précédentes consiste à trouver les meilleurs paramètres $\alpha^*$ tels que $f_{\alpha^*}$ approche au mieux *(pour une métrique pré-choisie)* a les $(X_i, y_i)$.

:::

## La regression lineaire
Le plus simple des problèmes de *map fitting* est celui de la régression linéaire. Dans le cas de dimension 1 (on cherche à approcher une fonction de $\mathbb R$ dans $\mathbb R$) il se décline comme ceci:
- la famille différentiable à laquelle on s’intéresse est indexées par $\mathbb R^2$: $f_{\alpha}(x)=\alpha_1x+\alpha_0$ pour $\alpha=(\alpha_0,\alpha_1)$
- la métrique standard utilisée est la _**MSE**_ pour _**Mean Square Error**_ donnée pour un $f_{\alpha}$ par

$$
\mathcal E(\alpha) = \sum_{i=1}^p\frac{1}{p}(f_{\alpha}(x_i)-y_i)^2
$$

c’est une estimation moyenne de la variance des prédictions de $f_{\alpha}$

:::success
Le but est de trouver un paramètre $\alpha=(\alpha_0,\alpha_1)$ tel que $\mathcal E(\alpha)$ est minimal, autrement dit de résoudre le problème d’optimisation sans contraintes **minimiser $\mathcal E(\alpha)$**.
:::

Le problème de régression linéaire a une solution _**analytique**_; càd une solution donnée par une expression explicite en fonction des entrées.

Cette solution implique cependant l’inversion d’une matrice de taille équivalent à celle des données en entrée. Chose particulièrement coûteuse.

# Empathie machine
## Approximation séquentielle

Il est rare qu’un problème d’optimisation ait une solution analytique. Même quand cela est le cas il est souvent plus efficace de chercher une solution approchée.

Un processus itératif qui résout un problème d’optimisation $(P)$ est
1. un choix initial d’un point de départ (de préférence) admissible $x_0$ ;
2. un processus itératif qui construit un point admissible $x_{n+1}$ à partir de $x_n$ et de données locales ayant une valeur objectif plus petite que celle de $x_n$.

Cette démarche ne nous offre en général qu’une approximation d’une solution. Elle a cependant l’avantage de pouvoir se dérouler en temps raisonnable. Il faut par ailleurs prendre en compte que l’implémentation des flottants en machines nous contraint déjà à approcher les grandeurs qu’on manipule.

# Acquis d'apprentissages vises (AAVs)
- _**Savoirs**_
- Identifier les éléments composants un problème d’optimisation et des éléments nécessaires à son étude qualitative
- Cartographier les outils à disposition pour résoudre un problème d’optimisation et les hyperparamètres qui déclinent et gouvernent ceux-ci.
- Décrire le domaine de validité d’un algorithme.
- _**Savoir-faire**_
- Implémenter des algorithmes standards d’optimisation sans contraintes
- Effectuer des analyses comparatives entre des différentes algorithmes d’optimisation sans contraintes
- Reconnaître les problèmes liés aux approximations numériques qui apparaissent dans toute implémentation.
- _**Attitude**_ - Analyse de risque
- Vivre par le moto : _**Un**_ test n’est pas une _**statistique**_ et une _**statistique**_ ne vient pas sans _**variabilité**_.

# Contenus notionnels
1. Pré-requis techniques
- Des éléments de géométries
- Interprétation géométrique du produit scalaire
- Courbes de niveau et epigraphes de fonctions.
- Parties et fonctions convexese en dimension finie.
- Des éléments de topologie
- Comment calculer des distances et définir des voisinanges dans $\mathbb R^n$
- Approcher et comparer des fonctions à plusieurs variables.
- Des éléments de calcul différentiel
- Approcher localement une fonction multivariées par une fonction affine.
- Écriture en base ; jacobienne et gradient.
- Interprétation géométrique du gradient
- Approximation locale de second ordre : la hessienne
2. Étude qualitative des problèmes d’optimisation.
- Le lieu critique d’une fonction objectif.
- Apport de la convexité au contexte de l’optimisation.
- Études du cas quadratique.
3. Méthodes de résolutions itératives.
- Descentes de gradients et Méthodes de Newton

# Evaluation
Deux modes d’évaluations vont intéragir dans le cadre de ce cours
1. Des évaluations formatives via moodle, ce qui est suffisant pour garantir le fait que vous consacrez suffisamment de temps à comprendre les éléments de cours et l’assimiler. Une évaluation formative est notée de manière binaire : 0% de la note si l’étudiant n’y participe pas sérieusement et 100% sinon.
2. Des évaluations sommatives comptabilisées de manière classique. Elle seront composées
- d’une évaluation intermédiaire qui prendra la forme d’un devoir sur table, celui-ci vise à garantir votre capacité à formuler un raisonnement géométrique / différentiel concernant les problématiques d’optimisation
- d’une évaluation TP afin d’avoir un regard sur l’ensemble des éléments que vous aurez pu mobiliser pour atteindre les objectifs de cours.

Les évaluations formatives comptent pour 20% de la note finale. On attend de vous de faire preuve _**d’autonomie**_ lors du suivi de ce cours.

# Moodle
L’ensemble des contenus de cours, d’annonces, de bibliographies de travail à rendre et des tests d’évaluation seront disponibles sur un cours moodle auquels vous serez inscrit bientôt.