Multilevel optimization in infinity norm and associated stopping criteria. Optimisation multiniveaux en norme infinie et critères d'arrêt associés

Mélodie Mouffe

Informations

• Publié par: facultes_universitaires_notre-dame_de_la_paix
• Publié le: 01 janvier 2009
• Nombre de lectures: 45
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

THÈSE


En vue de l'obtention du

DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE

Délivré par l'Institut National Polytechnique de Toulouse
Discipline ou spécialité : Mathématiques, informatique et télécommunications


Présentée et soutenue par Mélodie MOUFFE
Le 10 février 2009

Titre : Multilevel optimization in infinity norm and associated stopping criteria

JURY
Iain DUFF, Président
François GLINEUR, Rapporteur
Serge GRATTON, Directeur
Michal KOCVARA, Rapporteur
Annick SARTENAER, Membre
Philippe TOINT, Directeur
Xavier VASSEUR, Invité


Ecole doctorale : Mathématiques, Informatique et télécommunications (MITT)
Unité de recherche : CERFACS
Directeur(s) de Thèse : Serge GRATTON et Philippe TOINT
Rapporteurs : François GLINEUR et Michal Kocvara

THÈSE
présentée en vue de l’obtention du titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE
TOULOUSE (FRANCE)
Spécialité : Mathématiques, Informatique et Télécommunications
et de
DOCTEUR DES FACULTÉS UNIVERSITAIRES NOTRE-DAME DE LA
PAIX DE NAMUR (BELGIQUE)
Spécialité : Sciences Mathématiques
par
Mélodie MOUFFE
CERFACS
Optimisation multiniveaux en norme
infinie et critères d’arrêt associés
Multilevel optimization in infinity norm and
associated stopping criteria
Composition du jury :
Iain DUFF President RAL, UK and CERFACS, France
François GLINEUR Referee Université Catholique de Louvain, Belgium
Serge GRATTON Advisor CNES and CERFACS, France
Michal KOCVARA Referee University of Birmingham, UK
Annick SARTENAER Member FUNDP University of Namur, Belgium
Philippe TOINT Advisor FUNDP University of Namur, Belgium
Xavier VASSEUR Guest CERFACS, FranceJe souhaite remercier tout d’abord mes directeurs de
thèse, Serge Gratton et Philippe Toint pour le temps et
les conseils qu’ils m’ont donnés tout au long de la thèse.
Je remercie aussi l’ensemble des membres du jury et en
particulier les rapporteurs pour leur avis éclairé sur le
manuscript. Je remercie tous mes co-auteurs avec une
mention spéciale pour Dimitri avec qui c’est toujours un
véritable plaisir de travailler. Je tiens aussi à remercier
Iain Duff pour m’avoir donné la chance de réaliser cette
thèse et l’ensemble de l’équipe Algo pour leur bonne
humeur.
Je remercie bien entendu mes parents pour me soutenir
dans tous mes projets ainsi que pour leurs conseils avisés,
et Jérôme pour sa présence distrayante et indispensable.
Pour terminer, je souhaite remercier de tout mon coeur
Jimmy, toujours là pour m’encourager, avec qui une toute
autre aventure va commencer.Abstract of : Multilevel optimization in infinity norm and
associated stopping criteria
This thesis concerns the study of a multilevel trust-region algorithm in infin-
ity norm, designed for the solution of nonlinear optimization problems of high size,
possibly submitted to bound constraints. The study looks at both theoretical and
numerical sides.
The multilevel algorithm RMTR that we study has been developed on the basis∞
ofthealgorithmcreatedbyGratton, SartenaerandToint(2008b), whichwasmodified
first by replacing the use of the Euclidean norm by the infinity norm and also by
adapting it to solve bound-constrained problems.
In a first part, the main features of the new algorithm are exposed and discussed.
The algorithm is then proved globally convergent in the sense of Conn, Gould and
Toint (2000), which means that it converges to a local minimum when starting from
any feasible point. Moreover, it is shown that the active constraints identification
property of the trust-region methods based on the use of a Cauchy step can be
extended to any internal solver that satisfies a sufficient decrease property. As a
consequence, this identification property also holds for a specific variant of our new
algorithm.
Later, we study several stopping criteria for nonlinear bound-constrained algo-
rithms, in order to determine their meaning and their advantages from specific points
of view, and such that we can choose easily the one that suits best specific situations.
In particular, the stopping criteria are examined in terms of backward error analysis,
which has to be understood both in the usual meaning (using a product norm) and
in a multicriteria optimization framework.
Intheend, apractical algorithm isseton, thatusesaGauss-Seidel-like smoothing
techniqueasan internal solver. Numerical tests arerunonaFORTRAN 95version of
the algorithm in order to define a set of efficient default parameters for our method,
as well as to compare the algorithm with other classical algorithms like the mesh
refinement technique and the conjugate gradient method, on both unconstrained and
bound-constrained problems. These comparisons seem to give the advantage to the
designed multilevel algorithm, particularly on nearly quadratic problems, which is
the behavior expected from an algorithm inspired by multigrid techniques.
In conclusion, the multilevel trust-region algorithm presented in this thesis is an
improvement of the previous algorithm of this kind because of the use of the infinity
norm as well as because of its handling of bound constraints. Its convergence, its
behavior concerning the boundsand the definition of its stopping criteria are studied.
Moreover, it shows a promising numerical behavior.Résumé de : Optimisation multiniveaux en norme infinie et
critères d’arrêt associés
Cette thèse se concentre sur l’étude d’un algorithme multiniveaux de régions de
confianceen normeinfinie, conçu pourla résolution deproblèmes d’optimisation non-
linéaires de grande taille pouvant être soumis à des contraintes de bornes. L’étude
est réalisée tant sur le plan théorique que numérique.
L’algorithme RMTR que nous étudions ici a été élaboré à partir de l’algorithme∞
présenté par Gratton, Sartenaer et Toint (2008b), et modifié d’abord en remplaçant
l’usage de la norme Euclidienne par une norme infinie, et ensuite en l’adaptant à la
résolution de problèmes de minimisation soumis à des contraintes de bornes.
Dans un premier temps, les spécificités du nouvel algorithme sont exposées et dis-
cutées. De plus, l’algorithme est démontré globalement convergent au sens de Conn,
Gould et Toint (2000), c’est-à-dire convergent vers un minimum local au départ de
tout point admissible. D’autre part, il est démontré que la propriété d’identification
des contraintes actives des méthodes de régions de confiance basées sur l’utilisation
d’unpointdeCauchy peutêtreétendueà tout solveur interne respectant unedécrois-
sance suffisante. En conséquence, cette propriété d’identification est aussi respectée
par une variante particulière du nouvel algorithme.
Par la suite, nous étudions différents critères d’arrêt pour les algorithmes d’opti-
misation avec contraintes de bornes afin de déterminer le sens et les avantages de
chacun, et ce pour pouvoir choisir aisément celui qui convient le mieux à certaines
situations. Enparticulier, lescritères d’arrêtssontanalysés entermesd’erreurinverse
(backwarderreur),tantausensclassiqueduterme(avec l’usaged’unenormeproduit)
que du point de vue de l’optimisation multicritères.
Enfin, un algorithme pratique est mis en place, utilisant en particulier une tech-
nique similaire au lissage de Gauss-Seidel comme solveur interne. Des expérimen-
tations numériques sont réalisées sur une version FORTRAN 95 de l’algorithme.
Elles permettent d’une part de définir un panel de paramètres efficaces par défaut
et, d’autre part, de comparer le nouvel algorithme à d’autres algorithmes classiques
d’optimisation, comme la technique de raffinement de maillage ou la méthode du
gradient conjugué, sur des problèmes avec et sans contraintes de bornes. Ces com-
paraisons numériques semblent donner l’avantage à l’algorithme multiniveaux, en
particulier sur les cas peu non-linéaires, comportement attendu de la part d’un algo-
rithme inspiré des techniques multigrilles.
En conclusion, l’algorithme de région de confiance multiniveaux présenté dans
cette thèse est une amélioration du précédent algorithme de cette classe d’une part
par l’usage de la norme infinie et d’autre part grâce à son traitement de possibles
contraintes de bornes. Il est analysé tant sur le plan de la convergence que de son
comportement vis-à-vis des bornes, ou encore de la définition de son critère d’arrêt.
Il montre en outre un comportement numérique prometteur.