Optimisation et convexité

L'optimisation comporte en gros deux mondes, dont les problèmes se ressemblent vus de loin, mais bien différents quant aux méthodes : le continu et le discret. Le présent dossier traite surtout de l'optimisation non différentiable, qui est un peu à cheval entre les deux mondes : les méthodes appartiennent à 100 % au monde continu mais 90 % des problèmes touchent de près ou de loin à l'optimisation discrète.

Parmi ces derniers, citons par exemple : la découpe industrielle, les tournées de véhicules ou d'équipages, le routage de multiflots en télécommunications, etc. Certaines techniques parmi les plus efficaces pour attaquer ces problèmes (génération de colonnes, Branch and Price) font appel à l'optimisation dont il est question ici : continue et non différentiable.

Les problèmes de grande taille appartiennent à la même famille : par leur nombre de variables ou de contraintes, ou encore parce qu'ils comportent plusieurs éléments hétérogènes, ces problèmes nécessitent de faire appel à une technologie spéciale : la décomposition, laquelle conduit généralement à l'optimisation non différentiable. En productique par exemple, on peut disposer d'un grand nombre de moyens de production de différents types, participant tous à la même production : c'est le cas de l'énergie électrique, produite à la fois par des centrales nucléaires, thermiques classiques, et des turbines hydro-électriques ; ces moyens de production sont bien différents les uns des autres.

Les grands types de problèmes sus-mentionnés proviennent des sciences « sociales » ; on en trouve d'autres de nature analogue, provenant de l'automatique (stabilisation), de la statistique (calibrage de matrices de covariance), de la mécanique (problèmes d'impacts), de l'électronique (semi-conducteurs) – liste non exhaustive.