Issue ESAIM: PROC Volume 13, 2003 Proceedings of 2003 MODE-SMAI Conference Page(s) 41 - 64 DOI 10.1051/proc:2003006

ESAIM: Proc., December 2003, Vol. 13, pp. 41-64
DOI: 10.1051/proc:2003006

Some recent developments in nonlinear optimization algorithms

A. Sartenaer

Department of Mathematics, Facultés Universitaires Notre-Dame de la Paix, Namur, Belgium,

annick.sartenaer@fundp.ac.be

Abstract
This article provides a condensed overview of some of the major today's features (both classical or recently developed), used in the design and development of algorithms to solve nonlinear continuous optimization problems. We first consider the unconstrained optimization case to introduce the line-search and trust-region approaches as globalization techniques to force an algorithm to converge from any starting point. We then focus on constrained optimization and give the main ideas of two classes of methods, the Sequential Quadratic Programming (SQP) methods and the interior-point methods. We briefly discuss why interior-point methods are now so popular, in their primal-dual version, while they have been abandoned about twenty years ago. We also introduce a newly emerging alternative, called filter method, to the use of a merit function as a tool to measure progress from one iteration to the next in constrained optimization. We relate some of the most widely used nonlinear optimization solvers to the algorithmic features presented, and we finally give some useful tools for an easy and comprehensive access to recent developments in nonlinear optimization algorithms and to practical solvers and their performance.

Résumé
Nous présentons une sélection des principales stratégies (classiques ou récentes) utilisées à l'heure actuelle dans la conception et le développement d'algorithmes pour la résolution de problèmes d'optimisation continus non linéaires. Nous considérons tout d'abord le cas sans contraintes, afin d'introduire les techniques de recherche linéaire et de région de confiance, techniques de globalisation permettant de garantir la convergence d'un algorithme à partir de n'importe quel point de départ. Nous donnons ensuite les idées principales, dans le cadre de l'optimisation avec contraintes, de deux classes de méthodes : les méthodes de Programmation Quadratique Successive (PQS) et les méthodes de points intérieurs. Nous expliquons brièvement pourquoi les méthodes de points intérieurs sont actuellement si populaires, particulièrement dans leur version primale-duale, alors qu'elles avaient été laissées à l'abandon voici une vingtaine d'années. Nous introduisons d'autre part une récente alternative à l'utilisation d'une fonction de mérite comme outil de mesure, d'une itération à l'autre, de la progression d'un algorithme d'optimisation avec contraintes. Cette alternative porte le nom de méthode des filtres. Finalement, nous indiquons, pour certains logiciels d'optimisation non linéaire parmi ceux les plus utilisés à ce jour, les caractéristiques algorithmiques présentées dans ce travail qui les distinguent. Nous donnons quelques indications utiles pour un accès aisé et compréhensif aux développements récents en optimisation non linéaire, ainsi qu'à des logiciels récents et à leurs profils de performance.

Mathematics Subject Classification. 65K05, 90C26, 90C30, 90C51

Key words: Nonlinear optimization, overview of algorithms, globalization techniques, SQP methods, interior-point methods, filter methods.


© EDP Sciences, ESAIM 2003

What is OpenURL?