Optimisation convexe

Un problème d'optimisation convexe consiste à minimiser une fonction objectif convexe sur un ensemble convexe, éventuellement avec des contraintes convexes :

où $$ et les $$ sont convexes, les $$ sont affines, et $$ est un ensemble convexe (souvent $$ ou un sous-espace).

La forme la plus courante en pratique :

avec $$ convexe et contraintes linéaires.

L'optimisation convexe est le cas « bien posé » de l'optimisation : il n'existe pas de minimum local piégé. Si vous trouvez un point où le gradient s'annule (sans contrainte) ou où les conditions KKT sont satisfaites (avec contraintes), vous avez le minimum global.

C'est pourquoi des problèmes aussi variés que les moindres carrés, la régularisation ridge, l'allocation mean-variance ou les SVMs reposent sur cette structure : on obtient des solutions fiables, souvent uniques, avec des algorithmes éprouvés.

Rappel des prérequis (voir Convexité et Dérivées, gradient et Hessienne) :

• intersection de contraintes convexes = domaine convexe ;
• somme de fonctions convexes = objectif convexe ;
• tout minimum local d'une fonction convexe sur un domaine convexe est global.

Conséquence pratique : pas besoin de multi-start agressif ni de heuristiques d'échappement pour éviter les minima locaux — la difficulté vient surtout de l'échelle, du conditionnement et du coût de calcul.

Si $$ est convexe et différentiable, un point $$ est optimal si et seulement si :

Pour un problème convexe avec contraintes qualifiées, les conditions de Karush-Kuhn-Tucker sont nécessaires et suffisantes :

Les multiplicateurs $$ mesurent le coût marginal d'une contrainte : augmenter légèrement la marge d'une contrainte active déplace l'optimum d'environ $$.

Dans le cas égalité seule ($$), on forme le Lagrangien :

L'optimum vérifie $$ et $$. Avec des inégalités, les multiplicateurs de Lagrange généralisent cette idée via les KKT.

À tout problème convexe (primal) est associé un problème dual, souvent plus simple à optimiser ou à interpréter :

• le dual fournit une borne inférieure sur l'optimum primal (faible dualité toujours vraie) ;
• sous dualité forte (Slater, contraintes qualifiées), optimum primal = optimum dual ;
• les multiplicateurs du dual sont les variables du problème dual.

Exemple classique : en SVM, le dual transforme un problème contraint en maximisation sur des multiplicateurs $$, avec une solution creuse (support vectors).

• Statistiques : MLE avec contraintes convexes, ridge/lasso, quantile regression (via reformulation LP).
• Machine learning : SVM, régression logistique (convexe en $$), régularisation.
• Finance : frontière efficiente, risk parity sous contraintes linéaires, optimisation robuste.
• Ingénierie : allocation de ressources, contrôle optimal discret convexe, calibration sous contraintes.

La page Descente de gradient détaille l'algorithme ; Newton et quasi-Newton restent à venir sur le hub Optimisation.