Skip to content
Retour aux résultats

Optimisation convexe

Introduite par
Stephen Boyd & Lieven Vandenberghe
Année
2004
Type
Mathematical optimization framework
Famille
Mathematical programming

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

L'optimisation convexe est un sous-domaine de l'optimisation mathématique qui étudie le problème de la minimisation de fonctions convexes sur des ensembles convexes.

Formalisé et popularisé par Stephen Boyd et Lieven Vandenberghe dans leur livre de référence de 2004, ce cadre unifie une large famille de problèmes — y compris la programmation linéaire, la programmation quadratique, la programmation semi-définie et la programmation conique du second ordre — sous un même toit théorique. Sa propriété distinctive est que toute solution localement optimale est également globalement optimale, ce qui la rend traitable et fiable pour l'ingénierie, les statistiques, l'apprentissage automatique et la recherche opérationnelle.

L’intuition derrière la méthode

Imaginez une vallée en forme de bol : peu importe où vous commencez à faire rouler une balle, elle finira toujours par atteindre le même point le plus bas. L'optimisation convexe formalise cette géométrie mathématiquement. La fonction objectif est le bol, la région réalisable est un terrain de forme convexe, et l'algorithme est la balle qui suit la pente. Parce qu'il n'y a pas de creux locaux cachés ni de crêtes trompeuses, vous êtes assuré de trouver le véritable minimum global — ce qui rend l'approche fondamentalement différente et plus fiable que l'optimisation non linéaire générale.

Histoire

Les fondements théoriques de l'analyse convexe remontent aux travaux de Minkowski et Farkas au début du XXe siècle, la programmation linéaire émergeant dans les années 1940 avec Dantzig. Les méthodes de points intérieurs, introduites par Karmarkar en 1984 et affinées dans les années 1990, ont rendu les programmes convexes généraux calculatoirement traitables. Le manuel de Boyd et Vandenberghe de 2004 publié par Cambridge University Press, librement disponible en ligne, a synthétisé des décennies de résultats dans un cadre cohérent et accessible et a engendré le paradigme de la programmation convexe disciplinée implémenté dans CVX, CVXPY et les outils associés.

Quand l’utiliser

Utilisez l'optimisation convexe lorsque l'objectif et toutes les contraintes peuvent être exprimés ou reformulés comme des fonctions convexes. Elle est appropriée pour l'optimisation de portefeuille, la régression avec régularisation, les flux de réseau, les machines à vecteurs de support et la conception de contrôle. Les hypothèses clés sont la convexité de l'ensemble réalisable et de l'objectif ; les violer supprime la garantie d'optimalité globale. Lorsque le problème est non convexe, envisagez des relaxations convexes ou des solveurs non linéaires locaux. Préférez les solveurs de programmation linéaire lorsque le problème est linéaire pour une efficacité accrue.

Limites et points d’attention

  • L'applicabilité dépend entièrement de la possibilité de poser ou d'approximer le problème sous forme convexe ; de nombreux problèmes du monde réel sont intrinsèquement non convexes.
  • Les méthodes de points intérieurs stockent et factorisent de grandes matrices, rendant les exigences de mémoire et de temps substantielles pour des problèmes de très haute dimension.
  • Les relaxations convexes de problèmes combinatoires ou entiers peuvent produire des solutions fractionnaires qui ne sont pas directement exploitables sans heuristiques d'arrondi.
  • La modélisation de problèmes nécessite une expertise : une assertion de convexité incorrecte supprime silencieusement les garanties théoriques tandis que le solveur renvoie toujours une réponse.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Garantit une solution globalement optimale chaque fois qu'une formulation convexe est réalisable — aucun risque de convergence vers un minimum local.
  • Résoluble en temps polynomial via des méthodes de points intérieurs, offrant une efficacité pratique même pour des problèmes à grande échelle.
  • La théorie de la dualité fournit des certificats d'optimalité, des variables duales avec des interprétations économiques et une analyse de sensibilité sans coût supplémentaire.
  • Une riche règle de composition (DCP) permet une vérification systématique de la convexité et une transformation automatique en forme prête pour le solveur.

Applications

  • Optimisation de portefeuille : minimisation de la variance ou du CVaR sous des objectifs de rendement et des contraintes d'allocation en finance quantitative.
  • Apprentissage automatique : l'entraînement des machines à vecteurs de support, la régression lasso et ridge, et la régression logistique sont des programmes convexes canoniques.
  • Traitement du signal et de l'image : la compression de données (compressed sensing), le débruitage par variation totale et la récupération parcimonieuse sont formulés comme des programmes convexes.
  • Allocation de réseau et de ressources : routage optimal, contrôle de puissance dans les réseaux sans fil et allocation de bande passante sous contraintes de capacité.
  • Systèmes de contrôle : synthèse de contrôleurs H-infini basée sur la programmation semi-définie et vérification de la stabilité de Lyapunov.

Comment ça marche

Comment ça marche

1

L'analyste formule le problème de décision comme un programme convexe de forme standard : minimiser une fonction objectif convexe f0(x) sous contrainte d'inégalités convexes fi(x) ≤ 0 et d'égalités affines Ax = b. Obtenir la bonne formulation — choisir la bonne représentation des variables et exprimer toutes les contraintes sous forme convexe — est la première étape critique qui détermine si les garanties puissantes s'appliquent.

Formule
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = b
2

Avant la résolution, chaque fonction du problème est vérifiée comme étant convexe, ce qui signifie que son épigraphe est un ensemble convexe ou, de manière équivalente, qu'elle satisfait l'inégalité du point milieu. La règle de composition de la programmation convexe disciplinée (DCP) de Boyd et Vandenberghe fournit un moyen systématique de confirmer la convexité par des règles de composition, de sorte que les analystes n'ont pas besoin de prouver la convexité à partir de zéro pour chaque problème.

Formule
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]
3

Le Lagrangien L(x, λ, ν) est formé en relâchant les contraintes avec des multiplicateurs duaux. Sous la qualification de contrainte de Slater, la dualité forte est vérifiée : les optima primaux et duaux coïncident et les conditions KKT — stationnarité, réalisabilité primale/duale et holgure complémentaire — sont à la fois nécessaires et suffisantes pour l'optimalité globale. La dualité fournit également des certificats d'optimalité et des informations de sensibilité sur la façon dont l'optimum change avec les données du problème.

Formule
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0
4

Les méthodes de points intérieurs, les variantes de descente de gradient ou les algorithmes proximaux se déplacent itérativement à travers l'ensemble réalisable vers l'optimum. Pour les problèmes lisses sans contrainte, les étapes de gradient avec des tailles d'étape appropriées convergent à des taux connus. Pour les problèmes contraints ou structurés, les méthodes de points intérieurs atteignent une convergence en temps polynomial avec une haute précision, et les méthodes de premier ordre telles que ADMM s'adaptent à des instances très volumineuses.

Formule
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0

Pièges courants

  • Supposer qu'un problème est convexe sans vérification formelle — les règles de composition doivent être vérifiées rigoureusement, et non par inspection visuelle de l'objectif.
  • Négliger le conditionnement numérique : des problèmes mal mis à l'échelle font que les solveurs signalent des solutions inexactes ou irréalisables malgré la faisabilité théorique.
  • Ignorer les écarts de dualité dans les solveurs non standard ou les contextes où la condition de Slater échoue, ce qui peut invalider les affirmations d'optimalité basées sur KKT.
  • Traiter la solution de relaxation convexe comme la solution du problème d'origine lorsque des contraintes entières ou combinatoires ont été supprimées lors de la reformulation.

Questions fréquentes

Comment savoir si mon problème est convexe ?

Vérifiez si la fonction objectif et chaque fonction de contrainte satisfont l'inégalité de convexité du point milieu, ou vérifiez la convexité en utilisant la règle de composition de la programmation convexe disciplinée. Si chaque fonction est construite à partir de primitives convexes connues combinées selon des règles de composition préservant la convexité (fonction externe convexe non décroissante, fonctions internes convexes, etc.), le problème est convexe. Le chapitre 3 de Boyd et Vandenberghe fournit un catalogue exhaustif de fonctions convexes.

Quelle est la différence entre l'optimisation convexe et la programmation linéaire ?

La programmation linéaire est un cas particulier d'optimisation convexe où la fonction objectif et toutes les contraintes sont des fonctions affines (linéaires). L'optimisation convexe est beaucoup plus générale, englobant les programmes quadratiques, coniques du second ordre et semi-définis. Alors que les méthodes du simplexe et des points intérieurs résolvent les programmes linéaires, seules les méthodes de points intérieurs s'étendent directement à la classe convexe complète.

L'optimisation convexe peut-elle gérer des variables entières ou binaires ?

Pas directement — les contraintes entières rendent un problème combinatoirement difficile et généralement non convexe. Une approche courante consiste à résoudre la relaxation convexe (en ignorant l'intégralité) pour obtenir une borne inférieure, puis à appliquer une méthode de branchement et bornes (branch-and-bound) ou d'arrondi. Les solveurs de programmation mixte entière convexe combinent ces idées, mais la garantie d'optimalité globale de l'optimisation convexe pure ne s'applique plus en pleine généralité.

Méthodes associées

Sources

  1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

    ISBN : 978-0-521-83378-3
    Copié.