Une méthode de linéarisation robuste pour les problèmes de complémentarité. Un détour par les arrangements d'hyperplans

Le but initial de cette thèse est la résolution de problèmes de complémentarité. Ces problèmes sont reformulés ici par la C-fonction minimum, qui est linéaire par morceaux, donc non différentiable, ce qui conduit à des systèmes d'équations non lisses à résoudre. La globalisation de méthodes pseudo-linéarisant de telles équations (Newton semi-lisse par exemple) se heurte généralement à la difficulté que les directions calculées ne sont pas nécessairement de descente pour la fonction de mérite associée, utilisée par les méthodes de recherche linéaire (alors que dans le cas d'équations différentiables, l'opposé du gradient de la fonction de mérite convient toujours).Dans le cas de la C-fonction minimum, une méthode récente remplace la direction de pseudo-linéarisation par une direction trouvée dans un polyèdre convexe adapté. Cependant, pour s'assurer que tous les points stationnaires de la suite générée soient solutions du problème, ceux-ci doivent vérifier une condition de régularité contraignante. Celle-ci assure alors que polyèdre convexe n'est pas vide dans le voisinage de tels points. L'objectif initial de cette thèse était de se libérer de cette hypothèse de régularité, comme pour les systèmes lisses, en utilisant l'approche de Levenberg-Marquardt. Le caractère différentiable par morceaux de la fonction de mérite induit par la C-fonction minimum implique de devoir choisir un certain morceau, et cette thèse propose, dans son chapitre 6, une approche sur cette question, via des observations géométriques permettant une description de la difficulté de la tâche. En cherchant à mieux comprendre cette méthode et à analyser le B(ouligand)-différentiel de la fonction minimum, qui y joue un rôle central, il est apparu, dans les cas simples de problèmes linéaires (ou affines), que la structure inhérente à ce B-différentiel est celle d'un arrangement d'hyperplans. Ce problème très classique en géométrie combinatoire, que nous avons découvert à cette occasion, s'est révélé surprenamment riche et profond (ce que les spécialistes de ce domaine savaient parfaitement). Nous proposons, aux chapitres 3 et 5, une analyse en lien avec la question des méthodes non lisses ainsi que des améliorations sur un algorithme de l'état de l'art identifiant les chambres. En particulier, des variantes ``(primales-)duales'', reliant explicitement les chambres d'un arrangement et les circuits du matroïde associé, semblent prometteuses. Ce long détour, qui constitue la majeure partie du manuscrit, s'est révélé instructif pour l'algorithme non lisse et le choix du ``morceau'' -- la linéarisation des fonctions faisant apparaître un (B-)différentiel du minimum de fonctions affines -- mais nous pensons surtout que cela a permis de mettre en lumière des liens intéressants entre non-différentiabilité et géométrie combinatoire.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.