Dans cette Thèse par article, nous nous intéressons au domaine de l'optimisation sans contrainte, non linéaire et différentiable. En considérant la recherche d'un optimum de la fonction f : R[indice supérieur n] [flèche vers la droite] R, on se restreint dans ce travail à chercher une racine x* de la fonction F = [triangle pointant vers le bas] f : R[indice supérieur n] [flèche vers la droite] R[indice supérieur n], c'est-à-dire un point stationnaire de la fonction f. Notre objectif a été de proposer une vision "différente" des méthodes d'ordres supérieurs. À cet effet, cette Thèse regroupera quatre articles qui soulignent le cheminement de notre travail de doctorat et la logique de notre recherche. Dans un premier article, qui servira d'introduction et de mise en contexte de cette Thèse, nous revenons sur les méthodes connues d'ordres supérieurs. Les méthodes de Newton, Chebyshev, Halley et SuperHalley ont en effet été étudiées dans différents travaux. Dans cet article, nous exhibons certaines problématiques reliées à ces méthodes : comment formuler correctement et intelligemment les méthodes utilisant des dérivées d'ordres supérieurs, comment mieux calculer leur complexité, comment vérifier leur convergence. Dans un second article, l'idée des méthodes d'ordres supérieures perçues comme directions de déplacement est proposée. En réalité, cet article exploratoire pose les bases de notre idée principale, les pistes de réflexion, les sources d'optimisme quand [i.e. quant] à l'efficacité de telles méthodes. Nous y proposons deux familles de méthodes : celle de type Halley, qui généralise et regroupe les méthodes de Halley et SuperHalley ; et celle de type Chebyshev, qui englobe et développe les algorithmes de Newton, Chebyshev, et les méthodes d'extrapolations de Jean-Pierre Dussault. Par ailleurs, dans ce chapitre, nous démontrons les propriétés de convergence (dans le cas réel) de telles méthodes et les illustrons dans un cas spécifique. Le troisième article constitue quant à lui le coeur de notre travail. Certaines pistes proposées dans le précédent article ont été abandonnées (la famille de méthode Halley) au profit d'autres plus prometteuses (la famille Chebyshev). Dans ce chapitre, nous élaborons et définissons précisément les méthodes de type Chebyshev d'ordres supérieurs. Une formulation plus globale nous permet d'y regrouper les méthodes d'extrapolations d'ordres supérieurs à 3. La convergence dans R[indice supérieur n] est démontrée (et non plus simplement dans le cas scalaire). Pour cela, nous nous appuyons sur la méthode de Shamanskii, que l'on retrouvera en fin d'article et au chapitre 4. Dans cet article, nous accordons une importance primordiale à la notion d'efficacité d'un algorithme, et en ce sens, nous définissons plus minutieusement (que la quasi-totalité des articles consultés) la notion de coût de calcul d'un algorithme. Cela nous permet de montrer que les méthodes de Chebyshev d'ordres supérieurs concurrencent les méthodes de Shamanskii (c'est-à-dire la méthode de Shamanskii à différents ordres d'itérations), connues pour être des références difficilement battables. En ce sens, plus les problèmes étudiés ont une grande taille, plus l'efficacité de nos méthodes est optimale, en comparaison avec d'autres algorithmes. La partie annexe concerne un complément, effectué dans le cadre de notre recherche. N'ayant pas été publié, nous en énoncons les résultats principaux comme piste de recherche. En effet, nos travaux ont concerné les problèmes en optimisation sans distinction autre que celle du domaine précis d'étude (des fonctions différentiables, sans contraintes, non linéaires). Or dans de nombreux cas, les problèmes que l'on cherche à minimiser ont des structures particulières : certaines fonctions ont des Hessiens creux, dont les éléments nuls sont structurés et identifiables. Autrement dit, il est concevable d'affiner nos travaux pour des cas plus spécifiques, ceux des systèmes dits "sparse". En particulier, les systèmes par bande constituent une illustration récurrente de ce type de fonctions. Nous revenons donc avec certains détails de coûts de calculs et d'efficacités de certains algorithmes présentés dans nos articles.

The main result is a new original algorithm: CONDOR ("COnstrained, Non-linear, Direct, parallel Optimization using trust Region method for high-computing load, noisy functions"). The aim of this algorithm is to find the minimum x* of an objective function F(x) (x is a vector whose dimension is between 1 and 150) using the least number of function evaluations of F(x). It is assumed that the dominant computing cost of the optimization process is the time needed to evaluate the objective function F(x) (One evaluation can range from 2 minutes to 2 days). The algorithm will try to minimize the number of evaluations of F(x), at the cost of a huge amount of routine work. CONDOR is a derivate-free optimization tool (i.e., the derivatives of F(x) are not required. The only information needed about the objective function is a simple method (written in Fortran, C++,...) or a program (a Unix, Windows, Solaris,... executable) which can evaluate the objective function F(x) at a given point x. The algorithm has been specially developed to be very robust against noise inside the evaluation of the objective function F(x). This hypotheses are very general, the algorithm can thus be applied on a vast number of situations. CONDOR is able to use several CPU's in a cluster of computers. Different computer architectures can be mixed together and used simultaneously to deliver a huge computing power. The optimizer will make simultaneous evaluations of the objective function F(x) on the available CPU's to speed up the optimization process. The experimental results are very encouraging and validate the quality of the approach: CONDOR outperforms many commercial, high-end optimizer and it might be the fastest optimizer in its category (fastest in terms of number of function evaluations). When several CPU's are used, the performances of CONDOR are currently unmatched (may 2004). CONDOR has been used during the METHOD project to optimize the shape of the blades inside a Centrifugal Compressor (METHOD stands for Achievement Of Maximum Efficiency For Process Centrifugal Compressors THrough New Techniques Of Design). In this project, the objective function is based on a 3D-CFD (computation fluid dynamic) code which simulates the flow of the gas inside the compressor.

Cette thèse porte sur la recherche d'une réponse au problème de prise en compte d'un cahier des charges génériques par une approche de synthèse par optimisation non linéaire. Étant donnés un processus et un ensemble de spécifications (en général de natures très diverses) sur le comportement souhaité pour le système bouclé, peut-on développer une formulation générique qui permet via des algorithmes d'optimisation adaptées, de répondre aux spécifications du cahier des charges ? Dans notre problématique, nous nous intéresseront à l'efficacité de la mise en œuvre :<br />• Efficacité des méthodes tant dans le choix de la formulation ; type de formulation des critères et des contraintes, que dans le choix des algorithmes.<br />• Adaptation ou création d'algorithmes spécifiques.<br />• Et surtout, prise en compte des régularités des problèmes pour obtenir des méthodes efficaces et faciles à mettre en œuvre.<br />Ce travail de recherche se propose d'étudier ces problématiques dans le prolongement des travaux portant sur les formulations convexes en utilisant différentes méthodes de l'optimisation non linéaire avec prise en compte de l'information a priori : correcteur initial intelligent, utilisation de changement de paramètres pour le conditionnement (tenant compte des comportements attendus pour la solution), hiérarchisation du problème global en sous problèmes présentant des qualités de résolutions supérieures

Un robot humanoïde est un système polyarticulé complexe dont la cinématique et la dynamique sont gouvernées par des équations non linéaires. Trouver des postures viables qui minimisent une tâche objectif tout en satisfaisant un ensemble de contraintes (intrinsèques ou extrinsèques) est un problème central pour la planification de mouvement robotique et est une fonctionnalité importante de tout logiciel de robotique. Le générateur de posture (PG) a pour rôle de trouver une posture viable en formulant puis résolvant un problème d’optimisation non linéaire. Nous étendons l’état de l’art en proposant de nouvelles formulations et méthodes de résolution de problèmes de génération de postures. Nous enrichissons la formulation de contraintes de contact par ajout de variables au problème d’optimisation, ce qui permet au solveur de décider automatiquement de la zone d’intersection entre deux polygones en contact ou encore de décider du lieu de contact sur une surface non plane. Nous présentons une reformulation du PG qui gère nativement les variétés non Euclidiennes et nous permet de formuler des problèmes mathématiques plus élégants et efficaces. Pour résoudre de tels problèmes, nous avons développé un solveur non linéaire par SQP qui supporte nativement les variables sur variétés. Ainsi, nous avons une meilleure maîtrise de notre solveur et pouvons le spécialiser pour la résolution de problèmes de robotique. / Humanoid robots are complex poly-articulated structures whose kinematics and dynamics are governed by nonlinear equations. Finding viable postures to realize set-point task objectives under a set of constraints (intrinsic and extrinsic limitations) is a key issue in the planning of robot motion and an important feature of any robotics framework. It is handled by the so called posture generator (PG) that consists in formalizing the viable posture as the solution to a nonlinear optimization problem. We present several extensions to the state-of-the-art by exploring new formulations and resolution methods for the posture generation problems. We reformulate the notion of contact constraints by adding variables to enrich our optimization problem and allow the solver to decide on the shape of the intersection of contact polygons or of the location of a contact point on a non-flat surface. We present a reformulation of the PG problem that encompasses non-Euclidean manifolds natively for a more elegant and efficient mathematical formulation of the problems. To solve such problems, we decided to implement a new SQP solver that is most suited to non-Euclidean manifolds structural objects. By doing so, we have a better mastering in the way to tune and specialize our solver for robotics problems.

L'introduction de l'écrouissage dans l'étude de l'adaptation élastoplastique est abordée ici, en particulier lorsque celle-ci impose de se placer en plasticité non associée. Le cadre des matériaux standards généralisés (MSG) n'étant plus adapté dans ce dernier cas, une approche alternative, fournie par le concept de matériaux standards implicites (MSI), est alors utilisée. En particulier, on présente dans ce travail l'étude d'exemples caractéristiques en adaptation élastoplastique par le modèle des MSI, soit par l'approche du bipotentiel. <br /> Un premier exemple concernant une éprouvette sous traction constante et torsion alternée est traité en utilisant la méthode pas à pas puis dans le cadre des MSI. La confrontation des résultats porte aussi bien sur le facteur d'adaptation que sur les contraintes internes. La comparaison entre les prédictions du calcul incrémental et celles de la solution analytique puis de la programmation mathématique, construites par l'approche du bipotentiel, montre une très bonne concordance. <br />La deuxième partie de l'étude est consacrée aux structures de type coques minces. Après avoir constaté que l'implémentation du problème de borne statique dans le cas de l'écrouissage cinématique linéaire limité nécessite d'imposer explicitement la limitation des contraintes internes pour que les résultats soient mécaniquement acceptables, il est montré que le cadre des MSI permet de construire un problème de borne cinématique. Son implémentation donne un encadrement très précis du facteur d'adaptation entre les facteurs cinématique et statique. Enfin, une règle d'écrouissage cinématique non linéaire et un bipotentiel sont construits pour les coques minces.

L'enregistrement Holter (enregistrement électrocardiographique de 24 heures) est un examen très fréquemment utilisé en cardiologie. Parmi les 100 000 battements enregistrés, seul un petit nombre d'entre eux peut traduire la présence d'une pathologie sous-jacente; l'analyse automatique est donc indispensable. Les outils actuels fonctionnent sur le principe d'un système expert, robuste, mais peu adaptatif et essentiellement limité à la détection et la classification des signaux de dépolarisation ventriculaire. Une analyse plus détaillée des signaux cardiaques permet une bien meilleure détection de nombreuses pathologies, en particulier grâce à l'extraction des signaux d'origine auriculaire et des ondes de repolarisation. Nous proposons dans cette thèse une méthode de décomposition mathématique originale des battements cardiaques sur une base de fonctions appelées "bosses". Contrairement aux régresseurs classiques utilisés en modélisation (ondelettes, RBF...), les bosses sont des fonctions prévues pour modéliser chaque onde caractéristique du battement cardiaque (les ondes P, Q, R, S et T). Chaque battement de l'enregistrement est ainsi décomposé en bosses; puis les labels médicaux P, Q, R, S et T leur sont attribués par des classifieurs (réseaux de neurones). Disposant alors de l'emplacement et de la forme des toutes les ondes caractéristiques pour l'ensemble de l'ECG, nous pouvons désormais repérer automatiquement des anomalies comme l'inversion de l'onde P, jusqu'alors non détectées par les algorithmes sur les enregistrements de longues durées. Cette approche a été testée sur de nombreuses bases de données et a montré toute son efficacité par rapport aux méthodes actuelles dem détection d'anomalies

Les travaux présentés dans cette thèse portent sur la conception d'une méthodologie d'ordonnancement/optimisation pour les systèmes de production à grande variété de produits et faible densité de flux appelés systèmes HVLV (High-Variety, LowVolume). Les caractéristiques de ces systèmes nous permettent d'appréhender la représentation des flux y circulant par un modèle discret. Le comportement discontinu des systèmes HVLV peut être caractérisé par la connaissance des dates de début et de fin des activités de production. L'algèbre (max, +) est utilisée pour représenter ce type de systèmes où les relations entre les dates de début des activités nécessitent l'utilisation des opérateurs maximum et addition. Afin d'utiliser l'algèbre (max, +) pour l'ordonnancement des systèmes HVLV, il est indispensable de résoudre un problème de conflit et d'optimisation sous contraintes dans cette algèbre. D'abord, nous avons développé dans ces travaux de recherche un modèle d'ordonnancement (max, +) pour les systèmes HVLV dans lequel des variables de décision ont été introduites afin de résoudre le problème de conflit entre les opérations exécutées sur les machines. Ensuite, nous avons amélioré le modèle proposé pour tenir compte de la maintenance préventive. Deux types de maintenance ont été considérés : Maintenance Périodique Répétitive (MPR) et Maintenance Flexible Périodique (MFP). Dans les deux cas, un problème d'ordonnancement non-linéaire sous contraintes a été résolu afin de minimiser certains critères de performance. Enfin, la méthodologie proposée a été validée par simulation, sur des systèmes HVLV complexes de type job-shop.

Un robot humanoïde est un système complexe doté de nombreux degrés de liberté, et dont le comportement est sujet aux équations non linéaires du mouvement. Par conséquent, la planification de mouvement pour un tel système est une tâche difficile d'un point de vue calculatoire. Dans ce mémoire, nous avons pour objectif de développer une méthode permettant d'utiliser la puissance de calcul des GPUs dans le contexte de la planification de mouvement corps-complet basée sur de l'optimisation. Nous montrons dans un premier temps les propriétés du problème d'optimisation, et des pistes d'étude pour la parallélisation de ce dernier. Ensuite, nous présentons notre approche du calcul de la dynamique, adaptée aux architectures de calcul parallèle. Cela nous permet de proposer une implémentation de notre problème de planification de mouvement sur GPU: contraintes et gradients sont calculés en parallèle, tandis que la résolution du problème même se déroule sur le CPU. Nous proposons en outre une nouvelle paramétrisation des forces de contact adaptée à notre problème d'optimisation. Enfin, nous étudions l'extension de notre travail au contrôle prédictif. / A humanoid robot is a complex system with numerous degrees of freedom, whose behavior is subject to the nonlinear equations of motion. As a result, planning its motion is a difficult task from a computational perspective.In this thesis, we aim at developing a method that can leverage the computing power of GPUs in the context of optimization-based whole-body motion planning. We first exhibit the properties of the optimization problem, and show that several avenues can be exploited in the context of parallel computing. Then, we present our approach of the dynamics computation, suitable for highly-parallel processing architectures. Next, we propose a many-core GPU implementation of the motion planning problem. Our approach computes the constraints and their gradients in parallel, and feeds the result to a nonlinear optimization solver running on the CPU. Because each constraint and its gradient can be evaluated independently for each time interval, we end up with a highly parallelizable problem that can take advantage of GPUs. We also propose a new parametrization of contact forces adapted to our optimization problem. Finally, we investigate the extension of our work to model predictive control.

Le diagnostic des tumeurs à un stade précoce est une clé indispensable à la lutte contre le cancer. Les techniques de détection se sont donc développées, notamment dans le domaine de l'optique biomédicale. Ce travail de thèse s'inscrit dans ce domaine d'étude. Nous proposons dans ce manuscrit une description et une comparaison des modèles statistique et déterministe mis en oeuvre pour simuler la propagation de la lumière dans les tissus biologiques par les méthodes de Monte Carlo, Monte Carlo hybride et les éléments finis avec intégration du processus de fluorescence exogène. La performance de la méthode des éléments finis a permis d'étudier la sensibilité des signaux de fluorescence résolus en temps en analysant l'influence de différents paramètres structurels et informels. Enfin , deux techniques de reconstruction d'images des tissus analysés sont implémentées. Pour ce faire, les méthodes d'inversion proposées ( Gauss Newton et méthode gradients conjugués ) sont non linéaires et font appel à des processus itératifs cherchant à optimiser les résultats obtenus par les simulations résolues par la méthode des éléments finis. Une adaptation stratégique et automatique du maillage est réalisée et intégrée dans le modèle d'inversion non linéaire. Une confrontation des deux méthodes est effectuée pour différents cas d'étude. Nous considérons tout d'abord un domain dans lequel est inséré une unique source fluorescente. Puis, le milieu biologique est simulé avec deux objets fluorescents. Nous étudions l'influence sur les images reconstruites de la distance entre les deux tumeurs ainsi que l'effet de la présence de fluorescence résiduelle au sein des tissus biologiques environnants.

Ce travail est une contribution à l'analyse de la tenue mécanique de milieux hétérogènes soumis à des chargements variables et bornés. On propose une méthode numérique permettant d'étudier, par une approche directe essentiellement basée sur le théorème statique de Melan, l'adaptation de matériaux élastoplastiques parfaits à microstructure hétérogène, périodique et tridimensionnelle. L'objectif est de coupler la théorie de l'adaptation élastoplastique, permettant d'étudier le comportement de milieux soumis à des chargements variables, avec la théorie de l'homogénéisation périodique, permettant de prendre finement en compte l'influence du comportement microscopique de milieux hétérogènes sur leur comportement macroscopique. La méthode consiste à résoudre le problème d'adaptation sur une cellule de base 3D -considérée comme une microstructure représentative des hétérogénéités- et à exprimer les résultats, par l'intermédiaire de relations de moyenne, en termes de domaines admissibles de chargements extérieurs : les déformations et contraintes macroscopiques. Numériquement, ceci se traduit par le couplage entre un code éléments finis, permettant de prendre en compte l'aspect homogénéisation du problème en formulant rigoureusement les relations de périodicité et de moyenne, et un logiciel d'optimisation non linéaire sous contraintes, permettant d'expliciter le problème d'adaptation. La méthode est appliquée à des milieux 3D classiques ainsi qu'à des structures de type plaque mince périodique. Au terme de ce travail, on dispose d'un outil numérique général, en ce sens qu'il permet d'étudier comment éviter la rupture, par dissipation plastique illimitée, de milieux périodiquement hétérogènes, et ce, quelle que soit la cellule de base 3D considérée.