Multilevel Optimization: Convergence Theory, Algorithms and Application to Derivative-Free Optimization

We present new developments in the context of multilevel trust-region methods for nonlinear optimization. Motivated by the results obtained for unconstrained problems, we have extended the convergence theory for bound-constrained problems and for the use of infinity-norm trust regions. As an alternative for these methods, we have developed an algo- rithm that uses multilevel techniques for the exact resolution of the trust-region subproblem. This new method guarantees the convergence of the trust-region algorithm to a second-order critical point, with a much reduced associated cost when compared to classical methods. Un- fortunately, there are problems for which we cannot compute the derivatives of the objective function. The methods used today to solve this kind of problems are limited by the cost of the objective function computation. We present a multilevel version of one of these methods, that allows for the treatment of larger instances of the problem, as well as numerical results obtained with this new algorithm.Nous présentons des nouveaux développements dans le cadre des méthodes de ré- gion de confiance multi-niveaux pour l’optimisation non-linéaire. Motivés par les résultats obtenus pour l’optimisation sans contraintes, nous avons développé une théorie de conver- gence pour les problèmes aux contraintes de borne, et pour les régions de confiance définies par la norme infinie. Comme alternative à ce genre de méthodes, nous avons développé un al- gorithme qui utilise des techniques multi-niveaux pour la résolution exacte du sous-problème de la région de confiance. Cette nouvelle méthode garantit la convergence de l’algorithme à un point critique du deuxième ordre, avec un coût associé nettement inférieur comparé aux méthodes classiques. Malheureusement, il y a des problèmes où les dérivées de la fonction objectif ne peuvent pas être calculées. Les méthodes utilisées pour résoudre ce genre de problèmes sont limitées par le coût du calcul de la fonction objective. Nous présentons donc une version multi-niveaux de cette méthode qui permet de traiter des problèmes de taille plus conséquente, ainsi que des résultats numériques obtenus avec ce nouvel algorithme.(DOCSC00 ) -- FUNDP, 200