Optimisation convexe — concepts, méthodes et applications

L’optimisation convexe consiste à minimiser une fonction convexe sur un ensemble admissible convexe. La raison principale de son importance est simple : si ces conditions de convexité sont vérifiées, tout minimum local est aussi un minimum global.

Cette garantie rend ces problèmes bien plus fiables que les problèmes d’optimisation généraux. Il faut toujours modéliser correctement le problème, mais une fois le modèle convexe, on ne cherche pas une solution qui n’est optimale que dans un petit voisinage.

Une forme courante est

$$\text{minimize } f(x)$$

sous les contraintes

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

où $f$ et chaque $g_i$ sont convexes, et les contraintes d’égalité sont affines. Dans ces conditions, l’ensemble admissible est convexe et le problème d’optimisation est convexe.

Définition de l’optimisation convexe

Une fonction $f$ est convexe si, pour tous points $x$ et $y$ de son domaine et tout $0 \le t \le 1$,

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

En langage simple, le segment reliant deux points du graphe se situe au-dessus du graphe. En une variable, beaucoup de fonctions convexes ont une forme de bol, mais c’est bien l’inégalité qui constitue le vrai critère.

Un ensemble est convexe si, dès qu’il contient deux points, il contient aussi tous les points du segment de droite qui les relie.

Il faut les deux éléments :

• une fonction objectif convexe
• un ensemble admissible convexe

Si l’un des deux manque, le problème peut cesser d’être convexe.

Pourquoi l’optimisation convexe est plus facile à analyser

L’optimisation est souvent difficile parce qu’il peut y avoir de nombreuses vallées. Un algorithme peut continuer à améliorer la fonction objectif et pourtant s’arrêter en un point qui n’est optimal que localement.

L’optimisation convexe élimine précisément ce mode d’échec. Si la fonction objectif est convexe et la région admissible est convexe, alors un point qu’on ne peut plus améliorer localement est déjà globalement optimal. C’est pourquoi les problèmes convexes sont importants en statistique, en apprentissage automatique, en automatique et en recherche opérationnelle.

Cela ne veut pas dire que tout problème convexe est facile. Certains restent de grande taille ou coûteux en calcul. Cela signifie que la structure est suffisamment propre pour que de bons algorithmes puissent viser le véritable optimum au lieu de se laisser piéger par un comportement local trompeur.

Exemple d’optimisation convexe résolu

Considérons le problème sans contrainte

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

C’est un problème d’optimisation convexe parce que $f(x)$ est un polynôme du second degré dont le coefficient dominant est positif ; elle est donc convexe sur tous les réels.

Pour trouver le minimiseur, on dérive :

$$f'(x) = 2(x-3).$$

On pose la dérivée égale à zéro :

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

On évalue maintenant la fonction objectif :

$$f(3) = (3-3)^2 + 2 = 2.$$

La valeur minimale est donc $2$, atteinte pour $x=3$.

Cet exemple est simple, mais il montre l’idée principale. Une fois arrivé à $x=3$, il n’existe pas de vallée plus basse cachée ailleurs.

Méthodes courantes en optimisation convexe

La méthode dépend de la structure du problème.

Pour les problèmes lisses sans contrainte ou avec des contraintes simples, les méthodes à base de gradient sont courantes, car se déplacer dans la direction opposée au gradient peut réduire la fonction objectif.

Pour de nombreux problèmes convexes avec contraintes, les méthodes de point intérieur sont largement utilisées, car elles traitent directement les contraintes et donnent souvent de bonnes performances en pratique.

Pour les problèmes convexes non lisses, les méthodes de sous-gradient ou les méthodes proximales peuvent être plus adaptées. L’idée importante n’est pas la liste des algorithmes. C’est la garantie qu’offre la structure convexe, qui donne à ces algorithmes un cadre stable pour travailler.

Erreurs fréquentes en optimisation convexe

Supposer qu’un graphique prouve la convexité

Un graphe peut sembler avoir une forme de bol sur une figure et pourtant ne pas être convexe sur tout le domaine ou en dimension supérieure. La définition ou les règles standard de convexité comptent davantage qu’un simple croquis.

Oublier que les contraintes comptent

Une fonction objectif convexe ne suffit pas à elle seule. Si l’ensemble admissible n’est pas convexe, alors le problème global n’est pas un problème d’optimisation convexe.

Considérer tout point critique comme un minimum

Pour une fonction convexe différentiable, un point où le gradient est nul est un minimiseur global. Sans convexité, cette conclusion n’est généralement pas valable.

Confondre convexe et strictement convexe

La stricte convexité est une propriété plus forte. Elle donne souvent un minimiseur unique, alors que la simple convexité ne garantit pas toujours l’unicité.

Où l’optimisation convexe est utilisée

L’optimisation convexe apparaît chaque fois qu’un problème réel peut être modélisé avec des coûts convexes et des contraintes convexes.

Parmi les exemples courants, on trouve l’ajustement aux moindres carrés, les machines à vecteurs de support, la sélection de portefeuille sous des modèles de risque convexes et de nombreux problèmes d’allocation de ressources. Le modèle exact compte : une application n’est convexe que si la fonction objectif choisie et les contraintes satisfont réellement les hypothèses de convexité.

Quand la convexité aide en pratique

L’optimisation convexe est particulièrement utile quand on a besoin de plus qu’un simple nombre. On veut souvent une garantie que la réponse est réellement optimale pour le modèle que l’on a écrit.

Cette garantie est importante en ingénierie et dans le travail sur les données, car elle permet de séparer deux questions :

1. Avons-nous correctement résolu le problème mathématique ?
2. Le problème mathématique était-il un bon modèle de la réalité ?

La convexité aide beaucoup pour la première question. Elle ne résout pas automatiquement la seconde.

Essayez un problème similaire

Prenez $f(x) = (x+1)^2 + 5$ et trouvez son minimum. Comparez ensuite avec $f(x) = -(x+1)^2 + 5$, qui est concave et non convexe. Cette comparaison côte à côte rend le rôle de la convexité beaucoup plus clair.

Si vous voulez explorer un autre cas, essayez de mettre en place un petit problème de moindres carrés et voyez comment la minimisation d’une fonction d’erreur convexe conduit à un meilleur ajustement stable.