This dissertation presents recent contributions in tropical geometry with a view towards positivity, and on certain semialgebraic sets which are constructed from polytopes. Tropical geometry is an emerging field in mathematics, combining elements of algebraic geometry and polyhedral geometry. A key in establishing this bridge is the concept of tropicalization, which is often described as mapping an algebraic variety to its 'combinatorial shadow'. This shadow is a polyhedral complex and thus allows to study the algebraic variety by combinatorial means. Recently, the positive part, i.e. the intersection of the variety with the positive orthant, has enjoyed rising attention. A driving question in recent years is: Can we characterize the tropicalization of the positive part? In this thesis we introduce the novel notion of positive-tropical generators, a concept which may serve as a tool for studying positive parts in tropical geometry in a combinatorial fashion. We initiate the study of these as positive analogues of tropical bases, and extend our theory to the notion of signed-tropical generators for more general signed tropicalizations. Applying this to the tropicalization of determinantal varieties, we develop criteria for characterizing their positive part. Motivated by questions from optimization, we focus on the study of low-rank matrices, in particular matrices of rank 2 and 3. We show that in rank 2 the minors form a set of positive-tropical generators, which fully classifies the positive part. In rank 3 we develop the starship criterion, a geometric criterion which certifies non-positivity. Moreover, in the case of square-matrices of corank 1, we fully classify the signed tropicalization of the determinantal variety, even beyond the positive part. Afterwards, we turn to the study of polytropes, which are those polytopes that are both tropically and classically convex. In the literature they are also established as alcoved polytopes of type A. We describe methods from toric geometry for computing multivariate versions of volume, Ehrhart and h^*-polynomials of lattice polytropes. These algorithms are applied to all polytropes of dimensions 2,3 and 4, yielding a large class of integer polynomials. We give a complete combinatorial description of the coefficients of volume polynomials of 3-dimensional polytropes in terms of regular central subdivisions of the fundamental polytope, which is the root polytope of type A. Finally, we provide a partial characterization of the analogous coefficients in dimension 4. In the second half of the thesis, we shift the focus to study semialgebraic sets by combinatorial means. Intersection bodies are objects arising in geometric tomography and are known not to be semialgebraic in general. We study intersection bodies of polytopes and show that such an intersection body is always a semialgebraic set. Computing the irreducible components of the algebraic boundary, we provide an upper bound for the degree of these components. Furthermore, we give a full classification for the convexity of intersection bodies of polytopes in the plane. Towards the end of this thesis, we move to the study of a problem from game theory, considering the correlated equilibrium polytope $P_G$ of a game G from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes, and prove that it is a semialgebraic set for any game. Through the use of oriented matroid strata, we propose a structured method for classifying the possible combinatorial types of $P_G$, and show that for (2 x n)-games, the algebraic boundary of each stratum is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for (2 x 3)-games.:Introduction 1. Background 2. Tropical Positivity and Determinantal Varieties 3. Multivariate Volume, Ehrhart, and h^*-Polynomials of Polytropes 4. Combinatorics of Correlated Equilibria

Tout p-cycle tropical VT de Rn, on attache naturellement un courant fermé (p, p) dimensionnel d'ordre 0 sur (C)n, noté Tp n(VT). Un tel "courant tropical" T p n(VT) ne saurait etre le courant d'intégration sur un quelconque sous-ensemble analytique de (C)n du fait qu'il a pour support l'ensemble log-1(VT) (C)n, où l'application Log désigne la multivluation (Z1, ..., Zn) 7! (logIZ1I, ..., logIZnI). On donne des conditions suffisantes (de nature locale) sur un p-cycle tropical VT pour le courant tropical T p n(VT) qui lui est associé soit" fortement extrémal" dans D0p, p((C)n). En particulier, si une telle condition s'avère remplie pour un p-cycle tropical effectif, alors le courant tropical qui lui est attaché est extrémal dans le cône des courants fermés de bidimension (p, p) sur (C)n. On explique ensuite comment prolonger ces courants tropicaux et les propirétés d'extrémilité dont ils héritent à l'espace projectif CPn. On montre également comment définir le produit de tels courants tropicaux pour en déduire une théorie de l'intersection entre cycles tropicaux. pour opérer ces calculs, on établit une formule pour la mesure de Monge Ampère réelle associée à un polynôme tropical. De plus, comme un tel courant tropical attaché à un p-cycle tropical VT s'obtient en moyennisant des courants d'intégration sur des variétés toriques, on met en correspondance théorie de l'intersection dans le cadre torique et théorie de l'intersection dans le cadre tropical. On explicite enfin certains liens entre les problèmes relevant de l'approximation (an sens ensembliste, pour la métrique de Hausdorff) des cycles tropicaus de Rn par les amibes de cycles algébriques de (C)n et l'approximation (ans sens faible) des courants tropicaux associées par des multiples positifs de courants d'intégration sur de tels cycles algébriques. on explique en quoi ces questions d'approximation se trouvent reliées à une formulation forte de la célèbre confecture de Hodge. / To a tropical p-cycle VT in Rn, we naturally assoicate a closed (p, p)-dimensional current of order zero on (C)n denoted bu T p n(VT). Such e "tropical current" T p n(VT) cannot be an integration current along any analytic set since its support has the form log -1(VT) (C)n, where log is the coordinate-wise valuation with log(I.I). We provide sufficient (local) conditions on a tropical p-cycle such that its associated tropical is "strongly extremal" in Dop, p((C)n). In particular, if these conditions hokd for the effective cycles, then the associated current are extremal in the cone of strongly positive closed currents of bidimension (p, p) on (C)n. Nexte we explain how to extend the currents and extremality results to CPn. Further, we demonstrate how to use the intersection theory of currents to derive an intersection theory for the inderlying tropical cycles. The explicit calculations will be established by using e formula for the real Monge-Ampère measure of a tropical polynomial. Moreoer, since such tropical currents are obtained by an averaging of integration currents on toric sets, an equality between toric intersection multipmicities and the tropical multiplicities is readily settled. Finally, we explain certain relations between approximation problems of tropical cycles by amoebas of algebraic cycles and approximations of the associated currents by positive multiples of integration currents along analytic cycles. Il will be discussed haw these approximtion problems are related to a stronger formulation of the celebrated hodge conjecture.

Tropical geometry is algebraic geometry over the tropical semiring, or min-plus algebra. In this thesis, I discuss the basic geometry of plane tropical curves. By introducing the notion of abstract tropical curves, I am able to pass to a more abstract metric-topological setting. In this setting, I discuss divisors on tropical curves. I begin a study of $G$-invariant divisors and divisor classes.

在這篇論文中，我們從K energy的角度探討緊緻法諾超平面上的K穩定性。首先，我們給K energy一個較明確的型式，接著再透過分析的手法求解其導函數。後續，我們引進熱帶幾何的結構來重新分析主要的結果，最後給一些法諾超平面的實例，驗證我們所得到的公式。 / In this thesis, we analyze K stability on compact Fano hypersurfaces from K energy. We first represent the K energy into an explicitly formula. Then we compute the derivative by using some analytic techniques. Furthermore, we introduce some structures of tropical geometry to analyze the main result. Finally, we give some examples of compact Fano hypersurface to test and verify the formula we get.

Les systèmes polynomiaux réels sont omniprésents dans de nombreux domaines des mathématiques pures et appliquées. A. Khovanskii a fourni une borne fewnomiale supérieure sur le nombre de solutions positives non-dégénérées d'un système polynomial réel de n équations à n variables qui ne dépend que du nombre de monômes apparaissant dans les équations. Cette dernière borne a été récemment améliorée par F. Bihan et F. Sottile, mais la borne résultante peut être encore améliorée, même dans certains cas simples.Le but de ce travail est d'aborder trois problèmes importants dans la théorie des Fewnomials. Considérons une famille de systèmes polynomiaux réels avec une structure donnée (par exemple, support ou le nombre de monômes). Un problème est de trouver de bonnes bornes supérieures pour leurs nombres de solutions réelles (ou positives). Un autre problème est de construire des systèmes dont le nombre de solutions réelles (ou positives) sont proches de la meilleure borne supérieure connue. Lorsqu'une borne supérieure optimale est bien connue, qu'est ce qu'on peut dire dans le cas où elle est atteinte?Dans cette thèse, nous affinons un résultat de M. Avendaño en démontrant que le nombre de points d'intersection réels d'une droite réelle avec une courbe réelle plane définie par un polynôme avec au plus t monômes est soit infini ou ne dépasse pas $6t -7$. En outre, on montre que notre borne est optimale pour t=3 en utilisant les dessins d'enfant réels de Grothendieck. Cela montre que le nombre maximal de points d'intersection réels d'une droite réelle avec une courbe trinomiale réelle plane est onze.Nous considérons ensuite le problème de l'estimation du nombre maximal de points d'intersection transverses positifs d'une courbe plane trinomiale et d'une courbe plane t-nomiale. T-Y Li, J.-M. Rojas et X. Wang ont montré que ce nombre est borné par 2^t - 2, et récemment P. Koiran, N. Portier et S. Tavenas ont trouvé la borne supérieure 2t^3/3 +5t. Nous fournissons la borne supérieure $ 3*2^(t-2) - 1 qui est optimale pour t = 3 et est la plus petite pour t=4,...,9. Ceci est réalisé en utilisant la notion de dessins d'enfant réels. De plus, nous étudions en détail le cas t = 3 et nous donnons une restriction sur les supports des systèmes atteignant la borne optimale cinq.Un circuit est un ensemble de n+ 2 points dans $mathbb{R}^n$ qui sont minimalement affinement dépendants. Il est connu qu'un système supporté sur un circuit a au plus n+1 solutions positives non dégénérées, et que cette borne est optimale. Nous utilisons les dessins d'enfant réels et le patchwork combinatoire de Viro pour donner une caractérisation complète des circuits supportant des systèmes polynomiaux avec le nombre maximal de solutions positives non dégénérées.Nous considérons des systèmes polynomiaux de deux équations à deux variables avec cinq monômes distincts au total. Ceci est l'un des cas les plus simples où la borne supérieure optimale sur le nombre de solutions positives non dégénérées n'est pas connue. F. Bihan et F. Sottile ont prouvé que cette borne optimale est majorée par quinze. D'autre part, les meilleurs exemples avaient seulement cinq solutions positives non dégénérées.Nous considérons des systèmes polynomiaux comme avant, mais défini sur le corps des séries de Puiseux réelles généralisées et localement convergentes. Les images par l'application de valuation des solutions d'un tel système sont des points d'intersection de deux courbes tropicales planes. En utilisant des intersections non transverses des courbes tropicales planes, on obtient une construction d'un système polynomial réel comme ci-dessus ayant sept solutions positives non dégénérées. / Real polynomial systems are ubiquitous in many areas of pure and applied mathematics. A. Khovanskii provided a fewnomial upper bound on the number of non-degenerate positive solutions of a real polynomial system of $n$ equations in n variables that depends only on the number of monomials appearing in the equations. The latter bound was recently improved by F. Bihan and F. Sottile, but the resulting bound still has room for improvement, even in some simple cases.The aim of this work is to tackle three main problems in Fewnomial theory. Consider a family of real polynomial systems with a given structure (for instance, supports or number of monomials). One problem is to find good upper bounds for their numbers of real (or positive) solutions. Another problem is to construct systems whose numbers of real (or positive) solutions are close to the best known upper bound. When a sharp upper bound is known, what can be said about reaching it?In this thesis, we refine a result by M. Avendaño by proving that the number of real intersection points of a real line with a real plane curve defined by a polynomial with at most t monomials is either infinite or does not exceed 6t -7. Furthermore, we prove that our bound is sharp for t=3 using Grothendieck's real dessins d'enfant. This shows that the maximal number of real intersection points of a real line with a real plane trinomial curve is eleven.We then consider the problem of estimating the maximal number of transversal positive intersection points of a trinomial plane curve and a t-nomial plane curve. T-Y Li, J.-M. Rojas and X. Wang showed that this number is bounded by 2^t-2, and recently P. Koiran, N. Portier and S. Tavenas proved the upper bound 2t^3/3 +5t. We provide the upper bound 3*2^{t-2} - 1 that is sharp for t=3 and is the tightest for t=4,...,9. This is achieved using the notion of real dessins d'enfant. Moreover, we study closely the case t=3 and give a restriction on the supports of systems reaching the sharp bound five.A circuit is a set of n+2 points in mathbb{R}^n that is minimally affinely dependent. It is known that a system supported on a circuit has at most n+1 non-degenerate positive solutions, and that this bound is sharp. We use real dessins d'enfant and Viro's combinatorial patchworking to give a full characterization of circuits supporting polynomial systems with the maximal number of non-degenerate positive solutions.We consider polynomial systems of two equations in two variables with a total of five distinct monomials. This is one of the simplest cases where the sharp upper bound on the number of non-degenerate positive solutions is not known. F. Bihan and F. Sottile proved that this sharp bound is not greater than fifteen. On the other hand, the best examples had only five non-degenerate positive solutions. We consider polynomial systems as before, but defined over the field of real generalized locally convergent Puiseux series. The images by the valuation map of the solutions of such a system are intersection points of two plane tropical curves. Using non-transversal intersections of plane tropical curves, we obtain a construction of a real polynomial system as above having seven non-degenerate positive solutions.

Often mathematics is seen by high school students as a science restricted to memorizing formulas and concepts. Therefore limiting in its essence. The work seeks to reverse that view by submitting a new eld of study: Tropical Algebra. Relatively new area of mathematics that keeps the curious feature to handle the operations of addition and multiplication di erently from traditional, already presents interesting practical results. Tropical algebra will be presented in a didactic way, comparing it with the traditional algebra, showing the consequences of tropical operations in the study of polynomials, matrices and geometry, and presenting some practical applications. / Frequentemente a matemática é vista pelos alunos do ensino médio como uma ciência restrita à memorização de fórmulas e conceitos. Portanto, limitante em sua essência. O trabalho busca reverter tal visão através da apresentação de um novo campo de estudos: A Àlgebra Tropical. Área relativamente nova da matemática que guarda a curiosa característica de tratar as operações de adi- ção e multiplicação de forma diferente da tradicional, já apresenta resultados práticos interessantes. A Àlgebra Tropical será apresentada de forma didática, comparando-a com a álgebra tradicional e mostrando as consequências das operações tropicais no estudo dos polinômios, matrizes e geometria, além de apresentar algumas aplicações práticas.

Tropical geometry is an area of mathematics that interfaces algebraic geometry and combinatorics. The main object of study in tropical geometry is the tropical variety, which is the combinatorial counterpart of a classical variety. A classical variety is converted into a tropical variety by a process called tropicalization, thus reducing the problems of algebraic geometry to problems of combinatorics. This new tropical variety encodes several useful information about the original variety, for example an algebraic variety and its tropical counterpart have the same dimension. In this thesis, we look at the some of the computational aspects of tropical algebraic geometry. We study a generalization of Grobner basis theory of modules which unlike the standard Grobner basis also takes the valuation of coefficients into account. This was rst introduced in (Maclagan & Sturmfels, 2009) in the settings of polynomial rings and its computational aspects were first studied in (Chan & Maclagan, 2013) for the polynomial ring case. The motivation for this comes from tropical geometry as it can be used to compute tropicalization of varieties. We further generalize this to the case of modules. But apart from that it has many other computational advantages. For example, in the standard case the size of the initial submodule generally grows with the increase in degree of the generators. But in this case, we give an example of a family of submodules where the size of the initial submodule remains constant. We also develop an algorithm for computation of Grobner basis of submodules of modules over Z=p`Z[x1; : : : ; xn] that works for any weight vector. We also look at some of the important applications of this new theory. We show how this can be useful in efficiently solving the submodule membership problem. We also study the computation of Hilbert polynomials, syzygies and free resolutions.

Cette thèse est divisée en deux parties principales. D’abord on étudie des relations entre les théories d’intersection en géométrie tropicale et géométrie algébrique. Puis on étudie la question des possibilités pour la distribution de points d’inflexion réels associés à un système linéaire réel défini sur une courbe algébrique réelle lisse. Dans la première partie, nous présentons des nouveaux résultats reliant les théories d’intersection algébrique et tropicale dans une variété algébrique très affine définie sur un corps non-archimédien particulier (dit corps de Mal’cev-Neumann). Le résultat principale concerne l’intersection d’un cycle algébrique de dimension 1 dans une variété à tropicalisation simple avec un diviseur de Cartier. Dans la deuxième partie, nous obtenons d’abord une caractérisation de la répartition des points d’inflexion réels d’un système linéaire complet de degré d>1 sur une courbe elliptique réelle lisse. Puis nous étudions quelques courbes réelles non-hyperelliptiques canoniques de genre 4 dans l’espace projectif de dimension 3. Nous obtenons une formule qui relie le nombre de points de Weierstrass réels d’une telle courbe avec la caractéristique d’Euler-Poincaré d’un certain espace topologique. Finalement, en utilisant la technique du Patchworking (dû à O. Viro), on construit un exemple de courbe réelle, lisse, non-hyperelliptique de genre 4 ayant 30 points de Weierstrass réels. / This thesis is divided in two main parts. First, we study the relationships between intersection theories in tropical and algebraic geometry. Then, we study the question of the possibilities for the distribution of the real inflection points associated to a real linear system defined on a smooth real algebraic curve. In the first part, we present new results linking algebraic and tropical intersection theories over a very-affine algebraic variety defined over a particular non-Archimedean field (known as Mal’cev-Newmann field). The main result concerns the intersection of a one-dimensional algebraic cycle with a Cartier divisor in a variety with simple tropicalization. In the second part, we obtain first a characterization of the distribution of real inflection points associated to a real complete linear system of degree d>1 defined over a smooth real elliptic curve. Then we study some canonical, non-hyperelliptic real algebraic curves of genus 4 in a 3-dimensional projective space. We obtain a formule that relies the amount of real Weierstrass points of such a curve with the Euler-Poincaré characteristic of certain topological space. Finally, using O. Viro’s Patch-working technique, we construct an example of a smooth, non-hyperelliptic real algebraic curve of genus 4 having 30 real Weierstrass points.

La programmation semi-définie est un outil fondamental d'optimisation convexe et polynomiale. Elle revient à optimiser une fonction linéaire sur un spectraèdre (un ensemble défini par des inégalités matricielles linéaires). En particulier, la programmation semi-définie est une généralisation de la programmation linéaire.Nous étudions l'analogue non-archimédien de la programmation semi-définie, en remplaçant le corps des nombres réels par le corps des séries de Puiseux. Notre approche est fondée sur des méthodes issues de la géométrie tropicale et, en particulier, sur l'étude de la tropicalisation des spectraèdres.En première partie de la thèse, nous analysons les images par la valuation des ensembles semi-algébriques généraux définis dans le corps des séries de Puiseux. Nous montrons que ces images ont une structure polyédrale, ce qui fournit un analogue réel du théorème de Bieri et Groves. Ensuite, nous introduisons la notion de spectraèdres tropicaux et nous montrons que, sous une hypothèse de généricité, ces objets sont décrits par des systèmes d'inégalités polynomiales de degré 2 sur le semi-corps tropical. Cela généralise un résultat de Yu sur la tropicalisation du cône des matrices positives.Une question importante relative à la programmation semi-définie sur les réels consiste à caractériser des projections de spectraèdres. Dans ce cadre, Helton et Nie ont conjecturé que tout ensemble semi-algébrique convexe est la projection d'un spectraèdre. La conjecture a été réfutée par Scheiderer. Néanmoins, nous montrons qu'elle est vraie ''à valuation près'' : dans le corps réel clos des séries de Puiseux, les ensembles semi-algébriques convexes et les spectraèdres projetés ont exactement les mêmes images par la valuation non-archimédienne.En seconde partie de la thèse, nous étudions des questions algorithmiques liées à la programmation semi-définie. Le problème algorithmique de base consiste à décider si un spectraèdre est vide. On ne sait pas si ce problème appartient à NP dans le modèle de la machine de Turing, et les algorithmes fondés sur la décomposition cylindrique algébrique ou la méthode de points critiques constituent l'état de l'art dans ce domaine. Nous montrons que, dans le cadre non-archimédien, les spectraèdres tropicaux génériques sont décrits par des opérateurs de Shapley associés aux jeux à paiement moyen stochastiques. Cela donne une méthode pour résoudre des problèmes de réalisabilité en programmation semi-définie non-archimédienne en utilisant les algorithmes combinatoires conçus pour les jeux stochastiques.Dans les chapitres finals de la thèse, nous établissons des bornes de complexité pour l'algorithme d'itération sur les valeurs qui exploitent la correspondance entre les jeux stochastiques et la convexité tropicale. Nous montrons que le nombre d'itérations est contrôlé par un nombre de conditionnement relié au diamètre intérieur du spectraèdre tropical associé.Nous fournissons des bornes supérieures générales sur le nombre de conditionnement. Pour cela, nous établissons des bornes optimales sur la taille en bits des mesures invariantes de chaînes de Markov. Comme corollaire, notre estimation montre que l'itération sur la valeur résout les jeux ergodiques à paiement moyen en temps pseudo-polynomial si le nombre de positions aléatoires est fixé. Enfin, nous expérimentons notre approche à la résolution de programmes semi-définis non-archimédiens aléatoires de grande taille. / Semidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing the linear functions over the spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming.The purpose of this thesis is to study the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra.In the first part of the thesis, we analyze the images by valuation of general semialgebraic sets defined over the Puiseux series. We show that these images have a polyhedral structure, giving the real analogue of the Bieri--Groves theorem. Subsequently, we introduce the notion of tropical spectrahedra and show that, under genericity conditions, these objects can be described explicitly by systems of polynomial inequalities of degree 2 in the tropical semifield. This generalizes the result of Yu on the tropicalization of the SDP cone.One of the most important questions about real SDPs is to characterize the sets that arise as projections of spectrahedra. In this context, Helton and Nie conjectured that every semialgebraic convex set is a projected spectrahedron. This conjecture was disproved by Scheiderer. However, we show that the conjecture is true ''up to taking the valuation'': over a real closed nonarchimedean field of Puiseux series, the convex semialgebraic sets and the projections of spectrahedra have precisely the same images by the nonarchimedean valuation.In the second part of the thesis, we study the algorithmic questions related to SDP. The basic computational problem associated with SDP over real numbers is to decide whether a spectrahedron is nonempty. It is unknown whether this problem belongs to NP in the Turing machine model, and the state-of-the-art algorithms that certify the (in)feasibility of spectrahedra are based on cylindrical decomposition or the critical points method. We show that, in the nonarchimedean setting, generic tropical spectrahedra can be described by Shapley operators associated with stochastic mean payoff games. This provides a tool to solve nonarchimedean semidefinite feasibility problems using combinatorial algorithms designed for stochastic games.In the final chapters of the thesis, we provide new complexity bounds for the value iteration algorithm, exploiting the correspondence between stochastic games and tropical convexity. We show that the number of iterations needed to solve a game is controlled by a condition number, which is related to the inner radius of the associated tropical spectrahedron. We provide general upper bounds on the condition number. To this end, we establish optimal bounds on the bit-length of stationary distributions of Markov chains. As a corollary, our estimates show that value iteration can solve ergodic mean payoff games in pseudopolynomial time, provided that the number of random positions of the game is fixed. Finally, we apply our approach to large scale random nonarchimedean SDPs.

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.