Un cadre d'optimisation où la fonction objectif est convexe et l'ensemble faisable est convexe, garantissant que tout minimum local est un minimum global et permettant des méthodes de résolution efficaces.

Principe

Exploiter la convexité pour assurer que les segments entre points faisables restent faisables et que les objectifs convexes n'ont pas de minima locaux distincts du minimum global ; utiliser la dualité et l'analyse convexe pour les algorithmes et certificats.

Démonstration

Minimiser un quadratique convexe soumis à des contraintes linéaires d'inégalité : le problème admet un unique minimiseur global si l'objectif est strictement convexe ; les méthodes de points intérieurs ou de gradient avec garanties de convergence trouvent la solution efficacement.

Mauvaise application

Appliquer des algorithmes d'optimisation convexe à des problèmes non convexes en les traitant comme convexes peut produire des optima incorrects ; les relaxations convexes peuvent induire en erreur si l'écart de relaxation est large ou si la structure discrète est essentielle.

Conséquence

Une application correcte fournit des solutions globalement optimales avec forte dualité sous des conditions faibles, un comportement numérique robuste et des algorithmes évolutifs depuis les points intérieurs jusqu'aux méthodes du premier ordre selon la taille et la structure.

Inversion

L'inverse est l'optimisation non convexe, où plusieurs minima locaux peuvent exister et où les méthodes locales peuvent rester piégées ; résoudre des problèmes non convexes nécessite des heuristiques globales, branch-and-bound ou des connaissances spécifiques au problème.

Limite

Limité aux problèmes dont l'objectif et les contraintes peuvent être formulés comme fonctions et ensembles convexes ; exclut les objectifs intrinsèquement non convexes, les variables décisionnelles discrètes sans relaxation et les problèmes d'équilibre adversarial non convexifiables.

Tension sémantique

Tension entre fidélité du modèle et convexité : imposer la convexité simplifie le calcul mais peut forcer des approximations qui sacrifieraient la précision ou omettraient une structure critique.

Synthèse

L'optimisation convexe consiste à étudier et appliquer l'optimisation d'objectifs convexes sur des régions faisables convexes, échangeant généralité de modélisation contre garanties d'optimalité globale et comportement algorithmique maîtrisé.