Le classique TSP et ses variantes n'ont peut-être pas encore livré tous leurs secrets. Il suffit pour s'en convaincre de ré-écrire le problème de minimisation sous sa forme matricielle. La solution de ce problème consiste finalement à chercher la matrice de permutation optimale des villes.
Or, chercher directement une matrice par des méthodes d'optimisation a reçu depuis quelques années maintenant un regain d'intérêt dû à une meilleure appropriation des outils de géométrie différentielle. En particulier, l'ensemble dans lequel vit la dite matrice recherchée possède une structure de variété différentielle (ou de sous-variété). Il s'agit donc d'opérer une optimisation sur cette variété en définissant naturellement des flots, qui dans notre cas seront des flots de gradient. La minimisation peut être alors traitée de manière continue. Plus « magique » encore, les flots qui définissent l'optimisation sont étroitement liés au système physique assez répandu qu'est le système de Toda. Cette analogie permet alors d'utiliser un certain nombre de résultats issus de cette approche pour caractériser des preuves de convergence des algorithmes vers les matrices optimales et d'entrevoir également de nouvelles méthodes.
Dans cet exposé, qui se veut néanmoins pédagogique, seront traités d'une part dans une première partie les notions et définitions essentielles de la géométrie différentielle pour la résolution du problème de TSP, puis dans un second temps l'analogie du problème avec le système de Toda.
We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. First we derive a convergence rate in O(1/k) for the Cutting Plane algorithm in the case where the objective function is strongly convex, and under a strict feasibility assumption.
Second we propose a new approach to solve these semi-infinite programs, that generates a sequence of feasible solutions. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the semi-infinite program.
We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an Inner-Outer Approximation Algorithm, and its value converges to the value of the original semi-infinite program.
This new algorithmic approach is tested on two applications (a constrained quadratic regression and a zero-sum game with cubic payoff) and compared with the classical Cutting Plane algorithm, the Mitsos algorithm and the KKT-based relaxation approach.