Abstract :
[en] This work deals with optimisation problems in which the numerical cost associated with the evaluation of the target function and/or of the constraints is large; the number of calls to these functions by the optimisation algorithm should therefore be kept as small as possible.
The first part of the work is about globalisation by trust regions where the objective function and the constraints are replaced by a local approximation, easier to use, in a certain region of confidence.
Different types of local approximations are introduced but the main part of the work deals with quadratic approximations. The theoretical aspects of the global convergence of trust regions methods are also presented.
One of the applications considered in this work is the parametrical identification of a dynamical model with respect to experimental measurements. This identification can be expressed in the form of an unconstrained optimisation problem. For the practical implementation of the identification algorithm, the derivative of the objective function is required, which asks for the derivation of the underlying model. An algorithm, named Trust, has been implemented: it is a trust region method of quasi-Newton type which uses quadratic local approximations. The choice of the differentiation method is analysed in details in relation with its influence on the rate of convergence.
A brand new update strategy of the trust region radius is also introduced. The trust region radius is a parameter that measures the size of the trust region around the current iterate. The new approach relies on the identification and appropriate handling of so-called “too successful iterations” that lead to a much more important reduction of the function objective than predicted by the local approximation. This approach goes with a significant improvement of the performances of the algorithm.
Constrained optimisation is then considered using sequential quadratic methods. A fully effective algorithm for the resolution of quadratic convex sub-problems with quadratic constraints is introduced. This original method, named UVQCQP, makes use of an exact non-differentiable penalty function to addresses the constrained optimisation problem. The algorithm relies on a decomposition of the variable space into three orthogonal subspaces: a first subspace taking into account bound constraints, a second one in which the objective function is continuously derivable and a third one with slope discontinuities. The performances of this algorithm are further improved by the implementation of a fast mode taking into account the second order corrections.
Eventually, the UVQCQP algorithm is applied within the framework of sequential algorithms of quadratic programming with quadratic constraints: its advantages are demonstrated through some examples. The numerical tests carried out reveal very encouraging prospects.
[fr] Ce travail s'intéresse aux problèmes d’optimisation dans lesquels le temps de calcul de la fonction cible et/ou des contraintes est très important et où le nombre d’appels à ces fonctions par l'algorithme d’optimisation doit donc être aussi réduit que possible.
La première partie du travail porte sur la technique de globalisation dite par régions de confiance où la fonction objectif et les contraintes peuvent être remplacées par une approximation locale, plus facile à utiliser, dans une certaine zone de confiance.
Plusieurs types d'approximations locales sont développées en détail mais l'essentiel du travail se concentre sur les approximations quadratiques. Les aspects théoriques de convergence globale des méthodes par régions de confiance sont également présentés.
Une des applications envisagées porte sur l'identification paramétrique d'un modèle dynamique par rapport à des mesures expérimentales. Cette identification peut être exprimée sous la forme d'un problème d'optimisation non-contraint. Pour être menée à bien, l’identification nécessite la différentiation de la fonction objectif et donc du modèle sous-jacent : le facteur-clé est son coût en ressources informatiques et cette question est passée en revue en détail. Un algorithme, nommé Trust, a été implémenté : c’est une méthode par régions de confiance de type quasi-Newton qui utilise des approximations locales quadratiques. Le choix de la méthode de différentiation est analysé car celui-ci influence la vitesse de convergence.
Ce travail introduit également une stratégie nouvelle de mise à jour du rayon de confiance. Le rayon de confiance est un paramètre des méthodes par régions de confiance qui mesure l'étendue de la dite région autour de l'itéré courant. La nouveauté développée ici invite à se méfier des itérations menant à une réduction de la fonction objectif bien plus importante que celle prévue par l'approximation locale. Cette approche permet une amélioration sensible des performances de l'algorithme.
Le travail aborde ensuite la question de l'optimisation contrainte en se basant sur les méthodes quadratiques séquentielles. Il présente un algorithme complet et efficace de résolution d'un sous-problème convexe quadratique à contraintes quadratiques. Cette méthode originale, nommée UVQCQP, se base sur une fonction de pénalité exacte non-différentiable. L'algorithme tire profit d'une décomposition de l'espace des variables en trois sous-espaces orthogonaux : un premier permettant de gérer des contraintes de bornes, un deuxième dans lequel la fonction objectif est continûment dérivable et un troisième où elle présente des cassures de pente. Les performances de cet algorithme sont encore améliorées par l'implémentation d'un mode rapide qui tire profit de corrections du second ordre.
Pour terminer, l’algorithme UVQCQP est appliqué dans le cadre d’algorithmes séquentiels de programmation quadratique à contraintes quadratiques : ses avantages sont abordés au travers de quelques exemples. Les tests numériques effectués font apparaître des perspectives très encourageantes.
Disciplines :
Physical, chemical, mathematical & earth Sciences: Multidisciplinary, general & others
