Tropical aspects of linear programming

Pascal Benchimol 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Résumé : Cette thèse présente de nouveaux résultats de complexité concernant d'un côté la programmation linéaire classique, et de l'autre la programmation linéaire tropicale, cette dernière étant reliée aux jeux répétés. Les contributions proviennent de l'étude du processus de déquantisation qui relie ces deux problèmes. La déquantisation transforme les programmes linéaires classiques en programmes linéaires sur des semi-anneaux tropicaux, comme l'ensemble $\R \cup \{ - \infty \}$ muni de $\max$ en tant qu'addition, et de $+$ en tant que multiplication. Concernant la complexité de la programmation linéaire, notre première contribution est la tropicalisation de la méthode du simplexe. Plus précisément, nous décrivons une implémentation de la méthode du simplexe qui, sous des conditions de généricité, résoud un programme linéaire sur un corps ordonné. Cette implémentation utilise seulement l'information partielle donnée par la valuation, ce qui correspond aux ``ordres de grandeur'' des coefficients du problème. Cette approche permet de construire une classe de programmes linéaires réels sur lesquels la méthode du simplexe termine en un nombre d'itérations qui est polynomial en la taille de l'encodage binaire du problème, et ce indépendamment du choix de la régle de pivotage. Notre deuxième contribution concerne les méthodes de points intérieurs pour la programmation linéaire classique. Nous réfutons l'analogue continu de la conjecture de Hirsch proposé par Deza, Terlaky et Zinchenko, en construisant une famille de programmes linéaires décrits par $3r+4$ inégalités sur $2r+2$ variables pour lesquels le chemin central a une courbure totale qui est exponentielle en $r$. La tropicalisation du chemin central présente des propriétés inattendues. Par exemple, le chemin central tropical peut être décrit de manière purement géométrique, alors que de manière classique le chemin central dépend de la représentation des contraintes. De plus, le chemin central tropical peut rencontrer la frontière de la tropicalisation de l'ensemble réalisable, et peut même co\"incider avec un chemin suivi par la méthode du simplexe tropical. Concernant la programmation linéaire tropicale et les jeux répétés, notre résultat principal est une nouvelle méthode pour résoudre ces problèmes, basée sur la tropicalisation de la méthode du simplexe. Cette dernière résoud directement les programmes linéaires tropicaux satisfaisant des conditions de généricités. Afin de résoudre les problèmes ne satisfaisant pas ces conditions, une technique de perturbation est utilisée. L'idée principale est d'utiliser des semi-anneaux tropicaux basés sur des groupes de vecteurs ordonnées lexicographiquement. Nous transférons des résultats de complexité de la programmation linéaire classique vers la programmation linéaire tropicale. Nous montrons que l'existence d'une règle de pivotage polynomiale pour la méthode du simplexe classique fournirai un algorithme polynomial pour la programmation linéaire tropicale, et donc pour les jeux répétés. En transférant l'analyse de Adler, Karp et Shamir de la régle de pivotage dite du ``shadow-vertex'', nous obtenons le premier algorithme qui résoud les jeux répétés en temps polynomial en moyenne, en supposant que la distribution des jeux satisfait une propriété d'invariance. Nous établissons une correspondance géométrique entre les cellules d'un arrangement d'hyperplans classiques et leur tropicalisation. Ceci donne une interprétation géométrique à la tropicalisation de la méthode du simplexe. Comme dans le cas classique, l'algorithme tropical pivote sur le graphe d'un arrangement d'hyperplans associé au polyèdre. Ce point de vue géométrique nous permet d'établir des raffinements algorithmiques de l'opération de pivotage tropical. Nous présentons un algorithme qui pivote le long d'une arête d'un polyèdre tropical défini par $m$ inégalités en dimension $n$ en temps $O(n(m+n))$. Nous montrons aussi que le calcul des signes des coûts réduits peut se faire tropicalement en temps $O(n(m+n))$
Type de document :
Thèse
Optimization and Control [math.OC]. Ecole Polytechnique, 2014. English
Liste complète des métadonnées

Littérature citée [146 références]  Voir  Masquer  Télécharger

https://hal-polytechnique.archives-ouvertes.fr/tel-01198482
Contributeur : Pascal Benchimol <>
Soumis le : dimanche 13 septembre 2015 - 15:48:20
Dernière modification le : mercredi 25 avril 2018 - 10:45:37
Document(s) archivé(s) le : mardi 29 décembre 2015 - 01:04:31

Fichier

Identifiants

  • HAL Id : tel-01198482, version 1

Collections

Citation

Pascal Benchimol. Tropical aspects of linear programming. Optimization and Control [math.OC]. Ecole Polytechnique, 2014. English. 〈tel-01198482〉

Partager

Métriques

Consultations de la notice

372

Téléchargements de fichiers

266