Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse s'intéresse à la résolution de problèmes d'optimisation non-differentiable de grandes tailles résultant le plus souvent d'une relaxation Lagrangienne d'un problème difficile. Cette technique est couramment utilisée pour appréhender des problèmes linéaires avec nombres entiers ou des problèmes convexes complexes. Le problème dual obtenu est non-différentiable - éventuellement séparable - et peut être résolu par exemple par un algorithme de faisceau. Le Chapitre 2 propose une revue de littérature des méthodes d'optimisation non-différentiable. Dans certaines situations, le problème dual peut être lui-même très difficile à résoudre et nécessiter des stratégies adaptées. Par exemple, lorsque le nombre de contraintes dualisées est très élevé, une dualisation explicite peut s'avérer impossible ou la mise a jour des variables duales peut échouer. Au Chapitre 3, nous étudions les propriétés de convergence lorsqu'une relaxation Lagrangienne dynamique est effectuée : seul un sous-ensemble de contraintes est dualisé a chaque itération, ce qui permet de réduire la dimension du problème dual. Une autre limite de la relaxation Lagrangienne peut apparaître lorsque la fonction duale est séparable en un grand nombre de sous fonctions, ou que celles-ci restent difficiles a évaluer. Une stratégie naturelle consiste alors à tirer partie de la structure séparable en effectuant des itérations duales en n'ayant évalué qu'un sous-ensemble des sous fonctions. Au chapitre 4, nous proposons d'utiliser une méthode de faisceau dans ce contexte incrémental. Enfin, le Chapitre 5 présente des applications numériques sur des problèmes de gestion de production d'électricité.