MGDA Variants for Multi-Objective Optimization

This report is a sequel to several publications in which a Multiple-Gradient Descent Algorithm (MGDA), has been proposed and tested for the treatment of multi-objective differentiable optimization. Originally introduced in [2], the method has been tested and reformulated in [6]. Its efficacy to identify the Pareto front has been demonstrated in [7], in comparison with an evolutionary strategy. Recently, a variant, MGDA-II, has been proposed in which the descent direction is calculated by a direct procedure [4] based on a Gram-Schmidt orthogonalization process (GSP) with special normalization. This algorithm was tested in the context of a simulation by domain partitioning, as a technique to match the different interface components concurrently [3]. The experimentation revealed the importance of scaling, and a slightly modified normalization procedure was proposed ("MGDA-IIb"). In this new report, two novel variants are proposed. The first, MGDA-III, realizes two enhancements. Firstly, the GSP is conducted incompletely whenever a test reveals that the current estimate of the direction of search is adequate also w.r.t. the gradients not yet taken into account; this improvement simplifies the identification of the search direction when the gradients point roughly in the same direction, and makes the Fréchet derivative common to several objective-functions larger. Secondly, the order in which the different gradients are considered in the GSP is defined in a unique way devised to favor an incomplete GSP. In the second variant, MGDA-IV, the question of scaling is addressed when the Hessians are known. A variant is also proposed in which the Hessians are estimated by the Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula.Ce rapport fait suite à plusieurs publications dans lesquelles on a proposé et testé un Algorithme de Descente à Gradients Multiples (MGDA) pour traiter les problèmes d'optimisation différentiable multiobjectifs. La méthode a été introduite originellement dans [2], et à nouveau formalisée dans [6]. Sa capacité à identifier le front de Pareto a été mise en évidence dans [7], en comparaison à une stratégie évolutionnaire. Récemment, une variante, MGDA II, a été proposée dans laquelle la direction de descente est calculée par une procédure directe [4] s'appuyant sur le processus d'orthogonalisation de Gram-Schmidt (GSP), effectué avec une certaine normalisation. On a testé l'efficacité de l'algorithme dans le contexte d'une simulation par partitionnement de domaine, comme technique pour raccorder concouramment les différentes composantes d'interface [3]. On a observé l'importance des facteurs d'échelle, ce qui a conduit a une légère modification de la procédure de normalisation ("MGDA-IIb"). Dans ce nouveau rapport, deux nouvelles variantes sont proposées. La première, MGDA-III, réalise deux améliorations. Premièrement, le GSP est exécuté incomplètement dès lors qu'un test révèle que l'estimation courante de la direction de recherche convient aussi aux vecteurs gradients qui n'ont pas encore été pris en considération; cette amélioration simplifie l'identification de la direction de recherche lorsque les gradients ont une direction commune approchée, et présente également l'avantage d'augmenter la dérivée de Fréchet commune aux fonctions objectifs. Deuxièmement, l'ordre dans lequel les differents gradients sont pris en compte dans le GSP est défini d'une manière unique conçue pour favoriser l'interruption rapide du GSP. Dans la seconde variante, MGDA-IV, la question du choix des échelles appropriées pour normaliser les gradients est abordée en supposant les hessiens connus. Une variante est également proposée dans laquelle les hessiens sont estimés par la formule de Broyden-Fletcher-Goldfarb-Shanno (BFGS)