Дисертації з теми "Méthodes des points intérieurs"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Méthodes des points intérieurs.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Méthodes des points intérieurs".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
SEGALAT, Philippe. "Méthodes de Points Intérieurs et de quasi-Newton." Phd thesis, Université de Limoges, 2002. http://tel.archives-ouvertes.fr/tel-00005478.
Анотація:
Cette thèse s'intéresse à des méthodes de points intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L'originalité de cette approche est l'emploi de ces formules dans le cadre des méthodes de points intérieurs. L'espace mémoire et le coût en opérations du calcul d'une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références l-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d'inégalité et contraintes d'égalité linéaire. L'idée est de pénaliser le problème à l'aide de variables de décalage et d'une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontrées.
2
Orban, Dominique. "Méthodes de points intérieurs pour l'optimisation non-linéaire." Toulouse, INPT, 2001. http://www.theses.fr/2001INPT012H.
Анотація:
Ce travail se scinde principalement en deux grandes composantes ; l'une de type théorique et l'autre de type numérique. Dans la partie théorique, on se place dans le cadre de l'optimisation non linéaire avec contraintes. La globalisation d'un algorithme de points intérieurs par des régions de confiance est examinée et l'on détaille ses propriétés de convergence, étayées par des expérimentations numériques sur des problèmes de programmation quadratique. Sous des hypothèses du premier et second ordre, les propriétés de convergence locale, asymptotique, d'une classe d'algorithmes de points intérieurs, parmi laquelle l'algorithme précédent, sont étudiées et l'on montre que l'on peut obtenir une convergence sous-quadratique qui a lieu en composantes. Les résultats sont généralisés à un taux de convergence arbitrairement élevé, au prix de la résolution d'un nombre suffisamment élevé de systèmes de Newton pour chaque valeur du paramètre barrière. Ces résultats asymptotiques supposent que la condition de qualification des contraintes d'indépendance des gradients actifs est satisfaite. Il s'avère que la condition de qualification des contraintes peut être relachée en la condition de Mangasarian et Fromowitz, tout en conservant les propriétés de convergence importantes. Les techniques utilisées et les résultats de convergence asymptotique en les composantes sont enfin généralisés à la résolution de systèmes d'équations non linéaires de rang plein. Dans la composante numérique, on examine ensuite l'environnement CUTE et l'on décrit les nouvelles fonctionnalités et les apports de CUTEr.
3
Segalat, Philippe. "Méthodes de points intérieurs et de quasi-Newton." Limoges, 2002. http://www.theses.fr/2002LIMO0041.
Анотація:
Cette thèse s' intéresse à des méthodes de ponts intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L' originalité de cette approche est l' emploi de ces formules dans le cadre des méthodes de points intérieurs. L' espace mémoire et le coût en opérations du calcul d' une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références 1-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d' inégalité et contraintes d' égalité linéaire. L' idée est de pénaliser le problème à l' aide de variables de décalage et d' une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontréesThis thesis is interested in interior point and quasi-Newton methods in nonlinear optimization and with their implementation. One presents the code NOPTIQ using the limited memory BFGS formulas to solve large scale problems. The originality of this approach is the use of these formulas within the framework of interior point methods. The storage requirement and the computing cost of one iteration are then low. One shows that NOPTIQ is robust and that its performance are comparable with the reference codes 1-BFGS-B and LANCELOT. One presents also an infeasible algorithm using the preceding methods to solve a nonlinear problem with inequality constraints and linear equality constraints. The idea to penalize the problem using shift variables and a variant of the big-M method of linear programming. The q-superlinear convergence of the inner iterates and the global convergence of outer iterates are shown
4
Hadjou, Tayeb. "Analyse numérique des méthodes de points intérieurs : simulations et applications." Rouen, 1996. http://www.theses.fr/1996ROUES062.
Анотація:
La thèse porte sur une étude à la fois théorique et pratique des méthodes de points intérieurs pour la programmation linéaire et la programmation quadratique convexe. Dans une première partie, elle donne une introduction aux méthodes de points intérieurs pour la programmation linéaire, décrit les outils de base, classifie et présente d'une façon unifiée les différentes méthodes. Elle présente dans la suite un exposé des algorithmes de trajectoire centrale pour la programmation linéaire et la programmation quadratique convexe. Dans une seconde partie sont étudiées des procédures de purification en programmation linéaire. Il s'agit des procédures qui déterminent, via une méthode de points intérieurs, un sommet (ou face) optimal. Dans cette partie, nous avons introduit et développé une nouvelle procédure de purification qui permet de mener dans tous les cas à un sommet optimal et de réduire le temps de calcul. La dernière partie est consacrée aux illustrations et aux expériences numériques.
5
Bouhtou, Mustapha. "Méthodes de points intérieurs pour l'optimisation des systèmes de grande taille." Paris 9, 1993. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1993PA090061.
Анотація:
Les nouvelles méthodes de points intérieurs jouent aujourd'hui un rôle de plus en plus important dans l'optimisation des systèmes de grande taille. Dans cette thèse nous étudions dans une première partie, du point de vue théorique et numérique, une extension d'un algorithme de points intérieurs pour la programmation quadratique convexe et non convexe. Celle-ci utilise l'idée de la région de confiance que l'on peut expliciter grâce à une transformation affine. Sous certaines hypothèses nous démontrons des résultats sur la convergence globale et sur la vitesse de convergence de l'algorithme. Nous donnons aussi une version pratique de cet algorithme, basée sur une généralisation de la méthode de Lanczos pour la résolution des systèmes linéaires indéfinis. Celle-ci donne dans la pratique des résultats très encourageants. Dans la seconde partie, nous étudions du point de vue théorique une extension d'un autre algorithme de points intérieurs pour l'optimisation non linéaire avec contraintes linéaires. Cette extension utilise l'idée de la réduction d'une fonction potentiel après une transformation affine de l'ensemble admissible. Des résultats sur la convergence globale et sur la complexité de l'algorithme sont donnés
6
Bouafia, Mousaab. "Étude asymptotique des méthodes de points intérieurs pour la programmation linéaire." Thesis, Le Havre, 2016. http://www.theses.fr/2016LEHA0019/document.
Анотація:
Dans cette recherche, on s’intéresse à l’étude asymptotique des méthodes de points intérieurs pour la programmation linéaire. En se basant sur les travaux de Schrijver et Padberg, nous proposons deux nouveaux pas de déplacement pour accélérer la convergence de l'algorithme de Karmarkar et réduire sa complexité algorithmique. Le premier pas est une amélioration modérée du comportement de l'algorithme, le deuxième représente le meilleur pas de déplacement fixe obtenu jusqu'à présent. Ensuite nous proposons deux approches paramétrées de la l'algorithme de trajectoire centrale basé sur les fonctions noyau. La première fonction généralise la fonction noyau proposé par Y. Q. Bai et al., la deuxième est la première fonction noyau trigonométrique qui donne la meilleure complexité algorithmique, obtenue jusqu'à présent. Ces propositions ont apporté des nouvelles contributions d'ordre algorithmique, théorique et numériqueIn this research, we are interested by asymptotic study of interior point methods for linear programming. By basing itself on the works of Schrijver and Padberg, we propose two new displacement steps to accelerate the convergence of Karmarkar's algorithm and reduce its algorithmic complexity. The first step is a moderate improvement of the behaviour of this algorithm; the second represents the best fixed displacement step obtained actually. We propose two parameterized approaches of the central trajectory algorithm via a kernel function. The first function generalizes the kernel function given by Y. Q. Bai et al., the second is the first trigonometric kernel function that gives the best algorithmic complexity, obtained until now. These proposals have made new contributions of algorithmic, theoretical and numerical order
7
Zerari, Amina. "Méthodes de points intérieurs et leurs applications sur des problèmes d'optimisation semi-définis." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMLH24.
Анотація:
Les méthodes de points intérieurs sont bien connues comme les plus efficaces pour résoudre les problèmes d’optimisation. Ces méthodes possèdent une convergence polynômiale et un bon comportement numérique. Dans cette recherche, nous nous sommes intéressés à une étude théorique, algorithmique et numérique des méthodes de points intérieurs pour la programmation semi-définie.En effet, on présente dans une première partie un algorithme réalisable projectif primal-dual de points intérieurs de type polynômial à deux phases, où on a introduit trois nouvelles alternatives efficaces pour calculer le pas de déplacement.Ensuite, dans la deuxième partie, on s’intéresse aux méthodes de type trajectoire centrale primale-duale via une fonction noyau, nous proposons deux nouvelles fonctions noyaux à terme logarithmique qui donnent la meilleure complexité algorithmique, obtenue jusqu’à présentInterior point methods are well known as the most efficient to solve optimization problems. These methods have a polynomial convergence and good behavior. In this research, we are interested in a theoretical, numerical and an algorithmic study of interior-point methods for semidefinite programming.Indeed, we present in a first part, a primal-dual projective interior point algorithm of polynomial type with two phases, where we introduced three new effective alternatives for computing the displacement step.Then, in the second part, we are interested in a primal-dual central trajectory method via a kernel function, we proposed two new kernel functions with a logarithmic term that give the best-known complexity results
8
Roumili, Hayet. "Méthodes de points intérieurs non réalisables en optimisation : théorie, algorithmes et applications." Le Havre, 2007. http://www.theses.fr/2007LEHA0013.
Анотація:
Dans cette étude, nous nous intéressons au problème d'initialisation dans les méthodes de points intérieurs de types trajectoire centrale, en prenant comme référence les travaux de Y. Zhang pour la programmation linéaire (PL). Après avoir mis en oeuvre un algorithme pour la programmation linéaire (PL), nous proposons une extension pour la programmation quadratique convexe (PQC) puis pour la programmation semidéfinie (PSD)In this study, we are interested to the initialization problem for central path following interior point methods, taking Y. Zhang's work for the linear programming (LP) as bench-mark. After, we make use of an appropriate algorithm for linear programming, we propose an extension for the quadratic convex programming as well semidefinite programming
9
Veiga, Géraldo. "Sur l'implantation des méthodes de points intérieurs pour la programmation linéaire : Texte imprimé." Paris 13, 1997. http://www.theses.fr/1997PA132010.
Анотація:
L'objectif de ce travail vise a l'implantation des algorithmes de points interieurs pour la programmation lineaire. En demarrant avec la premiere implantation d'une variante de l'algorithme de points interieurs qui s'est averee competitive par rapport a la methode du simplexe sur un grand nombre d'experiences numeriques, nous presentons notre contribution pour ce domaine de recherche. A partir d'une famille d'algorithmes de points interieurs de type echelle affine, nous avons developpe une implantation dont les tests numeriques ont confirme sa competitivite, surtout lorsque la taille des problemes testes augmente. Pour une implantation efficace, nous avons developpe des structures de donnees et des techniques de programmation centrees sur la methode d'elimination de gauss appliquee a la resolution d'une sequence de systemes d'equations a matrices symetriques et definies positives. Pour cela, notre approche consiste en un schema de decomposition directe pour les matrices creuses, a l'aide d'une decomposition symbolique effectuee a une etape preparatoire de l'algorithme de programmation lineaire. Une specialisation des methodes duales de points interieurs a ete concue pour les problemes d'optimisation dans les reseaux. Notre implantation utilise une methode du gradient conjugue avec des preconditionneurs diagonaux et des arbres generateurs. Une nouvelle variante de l'algorithme dual propose par tsuchiya et muramatsu a ete ajoutee a notre implantation en vue de la detection anticipee d'une solution optimale. Toujours pour les problemes d'optimisation dans les reseaux, nous avons developpe une methode tronquee du type primal(non realisable)-dual(realisable). Nos remarques finales insistent sur le role des algorithmes de points interieurs parmi les techniques modernes pour la solution des problemes d'optimisation lineaire de grande taille
10
Kebbiche, Zakia. "Étude et extensions d'algorithmes de points intérieurs pour la programmation non linéaire." Le Havre, 2007. http://www.theses.fr/2007LEHA0014.
Анотація:
Dans cette thèse, nous présentons une étude algorithmique et numérique concernant la méthode de trajectoire centrale appliquée au problème de complémentarité linéaire considéré comme une formulation unificatrice de la programmation linéaire et de la programmation quadratique convexe. Puis, nous proposons deux variantes intéressantes, l'une de trajectoire centrale et l'autre de type projectif avec linéarisation, pour minimiser une fonction convexe différentiable sur un polyèdre. Les algorithmes sont bien définis et les résultats théoriques correspondants sont établisIn this thesis, we present an algorithmically and numerical study concerning the central path method for linear complementarity problem wich is considered as an unifying framework of linear and quadratic programming. Then, we propose two intersting variants namely the central path and the projective with linearization methods for minimizing a convex differentiable function on a polyhedral set. The algorithms are well defined and the corresponding theoretical results are established
11
Ouriemchi, Mohammed. "Résolution de problèmes non linéaires par les méthodes de points intérieurs : théorie et algorithmes." Phd thesis, Université du Havre, 2005. http://tel.archives-ouvertes.fr/tel-00011376.
Анотація:
Les méthodes barrières proposent de résoudre le problème non linéaire en résolvant une suite de problèmes pénalisés. Le lien entre la suite, dite externe, des solutions des fonctions pénalisées et la solution du problème initial a été établie dans les années soixante.Dans cette thèse, nous avons utilisé une fonction barrière logarithmique. A chaque itération externe, la technique SQP se charge de produire une série de sous-problèmes quadratiques dont les solutions forment une suite, dite interne, de directions de descente pour résoudre le problème non linéaire pénalisé.
Nous avons introduit un changement de variable sur le pas de déplacement ce qui a permis d'obtenir des conditions d'optimalité plus stable numériquement.
Nous avons réalisé des simulations numériques pour comparer les performances de la méthode des gradients conjugués à celle de la méthode D.C., appliquées pour résoudre des problèmes quadratiques de région de confiance.
Nous avons adapté la méthode D.C. pour résoudre les sous-problèmes verticaux, ce qui nous a permis de ramener leurs dimensions de $n+m$ à $m+p$ ($ p < n $).
L'évolution de l'algorithme est contrôlée par la fonction de mérite. Des tests numériques permettent de comparer les avantages de différentes formes de la fonction de mérite. Nous avons introduit de nouvelles règles pour améliorer cette évolution.
Les expériences numériques montrent un gain concernant le nombre de problèmes résolus. L'étude de la convergence de notre méthode SDC, clôt ce travail.
12
Kadiri, Abderrahim. "Analyse des méthodes des points intérieurs pour les problèmes de complémentarité linéaire et la programmation quadratique convexe." INSA de Rouen, 2001. http://www.theses.fr/2001ISAM0008.
Анотація:
Cette thèse porte sur une étude théorique et pratique des méthodes de points intérieurs pour les problèmes de complémentarité linéaire (LCP) et la programmation linéaire convexe (PQC). Le premier chapitre est un survol de quelques méthodes classiques pour la résolution d'un (PQC). Dans le deuxième chapitre, elle présente les notions de base nécessaires pour les méthodes de trajectoire centrale. Ensuite, elle donne une description d'un algorithme de trajectoire centrale pour résoudre un (PQC). Le troisième est consacré aux méthodes de points intérieurs pour le (LCP). Il contient un exposé de quelques algorithmes principaux avec leurs propriétés de convergence et complexité. Les procédures de purification sont étudiées au chapitre 4. Nous proposons une nouvelle procédure pour le (LCP) et le (PQC) qui permet de mener à une solution exacte et de réduire le temps global de calcul. Des aspects pratiques et des résultats numériques sont présentés dans le dernier chapitre.
13
Seguin, Jean-Philippe. "Simulation thermomécanique de structures en alliages à mémoire de forme par la méthode des points intérieurs." Versailles-St Quentin en Yvelines, 2010. http://www.theses.fr/2010VERS0016.
Анотація:
Les Alliages à Mémoire de Forme (AMF) sont des matériaux dont le comportement mécanique dépend de la sollicitation thermique. La prise en compte du couplage thermomécanique dans les modèles est nécessaire pour mieux comprendre ce type de matériau. Ces travaux de thèse s’intéressent donc aux outils numériques pour simuler les évolutions thermomécaniques de structures en alliages à mémoire de forme. Une nouvelle méthode de résolution est proposée, reposant sur la reformulation du problème incrémental en un problème de complémentarité linéaire et l’utilisation d’un algorithme de points intérieurs. Des simulations tests à température fixée ont permis de valider cette méthode. Enfin, d’autres simulations ont été réalisées pour étudier l’influence du couplage thermomécaniqueShape Memory Alloys (SMA) are materials on which mechanical behaviour depends of thermal solicitation. Thermomechanical coupling in models is necessary to understand better this kind of material. PhD thesis is concerned with the development of numerical tools for simulating thermomechanical evolutions of 3D SMA structures. In the approach that is presented, a crucial point consists in reformulating the incremental problem as a linear complementarity problem. This allows one to take advantage of interior point algorithms for solving the discretized evolutionary equations. Tests simulations with fixed temperature allowed to validate this approach. At least, others simulations have been made to study the influence of the thermomechanical coupling on the structural response
14
Halard, Matthieu. "Méthodes du second ordre pour la conception optimale en élasticité non-linéaire." Paris 9, 1999. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1999PA090029.
Анотація:
La conception optimale de structures élastiques non-linéaires se heurte d'abord au cout de résolution de l'équation d'équilibre soit une vingtaine d'itérations de Newton comprenant une factorisation de la matrice de raideur tangente et une descente-remontée ; puis au mauvais conditionnement du critère à optimiser vis-à-vis des variables de conception ; enfin au traitement des contraintes de conception parfois impératives même au cours de l'optimisation. Les deux premiers points sont résolus en appliquant une méthode de type Newton au système d'optimalité, dans lequel les variables de conception et d'état sont les inconnues. L'algorithme hybride adjoint-direct est techniquement réalisable avec des calculs analytiques de gradients et des dérivées secondes du lagrangien approchées par différences finies. La recherche linéaire dans la direction de Newton est remplacée par une recherche sur un arc linéaire ou parabolique collant à la courbe d'équilibre de l'espace conception-état, afin de se rapprocher d'une méthode de Newton réduite à l'espace de conception. La convergence rapide se voit sur les résultats. Le dernier point est abordé par l'étude d'une méthode de points intérieurs dans laquelle la direction de recherche est déviée vers l'intérieur du domaine de conception pour accroitre la robustesse de l'algorithme. Nous élaborons un autre calcul de déflexion, itératif, fournissant une direction restant dans le domaine linéarisé avec un taux de descente par rapport à la direction de Newton supérieur à un critère de trajectoire centrale. Des exemples bidimensionnels parlants montrent que la combinaison des deux idées allie robustesse et performance. La première partie se clôt sur l'algorithme de conception optimale avec contraintes d'inégalité. La deuxième est consacrée à son application à l'élasticité et à sa programmation avec des couts détaillés car sa performance en dépend. Des cas semi-industriels prouvent l'intérêt des techniques retenues.
15
Akoa, François Bertrand. "Approches de points intérieurs et de la programmation DC en optimisation non convexe. Codes et simulations numériques industrielles." Rouen, INSA, 2005. http://www.theses.fr/2005ISARA001.
Анотація:
Cette thèse est principalement consacrée à l'association des méthodes de points intérieurs et des techniques de l'optimisation DC et DCA pour résoudre les problèmes d'optimisation non convexe de grande taille. La thèse comporte trois parties : La première partie est consacrée aux techniques d'optimisations locales et s'articule autour des méthodes de points intérieurs et de la programmation DC. Nous y développons deux algorithmes. La seconde partie de la thèse est consacrée à l'intégration de l'algorithme des points intérieurs dans un schéma séparation-évaluation. La dernière partie de la thèse est consacrée aux applications industrielles. Nous y appliquons les deux nouveaux algorithmes développés dans la première partie à un problème de mécanique de structure de grande dimension, puis à un problème de séparateur à vaste marge
16
Jonsson, Xavier. "Méthodes de points intérieurs et de régions de confiance en optimisation non linéaire et application à la conception de verres ophtalmiques progressifs." Paris 6, 2002. http://www.theses.fr/2002PA066191.
17
Davy, Guillaume. "Génération de codes et d'annotations prouvables d'algorithmes de points intérieurs à destination de systèmes embarqués critiques." Thesis, Toulouse, ISAE, 2018. http://www.theses.fr/2018ESAE0034/document.
Анотація:
Dans l'industrie, l'utilisation de l'optimisation est omniprésente. Elle consiste à calculer la meilleure solution tout en satisfaisant un certain nombre de contraintes. Cependant, ce calcul est complexe, long et pas toujours fiable. C'est pourquoi cette tâche est longtemps restée cantonnée aux étapes de conception, ce qui laissait le temps de faire les calculs puis de vérifier que la solution était correcte et si besoin refaire les calculs. Ces dernières années, grâce à la puissance toujours grandissante des ordinateurs, l'industrie a commencé à intégrer des calculs d'optimisation au cœur des systèmes. C'est-à-dire que des calculs d'optimisation sont effectués en permanence au sein du système, parfois des dizaines de fois par seconde. Par conséquent, il est impossible de s'assurer a posteriori de la correction d'une solution ou de relancer un calcul. C'est pourquoi il est primordial de vérifier que le programme d'optimisation est parfaitement correct et exempt de bogue.L'objectif de cette thèse a été de développer outils et méthodes pour répondre à ce besoin.Pour ce faire, nous avons utilisé la théorie de la preuve formelle qui consiste à considérer un programme comme un objet mathématique. Cet objet prend des informations en entrée et produit un résultat. On peut alors, sous certaines conditions sur les entrées, prouver que le résultat satisfait nos exigences. Notre travail a consisté à choisir un programme d'optimisation puis à prouver formellement que le résultat de ce programme est correctIn the industry, the use of optimization is ubiquitous. Optimization consists of calculating the best solution subject to a number of constraints. However, this calculation is complex,long and not always reliable. This is why this task has long been confined to the design stages,which allowed time to do the computation and then check that the solution is correct and if necessary redo the computation. In recent years, thanks to the ever-increasing power of computers, the industry has begun to integrate optimization computation at the heart of the systems. That is to say that optimization computation is carried out continuously within the system, sometimes dozens of times per second. Therefore, it is impossible to check a posteriori the solution or restart a calculation. That is why it is important to check that the program optimization is perfectly correct and bug-free. The objective of this thesis was to develop tools and methods to meet this need. To do this we have used the theory of formal proof that is to consider a program as a mathematical object. This object takes input data and produces a result. We can then, under certain conditions on the inputs, prove that the result meets our requirements. Our job was to choose an optimization program and formally prove that the result of this program is correct
18
Vu, Duc Thach Son. "Numerical resolution of algebraic systems with complementarity conditions : Application to the thermodynamics of compositional multiphase mixtures." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG006.
Анотація:
Dans les simulateurs de réservoir, la prise en compte des lois d’équilibre thermodynamique pour les mélanges polyphasiques d'hydrocarbures est une partie délicate. La difficulté réside dans la gestion de l'apparition et de la disparition des phases pour différents constituants. L'approche dynamique traditionnelle, dite de variable switching, consiste à ne garder que les inconnues des phases présentes et les équations relatives à celles-ci. Elle est lourde et coûteuse, dans la mesure où le « switching » se produit constamment, même d'une itération de Newton à l'autre.Une approche alternative, appelée formulation unifiée, permet de maintenir au cours des calculs un jeu fixe d'inconnues et d'équations. Sur le plan théorique, c'est un progrès important. Sur le plan pratique, comme la nouvelle formulation fait intervenir des équations de complémentarité qui sont non-lisses, on est obligé après discrétisation d'avoir recours à la méthode semi-lisse Newton-min, au comportement souvent pathologique.Pour aller au bout de l’intérêt de la démarche unifiée, cette thèse a pour objectif de lever cet obstacle numérique en élaborant des algorithmes de résolution mieux adaptés, avec une meilleure convergence. Notre méthodologie consiste à s’inspirer des méthodes qui ont fait leur preuve en optimisation sous contraintes et à les transposer aux systèmes généraux. Cela conduit aux méthodes de points intérieurs, dont nous proposons une version non-paramétrique appelée NPIPM, avec des résultats supérieurs à Newton-min.Une autre contribution de ce travail doctoral est la compréhension et la résolution (partielle) d’une autre obstruction au bon fonctionnement de la formulation unifiée, jusque-là non identifiée dans la littérature. Il s’agit de la limitation du domaine de définition des fonctions de Gibbs associées aux lois d’état cubiques. Pour remédier à l’éventuelle non-existence de solution du système, nous préconisons un prolongement naturel des fonctions de GibbsIn reservoir simulators, it is usually delicate to take into account the laws of thermodynamic equilibrium for multiphase hydrocarbon mixtures. The difficulty lies in handling the appearance and disappearance of phases for different species. The traditional dynamic approach, known as variable switching, consists in considering only the unknowns and equations of the present phases. It is cumbersome and costly, insofar as "switching" occurs constantly, even from one Newton iteration to another.An alternative approach, called unified formulation, allows a fixed set of unknowns and equations to be maintained during the calculations. From a theoretical point of view, this is an major advance. On the practical level, because of the nonsmoothness of the complementarity equations involved in the new formulation, the discretized equations have to be solved by the semi-smooth Newton-min method, whose behavior is often pathological.In order to fully exploit the interest of the unified approach, this thesis aims at circumventing this numerical obstacle by means of more robust resolution algorithms, with a better convergence. To this end, we draw inspiration from the methods that have proven their worth in constrained optimization and we try to transpose them to general systems. This gives rise to interior-point methods, of which we propose a nonparametric version called NPIPM. The results appear to be superior to those of Newton-min.Another contribution of this doctoral work is the understanding and (partial) resolution of another obstruction to the proper functioning of the unified formulation, hitherto unidentified in the literature. This is the limitation of the domain of definition of Gibbs' functions associated with cubic equations of state. To remedy the possible non-existence of a system solution, we advocate a natural extension of Gibbs' functions
19
Taha, Khaled. "Analyse numérique d'algorithmes pour la programmation linéaire-quadratique généralisée." Rouen, 1995. http://www.theses.fr/2000ROUES035.
Анотація:
Dans cette thèse, nous présentons une étude à la fois théorique et algorithmique de la programmation linéaire-quadratique généralisée. Nous commençons par dégager les différentes propriétés de l'objectif et de définir le lien de l'optimalité avec les inégalités variationnelles et le problème de complémentarité linéaire. Pour résoudre numériquement ces problèmes, nous adaptons en premier lieu une variante SQP de la méthode quasi-newtonienne BFGS et proposons d'appliquer l'algorithme du point proximal lorsque l'objectif est non différentiable. Ensuite, nous nous plaçons dans le cadres des méthodes de point intérieur et proposons une nouvelle méthode basée sur la résolution d'une suite de systèmes quasi-définis. Cette méthode tire un grand avantage de la structure particulière de ces systèmes. Après, nous généralisons notre étude au problème du minimax à termes linéaires croisés. Deux cas importants sont analysés, le cas des contraintes linéaires polyèdriques et celui des inégalités linéaires matricielles. Enfin, nous appliquons notre résultat à la résolution des problèmes issus de l'optimisation dynamique et stochastique. Les expériences numériques réalisées confirment les performances de notre méthodeIn this work, we present a theoretical and numerical study of extended linear-quadratic programming. We start with bringing out the different proprieties of objective and defining the relation of optimality with variational inequalities and linear complementarity problems. To solve the problem numerically, we adapt first and foremost a SQP variant of the quasi-Newton method BFGS and suggest the proximal point algorithm for the non-differentiable case. In the following, we deal with interior point methods and propose a new method based on solving a sequence of quasi-definite systems. This method takes advantage of the particular structure of these systems. Afterwards, we generalize our study on the minimax problem. In this context, two important cases are analysed; the case of polyhedral constraints and the case of linear matrix inequalities. Finally, we apply our results to solve problems of dynamic and stochastic optimisation. Numerical simulations done in this work assess the efficiency of our method
20
Malisani, Paul. "Pilotage dynamique de l'énergie du bâtiment par commande optimale sous contraintes utilisant la pénalisation intérieure." Phd thesis, Ecole Nationale Supérieure des Mines de Paris, 2012. http://pastel.archives-ouvertes.fr/pastel-00740044.
Анотація:
Dans cette thèse, une méthode de résolution de problèmes de commande optimale non linéaires sous contraintes d'état et de commande. Cette méthode repose sur l'adaptation des méthodes de points intérieurs, utilisées en optimisation de dimension finie, à la commande optimale. Un choix constructif de fonctions de pénalisation intérieure est fourni dans cette thèse. On montre que ce choix permet d'approcher la solution d'un problème de commande optimale sous contraintes en résolvant une suite de problèmes de commande optimale sans contraintes dont les solutions sont simplement caractérisées par les conditions de stationnarité du calcul des variations.Deux études dans le domaine de la gestion de l'énergie dans les bâtiments sont ensuite conduites. La première consiste à quantifier la durée maximale d'effacement quotidien du chauffage permettant de maintenir la température intérieure dans une certaine bande de confort, et ce pour différents types de bâtiments classés de mal à bien isolés. La seconde étude se concentre sur les bâtiments BBC et consiste à quantifier la capacité de ces bâtiments à réaliser des effacements électriques complets du chauffage de 6h00 à 22h00 tout en maintenant, là encore, la température intérieure dans une bande de confort. Cette étude est réalisée sur l'ensemble de la saison de chauffe.
21
Corbineau, Marie-Caroline. "Proximal and interior point optimization strategies in image recovery." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLC085/document.
Анотація:
Les problèmes inverses en traitement d'images peuvent être résolus en utilisant des méthodes variationnelles classiques, des approches basées sur l'apprentissage profond, ou encore des stratégies bayésiennes. Bien que différentes, ces approches nécessitent toutes des algorithmes d'optimisation efficaces. L'opérateur proximal est un outil important pour la minimisation de fonctions non lisses. Dans cette thèse, nous illustrons la polyvalence des algorithmes proximaux en les introduisant dans chacune des trois méthodes de résolution susmentionnées.Tout d'abord, nous considérons une formulation variationnelle sous contraintes dont la fonction objectif est composite. Nous développons PIPA, un nouvel algorithme proximal de points intérieurs permettant de résoudre ce problème. Dans le but d'accélérer PIPA, nous y incluons une métrique variable. La convergence de PIPA est prouvée sous certaines conditions et nous montrons que cette méthode est plus rapide que des algorithmes de l'état de l'art au travers de deux exemples numériques en traitement d'images.Dans une deuxième partie, nous étudions iRestNet, une architecture neuronale obtenue en déroulant un algorithme proximal de points intérieurs. iRestNet nécessite l'expression de l'opérateur proximal de la barrière logarithmique et des dérivées premières de cet opérateur. Nous fournissons ces expressions pour trois types de contraintes. Nous montrons ensuite que sous certaines conditions, cette architecture est robuste à une perturbation sur son entrée. Enfin, iRestNet démontre de bonnes performances pratiques en restauration d'images par rapport à une approche variationnelle et à d'autres méthodes d'apprentissage profond.La dernière partie de cette thèse est consacrée à l'étude d'une méthode d'échantillonnage stochastique pour résoudre des problèmes inverses dans un cadre bayésien. Nous proposons une version accélérée de l'algorithme proximal de Langevin non ajusté, baptisée PP-ULA. Cet algorithme est incorporé à un échantillonneur de Gibbs hybride utilisé pour réaliser la déconvolution et la segmentation d'images ultrasonores. PP-ULA utilise le principe de majoration-minimisation afin de gérer les distributions non log-concaves. Comme le montrent nos expériences réalisées sur des données ultrasonores simulées et réelles, PP-ULA permet une importante réduction du temps d'exécution tout en produisant des résultats de déconvolution et de segmentation très satisfaisantsInverse problems in image processing can be solved by diverse techniques, such as classical variational methods, recent deep learning approaches, or Bayesian strategies. Although relying on different principles, these methods all require efficient optimization algorithms. The proximity operator appears as a crucial tool in many iterative solvers for nonsmooth optimization problems. In this thesis, we illustrate the versatility of proximal algorithms by incorporating them within each one of the aforementioned resolution methods.First, we consider a variational formulation including a set of constraints and a composite objective function. We present PIPA, a novel proximal interior point algorithm for solving the considered optimization problem. This algorithm includes variable metrics for acceleration purposes. We derive convergence guarantees for PIPA and show in numerical experiments that it compares favorably with state-of-the-art algorithms in two challenging image processing applications.In a second part, we investigate a neural network architecture called iRestNet, obtained by unfolding a proximal interior point algorithm over a fixed number of iterations. iRestNet requires the expression of the logarithmic barrier proximity operator and of its first derivatives, which we provide for three useful types of constraints. Then, we derive conditions under which this optimization-inspired architecture is robust to an input perturbation. We conduct several image deblurring experiments, in which iRestNet performs well with respect to a variational approach and to state-of-the-art deep learning methods.The last part of this thesis focuses on a stochastic sampling method for solving inverse problems in a Bayesian setting. We present an accelerated proximal unadjusted Langevin algorithm called PP-ULA. This scheme is incorporated into a hybrid Gibbs sampler used to perform joint deconvolution and segmentation of ultrasound images. PP-ULA employs the majorize-minimize principle to address non log-concave priors. As shown in numerical experiments, PP-ULA leads to a significant time reduction and to very satisfactory deconvolution and segmentation results on both simulated and real ultrasound data
22
REBAI, Raja. "Optimisation de réseaux de télécommunications avec sécurisation." Phd thesis, Université Paris Dauphine - Paris IX, 2000. http://tel.archives-ouvertes.fr/tel-00010841.
Анотація:
La première partie de cette thèse, concerne une étude de robustesse des algorithmes de points intérieurs prédicteurs correcteurs, ainsi qu'une approche par décomposition de cette méthode pour la résolution de problè mes de multiflot. Dans la deuxième partie, nous nous intéressons au Problème de Sécurisation Globale dont l'objectif est de déterminer un multiflot (qui transporte toute demande de son noeud origine à son noeud destination en respectant la loi de Kirchhoff) et l'investissement de moindre coût en capacité s nominale et de réserve qui assure le routage nominal et garantit sa survie par reroutage global. Dans notre modèle les routages et les capacités peuvent être fractionnés. PSG se formule alors comme un problème linéaire de grande taille avec plusieurs niveaux de couplage. Sa structure particulière appelle à l'emploi d'algorithmes de décompositions. Nous proposons quatre méthodes utilisant la technique de génération de colonnes. Les deux premières sont basées sur les techniques proximales. Leur tâche principale consiste en la résolution de sous problèmes quadratiques indépendants. Le troisième algorithme s'inspire de l'approche de points intérieurs décrite à la première partie. Pour finir, nous intégrons une procédure d'élimination de chemins dans une adaptation d'un solveur de points intérieurs. Nous reportons des résultats numériques obtenus en testant ces algorithmes sur des données réelles fournies par le CNET.
23
Kallel, Emna. "Une synthèse sur les méthodes du point intérieur." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ35688.pdf.
24
Takouda, Pawoumodom Ledogada. "Problèmes d'approximation matricielle linéaires coniques : approches par projections et via optimisation sous contraintes de semidéfinie positivité." Toulouse 3, 2003. http://www.theses.fr/2003TOU30129.
25
Le, Manh Hung. "Études mathématiques et numériques de la complémentarité aux valeurs propres et des problèmes d'accélération dans l'optimisation du premier ordre." Electronic Thesis or Diss., Limoges, 2023. http://www.theses.fr/2023LIMO0104.
Анотація:
Dans cette thèse, j’explore deux sujets clés. Premièrement, je m’intéresse à l’étude mathématique et numérique du problème de complémentarité des valeurs propres de Pareto et de sa contrepartie inverse. Notre approche utilise des méthodes de points intérieurs, complétées par une technique de lissage non paramétrique. L’efficacité des méthodologies proposées est soulignée par un ensemble d’expériences numériques. En mettant l’accent sur l’optimisation continue, nous adoptons une perspective de systèmes dynamiques. Plus précisément, nous étudions divers algorithmes inertiels à gradient proximal, discrétisés à partir d’un système dynamique inertiel non régulier comportant des éléments de frottement sec et d’amortissement piloté par le Hessien. En outre, nous examinons une équation d’évolution doublement non linéaire régie par deux potentiels, ainsi que l’accélération de sa convergence par l’application de techniques de mise à l’échelle temporelle et de calcul de la moyenne, ce qui se traduit par une dynamique inertielle comportant un frottement sec et un amortissement implicite induit par le hessien. Les tests numériques corroborent la performance supérieure des systèmes inertiels par rapport à leurs homologues du premier ordre, ce qui correspond aux résultats théoriquesIn this thesis, I explore two key topics. Firstly, I delve into the mathematical and numerical study of the Pareto eigenvalue complementarity problem and its inverse counterpart. Our approach employs interior point methods, supplemented by a non-parametric smoothing technique. The efficacy of these proposed methodologies is underscored through an array of numerical experiments. Shifting our focus to continuous optimization, we adopt a dynamical systems perspective. Specifically, we study various proximal gradient inertial algorithms, discretized from a non-regular inertial dynamical system featuring elements of dry friction and Hessian-driven damping. Additionally, we examine a doubly nonlinear evolution equation governed by two potentials, and its convergence acceleration through the application of time scaling and averaging techniques, which results in inertial dynamics featuring dry friction and implicit Hessian-driven damping. The numerical tests corroborate the superior performance of inertial systems over their first-order counterparts, aligning with the theoretical results
26
Al, Kharboutly Mira. "Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMLH06/document.
Анотація:
Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problèmeOur objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem
27
Chatel, Gweltaz. "Comptage de points : application des méthodes cristallines." Rennes 1, 2007. http://www.theses.fr/2007REN1S023.
Анотація:
On s’intéresse dans cette thèse au calcul du nombre de points de courbes algébriques sur des corps finis. En utilisant la stabilité de la cohomologie rigide à support propre par descente finie étale, on montre que l’on peut ramener le calcul des groupes de cohomologie d’une telle courbe à celui des groupes de cohomologie d’un isocristal sur un ouvert de la droite affine, et on construit un algorithme effectuant ce calcul en temps polynomial. On montre alors qu’en utilisant un relevé de Frobenius pour une courbe algébrique sur un corps fini calculé à l’aide d’un algorithme présenté par Gerkmann dans sa thèse, on peut compter le nombre de points de la courbe en appliquant la formule des traces en cohomologie rigide, obtenant finalement un algorithme polynomial fonctionnant pour une large classe de courbes. On détermine de plus des complexités pour nos algorithmes, recourant pour cela à des méthodes dues à Lauder pour contrôler la valeur absolue des éléments de la base de cohomologie que l’on manipuleWe deal in this thesis with the computation of the number of points of algebraic curves over finite fields. By use of the stability of the rigid cohomology with compact support by finite etale descent, we show that the computation of the cohomology groups of such a curve can be reduced to the computation of the cohomology groups of an isocrystal over an open subset of the affine line and we build an algorithm achieving this operation in polynomial time. We then show that using a lifting of Frobenius for an algebraic curve over a finite field computed thanks to an algorithm presented by Gerkmann in his thesis, we can count the number of points of the curve by application of the trace formula for rigid cohomology, finally obtaining a polynomial time algorithm working for a large class of curves. We furthermore find complexities for our algorithms, using some technics introduced by Lauder in order to control the absolute value of the elements of the cohomology basis we handle
28
Djellali, Assia. "Optimisation technico-économique d'un réseau d'énergie électrique dans un environnement dérégulé." Paris 11, 2003. http://www.theses.fr/2003PA112211.
Анотація:
Avec l'ouverture du marché de l'électricité de nouveaux problèmes apparaissent dans la conduite du réseau. Dans ce contexte l'optimisation des réseaux électriques se heurte aux problèmes rencontrés dans le contexte monopolistique tel que: la nature des contraintes, la taille du problème à résoudre, la non linéarité des équations du réseau, auxquels il faut maintenant ajouter les contraintes du marché. Nous sommes amenés à faire appel aux modèles mathématiques permettant l'optimisation avec un critère non linéaire et sous contraintes non linéaires. Deux méthodes ont été étudiées pour connaître les difficultés que pose le problème de l'optimisation avec la programmation non linéaire d'une part et la conduite du réseau dans un environnement dérégulé d'autre part. La méthode Newton-Lagrange appliquée à un réseau simplifié à 5 nœuds traite le problème d'un marché monopolistique dont les objectifs d'une optimisation technico-économique du système consistent à déterminer la puissance que doit fournir chaque centrale électrique pour assurer la sûreté du système et le faire fonctionner au moindre coût. Cette méthode nous servira de base dans la seconde partie pour traiter le problème de l'exploitation des réseaux dans un environnement dérégulé. La vitesse de convergence de la méthode utilisée est liée aux contraintes inégalités; les résultats sont satisfaisants. Le second outil d'optimisation est basé sur la méthode primale duale du point intérieur, il est appliqué à un réseau test à 12 nœuds. Il traite les problèmes rencontrés dans un environnement concurrentiel, tels que la gestion des écarts entre les prévisions de production et la réalité des opérations d'injection sur le réseau, la gestion des congestions, la gestion des pertes, les effets de l'accès ouvert à de nouveaux producteurs et l'évaluation de leurs impacts sur le réseau. Les résultats obtenus avec cette méthode et la facilité du traitement des contraintes inégalités en font un modèle fiable et robusteThe electric utility industry is undergoing a process of liberalization and deregulation. In this context new difficulties are occurring in the field of transmission network management and optimization. In addition to the classical difficulties encountered in a monopolistic context such as the nature of the network constraints, the considerable size of the problem to be solved and the nonlinearity of the network equations, the optimization procedure has to take into account the new constraints, which are related to the deregulation of the electrical energy market. The nature of this problem requires mathematical models, which allow us the optimization of a nonlinear criterion being subject to nonlinear constraints. In this thesis we investigate two different methods in order to determine on the one hand the difficulties related to the resolution of a nonlinear optimization problem and on the other hand the difficulties related to the network operation in a deregulated environment. The first method is the so-called Newton-Lagrange method, which is applied to a simplified 5-buses network in a monopolistic context in order to achieve a technico-economical optimization. The optimization goal is the determination of the optimal power generation of each power producer to ensure the security of the system operation and to minimize the system operation costs. Even though convergence time can be considerable due to the inequality constraints, the method provides satisfactory results and will be used as a basis in the second part. A second optimization tool is developed, which is based on the primal-dual interior point method. It is applied to a 12-buses test network in order to investigate and to resolve the difficulties related to a competitive environment such as congestion and energy lasses management, the control of generation deviations and the impact of the occurrence of new independent power producers in an established network. An important advantage of this method is the capacity to treat the inequality constraints in an easy way. The reliable and robust optimization tool provides very satisfactory results
29
Primet, Maël. "Méthodes probabiliste pour le suivi de points et l'analyse d'images biologiques." Phd thesis, Université René Descartes - Paris V, 2011. http://tel.archives-ouvertes.fr/tel-00669220.
Анотація:
Nous nous intéressons dans cette thèse au problème du suivi d'objets, que nous abordons par des méthodes statistiques. La première contribution de cette thèse est la conception d'un algorithme de suivi de bactéries dans une séquence d'image et de reconstruction de leur lignage, travail ayant donné lieu à la réalisation d'une suite logicielle aujourd'hui utilisée dans un laboratoire de recherche en biologie. La deuxième contribution est une étude théorique du problème de la détection de trajectoires dans un nuage de points. Nous définissons un détecteur de trajectoires utilisant le cadre statistique des méthodes a contrario, qui ne requiert essentiellement aucun paramètre pour fonctionner. Ce détecteur fournit des résultats remarquables, et permet notamment de retrouver des trajectoires dans des séquences contenant un grand nombre de points de bruit, tout en conservant un taux de fausses détections de trajectoires très faible. Nous étudions ensuite plus spécifiquement le problème de l'affectation de nuages de points entre deux images, problème rencontré notamment pour la détection de trajectoires ou l'appariement d'images stéréographiques. Nous proposons d'abord un modèle théoriquement optimal pour l'affectation de points qui nous permet d'étudier les performances de plusieurs algorithmes classiques dans différentes conditions. Nous formulons ensuite un algorithme sans paramètre en utilisant le cadre a contrario, ce qui nous permet ensuite d'obtenir un nouvel algorithme de suivi de trajectoires.
30
Demarche, Cyril. "Méthodes cohomologiques pour l’étude des points rationnels sur les espaces homogènes." Paris 11, 2009. http://www.theses.fr/2009PA112146.
31
Primet, Maël. "Méthodes probabilistes pour le suivi de points et l'analyse d'images biologiques." Paris 5, 2011. http://www.theses.fr/2011PA05S009.
Анотація:
Nous nous intéressons dans cette thèse au problème du suivi d’objets, que nous abordons par des méthodes statistiques. La première contribution de cette thèse est la conception d’un algorithme de suivi de bactéries dans une séquence d’image et de reconstruction de leur lignage, travail ayant donné lieu à la réalisation d’une suite logicielle aujourd’hui utilisée dans un laboratoire de recherche en biologie. La deuxième contribution est une étude théorique du problème de la détection de trajectoires dans un nuage de points. Nous définissons un détecteur de trajectoires utilisant le cadre statistique des méthodes a contrario, qui ne requiert essentiellement aucun paramètre pour fonctionner. Ce détecteur fournit des résultats remarquables, et permet notamment de retrouver des trajectoires dans des séquences contenant un grand nombre de points de bruit, tout en conservant un taux de fausses détections de trajectoires très faible. Nous étudions ensuite plus spécifiquement le problème de l’affectation de nuages de points entre deux images, problème rencontré notamment pour la détection de trajectoires ou l’appariement d’images stéréographiques. Nous proposons d’abord un modèle théoriquement optimal pour l’affectation de points qui nous permet d’étudier les performances de plusieurs algorithmes classiques dans différentes conditions. Nous formulons ensuite un algorithme sans paramètre en utilisant le cadre a contrario, ce qui nous permet ensuite d’obtenir un nouvel algorithme de suivi de trajectoiresThe subject of this thesis is the problem of object tracking, that we approached using statistical methods. The first contribution of this work is the conception of a tracking algorithm of bacterial cells in a sequence of image, to recover their lineage; this work has led to the implementation of a software suite that is currently in use in a research laboratory. The second contribution is a theoretical study of the detection of trajectories in a cloud of points. We define a trajectory detector using the a-contrario statistical framework, which requires essentially no parameter to run. This detector yields remarkable results, and is in particular able to detect trajectories in sequences containing a large number of noise points, while keeping a very low number of false detections. We then study more specifically the correspondence problem between two point clouds, a problem often encountered for the detection of trajectories or the matching of stereographic images. We first introduce a theoretically optimal model for the point correspondence problem that makes it possible to study the performances of several classical algorithms in a variety of conditions. We then formulate a parameterless point correspondence algorithm using the a-contrario framework, that enables us to define a new trajectory tracking algorithm
32
Calenge, Clément. "Des outils statistiques pour l'analyse des semis de points dans l'espace écologique." Lyon 1, 2005. http://www.theses.fr/2005LYO10264.
Анотація:
La mise en relation d'un ou de plusieurs semis de points avec des cartes de variables environnementales est centrale en Écologie. Les points représentent en général des localisations d'individus d'une ou de plusieurs espèces. Cette thèse présente une démarche pour identifier les variables environnementales qui sont les plus structurantes de la distribution des points. Elle repose sur l'exploration des données dans l'espace géographique et dans l'espace défini par les variables environnementales (espace écologique). L'analyse d'un seul semis et celle de plusieurs semis de points sont considérées. Des collaborations ont permis de développer ou d'améliorer des outils d'analyse spatiale (analyse discriminante sur vecteurs propres du graphe de voisinage) ou écologique (ENFA, analyse K-select, analyse factorielle des rapports de sélection), reposant sur la théorie de l'analyse factorielle. Une bibliothèque de fonctions pour le logiciel R, adehabitat, a été programmée pour faciliter cette démarche d'analyse
33
Castro, Pedro Machado Manhães de. "Méthodes pour accélérer les triangulations de Delaunay." Nice, 2010. https://tel.archives-ouvertes.fr/tel-00531765.
Анотація:
Cette thèse propose de nouvelles méthodes pour accélérer certaines des plus importantes opérations dans une triangulation de Delaunay, conciliant efficacité et bonne complexité théorique. Nous proposons deux approches pour calculer la triangulation de Delaunay de points sur (ou proches) d’une sphère. La première approche calcule la triangulation de Delaunay de points exactement sur la sphère par construction. La deuxième approche calcule directement l’enveloppe convexe de l’ensemble d’entrée, et donne quelques garanties sur la sortie. Les deux approches sont basées sur la triangulation régulière sur la sphère. La deuxième approche améliore les solutions de l’état de l’art. L'opération de mise à jour d’une triangulation de Delaunay, quand les sommets bougent, est critique dans plusieurs domaines d’applications. Quand tous les sommets bougent, reconstruire toute la triangulation est étonnamment une bonne solution en pratique. Toutefois, lorsque les points se déplacent très peu, ou si seulement une fraction des sommets bouge, la reconstruction n’est plus la meilleure option. Nous proposons un système de filtrage basé sur le concept de tolérance d’un sommet. Nous avons mené plusieurs expériences pour évaluer le comportement de l’algorithme sur des ensembles de données variés. Les expériences ont montré que l’algorithme est particulièrement pertinent pour les régimes convergents tels que les itérations de Lloyd. En dimension deux, l’algorithme présenté est un ordre de grandeur plus rapide que la reconstruction pour les itérations de Lloyd. En dimension trois, l’algorithme présenté a des performances équivalentes à la reconstruction quand tous les sommets bougent, cependant il est entièrement dynamique et améliore les solutions dynamiques précédentes. Ce résultat permet d’aller plus loin dans le nombre d’itérations de façon à produire des maillages de qualité supérieure. La localisation de points dans une subdivision de l’espace est un classique de la géométrie algorithmique; nous réexaminons ce problème dans le cas des triangulations de R^d pour exploiter une éventuelle cohérence entre les requêtes. Nous analysons, implémentons, et évaluons une strategie de localisation de point adaptable aux distributions des requêtes, basée sur Jump & Walk, appel- lée Keep, Jump, & Walk. Pour des paquets de requêtes, l’idée principale est d’utiliser les requêtes précédentes pour améliorer le traitement de la requête courante. Maintenant à propos de la complexité d’une requête dans une triangulation de Delaunay, nous montrons que la hiérarchie de Delaunay peut être utilisée pour localiser un point q à partir d’une requête précédente p avec une complexité randomisée O(log #(pq)) pourvu que la triangulation vérifie certaines hypothèses (#(s) désigne le nombre de simplex traversés par le segment s). Finalement, nous combinons la bonne adaptabilité à la distribution des requêtes du Keep, Jump, & Walk, et la bonne complexité de la hiérarchie de Delaunay, en une nouvelle stratégie de localisation de points appellée Keep, Jump, & Climb. Selon nos connaissances, Keep, Jump, & Climb est le premier algorithme adaptable aux distributions des requêtes qui marche en pratique et en théorie pour les triangulations de Delaunay—dans nos expérimentations, Keep, Jump, & Climb est plus rapide que la hiérarchie de Delaunay independament de la cohérence spatiale des requêtes, et significativement plus rapide quand la cohérence spatiale est forteThis thesis proposes several new practical ways to speed-up some of the most important operations in a Delaunay triangulation. We propose two approaches to compute a Delaunay triangulation for points on or close to a sphere. The first approach computes the Delaunay triangulation of points placed exactly on the sphere. The second approach directly computes the convex hull of the input set, and gives some guarantees on the output. Both approaches are based on the regular triangulation on the sphere. The second approach outperforms previous solutions. Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a viable option compared to relocating the vertices. However, when all points move with a small magnitude, or when only a fraction of the vertices moves, rebuilding is no longer the best option. We propose a filtering scheme based upon the concept of vertex tolerances. We conducted several experiments to showcase the behavior of the algorithm for a variety of data sets. The experiments showed that the algorithm is particularly relevant for convergent schemes such as the Lloyd iterations. In two dimensions, the algorithm presented performs up to an order of magnitude faster than rebuilding for Lloyd iterations. In three dimensions, although rebuilding the whole triangulation at each time stamp when all vertices move can be as fast as our algorithm, our solution is fully dynamic and outperforms previous dynamic solutions. This result makes it possible to go further on the number of iterations so as to produce higher quality meshes. Point location in spatial subdivision is one of the most studied problems in computational geometry. In the case of triangulations of R^d, we revisit the problem to exploit a possible coherence between the query points. We analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical Jump & Walk, called Keep, Jump, & Walk. For a batch of query points, the main idea is to use previous queries to improve the retrieval of the current one. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log #(pq)) randomized expected complexity, where p is a previously located query and #(s) indicates the number of simplices crossed by the line segment s. We combine the good distribution-sensitive behavior of Keep, Jump, & Walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called Keep, Jump, & Climb. To the best of our knowledge, Keep, Jump, & Climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations---in our experiments, it is faster than the Delaunay hierarchy regardless of the spatial coherence of queries, and significantly faster when queries have reasonable spatial coherence
34
Surroca, Ortiz Andrea. "Méthodes de transcendance et géométrie diophantienne." Paris 6, 2003. http://www.theses.fr/2003PA066313.
35
AKOA, François. "APPROCHES DE POINTS INTERIEURS ET DE LA PROGRAMMATION DC EN OPTIMISATION NON CONVEXE. CODES ET SIMULATIONS NUMERIQUES INDUSTRIELLES." Phd thesis, INSA de Rouen, 2005. http://tel.archives-ouvertes.fr/tel-00008475.
Анотація:
Cette thèse est principalement consacrée à l'association des méthodes de points intérieurs et des techniques de l'optimisation DC et DCA pour résoudre les problèmes d'optimisation non convexes de grande taille.La thèse comporte trois parties :
la première partie est consacrée aux techniques d'optimisations locales et s'articule autour des méthodes de points intérieurs et de la programmation DC. Nous y développons deux algorithmes. Après une présentation non exhaustive de la programmation DC, des méthodes de points intérieurs et des propriétés essentielles de la classe des matrices quasi-définies au chapitre un, nous présentons au chapitre deux un nouvel algorithme basé sur une reformulation des conditions d'optimalité de Karush-Kuhn-Tucker. Le troisième chapitre est consacré à l'intégration des techniques d'optimisation DC dans un schéma de points intérieurs, c'est l'algorithme IPDCA.
La seconde partie de la thèse est consacrée aux solutions globales de problèmes de programmation quadratique. Dans le premier chapitre de cette partie nous explorons l'intégration d'IPDCA dans un schéma B&B. Le second chapitre de la partie est consacré à la résolution de problèmes quadratiques à variables 0-1 par un schéma B\&B dans lequel nous faisons intervenir IPDCA. Le troisième chapitre est quant à lui consacré à l'optimisation monotone due au Professeur Tuy. Nous examinons plus particulièrement son intégration dans un B&B dans lequelle DCA est appelé pour améliorer la borne supérieure.
Le quatrième et dernier chapitre de cette partie est consacré à une procédure de redémarrage de DCA.
La dernière partie de la thèse est consacrée aux applications industrielles. Nous y appliquons les deux algorithmes développés dans la première partie de la thèse à un problème de mécanique de structure de grande dimension et à un problème en Data Mining.
36
Calvet, Lilian. "Méthodes de reconstruction tridimensionnelle intégrant des points cycliques : application au suivi d’une caméra." Phd thesis, Toulouse, INPT, 2014. http://oatao.univ-toulouse.fr/11901/1/Calvet.pdf.
Анотація:
Cette thèse traite de la reconstruction tridimensionnelle d’une scène rigide à partir d’une collection de photographies numériques, dites vues. Le problème traité est connu sous le nom du "calcul de la structure et du mouvement" (structure-and/from-motion) qui consiste à "expliquer" des trajectoires de points dits d’intérêt au sein de la collection de vues par un certain mouvement de l’appareil (dont sa trajectoire) et des caractéristiques géométriques tridimensionnelles de la scène. Dans ce travail, nous proposons les fondements théoriques pour étendre certaines méthodes de calcul de la structure et du mouvement afin d’intégrer comme données d’entrée, des points d’intérêt réels et des points d’intérêt complexes, et plus précisément des images de points cycliques. Pour tout plan projectif, les points cycliques forment une paire de points complexes conjugués qui, par leur invariance par les similitudes planes, munissent le plan projectif d’une structure euclidienne. Nous introduisons la notion de marqueurs cycliques qui sont des marqueurs plans permettant de calculer sans ambiguïté les images des points cycliques de leur plan de support dans toute vue. Une propriété de ces marqueurs, en plus d’être très "riches" en information euclidienne, est que leurs images peuvent être appariées même si les marqueurs sont disposés arbitrairement sur des plans parallèles, grâce à l’invariance des points cycliques. Nous montrons comment utiliser cette propriété dans le calcul projectif de la structure et du mouvement via une technique matricielle de réduction de rang, dite de factorisation, de la matrice des données correspondant aux images de points réels, complexes et/ou cycliques. Un sous-problème critique abordé dans le calcul de la structure et du mouvement est celui de l’auto-calibrage de l’appareil, problème consistant à transformer un calcul projectif en un calcul euclidien. Nous expliquons comment utiliser l’information euclidienne fournie par les images des points cycliques dans l’algorithme d’auto-calibrage opérant dans l’espace projectif dual et fondé sur des équations linéaires. L’ensemble de ces contributions est finalement utilisé pour une application de suivi automatique de caméra utilisant des marqueurs formés par des couronnes concentriques (appelés CCTags), où il s’agit de calculer le mouvement tridimensionnel de la caméra dans la scène à partir d’une séquence vidéo. Ce type d’application est généralement utilisé dans l’industrie du cinéma ou de la télévision afin de produire des effets spéciaux. Le suivi de caméra proposé dans ce travail a été conçu pour proposer le meilleur compromis possible entre flexibilité d’utilisation et précision des résultats obtenus.
37
Calvet, Lilian. "Méthodes de reconstruction tridimensionnelle intégrant des points cycliques : application au suivi d'une caméra." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2014. http://tel.archives-ouvertes.fr/tel-00981191.
Анотація:
Cette thèse traite de la reconstruction tridimensionnelle d'une scène rigide à partir d'une collection de photographies numériques, dites vues. Le problème traité est connu sous le nom du "calcul de la structure et du mouvement" (structure-and/from-motion) qui consiste à "expliquer" des trajectoires de points dits d'intérêt au sein de la collection de vues par un certain mouvement de l'appareil (dont sa trajectoire) et des caractéristiques géométriques tridimensionnelles de la scène. Dans ce travail, nous proposons les fondements théoriques pour étendre certaines méthodes de calcul de la structure et du mouvement afin d'intégrer comme données d'entrée, des points d'intérêt réels et des points d'intérêt complexes, et plus précisément des images de points cycliques. Pour tout plan projectif, les points cycliques forment une paire de points complexes conjugués qui, par leur invariance par les similitudes planes, munissent le plan projectif d'une structure euclidienne. Nous introduisons la notion de marqueurs cycliques qui sont des marqueurs plans permettant de calculer sans ambiguïté les images des points cycliques de leur plan de support dans toute vue. Une propriété de ces marqueurs, en plus d'être très "riches" en information euclidienne, est que leurs images peuvent être appariées même si les marqueurs sont disposés arbitrairement sur des plans parallèles, grâce à l'invariance des points cycliques. Nous montrons comment utiliser cette propriété dans le calcul projectif de la structure et du mouvement via une technique matricielle de réduction de rang, dite de factorisation, de la matrice des données correspondant aux images de points réels, complexes et/ou cycliques. Un sous-problème critique abordé dans le calcul de la structure et du mouvement est celui de l'auto-calibrage de l'appareil, problème consistant à transformer un calcul projectif en un calcul euclidien. Nous expliquons comment utiliser l'information euclidienne fournie par les images des points cycliques dans l'algorithme d'auto-calibrage opérant dans l'espace projectif dual et fondé sur des équations linéaires. L'ensemble de ces contributions est finalement utilisé pour une application de suivi automatique de caméra utilisant des marqueurs formés par des couronnes concentriques (appelés CCTags), où il s'agit de calculer le mouvement tridimensionnel de la caméra dans la scène à partir d'une séquence vidéo. Ce type d'application est généralement utilisé dans l'industrie du cinéma ou de la télévision afin de produire des effets spéciaux. Le suivi de caméra proposé dans ce travail a été conçu pour proposer le meilleur compromis possible entre flexibilité d'utilisation et précision des résultats obtenus.
38
Czarnecki, Marc-Olivier. "Méthodes d’approximation pour des problèmes non différentiables : application à l’existence de points fixes." Paris 1, 1996. http://www.theses.fr/1996PA010075.
39
Bouju, Alain. "Etiquetage et poursuite de points caractéristiques d'un objet 3D par des méthodes connexionistes." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0017.
Анотація:
Cette thèse porte sur la poursuite et l'étiquetage des points caractéristiques d'un objet en déplacement. Pour cet objectif nous avons fait coopérer trois réseaux connexionnistes. Nous avons d'abord utilisé un algorithme de classification non supervisé. Puis nous avons utilisé et adapté un algorithme de diagnostic pour améliorer la classification. Finalement, en nous inspirant des techniques d'optimisation utilisées pour résoudre le problème du voyageur de commerce, nous avons développé un algorithme permettant d'associer deux ensembles de points en minimisant les déformations. Nous avons utilisé avec de bons résultats ces algorithmes pour le suivi des points caractéristiques d'un avion et nous avons appliqué l'algorithme d'association de points pour différents types d'images. Nous avons fait des essais sur des images satellitaires, des images R. M. N. Et des images d'objets.
40
Bornschlegell, Augusto Salomao. "Optimisation aérothermique d'un alternateur à pôles saillants pour la production d'énergie électrique décentralisée." Thesis, Valenciennes, 2012. http://www.theses.fr/2012VALE0023/document.
Анотація:
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étiquesThis 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
41
Bronschlegell, Augusto. "Optimisation aérothermique d'un alternateur à pôles saillants pour la production d'énergie électrique décentralisée." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2012. http://tel.archives-ouvertes.fr/tel-00768249.
Анотація:
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.
42
Seghir, Rachid. "Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes." Université Louis Pasteur (Strasbourg) (1971-2008), 2006. https://publication-theses.unistra.fr/public/theses_doctorat/2006/SEGHIR_Rachid_2006.pdf.
Анотація:
Le modèle polyédrique est un formalisme utilisé en optimisation automatique de programmes. Il permet notamment de représenter les itérations et les références à des tableaux, dans des nids de boucles affines, par des points à coordonnées entières de polyèdres bornés, ou Z-polytopes (paramétrés). Dans cette thèse, trois nouveaux algorithmes de dénombrement ont été développés : des points entiers dans un Z-polytope paramétré, dans une union non disjointe de Z-polytopes paramétrés et dans leurs images par des fonctions affines. Le résultat de ces dénombrements est donné par un ou plusieurs polynômes multivariable à coefficients périodiques. Ces polynômes, connus sous le nom de quasi-polynômes d’Ehrhart, sont définis sur des sous-ensembles de valeurs des paramètres, dits domaines de validité. De nombreuses méthodes d’analyse et d’optimisation de nids de boucles affines font appel à ces algorithmes. Nous les avons en particulier appliqués à la linéarisation de tableaux, dont l’objectif est la compression mémoire et l’amélioration de la localité spatiale. Outre l’optimisation de programmes, les algorithmes proposés ont des applications dans bien d’autres domaines, tels que les mathématiques et l’économieThe polyhedral model is a well-known framework in the field of automatic program optimization. Iterations and array references in affine loop nests are represented by integer points in bounded polyhedra, or (parametric) Z-polytopes. In this thesis, three new counting algorithms have been developed: counting integer points in a parametric Z-polytope, in a union of parametric Z-polytopes and in their images by affine functions. The result of such a counting is given by one or many multivariate polynomials in which the coefficients may be periodic numbers. These polynomials, known as Ehrhart quasipolynomials, are defined on sub-sets of the parameter values called validity domains or chambers. Many affine loop nest analysis and optimization methods require such counting algorithms. We applied them in array linearization which achieves memory compression and improves spatial locality of accessed data. Besides program optimization, the proposed algorithms have many other applications, as in mathematics and economics
43
Itier, Vincent. "Nouvelles méthodes de synchronisation de nuages de points 3D pour l'insertion de données cachées." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS017/document.
Анотація:
Cette thèse aborde les problèmes liés à la protection de maillages d'objets 3D. Ces objets peuvent, par exemple, être créés à l'aide d'outil de CAD développés par la société STRATEGIES. Dans un cadre industriel, les créateurs de maillages 3D ont besoin de disposer d'outils leur permettant de vérifier l'intégrité des maillages, ou de vérifier des autorisations pour l'impression 3D par exemple. Dans ce contexte nous étudions l'insertion de données cachées dans des maillages 3D. Cette approche permet d'insérer de façon imperceptible et sécurisée de l'information dans un maillage. Il peut s'agir d'un identifiant, de méta-informations ou d'un contenu tiers, par exemple, pour transmettre de façon secrète une texture. L'insertion de données cachées permet de répondre à ces problèmes en jouant sur le compromis entre la capacité, l'imperceptibilité et la robustesse. Généralement, les méthodes d'insertion de données cachées se composent de deux phases, la synchronisation et l'insertion. La synchronisation consiste à trouver et ordonner les éléments disponibles pour l'insertion. L'un des principaux challenges est de proposer une méthode de synchronisation 3D efficace qui définit un ordre sur les composants des maillages. Dans nos travaux, nous proposons d'utiliser les sommets du maillage, plus précisément leur représentation géométrique dans l'espace comme composants de base pour la synchronisation et l'insertion. Nous présentons donc trois nouvelles méthodes de synchronisation de la géométrie des maillages basées sur la construction d'un chemin hamiltonien dans un nuage de sommets. Deux de ces méthodes permettent de manière conjointe de synchroniser les sommets et de cacher un message. Cela est possible grâce à deux nouvelles méthodes d'insertion haute capacité (de $3$ à $24$ bits par sommet) qui s'appuient sur la quantification des coordonnées. Dans ces travaux nous mettons également en évidence les contraintes propres à ce type de synchronisation. Nous discutons des différentes approches proposées dans plusieurs études expérimentales. Nos travaux sont évalués sur différents critères dont la capacité et l'imperceptibilité de la méthode d'insertion. Nous portons également notre attention aux aspects sécurité des méthodesThis thesis addresses issues relating to the protection of 3D object meshes. For instance, these objects can be created using CAD tool developed by the company STRATEGIES. In an industrial context, 3D meshes creators need to have tools in order to verify meshes integrity, or check permission for 3D printing for example.In this context we study data hiding on 3D meshes. This approach allows us to insert information in a secure and imperceptible way in a mesh. This may be an identifier, a meta-information or a third-party content, for instance, in order to transmit secretly a texture. Data hiding can address these problems by adjusting the trade-off between capacity, imperceptibility and robustness. Generally, data hiding methods consist of two stages, the synchronization and the embedding. The synchronization stage consists of finding and ordering available components for insertion. One of the main challenges is to propose an effective synchronization method that defines an order on mesh components. In our work, we propose to use mesh vertices, specifically their geometric representation in space, as basic components for synchronization and embedding. We present three new synchronisation methods based on the construction of a Hamiltonian path in a vertex cloud. Two of these methods jointly perform the synchronization stage and the embedding stage. This is possible thanks to two new high-capacity embedding methods (from 3 to 24 bits per vertex) that rely on coordinates quantization. In this work we also highlight the constraints of this kind of synchronization. We analyze the different approaches proposed with several experimental studies. Our work is assessed on various criteria including the capacity and imperceptibility of the embedding method. We also pay attention to security aspects of the proposed methods
44
Keraghel, Abdelkrim. "Étude adaptative et comparative des principales variantes dans l'algorithme de Karmarkar." Phd thesis, Grenoble 1, 1989. http://tel.archives-ouvertes.fr/tel-00332749.
Анотація:
Après une description de la méthode de Karmarkar, il est montré que la valeur du pas de déplacement peut être largement améliorée. Les principales difficultés pratiques de la méthode sont discutées. Plus particulièrement, l'hypothèse de connaitre, au départ, la valeur optimale de l'objectif. Diverses extensions et variantes sont étudiées dans le but de relaxer l'hypothèse ci-dessus
45
De, Castro Pedro. "Méthodes pour accélérer les triangulations de Delaunay." Phd thesis, Université de Nice Sophia-Antipolis, 2010. http://tel.archives-ouvertes.fr/tel-00531765.
Анотація:
Cette thèse propose de nouvelles méthodes pour accélérer certaines des plus importantes opérations dans une triangulation de Delaunay, conciliant efficacité et bonne complexité théorique. Nous proposons deux approches pour calculer la triangulation de Delaunay de points sur (ou proches) d'une sphère. La première approche calcule la triangulation de Delaunay de points exactement sur la sphère par construction. La deuxième approche calcule directement l'enveloppe convexe de l'ensemble d'entrée, et donne quelques garanties sur la sortie. Les deux approches sont basées sur la triangulation régulière sur la sphère. La deuxième approche améliore les solutions de l'état de l'art. L'operation de mise à jour d'une triangulation de Delaunay, quand les sommets bougent, est critique dans plusieurs domaines d'applications. Quand tous les sommets bougent, reconstruire toute la triangulation est étonnamment une bonne solution en pratique. Toutefois, lorsque les points se déplacent tres peu, ou si seulement une fraction des sommets bougent, la reconstruction n'est plus la meilleure option. Nous proposons un système de filtrage basé sur le concept de tolérance d'un sommet. Nous avons mené plusieurs expériences pour évaluer le comportement de l'algorithme sur des ensembles de données variés. Les expériences ont montré que l'algorithme est particulièrement pertinent pour les régimes convergents tels que les itérations de Lloyd. En dimension deux, l'algorithme présenté est un ordre de grandeur plus rapide que la reconstruction pour les itérations de Lloyd. En dimension trois, l'algorithme présenté a des performances équivalentes à la reconstruction quand tous les sommets bougent, cependant il est entièrement dynamique et améliore les solutions dynamiques précédentes. Ce résultat permet d'aller plus loin dans le nombre d'itérations de façon à produire des maillages de qualité supérieure. La localisation de points dans une subdivision de l'espace est un classique de la géométrie algorithmique; nous réexaminons ce problème dans le cas des triangulations de Rd pour exploiter une éventuelle cohérence entre les requêtes. Nous analysons, implementons, et évaluons une strategie de localisation de point adaptable aux distributions des requêtes, basée sur Jump & Walk, appellée Keep, Jump, &Walk. Pour des paquets de requêtes, l'idée principale est d'utiliser les requêtes précédentes pour améliorer le traitement de la requête courante. Maintenant à propos de la complexité d'une requête dans une triangulation de Delaunay, nous montrons que la hiérarchie de Delaunay peut être utilisée pour localiser un point q à partir d'une requête précédente p avec une complexité randomisée O(log ](pq)) pourvu que la triangulation vérifie certaines hypothèses (](s) désigne le nombre de simplex traversés par le segment s). Finalement, nous combinons la bonne adaptabilité à la distribution des requêtes du Keep, Jump, & Walk, et la bonne complexité de la hiérarchie de Delaunay, en une nouvelle stratégie de localisation de points appellée Keep, Jump, & Climb. Selon nos connaissances, Keep, Jump, & Climb est le premier algorithme adaptable aux distributions des requêtes qui marche en pratique et en théorie pour les triangulations de Delaunay--dans nos expérimentations, Keep, Jump, & Climb est plus rapide que la hiérarchie de Delaunay indépendamment de la cohérence spatiale des requêtes, et significativement plus rapide quand la cohérence spatiale est forte.
46
Arnaud, Elise. "Méthodes de filtrage pour du suivi dans des équences d'images. Application au suivi de points caractéristiques." Rennes 1, 2004. http://www.theses.fr/2004REN10101.
Анотація:
Cette étude traite de l'utilisation de méthodes de filtrage pour du suivi dans des séquences d'images. Ces algorithmes reposent sur une représentation du système par une chaîne de Markov cachée, décrite par une dynamique et une vraisemblance. Pour construire une méthode générale, une loi dynamique estimée sur les images est considérée. Ce choix met en évidence les limitations du modèle simple de chaîne de Markov cachée, qui ne décrit pas la dépendance des éléments du système aux images. Nous proposons d'abord une modélisation originale du problème. Celle-ci rend les images explicites et permet de construire des algorithmes sans information a priori. Les filtres associés à cette nouvelle représentation sont dérivés. Ensuite, nous nous intéressons à la validation de cette modélisation. Trois méthodes de suivi de points sont construits. Ils associent des mesures de corrélation à une dynamique définie à partir d'un mouvement estimé. Enfin, cette approche est étendue au suivi de plans.
47
Guillemot, Thierry. "Méthodes et structures non locales pour la restaurationd'images et de surfaces 3D." Thesis, Paris, ENST, 2014. http://www.theses.fr/2014ENST0006/document.
Анотація:
Durant ces dernières années, les technologies d’acquisition numériques n’ont cessé de se perfectionner, permettant d’obtenir des données d’une qualité toujours plus fine. Néanmoins, le signal acquis reste corrompu par des défauts qui ne peuvent être corrigés matériellement et nécessitent l’utilisation de méthodes de restauration adaptées. J'usqu’au milieu des années 2000, ces approches s’appuyaient uniquement sur un traitement local du signal détérioré. Avec l’amélioration des performances de calcul, le support du filtre a pu être étendu à l’ensemble des données acquises en exploitant leur caractère autosimilaire. Ces approches non locales ont principalement été utilisées pour restaurer des données régulières et structurées telles que des images. Mais dans le cas extrême de données irrégulières et non structurées comme les nuages de points 3D, leur adaptation est peu étudiée à l’heure actuelle. Avec l’augmentation de la quantité de données échangées sur les réseaux de communication, de nouvelles méthodes non locales ont récemment été proposées. Elles utilisent un modèle a priori extrait à partir de grands ensembles d’échantillons pour améliorer la qualité de la restauration. Néanmoins, ce type de méthode reste actuellement trop coûteux en temps et en mémoire. Dans cette thèse, nous proposons, tout d’abord, d’étendre les méthodes non locales aux nuages de points 3D, en définissant une surface de points capable d’exploiter leur caractère autosimilaire. Nous introduisons ensuite une nouvelle structure de données, le CovTree, flexible et générique, capable d’apprendre les distributions d’un grand ensemble d’échantillons avec une capacité de mémoire limitée. Finalement, nous généralisons les méthodes de restauration collaboratives appliquées aux données 2D et 3D, en utilisant notre CovTree pour apprendre un modèle statistique a priori à partir d’un grand ensemble de donnéesIn recent years, digital technologies allowing to acquire real world objects or scenes have been significantly improved in order to obtain high quality datasets. However, the acquired signal is corrupted by defects which can not be rectified materially and require the use of adapted restoration methods. Until the middle 2000s, these approaches were only based on a local process applyed on the damaged signal. With the improvement of computing performance, the neighborhood used by the filter has been extended to the entire acquired dataset by exploiting their self-similar nature. These non-local approaches have mainly been used to restore regular and structured data such as images. But in the extreme case of irregular and unstructured data as 3D point sets, their adaptation is few investigated at this time. With the increase amount of exchanged data over the communication networks, new non-local methods have recently been proposed. These can improve the quality of the restoration by using an a priori model extracted from large data sets. However, this kind of method is time and memory consuming. In this thesis, we first propose to extend the non-local methods for 3D point sets by defining a surface of points which exploits their self-similar of the point cloud. We then introduce a new flexible and generic data structure, called the CovTree, allowing to learn the distribution of a large set of samples with a limited memory capacity. Finally, we generalize collaborative restoration methods applied to 2D and 3D data by using our CovTree to learn a statistical a priori model from a large dataset
48
Atallah, Nabil. "Analyse des méthodes itératives par points pour les problèmes de diffusion-convection approchés par les schémas compacts." Toulouse 3, 2002. http://www.theses.fr/2002TOU30010.
Анотація:
Le contexte de ce travail est celui des problèmes de diffusion-convection modélisés par les équations de Navier-Strokes linéaires, précisemment l'approximation par différences finies des problèmes fortement convectifs. Dans ce cadre, les limites d'utilisation des schémas de base, centré d'ordre 2 instable, décentré d'ordre 1 présentant une forte viscosité artificielle nous ont amenés à l'étude des schémas compacts d'ordre 4 (à 3 points en 1D et 9 points en 2D). Le pricipal objectif est l'étude et la résolution des systèmes linéaires associés. La prémière partie concernent les problèmes monodimensionnels. Dans ce contexte nous avons obtenude nouveaux résultats : estimation du conditionnement des systèmes linéaires associés, conditions suffisantes de convergence de la méthode Sor et mise en évidence du rôle du sens de parcours en liaison avec les caractéristiques de propagation du modèle. . . .
49
Pouliquen, Mathieu. "De l'identification des systèmes : points de vue sur les méthodes des sous-espaces, identification pour la commande." Caen, 2003. http://www.theses.fr/2003CAEN2074.
Анотація:
Ce travail est principalement motivé par l’identification des systèmes multivariables pour la synthèse des systèmes de commande linéaire. Il comprend trois parties indépendantes et complémentaires. La première partie est consacrée aux méthodes d’identification en boucle ouverte par l’approche des sous-espaces. Cette approche permet d’élaborer un modèle de commande sous forme d’une réalisation d’état. Deux méthodes ont été utilisées pour ce faire, selon que l’on adopte une approche du type erreur de sortie ou erreur de prédiction. Chacune de ces méthodes est caractérisée par un critère d’identification directement inspiré des méthodes d’identification usuelles. On montre que les méthodes des sous espaces proposées dans la littérature peuvent être conçues dans un contexte d’erreur de sortie ou d’erreur de prédiction. La seconde partie traite du problème d’interaction entre l’identification et la commande dans le contexte d’une synthèse H2. L’importance d’une identification en boucle fermée du modèle de commande est particulièrement mise en évidence. Un algorithme d’identification d’un régulateur à ordre réduit est proposé pour des considérations de souplesse de mise en œuvre. La dernière partie est dédiée au problème d’identification en boucle fermée à partir des méthodes des sous-espaces. Après une formulation du problème d’identification en boucle fermée par la méthode des sous espaces, trois classes d’ algorithmes d’identification sont proposées pour le résoudre selon l’approche adoptée, notamment une méthode directe, indirecte ou simultanée.
50
Guillemot, Thierry. "Méthodes et structures non locales pour la restaurationd'images et de surfaces 3D." Electronic Thesis or Diss., Paris, ENST, 2014. http://www.theses.fr/2014ENST0006.
Анотація:
Durant ces dernières années, les technologies d’acquisition numériques n’ont cessé de se perfectionner, permettant d’obtenir des données d’une qualité toujours plus fine. Néanmoins, le signal acquis reste corrompu par des défauts qui ne peuvent être corrigés matériellement et nécessitent l’utilisation de méthodes de restauration adaptées. J'usqu’au milieu des années 2000, ces approches s’appuyaient uniquement sur un traitement local du signal détérioré. Avec l’amélioration des performances de calcul, le support du filtre a pu être étendu à l’ensemble des données acquises en exploitant leur caractère autosimilaire. Ces approches non locales ont principalement été utilisées pour restaurer des données régulières et structurées telles que des images. Mais dans le cas extrême de données irrégulières et non structurées comme les nuages de points 3D, leur adaptation est peu étudiée à l’heure actuelle. Avec l’augmentation de la quantité de données échangées sur les réseaux de communication, de nouvelles méthodes non locales ont récemment été proposées. Elles utilisent un modèle a priori extrait à partir de grands ensembles d’échantillons pour améliorer la qualité de la restauration. Néanmoins, ce type de méthode reste actuellement trop coûteux en temps et en mémoire. Dans cette thèse, nous proposons, tout d’abord, d’étendre les méthodes non locales aux nuages de points 3D, en définissant une surface de points capable d’exploiter leur caractère autosimilaire. Nous introduisons ensuite une nouvelle structure de données, le CovTree, flexible et générique, capable d’apprendre les distributions d’un grand ensemble d’échantillons avec une capacité de mémoire limitée. Finalement, nous généralisons les méthodes de restauration collaboratives appliquées aux données 2D et 3D, en utilisant notre CovTree pour apprendre un modèle statistique a priori à partir d’un grand ensemble de donnéesIn recent years, digital technologies allowing to acquire real world objects or scenes have been significantly improved in order to obtain high quality datasets. However, the acquired signal is corrupted by defects which can not be rectified materially and require the use of adapted restoration methods. Until the middle 2000s, these approaches were only based on a local process applyed on the damaged signal. With the improvement of computing performance, the neighborhood used by the filter has been extended to the entire acquired dataset by exploiting their self-similar nature. These non-local approaches have mainly been used to restore regular and structured data such as images. But in the extreme case of irregular and unstructured data as 3D point sets, their adaptation is few investigated at this time. With the increase amount of exchanged data over the communication networks, new non-local methods have recently been proposed. These can improve the quality of the restoration by using an a priori model extracted from large data sets. However, this kind of method is time and memory consuming. In this thesis, we first propose to extend the non-local methods for 3D point sets by defining a surface of points which exploits their self-similar of the point cloud. We then introduce a new flexible and generic data structure, called the CovTree, allowing to learn the distribution of a large set of samples with a limited memory capacity. Finally, we generalize collaborative restoration methods applied to 2D and 3D data by using our CovTree to learn a statistical a priori model from a large dataset