Search

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "negative kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "bad kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved; the notion of regularity is associated with the algorithm and is analysed with care.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

In this thesis, we consider systems of linear algebraic equations arising from discretizations of second-order elliptic partial differential equations using finite elements of arbitrary polynomial degree.In Chapter 1, we propose an a posteriori estimator for the algebraic error whose construction is inherently interconnected with the design of a multigrid solver with zero pre- and only one post-smoothing step by overlapping Schwarz (block-Jacobi) methods. The main contribution of this approach consists in the two following results and their equivalence: the solver contracts the algebraic error independently of the polynomial degree ($p$-robustness); the estimator represents a two-sided $p$-robust bound on the algebraic error. The proofs of these results hold in one, two, and three space dimensions, under the minimal $H^1$-regularity of the weak solution, for quasi-uniform meshes as well as for possibly highly graded ones, and are independent of the basis of the chosen finite element space. We introduce here an optimal step-size (by line search) in the error correction stage of the multigrid.In Chapter 2, we introduce level-wise optimal step-sizes, thus maximizing the decrease of the algebraic error on each level. Under the $H^2$-regularity assumption, we prove here that the $p$-robust contraction/efficiency also hold independently of the number of mesh levels. Apart from improving the performance of the solver, the use of the level-wise step-sizes also leads to an explicit Pythagorean formula of the decrease of the algebraic error from one iteration to the next. The formula then serves as foundation of a simple and effective adaptive strategy which allows the solver to choose the necessary number of post-smoothing steps on each level.In Chapter 3, we introduce an adaptive local smoothing strategy thanks to our efficient a posteriori estimator, which has the important property of being localized level-wise and patch-wise. Thus, the estimator can detect and mark which patches of elements among all mesh levels contribute more than a user prescribed percentage to the global algebraic error (via a bulk-chasing criterion). Each iteration of the adaptive solver is here composed of two sub-steps: after a first non-adaptive V-cycle, a second adaptive and inexpensive V-cycle employs local smoothing only in the marked patches. We prove that each of these sub-steps contracts the algebraic error $p$-robustly.Finally, in Chapter 4, we provide an extension of the above results to the case of the mixed finite element method discretization in two space dimensions.A variety of numerical tests is presented to confirm the theoretical findings of this thesis, as well as to show the benefits of our $p$-robust and/or adaptive solver approaches.; Dans cette thèse, nous considérons des systèmes d’équations algébriques linéaires provenant de discrétisation d’équations aux dérivées partielles elliptiques de second ordre par des éléments finis de degré polynomial arbitraire.Dans le Chapitre 1 nous proposons un estimateur a posteriori pour l’erreur algébrique, la construction duquel est intrinsèquement liée à celle d’un solveur multigrille avec zéro pas de pré-lissage et seulement un pas de post-lissage par des méthodes de Schwarz (bloc-Jacobi) avec recouvrement. Les contributions principales de cette approche portent sur les deux résultats suivants ainsi que leur équivalence : le solveur contracte l’erreur algébrique indépendamment du degré polynomial ($p$-robustesse) ; l’estimateur représente une borne $p$-robuste supérieure et inférieure de l’erreur algébrique. Les preuves de ces résultats sont valables en un, deux, et trois dimensions d’espace, sous l’hypothèse de régularité minimale $H^1$ de la solution faible, pour des maillages quasi-uniformes ou bien des maillages issus de raffinements adaptatifs par bissection, et sont indépendantes de la base de l’espace d’éléments finis choisie. Nous introduisons ici un pas optimal (par recherche linéaire) de l’étape de correction d’erreur de multigrille.Dans le Chapitre 2 nous introduisons des pas optimaux par niveau, ainsi maximisant la réduction d’erreur algébrique à chaque niveau. Sous hypothèse de régularité $H^2$, nous prouvons ici que la contraction/efficacité $p$-robuste sont aussi indépendants du nombre de niveaux dans la hiérarchie de maillages. En plus de l’amélioration des performances du solveur, l’utilisation des pas optimaux par niveau conduit également à une formule de Pythagore explicite de la réduction de l’erreur algébrique d’une itération à l’autre. La formule sert alors de fondement pour une stratégie adaptative simple et efficace qui permet au solveur de choisir le nombre nécessaire de pas de post-lissage à chaque niveau.Dans le Chapitre 3 nous introduisons une stratégie de lissage local adaptatif grâce à notre estimateur efficace a posteriori, qui a la propriété importante d’être localisé par niveaux et par patchs d’éléments. Ainsi, l’estimateur peut détecter et marquer quels patchs d’éléments parmi tous les niveaux contribuent plus qu’un pourcentage prescrit par l’utilisateur de l’erreur algébrique globale (via un critère de type bulk-chasing). Chaque itération du solveur adaptatif est ici composée de deux sous-étapes: après un premier V-cycle non adaptatif, un deuxième V-cycle adaptatif et peu coûteux n’utilise le lissage local que dans les patchs marqués. Nous prouvons que chacune de ces sous-étapes contracte l’erreur algébrique de manière $p$-robuste.Pour terminer, dans le Chapitre 4 nous donnons des extensions des résultats ci-dessus au cadre d’éléments finis mixtes en deux dimensions d’espace.Une variété de tests numériques est présentée pour confirmer les résultats théoriques de cette thèse, ainsi que pour montrer les avantages de nos approches $p$-robustes et/ou d’adaptivité de solveurs algébriques.

In this thesis, we consider systems of linear algebraic equations arising from discretizations of second-order elliptic partial differential equations using finite elements of arbitrary polynomial degree. In Chapter 1, we propose an a posteriori estimator for the algebraic error whose construction is inherently interconnected with the design of a multigrid solver with zero pre- and only one post-smoothing step by overlapping Schwarz (block-Jacobi) methods. The main contribution of this approach consists in the two following results and their equivalence: the solver contracts the algebraic error independently of the polynomial degree ($p$-robustness); the estimator represents a two-sided $p$-robust bound on the algebraic error. The proofs of these results hold in one, two, and three space dimensions, under the minimal $H^1$-regularity of the weak solution, for quasi-uniform meshes as well as for possibly highly graded ones, and are independent of the basis of the chosen finite element space. We introduce here an optimal step-size (by line search) in the error correction stage of the multigrid. In Chapter 2, we introduce level-wise optimal step-sizes, thus maximizing the decrease of the algebraic error on each level. Under the $H^2$-regularity assumption, we prove here that the $p$-robust contraction/efficiency also hold independently of the number of mesh levels. Apart from improving the performance of the solver, the use of the level-wise step-sizes also leads to an explicit Pythagorean formula of the decrease of the algebraic error from one iteration to the next. The formula then serves as foundation of a simple and effective adaptive strategy which allows the solver to choose the necessary number of post-smoothing steps on each level. In Chapter 3, we introduce an adaptive local smoothing strategy thanks to our efficient a posteriori estimator, which has the important property of being localized level-wise and patch-wise. Thus, the estimator can detect and mark which patches of elements among all mesh levels contribute more than a user prescribed percentage to the global algebraic error (via a bulk-chasing criterion). Each iteration of the adaptive solver is here composed of two sub-steps: after a first non-adaptive V-cycle, a second adaptive and inexpensive V-cycle employs local smoothing only in the marked patches. We prove that each of these sub-steps contracts the algebraic error $p$-robustly. Finally, in Chapter 4, we provide an extension of the above results to the case of the mixed finite element method discretization in two space dimensions. A variety of numerical tests is presented to confirm the theoretical findings of this thesis, as well as to show the benefits of our $p$-robust and/or adaptive solver approaches., Dans cette thèse, nous considérons des systèmes d’équations algébriques linéaires provenant de discrétisation d’équations aux dérivées partielles elliptiques de second ordre par des éléments finis de degré polynomial arbitraire. Dans le Chapitre 1 nous proposons un estimateur a posteriori pour l’erreur algébrique, la construction duquel est intrinsèquement liée à celle d’un solveur multigrille avec zéro pas de pré-lissage et seulement un pas de post-lissage par des méthodes de Schwarz (bloc-Jacobi) avec recouvrement. Les contributions principales de cette approche portent sur les deux résultats suivants ainsi que leur équivalence : le solveur contracte l’erreur algébrique indépendamment du degré polynomial ($p$-robustesse) ; l’estimateur représente une borne $p$-robuste supérieure et inférieure de l’erreur algébrique. Les preuves de ces résultats sont valables en un, deux, et trois dimensions d’espace, sous l’hypothèse de régularité minimale $H^1$ de la solution faible, pour des maillages quasi-uniformes ou bien des maillages issus de raffinements adaptatifs par bissection, et sont indépendantes de la base de l’espace d’éléments finis choisie. Nous introduisons ici un pas optimal (par recherche linéaire) de l’étape de correction d’erreur de multigrille. Dans le Chapitre 2 nous introduisons des pas optimaux par niveau, ainsi maximisant la réduction d’erreur algébrique à chaque niveau. Sous hypothèse de régularité $H^2$, nous prouvons ici que la contraction/efficacité $p$-robuste sont aussi indépendants du nombre de niveaux dans la hiérarchie de maillages. En plus de l’amélioration des performances du solveur, l’utilisation des pas optimaux par niveau conduit également à une formule de Pythagore explicite de la réduction de l’erreur algébrique d’une itération à l’autre. La formule sert alors de fondement pour une stratégie adaptative simple et efficace qui permet au solveur de choisir le nombre nécessaire de pas de post-lissage à chaque niveau. Dans le Chapitre 3 nous introduisons une stratégie de lissage local adaptatif grâce à notre estimateur efficace a posteriori, qui a la propriété importante d’être localisé par niveaux et par patchs d’éléments. Ainsi, l’estimateur peut détecter et marquer quels patchs d’éléments parmi tous les niveaux contribuent plus qu’un pourcentage prescrit par l’utilisateur de l’erreur algébrique globale (via un critère de type bulk-chasing). Chaque itération du solveur adaptatif est ici composée de deux sous-étapes: après un premier V-cycle non adaptatif, un deuxième V-cycle adaptatif et peu coûteux n’utilise le lissage local que dans les patchs marqués. Nous prouvons que chacune de ces sous-étapes contracte l’erreur algébrique de manière $p$-robuste. Pour terminer, dans le Chapitre 4 nous donnons des extensions des résultats ci-dessus au cadre d’éléments finis mixtes en deux dimensions d’espace. Une variété de tests numériques est présentée pour confirmer les résultats théoriques de cette thèse, ainsi que pour montrer les avantages de nos approches $p$-robustes et/ou d’adaptivité de solveurs algébriques.

International audience; The plain Newton-min algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an M-matrix, but not when it is a P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an M-matrix, where n is the number of variables, but often much faster in practice). In 1990, Harker and Pang proposed to improve the convergence ability of this algorithm by introducing a stepsize along the Newton-min direction that results in a jump over at least one of the encountered kinks of the min-function, in order to avoid its points of nondifferentiability. This paper shows that, for the Fathi problem (an LCP with a positive definite symmetric matrix M, hence a P-matrix), an algorithmic scheme, including the algorithm of Harker and Pang, may require n iterations to converge, depending on the starting point.; L'algorithme de Newton-min standard pour résoudre le problème de complémentarité linéaire (PCL) 0 ≤ x ⊥ (Mx+q) ≥ 0 peut être vu comme une instance de la méthode de Newton semi-lisse agissant sur la formulation équationnelle min(x,Mx+q) = 0 du problème. Cet algorithme converge, quel que soit q, lorsque M est une M-matrice, mais pas lorsque M est une P-matrice. En cas de convergence, celle-ci est souvent très rapide (en moins de n itérations pour une M-matrice, où n est le nombre de variables, mais souvent bien plus rapidement en pratique). En 1990, Harker et Pang ont proposé d'améliorer la capacité de converger de cet algorithme en introduisant un pas le long de la direction de Newton-min qui se traduit par un saut au-dessus d'au moins le premier pli de la fonction min rencontré, de manière à éviter ses points de non-différentiabilité. Cet article montre que, pour le problème de Fathi (un PCL avec une matrice M symétrique définie positive, donc une P-matrice), un schéma algorithmique, incluant l'algorithme de Harker et Pang, peut requérir n itérations pour converger, une propriété qui dépend du point de départ.

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "bad kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved; the notion of regularity is associated with the algorithm and is analysed with care.; L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit être intérieur à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenus en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "mauvais plis" de la fonction minimum et d'agir en conséquence.De manière à éviter au si souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale vers des points régulier est démontrée; la notion de régularité est associée à l'algorithme et est analysée avec soin.

The plain Newton-min algorithm can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the linear complementarity problem (LCP) $"0 ≤ x ⊥ (Mx+q) ≥ 0"$. This algorithm converges, whatever is q, when M is an M-matrix, but not when it is a P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an M-matrix, where n is the number of variables, but often much faster in practice). In 1990, Harker and Pang proposed to improve the convergence ability of this algorithm by introducing a stepsize along the Newton-min direction that results in a small jump over the first encountered kink of the min-function, in order to avoid its points of nondifferentiability. This paper shows that, for the Fathi problem (an LCP with a positive definite symmetric matrix M, hence a P-matrix), an algorithmic scheme, including the algorithm of Harker and Pang, may require n iterations to converge, depending on the starting point.; L'algorithme de Newton-min peut être vu comme une instance de la méthode de Newton semi-lisse agissant sur la formulation équationnelle min(x,Mx+q) = 0 du problème de complémentarité linéaire (PCL) $0 ≤ x ⊥ (Mx+q) ≥ 0$. Cet algorithme converge, quel que soit q, lorsque M est une M-matrice, mais pas lorsque M est une P-matrice. En cas de convergence, celle-ci est souvent très rapide (en moins de n itérations pour une M-matrice, où n est le nombre de variables, mais souvent bien plus rapidement en pratique). En 1990, Harker et Pang ont proposé d'améliorer la capacité de converger de cet algorithme en introduisant un pas le long de la direction de Newton-min qui se traduit par une petit saut au-dessus du premier pli de la fonction min rencontré, de manière à éviter ses points de non-différentiabilité. Cet article montre que, pour le problème de Fathi (un PCL avec une matrice M symétrique définie positive, donc une P-matrice), un schéma algorithmique, incluant l'algorithme de Harker et Pang, peut requérir n itérations pour converger.

Parmi les méthodes d’estimation de paramètres de loi de probabilité en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions l´egères, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problèmes de maximum de vraisemblance peuvent être traités comme des problèmes de programmation non linéaires, éventuellement non convexe, pour lesquels deux grandes classes de méthodes de résolution sont les techniques de région de confiance et les méthodes de recherche linéaire. En outre, il est possible d’exploiter la structure de ces problèmes pour tenter d’accélerer la convergence de ces méthodes, sous certaines hypothèses. Dans ce travail, nous revisitons certaines approches classiques ou récemment d´eveloppées en optimisation non linéaire, dans le contexte particulier de l’estimation de maximum de vraisemblance. Nous développons également de nouveaux algorithmes pour résoudre ce problème, reconsidérant différentes techniques d’approximation de hessiens, et proposons de nouvelles méthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linéaire. Il s’agit notamment d’algorithmes nous permettant de changer d’approximation de hessien et d’adapter la longueur du pas dans une direction de recherche fixée. Finalement, nous évaluons l’efficacité numérique des méthodes proposées dans le cadre de l’estimation de modèles de choix discrets, en particulier les modèles logit mélangés., Maximum likelihood is one of the most popular techniques to estimate the parameters of some given distributions. Under slight conditions, the produced estimators are consistent and asymptotically efficient. Maximum likelihood problems can be handled as non-linear programming problems, possibly non convex, that can be solved for instance using line-search methods and trust-region algorithms. Moreover, under some conditions, it is possible to exploit the structures of such problems in order to speedup convergence. In this work, we consider various non-linear programming techniques, either standard or recently developed, within the maximum likelihood estimation perspective. We also propose new algorithms to solve this estimation problem, capitalizing on Hessian approximation techniques and developing new methods to compute steps, in particular in the context of line-search approaches. More specifically, we investigate methods that allow us switching between Hessian approximations and adapting the step length along the search direction. We finally assess the numerical efficiency of the proposed methods for the estimation of discrete choice models, more precisely mixed logit models.

This PhD thesis explains the recent issue concerning the resolution of high-dimensional problems. We present methods designed to solve them, and their applications for feature selection problems, in the data mining field. In the first part of this thesis, we introduce the stakes of solving high-dimensional problems. We mainly investigate line search methods, because we consider them to be particularly suitable for solving such problems. Then, we present the methods we developed, based on this principle : CUS, EUS and EM323. We emphasize, in particular, the very high convergence speed of CUS and EUS, and their simplicity of implementation. The EM323 method is based on an hybridization between EUS and a one-dimensional optimization algorithm developed by F. Glover : the 3-2-3 algorithm. We show that the results of EM323 are more accurate, especially for non-separable problems, which are the weakness of line search based methods. In the second part, we focus on data mining problems, and especially those concerning microarray data analysis. The objectives are to classify data and to predict the behavior of new samples. A collaboration with the Tenon Hospital in Paris allows us to analyze their private breast cancer data. To this end, we develop an exact method, called delta-test, enhanced by a method designed to automatically select the optimal number of variables. In a second time, we develop an heuristic, named ABEUS, based on the optimization of the DLDA classifier performances. The results obtained from publicly available data show that our methods manage to select very small subsets of variables, which is an important criterion to avoid overfitting, Cette thèse expose la problématique récente concernant la résolution de problèmes de grande dimension. Nous présentons les méthodes permettant de les résoudre ainsi que leurs applications, notamment pour la sélection de variables dans le domaine de la fouille de données. Dans la première partie de cette thèse, nous exposons les enjeux de la résolution de problèmes de grande dimension. Nous nous intéressons principalement aux méthodes de recherche linéaire, que nous jugeons particulièrement adaptées pour la résolution de tels problèmes. Nous présentons ensuite les méthodes que nous avons développées, basées sur ce principe : CUS, EUS et EM323. Nous soulignons en particulier la très grande vitesse de convergence de CUS et EUS, ainsi que leur simplicité de mise en oeuvre. La méthode EM323 est issue d'une hybridation entre la méthode EUS et un algorithme d'optimisation unidimensionnel développé par F. Glover : l'algorithme 3-2-3. Nous montrons que ce dernier algorithme obtient des résultats d'une plus grande précision, notamment pour les problèmes non séparables, qui sont le point faible des méthodes issues de la recherche linéaire. Dans une deuxième partie, nous nous intéressons aux problèmes de fouille de données, et plus particulièrement l'analyse de données de puces à ADN. Le but est de classer ces données et de prédire le comportement de nouveaux exemples. Dans un premier temps, une collaboration avec l'hôpital Tenon nous permet d'analyser des données privées concernant le cancer du sein. Nous développons alors une méthode exacte, nommée delta-test, enrichie par la suite d'une méthode permettant la sélection automatique du nombre de variables. Dans un deuxième temps, nous développons une méthode heuristique de sélection de variables, nommée ABEUS, basée sur l'optimisation des performances du classifieur DLDA. Les résultats obtenus sur des données publiques montrent que nos méthodes permettent de sélectionner des sous-ensembles de variables de taille très faible,ce qui est un critère important permettant d'éviter le sur-apprentissage

This PhD thesis explains the recent issue concerning the resolution of high-dimensional problems. We present methods designed to solve them, and their applications for feature selection problems, in the data mining field. In the first part of this thesis, we introduce the stakes of solving high-dimensional problems. We mainly investigate line search methods, because we consider them to be particularly suitable for solving such problems. Then, we present the methods we developed, based on this principle : CUS, EUS and EM323. We emphasize, in particular, the very high convergence speed of CUS and EUS, and their simplicity of implementation. The EM323 method is based on an hybridization between EUS and a one-dimensional optimization algorithm developed by F. Glover : the 3-2-3 algorithm. We show that the results of EM323 are more accurate, especially for non-separable problems, which are the weakness of line search based methods. In the second part, we focus on data mining problems, and especially those concerning microarray data analysis. The objectives are to classify data and to predict the behavior of new samples. A collaboration with the Tenon Hospital in Paris allows us to analyze their private breast cancer data. To this end, we develop an exact method, called delta-test, enhanced by a method designed to automatically select the optimal number of variables. In a second time, we develop an heuristic, named ABEUS, based on the optimization of the DLDA classifier performances. The results obtained from publicly available data show that our methods manage to select very small subsets of variables, which is an important criterion to avoid overfitting, Cette thèse expose la problématique récente concernant la résolution de problèmes de grande dimension. Nous présentons les méthodes permettant de les résoudre ainsi que leurs applications, notamment pour la sélection de variables dans le domaine de la fouille de données. Dans la première partie de cette thèse, nous exposons les enjeux de la résolution de problèmes de grande dimension. Nous nous intéressons principalement aux méthodes de recherche linéaire, que nous jugeons particulièrement adaptées pour la résolution de tels problèmes. Nous présentons ensuite les méthodes que nous avons développées, basées sur ce principe : CUS, EUS et EM323. Nous soulignons en particulier la très grande vitesse de convergence de CUS et EUS, ainsi que leur simplicité de mise en oeuvre. La méthode EM323 est issue d'une hybridation entre la méthode EUS et un algorithme d'optimisation unidimensionnel développé par F. Glover : l'algorithme 3-2-3. Nous montrons que ce dernier algorithme obtient des résultats d'une plus grande précision, notamment pour les problèmes non séparables, qui sont le point faible des méthodes issues de la recherche linéaire. Dans une deuxième partie, nous nous intéressons aux problèmes de fouille de données, et plus particulièrement l'analyse de données de puces à ADN. Le but est de classer ces données et de prédire le comportement de nouveaux exemples. Dans un premier temps, une collaboration avec l'hôpital Tenon nous permet d'analyser des données privées concernant le cancer du sein. Nous développons alors une méthode exacte, nommée delta-test, enrichie par la suite d'une méthode permettant la sélection automatique du nombre de variables. Dans un deuxième temps, nous développons une méthode heuristique de sélection de variables, nommée ABEUS, basée sur l'optimisation des performances du classifieur DLDA. Les résultats obtenus sur des données publiques montrent que nos méthodes permettent de sélectionner des sous-ensembles de variables de taille très faible,ce qui est un critère important permettant d'éviter le sur-apprentissage

This 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 its performance are comparable with the reference codes l-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 is 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., 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.