Approximations based on the method of moving asymptotes
Approximations basées sur la méthode des asymptotes mobiles
Résumé
The method of moving asymptotes (MMA) is widely used for minimizing a continuous function of several variables. At each iterate of this method, the objective function and the constraints of the optimization problem are approximated by a rational convex function. To ensure the convergence of the MMA method, the sub problem of each iteration needs to be solved to its unique global optimal. This method formulates separable and strictly convex nonlinear sub problems iteratively. Lower and upper asymptotes are introduced to truncate the feasible region. Due to the special structure, the resulting sub problems can be solved by numerous efficient nonlinear optimization methods, for example, interior-point methods (IPM) and sequential convex programming (SCP). The original version of the Method of Moving Asymptotes (MMA) is not guaranteed to be in the corresponding feasible region described by the constraints. As a consequence, it is not able to solve the optimization problems where the feasible region defined by the constraints of feasibility. We propose in this thesis a new approximations and algorithms for unconstrained optimization, easy to implement based on the method of moving asymptotes, have the same advantages of the original version of the MMA and the SCP, and more advantages of global convergence, and we do not need to solve the sub problems generated by other classical methods thanks to their explicit solutions. We compare the resulting algorithms with known methods like Newton’s method and the Gradient projection method (GP). An extension of the MMA using the spectral parameters instead of the second-order information is presented; these parameters keep the generated sequence conveniently conservative with respect to the original functions and give information about the curvature, preserving the global convergence property. As far as the objective function, conservative approximations ensure monotonically decreasing values. Strict convexity and separability of the model functions are kept so that the sub problems generated have a unique solution. The goal of using these parameters is to reduce the total effort computing of the algorithm and then the possibility to apply it for large scale optimization problems. In another part, we propose a modification of these algorithms for the constrained optimization that ensures feasibility with respect to a given set of inequality constraints. The procedure expands the resulting sub problems by additional nonlinear constraints, which are passed to the sub problem directly to ensure their feasibility in each iteration step. As globalization technique, a line search procedure is used to ensure convergence. The resulting sub problems can be solved efficiently taking the sparse structure.
La méthode des asymptotes mobiles (MMA) est largement utilisée pour minimiser une fonction continue de plusieurs variables. À chaque itération de cette méthode, la fonction objective et les contraintes du problème d'optimisation sont approchées par une fonction rationnelle convexe. Pour assurer la convergence de la méthode MMA, le sous-problème de chaque itération doit être résolu à son optimum global unique. Cette méthode formule de façon itérative des sous-problèmes non linéaires séparables et strictement convexes. Des asymptotes inférieures et supérieures sont introduites pour tronquer la région réalisable. En raison de sa structure spéciale, les sous-problèmes qui en résultent peuvent être résolus par de nombreuses méthodes efficaces d'optimisation non linéaire, par exemple les méthodes de points intérieurs (IPM) et la programmation séquentielle convexe (SCP). La version originale de la méthode des asymptotes mobiles (MMA) n'est pas garantie à l'intérieur de la région réalisable correspondante décrite par les contraintes. Par conséquent, il n'est pas en mesure de résoudre les problèmes d'optimisation lorsque la région réalisable est définie par les contraintes de faisabilité. Nous proposons dans cette thèse de nouvelles approximations et de nouveaux algorithmes d'optimisation sans et avec contraintes, faciles à mettre en oeuvre sur la base de la méthode des asymptotes mobiles, qui ont les mêmes avantages que la version originale du MMA et du SCP, et plus d'avantages de convergence globale. Nous ne devons pas résoudre les sous-problèmes générés par une autre méthode classique grâce à leur solution explicite. Pour montrer l'efficacité de nos algorithmes, on les a comparés à des méthodes connues comme la méthode de Newton et les méthodes du gradient projeté (GP). Une extension de la MMA, en utilisant les paramètres spectraux au lieu de l'information de second ordre, est présentée, ces paramètres gardent la séquence générée commodément conservatrice par rapport aux fonctions originales et donnent une information sur la courbure, préservant la propriété de convergence globale. En ce qui concerne la fonction objective, des approximations conservatrices assurent des valeurs monotones décroissantes. La convexité stricte et la séparabilité des fonctions du modèle sont conservées afin que les sous problèmes générés aient une solution unique. Le but de l'utilisation de ces paramètres est de réduire l'effort total de calcul de l'algorithme et la possibilité de l'appliquer à des problèmes d'optimisation à grande échelle. Dans une autre partie, nous proposons une modification de ces derniers algorithmes pour l'optimisation avec contraintes qui assure la faisabilité par rapport à un ensemble donné de contraintes d’inégalités. La procédure étend les sous problèmes résultants par des contraintes non linéaires supplémentaires, qui sont transmises directement au sous problème pour assurer leur faisabilité à chaque étape d'itération. Comme technique globale, une procédure de recherche de lignes est utilisée pour assurer la convergence. Les sous problèmes qui en résultent peuvent être résolus efficacement en utilisant la structure clairsemée.
Origine : Version validée par le jury (STAR)