Approximations Convexes des Programmes à Contraintes de Chance

Résumé. Nous considérons un problème à contraintes de chance, où l'on cherche à minimiser un objectif convexe sur des solutions satisfaisant, avec une probabilité donnée proche de un, un système de contraintes convexes aléatoirement perturbées. Ce problème peut s'avérer computationnellement intractable ; notre objectif est de construire son approximation computationnellement tractable, c'est-à-dire un programme d'optimisation déterministe résoluble efficacement avec l'ensemble faisable contenu dans le problème à contraintes de chance. Nous construisons une classe générale de telles approximations convexes conservatrices du problème à contraintes de chance correspondant. De plus, sous les hypothèses que les contraintes sont affines dans les perturbations et que les entrées dans le vecteur de perturbation sont des variables aléatoires indépendantes les unes des autres, nous construisons une approximation de type grande déviation, appelée « approximation de Bernstein », du problème à contraintes de chance. Cette approximation est convexe et résoluble efficacement. Nous proposons un schéma basé sur la simulation pour borner la valeur optimale dans le problème à contraintes de chance et faisons rapport d'expériences numériques visant à comparer les approches d'approximation de Bernstein et de scénarios bien connus. Enfin, nous étendons notre construction au cas des problèmes à contraintes de chance ambiguës, où les perturbations aléatoires sont indépendantes avec la collection de distributions connues pour appartenir à un ensemble convexe compact donné plutôt que d'être connues exactement, tandis que la contrainte de chance doit être satisfaite pour chaque distribution donnée par cet ensemble.