La convexité et pourquoi elle compte

Une vallée, une réponse

Une fonction est convexe si le segment qui joint deux points de son graphe est au-dessus du graphe ou sur lui : $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$ pour tout $\theta\in[0,1]$ . Pour une fonction deux fois dérivable il existe un test pratique : $f$ est convexe exactement quand sa hessienne est semi-définie positive partout, c'est-à-dire que toutes ses valeurs propres sont $\ge0$ . Les sommes de fonctions convexes, leurs multiples positifs et le maximum de fonctions convexes sont convexes, ce qui permet de construire de grands objectifs convexes à partir de petites pièces.

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

La convexité rend l'optimisation fiable. Tout minimum local est un minimum global, un gradient nul suffit pour s'arrêter, et la réponse ne dépend pas du point de départ du solveur. Si la fonction est strictement convexe, le minimiseur est en plus unique, et si elle est fortement convexe, avec une courbure d'au moins $\mu>0$ dans chaque direction, la descente de gradient converge à la vitesse géométrique vue plus haut. Sans convexité rien de cela n'est garanti : le solveur peut s'arrêter dans une vallée qui n'est pas la plus profonde.

Un test et un contre-exemplePour

f(x)=x^2

prenons les points

0

4

avec

\theta=\tfrac12

. La valeur au milieu est

f(2)=4

, alors que la moyenne des valeurs aux extrémités est

(0+16)/2=8

; l'écart de

4

est positif, comme l'exige la convexité. Prenons maintenant

f(x,y)=x^2+4xy+y^2

. Sa hessienne

\begin{pmatrix}2&4\\4&2\end{pmatrix}

a pour valeurs propres

6

-2

. L'une est négative, donc

f

n'est pas convexe : l'origine est un point selle.

En finance, les objectifs convexes comprennent la variance de portefeuille $\mathbf w^{T}\Sigma\mathbf w$ (une matrice de covariance est semi-définie positive), les pertes des moindres carrés, la norme $\ell_1$ $\lVert\mathbf w\rVert_1$ et l'expected shortfall (CVaR) en fonction des poids. La valeur à risque, un plafond sur le nombre de poids non nuls et le ratio de Sharpe tel quel ne sont pas convexes. Une matrice de covariance empirique estimée avec moins d'observations que d'actifs est semi-définie positive mais singulière : la variance est convexe sans être strictement convexe, et beaucoup de vecteurs de poids sont ex æquo pour le minimum.

Test de la hessienne : valeurs propres toutes $\ge0$ partout, convexe ; une valeur propre négative, non convexe.
Avantage : tout minimum local est global, donc le point de départ n'a pas d'importance.
Briques : sommes, multiples positifs et maxima de fonctions convexes restent convexes.

Relâcher ce qui n'est pas convexeQuand une exigence n'est pas convexe, comme au plus

k

poids non nuls, on la remplace souvent par une cousine convexe, ici la pénalité

\ell_1

. Le problème relâché se résout de façon fiable et donne en général une bonne réponse, mais c'est un autre problème : vérifiez le résultat par rapport à l'exigence d'origine avant de l'utiliser.

Lab : ce qui est noté

Un écart de convexité15 pts
La valeur propre qui casse la convexité15 pts
Quelle hessienne est convexe15 pts
Objectifs convexes en finance15 pts
Un gradient nul10 pts
Vocabulaire de la convexité15 pts
Pourquoi les solveurs aiment les problèmes convexes15 pts

Une vallée, une réponse

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

Un test et un contre-exemplePour

f(x)=x^2

prenons les points

0

4

avec

\theta=\tfrac12

. La valeur au milieu est

f(2)=4

, alors que la moyenne des valeurs aux extrémités est

(0+16)/2=8

; l'écart de

4

est positif, comme l'exige la convexité. Prenons maintenant

f(x,y)=x^2+4xy+y^2

. Sa hessienne

\begin{pmatrix}2&4\\4&2\end{pmatrix}

a pour valeurs propres

6

-2

. L'une est négative, donc

f

n'est pas convexe : l'origine est un point selle.

Test de la hessienne : valeurs propres toutes $\ge0$ partout, convexe ; une valeur propre négative, non convexe.
Avantage : tout minimum local est global, donc le point de départ n'a pas d'importance.
Briques : sommes, multiples positifs et maxima de fonctions convexes restent convexes.

Relâcher ce qui n'est pas convexeQuand une exigence n'est pas convexe, comme au plus

k

poids non nuls, on la remplace souvent par une cousine convexe, ici la pénalité

\ell_1

Lab : ce qui est noté

Un écart de convexité15 pts
La valeur propre qui casse la convexité15 pts
Quelle hessienne est convexe15 pts
Objectifs convexes en finance15 pts
Un gradient nul10 pts
Vocabulaire de la convexité15 pts
Pourquoi les solveurs aiment les problèmes convexes15 pts

La convexité et pourquoi elle compte

Une vallée, une réponse

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

La convexité et pourquoi elle compte

Une vallée, une réponse

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.