Dans de nombreux domaines tels que l’apprentissage statistique, la recherche opérationnelle ou encore la conception de circuits, une tâche est modélisée par un jeu de paramètres que l’on cherche à optimiser pour prendre la meilleure décision possible. Mathématiquement, le problème revient à minimiser une fonction de l’objectif recherché par des algorithmes itératifs. Le développement de ces derniers dépend alors de la géométrie de la fonction ou de la structure du problème. Dans une première partie, cette thèse étudie comment l’acuité d’une fonction autour de ses minima peut être exploitée par le redémarrage d’algorithmes classiques. Les schémas optimaux sont présentés pour des problèmes convexes généraux. Ils nécessitent cependant une description complète de la fonction, ce qui est rarement disponible. Des stratégies adaptatives sont donc développées et prouvées être quasi-optimales. Une analyse spécifique est ensuite conduite pour les problèmes parcimonieux qui cherchent des représentations compressées des variables du problème. Leur géométrie conique sous-jacente, qui décrit l’acuité de la fonction de l’objectif, se révèle contrôler à la fois la performance statistique du problème et l’efficacité des procédures d’optimisation par une seule quantité. Une seconde partie est dédiée aux problèmes d’apprentissage statistique. Ceux-ci effectuent une analyse prédictive de données à l’aide d’un large nombre d’exemples. Une approche générique est présentée pour à la fois résoudre le problème de prédiction et le simplifier en groupant soit les variables, les exemples ou les tâches. Des méthodes algorithmiques systématiques sont développées en analysant la géométrie induite par une partition des données. Une analyse théorique est finalement conduite lorsque les variables sont groupées par analogie avec les méthodes parcimonieuses. / In numerous fields such as machine learning, operational research or circuit design, a task is modeled by a set of parameters to be optimized in order to take the best possible decision. Formally, the problem amounts to minimize a function describing the desired objective with iterative algorithms. The development of these latter depends then on the characterization of the geometry of the function or the structure of the problem. In a first part, this thesis studies how sharpness of a function around its minimizers can be exploited by restarting classical algorithms. Optimal schemes are presented for general convex problems. They require however a complete description of the function that is rarely available. Adaptive strategies are therefore developed and shown to achieve nearly optimal rates. A specific analysis is then carried out for sparse problems that seek for compressed representation of the variables of the problem. Their underlying conic geometry, that describes sharpness of the objective, is shown to control both the statistical performance of the problem and the efficiency of dedicated optimization methods by a single quantity. A second part is dedicated to machine learning problems. These perform predictive analysis of data from large set of examples. A generic framework is presented to both solve the prediction problem and simplify it by grouping either features, samples or tasks. Systematic algorithmic approaches are developed by analyzing the geometry induced by partitions of the data. A theoretical analysis is then carried out for grouping features by analogy to sparse methods.

Dans cette thèse, nous nous étudions des algorithmes d’optimisation non linéaire. D’une part nous proposons des techniques de détection rapide de la non-réalisabilité d’un problème à résoudre. D’autre part, nous analysons le comportement local des algorithmes pour la résolution de problèmes singuliers. Dans la première partie, nous présentons une modification d’un algorithme de lagrangien augmenté pour l’optimisation avec contraintes d’égalité. La convergence quadratique du nouvel algorithme dans le cas non-réalisable est démontrée théoriquement et numériquement. La seconde partie est dédiée à l’extension du résultat précédent aux problèmes d’optimisation non linéaire généraux avec contraintes d’égalité et d’inégalité. Nous proposons une modification d’un algorithme de pénalisation mixte basé sur un lagrangien augmenté et une barrière logarithmique. Les résultats théoriques de l’analyse de convergence et quelques tests numériques montrent l’avantage du nouvel algorithme dans la détection de la non-réalisabilité. La troisième partie est consacrée à étudier le comportement local d’un algorithme primal-dual de points intérieurs pour l’optimisation sous contraintes de borne. L’analyse locale est effectuée sans l’hypothèse classique des conditions suffisantes d’optimalité de second ordre. Celle-ci est remplacée par une hypothèse plus faible basée sur la notion de borne d’erreur locale. Nous proposons une technique de régularisation de la jacobienne du système d’optimalité à résoudre. Nous démontrons ensuite des propriétés de bornitude de l’inverse de ces matrices régularisées, ce qui nous permet de montrer la convergence superlinéaire de l’algorithme. La dernière partie est consacrée à l’analyse de convergence locale de l’algorithme primal-dual qui est utilisé dans les deux premières parties de la thèse. En pratique, il a été observé que cet algorithme converge rapidement même dans le cas où les contraintes ne vérifient l’hypothèse de qualification de Mangasarian-Fromovitz. Nous démontrons la convergence superlinéaire et quadratique de cet algorithme, sans hypothèse de qualification des contraintes. / This thesis is devoted to the study of numerical algorithms for nonlinear optimization. On the one hand, we propose new strategies for the rapid infeasibility detection. On the other hand, we analyze the local behavior of primal-dual algorithms for the solution of singular problems. In the first part, we present a modification of an augmented Lagrangian algorithm for equality constrained optimization. The quadratic convergence of the new algorithm in the infeasible case is theoretically and numerically demonstrated. The second part is dedicated to extending the previous result to the solution of general nonlinear optimization problems with equality and inequality constraints. We propose a modification of a mixed logarithmic barrier-augmented Lagrangian algorithm. The theoretical convergence results and the numerical experiments show the advantage of the new algorithm for the infeasibility detection. In the third part, we study the local behavior of a primal-dual interior point algorithm for bound constrained optimization. The local analysis is done without the standard assumption of the second-order sufficient optimality conditions. These conditions are replaced by a weaker assumption based on a local error bound condition. We propose a regularization technique of the Jacobian matrix of the optimality system. We then demonstrate some boundedness properties of the inverse of these regularized matrices, which allow us to prove the superlinear convergence of our algorithm. The last part is devoted to the local convergence analysis of the primal-dual algorithm used in the first two parts of this thesis. In practice, it has been observed that this algorithm converges rapidly even in the case where the constraints do not satisfy the Mangasarian-Fromovitz constraint qualification. We demonstrate the superlinear and quadratic convergence of this algorithm without any assumption of constraint qualification.