Optimisation convexe

Trouver un point meilleur que ses voisins ne prouve généralement pas qu’il est le meilleur de tous. L’optimisation convexe étudie des problèmes où l’optimalité locale implique l’optimalité globale. Commencez par :

1. ensembles et fonctions convexes ;
2. formes standard des problèmes et transformations ;
3. conditions d'optimalité ;
4. dualité lagrangienne ;
5. méthodes du premier et du second ordre ;
6. applications en statistique et en apprentissage automatique.

Stanford EE364A et le livre Convex Optimization de Boyd et Vandenberghe fournissent le cours complet et les démonstrations.

Vocabulaire minimal

Cette carte présente les hypothèses des garanties globales ; le traitement complet de la dualité et des algorithmes reste dans Boyd et Vandenberghe, chapitres 2–5 et 9.

Un ensemble $C$ est convexe si le segment $(1-t)x+ty$ reste dans $C$ pour tous $x,y\in C$ et $0\le t\le1$. Une fonction est convexe sur un domaine convexe si

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

Son graphe est sous ses cordes. La stricte convexité impose une inégalité stricte pour des points distincts et $0<t<1$ ; elle implique au plus un minimiseur, pas son existence. Par exemple, $e^x$ est strictement convexe sur $\mathbb R$ mais n’a pas de minimiseur, seulement l’infimum zéro.

Pour une fonction convexe différentiable, l’inégalité du plan d’appui est

$$f(y)\ge f(x)+\nabla f(x)^T(y-x).$$

Un point stationnaire sans contrainte est donc un minimum global. Pour un point admissible $x_*\in C$ dans un ensemble convexe $C$, la condition $\nabla f(x_*)^T(y-x_*)\ge0$ pour tout $y\in C$ est nécessaire et suffisante. Pour $f(x)=x$ sur $[0,1]$, $x_*=0$ la satisfait malgré $f'(0)=1$. Tout minimum local d’un problème convexe est global : si un meilleur point admissible existait, des points arbitrairement proches sur le segment l’y reliant amélioreraient l’objectif, contredisant la minimalité locale.

Un problème convexe standard minimise un objectif convexe sous des inégalités convexes $g_i(x)\le0$ et des égalités affines $Ax=b$. Un objectif convexe sur un ensemble admissible non convexe ne suffit pas. Minimiser $x^2$ sur $\{-1,2\}$ fait ainsi de $2$ un minimum local non global, car ce point est isolé.

Pour une fonction deux fois continûment différentiable sur un domaine ouvert convexe, la convexité équivaut à une Hessienne semi-définie positive. Le guide du gradient et de la courbure définit la Hessienne et la définition positive par les dérivées secondes et les formes quadratiques. Pour les moindres carrés, $H=2X^TX/n\succeq0$ ; le rang colonne plein donne une Hessienne définie positive et une solution unique. La convexité seule n’assure pas la convergence de pas de gradient arbitraires : régularité et taille du pas restent importantes.

Rôle de la dualité

Le lagrangien est $\mathcal L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\nu^T(Ax-b)$, avec $\lambda_i\ge0$. Prendre $\inf_x\mathcal L$ fournit une borne inférieure du minimum primal ; maximiser cette borne constitue le problème dual. Une valeur primale admissible et une borne duale donnent un écart d’optimalité, contrairement à une faible variation des itérés.

Les conditions de Karush–Kuhn–Tucker combinent admissibilité primale, admissibilité duale, stationnarité du lagrangien et complémentarité $\lambda_i g_i(x)=0$. Pour des problèmes convexes différentiables, elles suffisent à garantir l’optimalité globale lorsqu’elles sont satisfaites. Leur nécessité et un écart de dualité nul exigent une régularité adaptée, telle la condition de Slater : un point admissible dans l’intérieur relatif du domaine satisfait strictement les inégalités. Ces garanties ne s’appliquent pas sans hypothèses à n’importe quel problème contraint ou neuronal.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.