L'objectif de l'optimisation de forme d'une pompe générique de fond de puits est de maximiser le gain de pression par unité de longueur de la pompe, en redessinant ses aubes et son moyeu, tout en respectant un certain nombre de contraintes géométriques. On génère la représentation de la géométrie 3D de la pompe grâce à des B-splines paramétriques cubiques 2D. Pour l'optimisation on utilise une méthode de gradient classique. On emploie Fluent, un logiciel de modélisation de mécanique des fluides "boîte noire" et on procède par conséquent à un calcul de gradient incomplet de la fonction coût. Pour cela on écrit l'expression analytique exacte du gradient à l'aide d'une formule d'intégration sur les bords variables puis on ne prend en compte que les termes que l'on peut calculer ou déterminer numériquement. Les termes généralement écartés sont les dérivées des solutions de l'équation d'état par rapport au déplacement d'un point de contrôle. On a d'abord développé un code d'optimisation pour le moyeu de la pompe seul, sans aubages, et on présente les résultats obtenus. On utilise une méthode d'optimisation sans contrainte et on prend en compte par réduction du problème des contraintes d'égalité linéaires. On constate qu'après une première phase de décroissance, la fonction coût ne converge pas vers un minimum. On propose alors quelques tests de façon à analyser ce résultat. Parmi ceux-là, l'emploi des différences finies confirme que le gradient incomplet n'est pas systématiquement une direction de descente. Enfin quelques pistes sont évoquées pour l'expliquer. / The aim of the optimization of a well-pump is to maximize the pressure gain per length unit in the pump by designing its blades and hub, while taking into account some geometrical constraints. The 3D representation of the geometry of the pump is generated thanks to 2D parametric and cubic B-splines. We lead the optimization with a classical gradient method. Fluent, a computational fluid dynamics (CFD) "black box" software, is used and therefore we chose to compute an incomplete gradient of the cost function. We calculate the exact analytical expression of the gradient thanks to an integration formula on variable boundaries. Only the terms we can calculate or compute numerically are then kept. The terms we generally omit are the derivatives of the solutions of the state equations with respect to the displacement of the control points. An optimization program for the single hub of the pump has first been developed and we present its results. We use an optimization method without constraints though linear equality constraints are taken into account by reducing the problem. After a first decreasing phase, the cost function does not converge to a minimum value. We suggest some tests so as to analyze this result. Among these, the use of finite differences confirms that the incomplete gradient is not systematically a descent direction. Some ideas are finally given in order to explain this phenomenon.

La présente étude concerne l'étude d'optimisation thermique d'une machine électrique. Un modèle nodal est utilisé pour la simulation du champ de température. Ce modèle résout l'équation de la chaleur en trois dimensions, en coordonnées cylindriques et en régime transitoire ou permanent. On prend en compte les deux mécanismes de transport les plus importants : La conduction et la convection. L'évaluation de ce modèle est effectuée par l'intermédiaire de 13 valeurs de débits de référence. C'est en faisant varier ces variables qu'on évalue la performance du refroidissement dans la machine. Avant de partir sur l'étude d'optimisation de cettegéométrie, on a lancé une étude d'optimisation d'un cas plus simple afin de mieux comprendre les différents outils d'optimisation disponibles. L'expérience acquise avec les cas simples est utilisée dans l'optimisation thermique de la machine. La machine est thermiquement évaluée sur la combinaison de deux critères : la température maximale et la température moyenne. Des contraintes ont été additionnées afin d'obtenir des résultats physiquement acceptables. Le problème est résolu à l'aide des méthodes de gradient (Active-set et Point-Intérieur) et des Algorithmes Génétiques.

Toute perturbation dans les systèmes linéaires peut gravement dégrader la performance des méthodes itératives lorsque les directions conjuguées sont constituées. Ce problème peut être partiellement résolu par les méthodes du gradient à retards, qui ne garantissent pas la descente de la fonction quadratique, mais peuvent améliorer la convergence par rapport aux méthodes traditionnelles. Les travaux ultérieurs se sont concentrés sur les méthodes du gradient alternées avec deux ou plusieurs types de pas afin d'interrompre le zigzag. Des papiers récents ont suggéré que la révélation d'information de second ordre avec des pas à retards pourrait réduire de manière asymptotique les espaces de recherche dans des dimensions de plus en plus petites. Ceci a conduit aux méthodes du gradient avec alignement dans lesquelles l'étape essentielle et l'étape auxiliaire sont effectuées en alternance. Des expériences numériques ont démontré leur efficacité. Cette thèse considère d'abord des méthodes du gradient efficaces pour résoudre les systèmes linéaires symétriques définis positifs. Nous commençons par étudier une méthode alternée avec la propriété de terminaison finie à deux dimensions. Ensuite, nous déduisons davantage de propriétés spectrales pour les méthodes du gradient traditionnelles. Ces propriétés nous permettent d’élargir la famille de méthodes du gradient avec alignement et d’établir la convergence de nouvelles méthodes. Nous traitons également les itérations de gradient comme un processus peu coûteux intégré aux méthodes de splitting. En particulier, nous abordons le problème de l’estimation de paramètre et suggérons d’utiliser les méthodes du gradient rapide comme solveurs internes à faible précision. Dans le cas parallèle, nous nous concentrons sur les formulations avec retards pour lesquelles il est possible de réduire les coûts de communication. Nous présentons également de nouvelles propriétés et méthodes pour les itérations de gradient s-dimensionnelles. En résumé, cette thèse s'intéresse aux trois sujets interreliés dans lesquelles les itérations de gradient peuvent être utilisées en tant que solveurs efficaces, qu’outils intégrés pour les méthodes de splitting et que solveurs parallèles pour réduire la communication. Des exemples numériques sont présentés à la fin de chaque sujet pour appuyer nos résultats théoriques. / Any perturbation in linear systems may severely degrade the performance of iterative methods when conjugate directions are constructed. This issue can be partially remedied by lagged gradient methods, which does not guarantee descent in the quadratic function but can improve the convergence compared with traditional gradient methods. Later work focused on alternate gradient methods with two or more steplengths in order to break the zigzag pattern. Recent papers suggested that revealing of second-order information along with lagged steps could reduce asymptotically the search spaces in smaller and smaller dimensions. This led to gradient methods with alignment in which essential and auxiliary steps are conducted alternately. Numerical experiments have demonstrated their effectiveness. This dissertation first considers efficient gradient methods for solving symmetric positive definite linear systems. We begin by studying an alternate method with two-dimensional finite termination property. Then we derive more spectral properties for traditional steplengths. These properties allow us to expand the family of gradient methods with alignment and establish the convergence of new methods. We also treat gradient iterations as an inexpensive process embedded in splitting methods. In particular we address the parameter estimation problem and suggest to use fast gradient methods as low-precision inner solvers. For the parallel case we focus on the lagged formulations for which it is possible to reduce communication costs. We also present some new properties and methods for s-dimensional gradient iterations. To sum up, this dissertation is concerned with three inter-related topics in which gradient iterations can be employed as efficient solvers, as embedded tools for splitting methods and as parallel solvers for reducing communication. Numerical examples are presented at the end of each topic to support our theoretical findings.

L'objectif de l'optimisation de forme d'une pompe générique de fond de puits est de maximiser le gain de pression par unité de longueur de la pompe, en redessinant ses aubes et son moyeu, tout en respectant un certain nombre de contraintes géométriques. On génère la représentation de la géométrie 3D de la pompe grâce à des B-splines paramétriques cubiques 2D. Pour l'optimisation on utilise une méthode de gradient classique. On emploie Fluent, un logiciel de modélisation de mécanique des fluides "boîte noire" et on procède par conséquent à un calcul de gradient incomplet de la fonction coût. Pour cela on écrit l'expression analytique exacte du gradient à l'aide d'une formule d'intégration sur les bords variables puis on ne prend en compte que les termes que l'on peut calculer ou déterminer numériquement. Les termes généralement écartés sont les dérivées des solutions de l'équation d'état par rapport au déplacement d'un point de contrôle. On a d'abord développé un code d'optimisation pour le moyeu de la pompe seul, sans aubages, et on présente les résultats obtenus. On utilise une méthode d'optimisation sans contrainte et on prend en compte par réduction du problème des contraintes d'égalité linéaires. On constate qu'après une première phase de décroissance, la fonction coût ne converge pas vers un minimum. On propose alors quelques tests de façon à analyser ce résultat. Parmi ceux-là, l'emploi des différences finies confirme que le gradient incomplet n'est pas systématiquement une direction de descente. Enfin quelques pistes sont évoquées pour l'expliquer.

Le calcul de gradients de fonctions aérodynamiques par rapport à des paramètres géométriques de la forme solide est une sous-discipline de la simulation numérique en mécanique des fluides. Cette dérivation par rapport à deux variables dépendantes, le champ aérodynamique et le maillage, liés par les équations discrètes de la mécanique des fluides, nécessite l'inversion d'un système linéaire dont la matrice est la matrice jacobienne des équations de la mécanique des fluides discrétisées par rapport au champ aérodynamique (méthode de l'équation linéarisée) ou la transposée de cette matrice jacobienne (méthode adjointe). La précision du calcul de cette matrice jacobienne fait débat lorsque les équations de la mécanique des fluides sont modélisées avec l'approche RANS. L'objectif de cette thèse est de déterminer le degré d'exactitude de la linéarisation d'un flux visqueux discret et des équations discrètes de certains modèles de turbulence, nécessaire à l'obtention de gradients précis de fonctions métiers des concepteurs de turbomachines par rapport à des paramètres géométriques d'une aube. L'écriture de linéarisations approchées du flux visqueux (avec ou sans approche dite de "couche mince") et de deux modèles de turbulence (modèle algébrique de Michel et al. et modèle à deux équations de transport k-e de Launder-Sharma) est détaillée. Pour le modèle de Michel et al., plusieurs approximations pour la linéarisation des équations du modèle ont été testées et comparées. Des résultats (valeurs de gradients de fonctions aérodynamiques, sensibilités d'écoulement pour la méthode linéarisée) sont présentés pour la tuyère de Déléry dite C, l'aile ONERA M6 et deux configurations d'aube isolée de turbine. Des recommandations sont formulées pour le calcul de gradients pour des configurations de machine tournante avec modélisation RANS.

La présente étude concerne l’étude d’optimisation thermique d’une machine électrique. Un modèle nodal est utilisé pour la simulation du champ de température. Ce modèle résout l’équation de la chaleur en trois dimensions, en coordonnées cylindriques et en régime transitoire ou permanent. On prend en compte les deux mécanismes de transport les plus importants : La conduction et la convection. L’évaluation de ce modèle est effectuée par l’intermédiaire de 13 valeurs de débits de référence. C’est en faisant varier ces variables qu’on évalue la performance du refroidissement dans la machine. Avant de partir sur l’étude d’optimisation de cettegéométrie, on a lancé une étude d’optimisation d’un cas plus simple afin de mieux comprendre les différents outils d’optimisation disponibles. L’expérience acquise avec les cas simples est utilisée dans l’optimisation thermique de la machine. La machine est thermiquement évaluée sur la combinaison de deux critères : la température maximale et la température moyenne. Des contraintes ont été additionnées afin d’obtenir des résultats physiquement acceptables. Le problème est résolu à l’aide des méthodes de gradient (Active-set et Point-Intérieur) et des Algorithmes Génétiques. / This work relates the thermal optimization of an electrical machine. The lumped method is used to simulate the temperature field. This model solves the heat equation in three dimensions, in cylindrical coordinates and in transient or steady state. We consider two transport mechanisms: conduction and convection. The evaluation of this model is performed by means of 13 design variables that correspond to the main flow rates of the equipment. We analyse the machine cooling performance by varying these 13 flow rates. Before starting the study of such a complicated geometry, we picked a simpler case in order to better understand the variety of the available optimization tools. The experience obtained in the simpler case is applyed in the resolution of the thermal optimization problem of the electrical machine. This machine is evaluated from the thermal point of view by combining two criteria : the maximum and the mean temperature. Constraints are used to keep the problem consistent. We solved the problem using the gradient based methods (Active-set and Interior-Point) and the Genetic Algorithms.

La première partie est consacrée à la résolution de systèmes linéaires. Le chapitre 1 expose des résultats théoriques et numériques sur les méthodes proposées par Altman et précise le lien avec les méthodes de Krylov. Le chapitre 2 utilise des techniques d'extrapolation introduites par Brezinski pour obtenir une estimation du vecteur erreur. Plusieurs méthodes de projection sont retrouvées et de nouvelles procédures d'accélération données. Dans la deuxième partie, une nouvelle stratégie inspirée de la méthode de Cauchy-Barzilai-Borwein permet de définir de nouveaux schémas résolvant des problèmes de point fixe. Des résultats numériques sur un problème de bifurcation et un théorème de convergence sont donnés. Les chapitres 4, 5 et 6 sont consacrés à l'accélération de l'algorithme EM utilisé pour calculer des estimateurs du maximum de vraisemblance. Une classe de schémas itératifs basés sur la stratégie précédente est présentée, un théorème de convergence et une application à un problème de tomographie sont donnés. La dernière partie, fruit d'un projet du cemracs 2003, traite d'un problème issu de la physique des plasmas : l'amélioration des Codes Particles in Cell à l'aide d'une reconstruction de la densité basée sur une méthode d'ondelettes et sa validation numérique.

.

La phase d’apprentissage des méthodes d’apprentissage statistique automatique correspondent à la résolution d’un problème d’optimisation mathématique dont la fonction objectif se décompose en deux parties: a) le risque empirique, construit à partir d’une fonction de perte, dont la forme est déterminée par la métrique de performance et les hypothèses sur le bruit; b) la pénalité de régularisation, construite a partir d’une norme ou fonction jauge, dont la structure est déterminée par l’information à priori disponible sur le problème a résoudre.Les fonctions de perte usuelles, comme la fonction de perte charnière pour la classification supervisée binaire, ainsi que les fonctions de perte plus avancées comme celle pour la classification supervisée avec possibilité d’abstention, sont non-différentiables. Les pénalités de régularisation comme la norme l1 (vectorielle), ainsi que la norme nucléaire (matricielle), sont également non- différentiables. Cependant, les algorithmes d’optimisation numériques les plus simples, comme l’algorithme de sous-gradient ou les méthodes de faisceaux, ne tirent pas profit de la structure composite de l’objectif. Le but de cette thèse est d’étudier les problèmes d’apprentissage doublement non-différentiables (perte non- différentiable et régularisation non-différentiable), ainsi que les algorithmes d’optimisation numérique qui sont en mesure de bénéficier de cette structure composite.Dans le premier chapitre, nous présentons une nouvelle famille de pénalité de régularisation, les normes de Schatten par blocs, qui généralisent les normes de Schatten classiques. Nous démontrons les principales propriétés des normes de Schatten par blocs en faisant appel à des outils d’analyse convexe et d’algèbre linéaire; nous retrouvons en particulier des propriétés caractérisant les normes proposées en termes d’enveloppe convexes. Nous discutons plusieurs applications potentielles de la norme nucléaire par blocs, pour le filtrage collaboratif, la compression de bases de données, et l’annotation multi-étiquettes d’images.Dans le deuxième chapitre, nous présentons une synthèse de différentes tech- niques de lissage qui permettent d’utiliser des algorithmes de premier ordre adaptes aux objectifs composites qui de décomposent en un terme différentiable et un terme non-différentiable. Nous montrons comment le lissage peut être utilisé pour lisser la fonction de perte correspondant à la précision au rang k, populaire pour le classement et la classification supervises d’images. Nous décrivons dans les grandes lignes plusieurs familles d’algorithmes de premier ordre qui peuvent bénéficier du lissage: i) les algorithmes de gradient conditionnel; ii) les algorithmes de gradient proximal; iii) les algorithmes de gradient incrémental.Dans le troisième chapitre, nous étudions en profondeur les algorithmes de gradient conditionnel pour les problèmes d’optimisation non-différentiables d’apprentissage statistique automatique. Nous montrons qu’une stratégie de lis- sage adaptative associée à un algorithme de gradient conditionnel donne lieu à de nouveaux algorithmes de gradient conditionnel qui satisfont des garanties de convergence théoriques. Nous présentons des résultats expérimentaux prometteurs des problèmes de filtrage collaboratif pour la recommandation de films et de catégorisation d’images. / Training machine learning methods boils down to solving optimization problems whose objective functions often decomposes into two parts: a) the empirical risk, built upon the loss function, whose shape is determined by the performance metric and the noise assumptions; b) the regularization penalty, built upon a norm, or a gauge function, whose structure is determined by the prior information available for the problem at hand.Common loss functions, such as the hinge loss for binary classification, or more advanced loss functions, such as the one arising in classification with reject option, are non-smooth. Sparse regularization penalties such as the (vector) l1- penalty, or the (matrix) nuclear-norm penalty, are also non-smooth. However, basic non-smooth optimization algorithms, such as subgradient optimization or bundle-type methods, do not leverage the composite structure of the objective. The goal of this thesis is to study doubly non-smooth learning problems (with non-smooth loss functions and non-smooth regularization penalties) and first- order optimization algorithms that leverage composite structure of non-smooth objectives.In the first chapter, we introduce new regularization penalties, called the group Schatten norms, to generalize the standard Schatten norms to block- structured matrices. We establish the main properties of the group Schatten norms using tools from convex analysis and linear algebra; we retrieve in particular some convex envelope properties. We discuss several potential applications of the group nuclear-norm, in collaborative filtering, database compression, multi-label image tagging.In the second chapter, we present a survey of smoothing techniques that allow us to use first-order optimization algorithms designed for composite objectives decomposing into a smooth part and a non-smooth part. We also show how smoothing can be used on the loss function corresponding to the top-k accuracy, used for ranking and multi-class classification problems. We outline some first-order algorithms that can be used in combination with the smoothing technique: i) conditional gradient algorithms; ii) proximal gradient algorithms; iii) incremental gradient algorithms.In the third chapter, we study further conditional gradient algorithms for solving doubly non-smooth optimization problems. We show that an adaptive smoothing combined with the standard conditional gradient algorithm gives birth to new conditional gradient algorithms having the expected theoretical convergence guarantees. We present promising experimental results in collaborative filtering for movie recommendation and image categorization.

Cette thèse porte sur la résolution de problèmes de décision séquentielle sous incertitude,modélisés sous forme de processus décisionnels de Markov (PDM) dont l’espace d’étatet d’action sont tous les deux de grande dimension. La résolution de ces problèmes avecun bon compromis entre qualité de l’approximation et passage à l’échelle est encore unchallenge. Les algorithmes de résolution dédiés à ce type de problèmes sont rares quandla dimension des deux espaces excède 30, et imposent certaines limites sur la nature desproblèmes représentables.Nous avons proposé un nouveau cadre, appelé PDMF3, ainsi que des algorithmesde résolution approchée associés. Un PDMF3 est un processus décisionnel de Markov àespace d’état et d’action factorisés (PDMF-AF) dont non seulement l’espace d’état etd’action sont factorisés mais aussi dont les politiques solutions sont contraintes à unecertaine forme factorisée, et peuvent être stochastiques. Les algorithmes que nous avonsproposés appartiennent à la famille des algorithmes de type itération de la politique etexploitent des techniques d’optimisation continue et des méthodes d’inférence dans lesmodèles graphiques. Ces algorithmes de type itération de la politique ont été validés sur un grand nombre d’expériences numériques. Pour de petits PDMF3, pour lesquels la politique globale optimale est disponible, ils fournissent des politiques solutions proches de la politique globale optimale. Pour des problèmes plus grands de la sous-classe des processus décisionnels de Markov sur graphe (PDMG), ils sont compétitifs avec des algorithmes de résolution de l’état de l’art en termes de qualité. Nous montrons aussi que nos algorithmes permettent de traiter des PDMF3 de très grande taille en dehors de la sous-classe des PDMG, sur des problèmes jouets inspirés de problèmes réels en agronomie ou écologie. L’espace d’état et d’action sont alors tous les deux de dimension 100, et de taille 2100. Dans ce cas, nous comparons la qualité des politiques retournées à celle de politiques expertes. Dans la seconde partie de la thèse, nous avons appliqué le cadre et les algorithmesproposés pour déterminer des stratégies de gestion des services écosystémiques dans unpaysage agricole. Les adventices, plantes sauvages des milieux agricoles, présentent desfonctions antagonistes, étant à la fois en compétition pour les ressources avec la cultureet à la base de réseaux trophiques dans les agroécosystèmes. Nous cherchons à explorerquelles organisations du paysage (ici composé de colza, blé et prairie) dans l’espace etdans le temps permettent de fournir en même temps des services de production (rendementen céréales, fourrage et miel), des services de régulation (régulation des populationsd’espèces adventices et de pollinisateurs sauvages) et des services culturels (conservationd’espèces adventices et de pollinisateurs sauvages). Pour cela, nous avons développé unmodèle de la dynamique des adventices et des pollinisateurs et de la fonction de récompense pour différents objectifs (production, maintien de la biodiversité ou compromisentre les services). L’espace d’état de ce PDMF3 est de taille 32100, et l’espace d’actionde taille 3100, ce qui en fait un problème de taille conséquente. La résolution de ce PDMF3 a conduit à identifier différentes organisations du paysage permettant d’atteindre différents bouquets de services écosystémiques, qui diffèrent dans la magnitude de chacune des trois classes de services écosystémiques. / This PhD thesis focuses on the resolution of problems of sequential decision makingunder uncertainty, modelled as Markov decision processes (MDP) whose state and actionspaces are both of high dimension. Resolution of these problems with a good compromisebetween quality of approximation and scaling is still a challenge. Algorithms for solvingthis type of problems are rare when the dimension of both spaces exceed 30, and imposecertain limits on the nature of the problems that can be represented.We proposed a new framework, called F3MDP, as well as associated approximateresolution algorithms. A F3MDP is a Markov decision process with factored state andaction spaces (FA-FMDP) whose solution policies are constrained to be in a certainfactored form, and can be stochastic. The algorithms we proposed belong to the familyof approximate policy iteration algorithms and make use of continuous optimisationtechniques, and inference methods for graphical models.These policy iteration algorithms have been validated on a large number of numericalexperiments. For small F3MDPs, for which the optimal global policy is available, theyprovide policy solutions that are close to the optimal global policy. For larger problemsfrom the graph-based Markov decision processes (GMDP) subclass, they are competitivewith state-of-the-art algorithms in terms of quality. We also show that our algorithmsallow to deal with F3MDPs of very large size outside the GMDP subclass, on toy problemsinspired by real problems in agronomy or ecology. The state and action spaces arethen both of dimension 100, and of size 2100. In this case, we compare the quality of thereturned policies with the one of expert policies. In the second part of the thesis, we applied the framework and the proposed algorithms to determine ecosystem services management strategies in an agricultural landscape.Weed species, ie wild plants of agricultural environments, have antagonistic functions,being at the same time in competition with the crop for resources and keystonespecies in trophic networks of agroecosystems. We seek to explore which organizationsof the landscape (here composed of oilseed rape, wheat and pasture) in space and timeallow to provide at the same time production services (production of cereals, fodder andhoney), regulation services (regulation of weed populations and wild pollinators) andcultural services (conservation of weed species and wild pollinators). We developed amodel for weeds and pollinators dynamics and for reward functions modelling differentobjectives (production, conservation of biodiversity or trade-off between services). Thestate space of this F3MDP is of size 32100, and the action space of size 3100, which meansthis F3MDP has substantial size. By solving this F3MDP, we identified various landscapeorganizations that allow to provide different sets of ecosystem services which differ inthe magnitude of each of the three classes of ecosystem services.