Spelling suggestions: "subject:"méthode d'homotopia"" "subject:"méthode d'homotopic""
1 |
Algorithmes d'ensemble actif pour le LASSO / Active set algorithms for the LASSOLoth, Manuel 08 July 2011 (has links)
Le LASSO est une méthode de régression ajoutant à la méthode des moindres-carrés une contrainte ou une pénalisation sur la norme l1 du coefficient linéaire. Cette contrainte a un effet de sélection de variable et de régularisation sur l'estimateur. Un estimateur LASSO est défini comme étant la solution d'un problème pouvant être vu comme un programme quadratique. Cette thèse se base sur deux algorithmes dédiés à la résolution du LASSO publiés en 2000 par M. Osbourne et alii. L'un, une méthode par homotopie, a été reformulé en 2004 par J. Friedman et alii sous le nom de LAR-LASSO (ou LARS), s'imposant alors comme la méthode standard. Le second, présenté comme une méthode d'ensemble actif, fût largement ignoré, semble-t-il pour deux raisons: une application apparemment limitée à la formulation "contrainte", et une compréhension plus difficile de l'algorithme. Nous reformulons donc le principe général du second, que nous baptisons "Descente sur Ensemble Actif" (DEA) et sa dérivation sur le LASSO, ainsi que la méthode par homotopie que nous mettons en évidence comme directement dérivée de la DEA. La formulation simplifiée des deux méthodes permet d'en améliorer la compréhension, mais aussi l'efficacité en temps de calcul. Elle met en outre en évidence l'applicabilité de la DEA sur la formulation "pénalisée" du LASSO, donnant un algorithme plus simple encore. Enfin, elle conduit à une analyse et un traitement de cas limites dans lesquels ces algorithmes peuvent échouer. Nous proposons ensuite une application directe du LASSO sur un nombre infini de variables formant un espace multidimensionel, et étudions l'adaptation des algorithmes d'ensemble actifs dans ce cadre. / The LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares methodThe LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares method. This constraint has variable-selection and a regularization effects over the estimator. The LASSO estimator is defined as a solution to a minimization problem that can be seen as a quadratic program. This thesis is based on two algorithms designed for solving the LASSO, that were published in 2000 by Osbourne et alii. One, an homotopy method, was re-formulated and popularized in 2004 by J. Friedman et alii under the name of LAR-LASSO (or LARS). The second, presented as an active set method, was largely ignored, for two main reasons: its apparent limitation to the constrained formulation, and a more difficult understanding of the algorithm. We re-formulate its general principle, under the name of "Active Set Descent", and its derivation for the LASSO problem, as well as the homotopy method, that appears as a direct extension of ASD. The simplified formulation of both methods yields a better understanding, and also a lower complexity, in terms of computation time. It also shows the direct appliability of ASD to the penalized formulation of the LASSO, in a even simpler algorithm than for the constrained one. Finally, it facilitates the analysis and workarounds of degenerate situations in which the algorithms may fail. We then propose a direct application of the LASSO on an infinite number of variables forming a multidimensional space, and study the adaptation of active set algorithms on this framework.
|
2 |
Sur l'algorithme de tir pour les problèmes de commande optimale avec contraintes sur l'étatHermant, Audrey 05 September 2008 (has links) (PDF)
Cette thèse s'intéresse au problème de commande optimale (déterministe) d'une équation différentielle ordinaire soumise à une ou plusieurs contraintes sur l'état, d'ordres quelconques, dans le cas où la condition forte de Legendre-Clebsch est satisfaite. Le principe du minimum de Pontryaguine fournit une condition d'optimalité nécessaire bien connue. Dans cette thèse, on obtient premièrement une condition d'optimalité suffisante du second ordre la plus faible possible, c'est-à-dire qu'elle est aussi proche que possible de la condition nécessaire du second ordre et caractérise la croissance quadratique. Cette condition nous permet d'obtenir une caractérisation du caractère bien posé de l'algorithme de tir en présence de contraintes sur l'état. Ensuite on effectue une analyse de stabilité et de sensibilité des solutions lorsque l'on perturbe les données du problème. Pour des contraintes d'ordre supérieur ou égal à deux, on obtient pour la première fois un résultat de stabilité des solutions ne faisant aucune hypothèse sur la structure de la trajectoire. Par ailleurs, des résultats sur la stabilité structurelle des extrémales de Pontryaguine sont donnés. Enfin, ces résultats d'une part sur l'algorithme de tir et d'autre part sur l'analyse de stabilité nous permettent de proposer, pour des contraintes sur l'état d'ordre un et deux, un algorithme d'homotopie dont la nouveauté est de déterminer automatiquement la structure de la trajectoire et d'initialiser les paramètres de tir associés.
|
Page generated in 0.0724 seconds