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