Groupe d’études et de recherche en analyse des décisions

Adaptation d'une décomposition à la méthode séquentielle pour l'optimisation non linéaire à grande dimension

Mehdi Lachiheb

La résolution des problèmes quadratiques convexes dans \(IR^n\) par la méthode de décomposition du type Dantzig-Wolfe consiste à transformer le problème principal, ayant comme inconnue le vecteur espace, en un problème équivalent dont les inconnues sont les coefficients de la combinaison convexe de points extrêmes (PE) de l'ensemble admissible exprimant le vecteur espace. Toute solution du problème quadratique peut, en effet, s'écrire comme combinaison convexe d'au plus \(n+1\) points extrêmes.

La conjonction de cette décomposition avec la méthode quadratique séquentielle pour la résolution des problèmes non linéaires est proposée et mise en oeuvre dans le cadre du présent travail. Cette approche donne lieu à une suite de problèmes quadratiques que l'on résout par décomposition. La solution optimale de chacun des problèmes quadratiques est exprimée en fonction d'un groupe de points extrêmes et rayons extrêmes. Selon une mise en oeuvre brute, ce groupe est généré itérativement en résolvant une suite de sous problèmes de programmation linéaire de dimension \(n\), le nombre de tels sous problèmes pouvant dépasser largement le nombre de points extrêmes du groupe optimal de (PE).

Constatant que la plus grande part du temps de calcul est consommée dans la résolution répétitive des sous problèmes générant la suite de points extrêmes, plusieurs tentatives sont envisagées dans le but de réduire le calcul nécessaire à la détermination des points extrêmes utiles.

Dans le schéma de décomposition classique l'algorithme est initialisé avec un seul PE. Le nombre de PE est ensuite augmenté dans la limite du nombre \(n+1\). Par contre, dans l'approche proposée l'algorithme est initialisé avec tout un groupe de points extrêmes.

Comme première approximation ce groupe est composé des PE qui sont définis par les mêmes matrices de base que ceux de la fin de l'itération précédente. Les exemples traités indiquent bien l'avantage de cette approche, notamment au voisinage de l'optimum où le groupe de points extrêmes tend à se stabiliser. Une autre approximation est basée sur l'étude des faces d'un polytope que constitue le domaine admissible : le groupe de points extrêmes initial est composé des PE qui recouvrent l'espace défini par les contraintes actives de l'itération précédente. L'application de cette approximation sur un exemple de problème de calcul à la rupture (pour différentes dimensions \(n\)) montre une réduction de temps de calcul dépassant 70% en faveur de la seconde approche.

De plus, une technique, qui découle de la connaissance d'une matrice de base d'un point extrême non dégénéré du groupe final de PE, a été introduite pour déduire aisément les multiplicateurs de Lagrange de chaque problème quadratique de la méthode séquentielle.