Tropical convexity, mean payoff games and nonarchimedean convex programming
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Alternativer Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 15 | |
| Autor | ||
| Mitwirkende | ||
| Lizenz | CC-Namensnennung 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/51291 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
2
7
15
00:00
OptimierungKonvexe MengeSpieltheorieArithmetisches MittelKombinatorikTheoretische PhysikFormation <Mathematik>RelativitätstheorieGlobale OptimierungKomplex <Algebra>Offene MengeKarush-Kuhn-Tucker-BedingungenOptimierungGeometrieVerschlingungSummierbarkeitKonvexe MengeKörper <Algebra>Arithmetisches MittelKartesische KoordinatenNumerische MathematikDivergente ReiheForcingGrundraumGruppenoperationComputeranimationBesprechung/Interview
01:16
PolynomModelltheoriePolygonNebenbedingungZentraler PfadVektorraumBewertungstheorieTetraederMatrizenrechnungDiagonale <Geometrie>Vorzeichen <Mathematik>UngleichungDefinitheit <Mathematik>Karush-Kuhn-Tucker-BedingungenApproximationFolge <Mathematik>GeometrieGravitationNatürliche ZahlNumerische MathematikOptimierungPerspektivePolynomSpieltheorieStereometrieMengenlehreVarianzModelltheorieBewertungstheorieGebäude <Mathematik>IterationProdukt <Mathematik>Profil <Aerodynamik>Quadratische FormModulformVariableKombinatorMittelwertReduktionsverfahrenVektorraumPolyederUniformer RaumPhysikalischer EffektUngleichungGesetz <Physik>Total <Mathematik>AnalogieschlussÜbergangGlobale OptimierungÄquivalenzklasseAggregatzustandAnalytische MengeArithmetisches MittelAusgleichsrechnungDeterministischer ProzessDivergente ReiheEbeneEinfach zusammenhängender RaumEinfacher RingEnergieerhaltungExakte SequenzForcingFreie GruppeFunktionalGeradeGreen-FunktionGrothendieck-TopologieGruppenoperationHill-DifferentialgleichungHyperebeneIndexberechnungInhalt <Mathematik>Inverser LimesKette <Mathematik>KnotenpunktKomplex <Algebra>Konvexe MengeKugelLokales MinimumMathieu-DifferentialgleichungMereologieMomentenproblemPhysikalische TheoriePhysikalisches SystemPhysikalismusPolygonPotenz <Mathematik>Projektive EbenePunktrechnungRadikal <Mathematik>ResultanteStellenringStichprobenfehlerTabelleTermTheoremWärmeübergangWechselsprungZentralisatorZentrische StreckungSchätzungMotiv <Mathematik>Güte der AnpassungKonstanteTeilbarkeitUnordnungFormale PotenzreiheExogene VariableMatchingZeitrichtungSuperstringtheorieEndlich erzeugte GruppeNichtlinearer OperatorWasserdampftafelBasis <Mathematik>AbstandParametersystemFaktor <Algebra>ReihenfolgeproblemPerfekte GruppeStrategisches SpielPunktspektrumDruckverlaufSterbezifferEnergiedichteBlockade <Mathematik>VektorpotenzialFormation <Mathematik>SummierbarkeitFächer <Mathematik>AdditionExistenzsatzPunktStreuungsdiagrammFeuchteleitungBetrag <Mathematik>Glattheit <Mathematik>Klasse <Mathematik>HorizontaleQuaderWellenlehreAbstimmung <Frequenz>Gleitendes MittelOffene MengePoisson-KlammerFlüssiger ZustandInnerer PunktKugelkappeKreisflächeExpandierender GraphKartesische KoordinatenOptimierungsproblemAuswahlverfahrenDruckspannungUmwandlungsenthalpieAbschattungBimodulVollständiger VerbandMultifunktionSummengleichungArithmetischer AusdruckEuler-WinkelVorzeichen <Mathematik>KnotenmengeWeg <Topologie>NichtunterscheidbarkeitBestimmtheitsmaßSupremum <Mathematik>DifferenteRechenbuchMedianwertp-BlockObjekt <Kategorie>sinc-FunktionPolstelleKlassische PhysikKreisbogenMultiplikationsoperatorSchlussregelStandardabweichungZweiSechsMinkowski-MetrikFigurierte ZahlOrtsoperatorSpezifisches VolumenEinsAlgebraische KurveGraphKombinatorikKurveLineare OptimierungMaß <Mathematik>Ordnung <Mathematik>Rationale ZahlRauschenRelativitätstheorieSignifikanztestTopologieTransformation <Mathematik>StochastikMatrizenrechnungAusdruck <Logik>Algebraisch abgeschlossener KörperGanze ZahlFinitismusUnendlichkeitGrenzschichtablösungNichtnewtonsche FlüssigkeitAlgebraisches ModellAuswahlaxiomBeweistheorieDrucksondierungEindeutigkeitEndlichkeitExponentLogarithmusLoopMaßerweiterungPermutationPolyhedronQuantisierung <Physik>SimplexverfahrenSinusfunktionSkalarfeldStationäre VerteilungTeilmengeVakuumpolarisationVertauschungsrelationVerschlingungKonfigurationsraumReelle ZahlEinflussgrößeGegenbeispielGewicht <Ausgleichsrechnung>Lineare GleichungKrümmungsmaßVorhersagbarkeitWinkelverteilungKörper <Algebra>Dichte <Physik>Symmetrische MatrixNegative ZahlQuelle <Physik>Sortierte LogikKoeffizientBeobachtungsstudieRichtungDifferenzkernWurzelsystem <Mathematik>Prozess <Physik>MinimumFlächentheorieEinschließungssatzAffine VarietätAbsolute KonvergenzAbgeschlossene MengeKonditionszahlGibbs-VerteilungAuflösung <Mathematik>Dreiecksfreier GraphDickeTVD-VerfahrenInnerer AutomorphismusRechter WinkelPrädikatenlogik erster StufeBesprechung/InterviewComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:16
So, many thanks to the organizer, it's a pleasure to be here.
00:21
So, this talk is about some relation between open complexity problems in convex programming optimization and the awesome guides. And so, the link will go through a particular geometry, that is by considering convex sets of non-archeminian fields. So, this is a kind of survey, I would say.
00:56
So, yes, I described some relation between problems of, let's say, non-archeminian optimization and problems of gain.
01:07
And I will give some application to a complexity problem. There is quite all problems in the programming, which is to understand whether there is a convex algorithm, an extended means. And so, some colleagues, who has a famous method, which is interior of those methods,
01:21
Well, we don't get some of the convex programming.
01:59
In a quantum world, it looks like a very monotony problem.
02:08
And you put integer prices on the edges, the prices that will be paid. So, there are two players, max and min. So, we'll find that the map is apartheid. It means that the two players, they alternate the move.
02:22
So, max plays and min plays, et cetera. And so, when there is a move, it's always a player who is called minimizer, who plays what is written on the arm to a player called maximizer. And the player can have a negative function. That's a good point.
02:41
So, right now, the game will be on a nation of states. You don't need to understand the position of the game. And the information. So, in the min, the player plays the game.
03:00
So, what he wins for the first order. Then the payment of his move. Then the payment of the next move, et cetera. So, max is interested about lima. He wants to maximize lima of this average payment.
03:22
And so, by symmetrically, min wants to maximize. So, on the whole, this result in this field of Ehrenfest and Mississippi says that this game has a value. And there are optimal conditional strategies, which are part of it. So, a value at a certain point in the space of the optimal strategies
03:45
are a certain point in the space, if you want to play it. So, we know this game has an optimal conditional strategy. It's a rule which tells you, if you are in this state, you always play this action. And it's optimal to play in this game.
04:02
So, let's look at an example. So, here we have a circle state which belongs to minimizer. And we have a square state which belongs to maximizer. So, maybe minimizer will want to go up. So, if minimizer wants to go up, minimizer will play minus one to max.
04:30
And there is no choice in the next step. Instead, after that, it's minimizer pays one.
04:43
So, in this loop, first, minimizer pays minus two. Then, minimizer pays one. Minimizer plays minus one. So, it's a win for minimizer. Minimizer receives one for max. But, minimizer can also go down.
05:00
So, here, if minimizer goes down, he pays minus eight. So, this minimizer receives eight. And then, it's maximizer who plays. So, maybe, maximizer will play. So, here, minimizer feels rich because he has eight plus twelve. But now, there is no choice in this game. The only action, possible action, is to go left.
05:22
And then, forever, maximizer can enforce this loop. And so, on this loop, well, mean pay to max. Pay five down. Owing to this terrible loop. It's the price of the ingredient.
05:42
So, what we can say is that the initial state one is winning for me. Because by this upper cycle, minimizer can make sure to win at least one part-time unit. This initial state, it is winning for max.
06:04
Because by this loop, maximizer can make sure to win five part-time units. And if minimizer is foolish and makes a bad action, he moves from a winning state to a losing state. Which I did. I push up again. So, the mean pay of part-time unit here, we can say that from the point of view of max,
06:22
it is five from state two. And it is minus one instead of half. It corresponds to these cycles which are determined by positional strategies. So, the mean pay of problem consists of computing these numbers which took very little time.
06:40
Mean pay of part-time unit for all initial states. So, this problem was introduced, was first considered by Burek, Karsanov and Rachan. And they introduced the first combinatorial algorithm to solve this case. And they asked in 1988 whether we can solve this problem in polynomial time.
07:03
And still today, it's not known. It's not known. And so, to understand what polynomial time means, we have a difficulty here. We want the number of iterations, as usually in the Turing model. It's polynomial time, the number of bits of input.
07:22
And so, the number of bits in the input, you put the log of the integer payment. So, the reason why the game is still not solved today, this is still an open problem today, it is because the naive algorithm which consists in playing the game in a certain long time, to see whether Max or Min is unique, a very natural idea,
07:44
it is to approximate the infinite horizon game by the finite horizon game. On this issue three, you use that, then you need a time, let's say, which is of exponential of L or not L, essentially. For large integers, it is a difficult problem.
08:01
You see what this says. There is some, at least it's a very motivating problem, because MinP of game, it is the complexity class introduced by n modes, which is called the NP-intersection of coin P. These problems are called also good characterization by n modes. So, when you are in this class, you know that you are not NP-hard, unless NP is equal to coin P, which is unlucky.
08:23
So, when you are in NP-intersection of coin P, you try to look whether or not the preliminary algorithm is very intriguing question. Do you still see where you get your shares? So, now a second problem, which is more known, it's a linear programming problem.
08:41
Again, it's much older. So, we consider linear programming. So, linear programming is an optimization problem. So, you take a polyhedron, the input is rational, and three of them are linear programming. So, we can see the vector on the other side of the point,
09:03
which is the smallest introduction of the vector. That's linear programming. So, there are still some answers to the question about linear programming. So, one was raised by Smeda. In this problem, essentially, there are some unknowns. You decide whether you want to take a polyhedron.
09:33
Guebert, we have a problem with the sound. So, we have a problem with the sound. We have a problem with the sound, it's a noise.
09:41
I don't know if it's the other way around. You don't hear me? I don't know if it's your connection to the internet and... Well, you can hear the sound and hear it. Well, I hear the sound very well. I can hear the sound a lot. So, you have a problem with the sound?
10:01
It becomes better in one second. Yes. I'm sorry, you have to copy the video, is that okay? Yes. Yes, because the sound is going to be on the film, which is going to be on the internet. Okay.
10:21
Okay. Normally, it should shift to... I try to improve. There is a risk. It cuts once a month, okay? Okay. So, I try to shift.
10:40
Now, are you with me? Oui, oui, oui. Vous entendre? Okay, so now, the sound should be perfect now. The sound is good now, yes. Yeah, sorry, sorry. Okay. Voilà. So, when you say polynomial time, it means uniquely polynomial, that is, as usual,
11:00
the execution time is bounded by a polynomial in the number of bits of input. So, strongly polynomial time is nice on its... So, it's a model of computation, so-called arithmetic model. So, what you want, you want the number of arithmetic operations. We are strongly polynomial.
11:20
Now, we are going to... on the number of constants. So, a with the other side, n times n, number of arithmetic, number of variables. And you want the number of arithmetic operations is bounded uniformly, polynomial-y, uniformly in the bit length of the input.
11:41
So, if you have a great precision in the matrix, in the collection of p, you don't want that it has an impact on the execution time. And, in addition to that, this uniform kind of pair requires that algorithm is also polynomial time, to itself. Okay. Well, that's the size condition.
12:02
That's strongly polynomial, and we still have this technology. So, let's see why... I think the approaches of linear programming say about this strongly polynomial aspect. So, the most well-known method in linear programming is the simplex of advantage. So, the simplex, it goes on the...
12:20
there is a polynomial. So, it makes a move on the graph of the polynomial. So, you start from a given vertex, and you make a walk. So, in this walk, you move from one node to another node, and you decrease the cost, the whole of the simplex. So, when you have a simplex algorithm, you have what is called a sky-voting rule, because you have several passes,
12:42
which can lead you to the same optimum. For instance, for this polynomial, you can go down or up. If you go up, it is faster. This choice is called the sky-voting rule, which tells you where you go, what is the neighbor of your account, which neighbor of your current vertex you choose.
13:02
So, what you can check is that to perform a single iteration, solving the R-system, completing the RTC. So, a single iteration is a strong polynomial. However, it's a very well-known problem to you. There is no, since non-silicon seeking is 47, there is no piloting rule,
13:20
which is known to be polynomial. The counter-example has been found to most known rules, and even if you take the perfect lucid rule, you take the shortest path on the polynomial, it's not a non-resar. You can make a polynomial, it's not necessarily a polynomial-ish conjecture. So, the simplex is very interesting for this perspective, because it's nature,
13:41
it's pivoting as a strongly polynomial local character, but globally, it's not an awesome problem. Now, let's look for something which is a bit less known outside the optimization community, and which is the method of choice in our programming, because it is both efficient in practice, and it has some polynomial complex attributes.
14:03
It's the entire polynomial. So, the entire polynomial, the idea is to replace your linear programming problem by a so-called barrier problem. So, linear programming, you have your polyhedron, you have your vector c, which represents the gravity. Maybe, don't minimize,
14:21
you want to find the smallest point and the lowest point in your polyhedron. You can see, like, a force opposite to c, which drives your point to the bottom. And so, in the barrier problem, you compensate the gravity. By a force, which goes from a Newtonian potential,
14:44
logarithmic potential, so you put a repulsive potential, given by every facet, every facet, the whole point, and when mu is the positive parameter, and so for a positive mu, we consider the minimum.
15:02
Well, it is compromised, between the forces, even the normal to the facets, which drive you to the interior of the polyhedron, and the gravity opposite of c, which passes you to the optimal. And so, when you consider this problem, you minimize the smooth, strictly convex function.
15:23
So, you have a well-defined optimal solution. So, the map, which to the barrier mu, the parameter, the motopy parameter, gives unique numbers of this expression. It's called the Central Pass. It's part of an empirical, as you can see. And, well, when mu goes to zero,
15:42
the barrier vanishes on the finish with the optimal. So, the Central Pass, it draws a pass from a certain point in the interior of the polyhedron called the magnetic center, and it goes to the optimal. And so, when you have that, you can do some numerical methods,
16:02
that is, you can do some decrease mu, or you can do some Newton steps, right to stay in the middle of the Central Pass. And so, the pass-through method will lead you to work to work. So, this is what are the entire points, so there are many versions for the motopy, so there is a technical question.
16:23
And so, these entire points, they are weakly polyhedron. So, this was invented by Karmarkar, an entire point, until he developed an idea, and the, and still, from the early on, it was a question whether you could improve the balance,
16:42
or the algorithm, to get the strongly polyhedron method, and this is the sort of resistance. And, since it's very difficult to show that there is no method, which is strongly polyhedron, because the method is parametrized, I mean, it's a mathematical method,
17:02
the view on sugar is considered a purified version, that means, they say that, instead of considering the total curvature, instead of considering the number of iterations, that is made in the upper middle, is considered a geometric complexity measure of the Central Pass, which is the total curvature. So, the thought that if the total curvature was small,
17:22
this could be a indication that this approach of strongly polyhedron method could be successful. So, it's like a toy result, which is purer, which is more geometric. And so, the conjecture that the total curvature of the Central Pass is linear in the number of variables. And actually, this was motivated by the theorem
17:41
of the dual manager of this on sugar. So, what they did is that, they considered the polyhedron, and when you are a polyhedron, you have an arrangement of either plane, which is given by the process of the polyhedron, and so, it defines many sets. So, the Central Pass of the polyhedron, it's a part of an algebraic curve. On this algebraic curve, it will fill all cells.
18:02
In every cell, you have the Central Pass corresponding to the cell. So, the theorem of the dual manager of the sugar is that, if you take the total curvature of this curve, average over all the cells, and they are essentially 2 to the n plus m, they are equal to the n plus m cells. So, if you take the average, it is linear.
18:20
So, the conjecture was saying that the worst case is like a fresh case, basically. Then, this iteration on Xin Zhen Kuo, they thought that the conjecture was too optimistic. That is, if you put many equities, then you can defeat the conjecture.
18:41
And so, the revision of the conjecture on saying that your expected behavior is that the total curvature should be O of m. Where m is the number of no O of the number of variables. So, now I will show you, and after I read all the talk, we will take it from a typical method to do that. So, we will show you some of this application of this,
19:02
of this conjecture that I give. So, the problems of min-pov gain, how much you mean that you mean in this two-player min-pov gain, on the problem of linear programming, they are apparently unrelated. However, there is a very quite close relation at the combinatorial level. That is,
19:21
if there was a strongly polynomial for a pi-voting rule for linear programming, and you should require some technical condition in this pi-voting rule, which should be semi-algebraic. You are not allowed to use the logarithm, exponential, and transient functions in your pi-voting rule. You should use the polynomials on inequality. So, if it is of a semi-algebraic nature,
19:41
and if it could solve linear programming, then it would solve min-pov gain in polynomial time. So, in some sense, min-pov gain are easier on a subset of linear programming, in the big sense. So, example of combinatorial rules is when you consider sine of min of the metric, of the linear program. So, this is a valid rule,
20:02
which could seem to be sterile. So, this more positively defeats the polynomiality of the average sense. For instance, ideally, you consider the same kind of model as the Duobelas-Yubitam-Shub, that is, instead of using a single polyhedral, you consider a collection of exponential numbers of polyhedron,
20:21
where you flip each inequality with probability one out. And then, it's known that the simplex is polynomial time in average, in this probabilistic model. So, when you use this transfer theorem, you get that you can solve the class of min-pov gain in polynomial time in average. But, of course, this probabilistic model of, well,
20:42
of a darker Shamir is a bit, I would say, particular. It doesn't reflect the complexity of the ordinary So, this was a positive result. And now, here is the negative one, which is somehow more neat.
21:01
So, if you actually believe that the central pass would have a small curvature, is wrong, and not only the central pass has a large curvature, but interior polynomials can be very good on this problem. So, there is an instance of a linear program with a number of variables in equality of order r,
21:23
which makes such that the total curvature is 2R. For order 2R. And if you run the log-barrier interior polynomials, if you look at the number of variations, you make an exponential number of variations. So, now I will explain in the rest of the talk how to improve this technique.
21:43
So, the proof goes by some tropical ideas, tropical module, tropical convex code, by going to the non-archemic density. So, first, I need to recall some operator approach of min-perf game. I don't think it's so classical, except in game theory.
22:01
So, let's go. So, the way you study this game is to consider the finite horizon game. What is difficult in the min-perf game is that you consider the min-perf per time in it. If you consider finite horizon, so you fix some initial state, for instance, i, a state of min, you say it starts from a certain state,
22:21
and you agree that you will play k terms. So, the number of years is k, and maybe 2020 years you will play the k terms. And then, the value is indexed by the initial state and by the horizon. So, the value is a real number, indexed,
22:40
depending on two indices' initial position on time. And then, the so-called Shapley coefficient tells you that you can compute the value at your city by determining for value. That is, the value in horizon k, given by the min-max expression, or the value in horizon k minus one, will be obtained by optimal strategies, by choosing minimizing action for player min
23:02
and maximizing action for player max. So, for the finite horizon problem, you solve it in that way. And so, you can look over the fact that the limit of this vector can coincide with the limit of vk over k. If you take the value of the sky horizon again, you write it back.
23:20
It's not so obvious, because I defined the limit of game vk and the addition of the epsilon-mines, and there is a kind of commutation of the epsilon-mines value. And you have that limit of the finite horizon again is equal to the limit that we want. So, here is a summary. So, you know these gates. The principle is that
23:41
you have a value vector, vk is in n, where n is the number of states. And the value vector in horizon k is given by applying a transformation t to the value vector in horizon k minus one. And the value in horizon zero, the game is finished. It's just a zero.
24:02
This vector is called the shepherd vector. So, for the deterministic game, it's very easy to see. The shepherd vector is the mean over all actions of the payment of the action and then it's a max in place plus the max over all actions, the max of the payment over all actions, plus the variable xk where k is the new state where we are
24:21
when min and max plays 63. So, it starts from state j, moves from i and moves from k. On the right-hand side, the shepherd vector is obtained by a mean max over all these links. So, it's nice to have a more abstract, more theoretical point of view about the shepherd vector.
24:40
So, we see that there are maps which are order-presented. So, you encrypt n with a partial order. So, the shepherd vector is order-presented and also it commutes with the addition of the constant vector. It's very straightforward when you look at the example. And this is how the appropriate actions to the games. So, in particular, these two actions
25:03
entail that the shepherd vector is non-expensive in the supply. Or you can have a long converse. That is, here is a general example of the shepherd vector. So, the example I showed you was a deterministic game, but actually it is a stochastic game,
25:21
which I'm watching now and it's very interesting. That is, every player, it's very similar to what I showed you. A player, I mean, chooses an action. Player max chooses another action, b. So, a, b are actions. So, it's not necessarily finite. Then, there is a payment for player b to player max, which depends on the state
25:40
and which depends on the action. This is the payment. And there is a transition probability. So, given the direction of player, we move from i to j. Given that player b chooses a and player max chooses b, we have a t, p, i, g, which is this number.
26:00
So, the general shepherd vector can be written in this way. We don't have to assume that the answer is true. So, what you should remember, so this operator is called the one-day operator. And to remember for the sequence, is that when you iterate k times
26:20
this operator, you play to vector zero. You take i coordinate, it gives you a value of a game, the original game, in horizon k, starting from set i. And you can modify the zero if you consider a t, k of u, where u is a vector, corresponds to modification of the game. You play as usual with every time you have payments.
26:42
On the last day, when the game is over, player max, row c, on additional payment of p, j, if the terminal state is e, j. So, there is, it's interesting to, you will need, we see it's essential to allow the game to vary, that is to consider, which I can. So, first,
27:01
what is known is that if operator, the Shapley operator, is reasonable, is semi algebraic, and, well, if you are an operator which is semi algebraic and non-exponsive in the norm, so it will be true for, like, Shapley operator which we need actually to be seen, then the mid-perf vector, the mid-perf pattern mid-exist,
27:20
does exist. Like this, this part, this side. So, now all the games, we consider, when the actions are finite, the perfect exist. On the, now here is the main, the main relation, the relation is from, how you can certify,
27:45
you can convince a friend that the game is winning for max. So, for example, the data missing case, the result is especially similar. Following the argument, the initial state, j, is winning for player max.
28:00
So, saying that the initial state is winning for player max, it means that the mean of the tk of 0 over k, indexing, the value, something from j, rising t, the value of t, is greater than 0. And then, it's characterized by the existence of what is called the sub-harmonic vector, that is,
28:20
vector u, such that u is smaller than t of u. So this is analog to sub-harmonic function in potential theory, you can see it as t of t, as a non-linear Markov operator. So, in that way, on the, so you look for a vector u, such that u is smaller than t of u, and you require that uj,
28:42
this vector, is different from minus infinity. So, the shape of the operator is going to extend continuously so that the argument contains a minus infinity value that is minus infinity here. And, if you confine the vector with a finite j-coordinate, such that u is smaller than t of u, it circulates and we start to create j in the minimum.
29:02
So by stealing the space, stealing the space of u, such that u is smaller than t of u, is equivalent in this sense, to solving the game. So here is an example. So you take, I don't draw the game in here, there are three states. So here, I show the set of
29:20
sub-harmonic vectors. So, they are in R, maybe, if you keep them free. I send them to R plus to be free, to the standard of time, to, by extension, to be able to visualize them. On that, I get a cross-section of the standard of time to show them. So here, if you have, for instance, the set of sub-harmonic vectors, which is in the interior, which has points in the interior
29:40
of the simplex, it will certificate that all of the initial states 1, 2, 3 are unique. But if you have a set of sub-harmonic vectors which is concentrated on the facet of the simplex, then you know that only this facet of the state are unique. Here, you know that the state 2 or 3 are unique. So, in that way, you reduce a minimum gain problem
30:01
to understand the geometry of the space of sub-harmonic vectors. I will go further on that. And I have to say that if you have a stochastic game of full generality when you have an initial action space then the sub-harmonic vectors are
30:20
still useful because you consider v smaller from t of v and you look for a non-trivial vector of the short of the non-trivial vector and then you characterize the existence of one winning state. question is more delicate here. So now we see
30:41
how tropical is unique. So, the tropical semi-field takes the position of one and the product in production is very unique.
31:01
So sometimes you do a plus and a minus instead of a minus and a plus instead of a plus and a minus. So, then we can consider a module of tropical semi-field. If you have an action of number of scalars, so they act scalars, they act on vector by the translation, by constant.
31:26
On that way, they coordinate with x. This is the action of scalars in a typical module. And the addition of vectors is just the 0.2S supremum. So in particular, R max to bn is a set of vectors of motion n. It's a free module, we have a typical semi-field.
31:43
And we control these are some modules. And they are precisely tropical convex coils. That is, this is the sub-module, if only stable by a tropical linear combination. For every x, y in the sub-module G, there is constant lambda of mu, lambda plus x, and lambda plus y.
32:03
So, the sub-module corresponds to the solution of polar. You have to also see that in the tropical world, every body has a number in a negative. So you don't see the difference between the cone and the convex signal of the module. On the same way, you can consider a convex set.
32:21
So the set is tropically convex. Stable by a tropical linear combination. As soon as, the sum of the weight is equal to the tropical mu. So as usual, there is no sort of equivalence between considering a convex set and a convex code by doing some originalization. So I will use both settings in this lecture.
32:47
So, if you look at, so we have to remember that we want to solve the game. We have to consider the space of several vectors. So, that is the set of the game. You should have given the game interpretation.
33:01
When you have z-spoilers on T of z, it means that you play one game, and then you receive a terminal payment of z. On z, you play zero games, and you receive immediately. So if T of z is greater than z, it means that you prefer to play the game one day, and not to play it.
33:21
This is what makes it stable for this object. So you can check that the closed sub-modules are precisely the set of several vectors associated with Chapeau characters. It's not difficult, because the Chapeau character is continuous. And when you have a closed sub-module, there is a canonical Chapeau character, which is the projection, the best approximation.
33:45
So, in that way, you see that Chapeau characters, their spaces are precisely closed. So we have some module closed. So, further two is the notion of topological. So, we have modules.
34:01
So, if you have a pre-module of max plus, we have linear vectors that are just matrices. So, when you have a max plus matrix, that's an adjoint. You can see that A x, rather than y, if and only if x relates from A sharp y. So it's like, let's say, spring linear conjugate. If you say sharp, it's a bit strange, you see.
34:21
You have to replace max by min, and you have to transpose the matrix, as usual, and you change the sum. And that's the right choice. It's adjoint in the sense of order structure, and that's useful. Because now, when you consider a Chapeau character of a linear game, you have to remember that it's what we need of A max plus max of A max plus the value that exists.
34:43
And so, it's precisely of the form A sharp b g. You take a linear map, a typical b, and you take the adjoint of an isochromic linear map, and you control them. And then, using the adjoint property, we have that v is closer than c g. So, v is a certificate, and the game is finished.
35:01
So, if you write it down, you see that this is the finite number of linear equations over the tropical surfaces. So, this means exactly that, while the set of certificates at the game is linear, what is called the tropical polyhalkon is defined by the free number of finitely mini inequalities,
35:22
where the number of variables are the number of states of one player, and the number of inequalities is the number of states of each other. So, this scratcher, this space is v is polar from t o v. In the case of the deterministic game, you see better, more closely, what is their shape.
35:40
So, their intersection is the simplest example of tropical aspects. So, if you take a singular inequality, a singular inequality, max of A i plus x i is polar, and max of B i plus x i is equal. Well, you have what is called a tropical Euler plane, which is a set of points on the maximum of finite terms A i plus x i is a chipwise function,
36:06
and defines the building dates of the space in the sector r's, and where one coordinate is greater than the other, and so this is one sector, considered x 2 greater than max x 1 minus 2 plus x 3. And so, a tropical outer space will be a union of such a sector,
36:23
and depending on which you put terms at left or at right, you can get a union of such a sector, and this is a tropical outer plane, and this is also a tropical outer space. And when you, when then you can take a, this consists of a tropical polaroid cone, their intersection of finitely linear spaces,
36:45
or they are also finitely generic in the tropical sense. You take a linear space, if you get a tropical cone, and you have also extreme directions, So here is a more interesting example,
37:04
so it's a tropical city polytope, made up of a physical object, and so this general tropical polydrome, they are known to be polydrome complex, as we studied by Guillaume Stenfels, and we talked about other sets of this polydrome complex, they have a remarkable structure,
37:21
they are so called alcove polydrones, alcove polydrones have been introduced by Fosdikov, they are a set of x polydrones, of the form xi minus xj, smaller than some constant eigen, meaning that the normal to the cassettes are vectors of the root system at the end. So this, you can think of the tropical polydrome, as a complex to the other sets,
37:42
are of this selection, this is a more special. Now, the link with non-archeme game complexity. So, now we go to the classical world, the classical convex side, because we don't need to solve inner programming, we need to solve the convex programming problem.
38:01
So for that, it will be convenient to work, we need to have a parameter, so we need to work with a real cross field, with a non-archeme variation, whose value group is the real number. So, a good example of that, is the set of generalized Poisson series, we can take the parameter, consider a series in this parameter p, so the coefficient of the real cross field,
38:23
the coefficient ci would be r, and I will take the exponent in r also, which is a bit unusual, but it's useful for the enemy, to have a real radical. And for this to be a field, we need to assume that the sequence of the exponent goes, is to be decreasing, and goes to minus infinity.
38:42
So, you have a Gaussian with normal series, and you have a Gaussian with absolute convergence series, and the fundamentalists on the space theory are shown, that you run the real cross field, you consider absolute convergence series. So this is convenient, it's unparticular, identifying the variation of the series,
39:01
as the log limit, the limit when t, the parameter t, goes to cross infinity, takes a positive value, of the logarithm of x, divided by the logarithm, this is also really my next comment. Now, here is the, So let me recall,
39:20
that if you have a, normal field, you can define a basic, semi algebraic set. So you take a field number, of a polynomial, or you can, you are allowed to write the equities, in the discrete, or equities. So if the set is written by a field number, of equities,
39:40
and speaks equities, it's called the basic semi algebraics, or the semi algebraic, it is a finite union, of basic semi algebraic sets. Also, you know, if you have, so this is for subset of the field, now you can consider subsets, of the value group, subset of the ein. So, a subset of the ein,
40:01
will be basic semi linear, is, well, again, given by, equities, or equities, you have the right hand side, is a real number, on the left hand side, is a linear form, with integer coefficient. Since we are starting from polynomials,
40:20
this one is the coefficient of the linear form, will be the exponent of the polynomial, in many ways. So you have to, it's essential to get the integer coefficient. And so this object is called, the basic semi linear, and the semi linear, is a set, is a finite union of basic semi linear. So, it's knowing that,
40:41
if I take a semi algebraic set, then the, so I will take it to the, positive, orthon, and the variation of this set, is semi linear, on this plot. By taking the variation, the stupid equity, becomes weak equity. And, it also follows, from older result, it's a different generality, called, the Deneff pass, concipiter elimination,
41:02
in a, theory of other fields. So, there are, different approaches, in this field. And then, here is something more, but you want to, not only, to do, concipiter elimination, which is very expensive, after something more constructive, and more expensive. So, there is no way, you can compute the image, by the variation, of, some basics,
41:21
as you already said. You consider, number of inequalities, so, polynomial inequalities. And so, you want to compute the image, by the variation. So, you can write, an equality of a form, p, polynomial inequalities, p minus x, minus on t plus x, where you put, all the positive, non-negative terms at left,
41:41
all the non-negative terms at right. And then, you can do a naive, topicalization, which is, well, if, you have, a point x, which is a solution of this inequality, you consider the value of x, you apply the variation, to the left or right, and so, you see that the value, variation, of x, satisfies some, this was linear inequality,
42:01
when you apply the sum, by the maximum, and you take variation of prediction. So, what is, a, a, is to say that, well, the, variation, of the intersection, set defined by, the equality, is already included, it satisfies this relation.
42:21
the max pre-correlation, it's obvious that, it satisfies that, in both, the intersection, of this, of this set. But, the interesting part of this result, is that, the real quality of, that is, when you take variation, you have, a sandwich collapse, a sandwich collapse, well, if, when you compute the, which is the tropical set,
42:40
the set defined by this inequality, it is the closure, of its interior. In particular, this occurs, if you take general evaluation of polynomials. Let me show you. Here is a simple example. You take a single polynomial inequality, x1 squared smaller than t, x2 plus t4, x2, x3. You take, the, to be the variation,
43:00
you just, tropicalize the inequality, so 2x1 smaller than max. And, well, so here, you know, since there is a single inequality, it's only this poo. So, if the set that you obtain is, of an interior, then, actually, it is the true variation.
43:22
For instance, if you consider a set like that, it is the closure of its interior, so you can obtain it by this technique. Well, so we have a following general, quite general correspondence. So, you take a subset of N higher, particularly, to say, that this set is the image by variation
43:41
of the convex algebraic code. you know, it's a pretty qualitative effort of, in the series of my finger. It's the same as saying that it's a closed tropical convex code with an odd system in the air. And it's the same to say, as there is a shapely operator, so we have to allow a stochastic game.
44:02
However, we have finite action spaces of the right transition probability and rational numbers. And so, the image by a variation of convex algebraic codes are precisely the set of several unique vectors of the shapely operator, with the actions on the rational probability.
44:23
So, the way, so in a certain way, is a kind of equivalence between convex algebraic sets on the ring of a game of convex equivalence, with the dual relation. So, the way this is proven is by considering working on the case of spec-hydra. So, a spec-hydra,
44:40
it is a set of vectors, S, such that you take a fine combination of symmetric matrices, and you want that the fine combination is positive symmetric. So, this is known as a spec-hydron, it is a degeneration of a notion of polynomial. And so, you can define topical spec-hydron as image by variation of the spec-hydron.
45:01
And so, the way to prove that, when you consider the variation of a convex algebraic set, you get, well, the symbolic vector of a Chapeau operator, you consider the special case of the spec-hydron. On the even starting, you have a more special case called Bézier spec-hydron, where the all-degenerative is a monoid and a composite b. And then,
45:20
you apply the previous version of Kapanov theorem, when you say that the variation commutes with intersection and their generic condition. And then, in that way, when you tropicalize the mean, if you make which is positive to be definite, you have a formula for the r1 and r2, because they are negative. And if you tropicalize this relation, you see that they are sufficiently characterized
45:40
by the variation. And when you write them, you have a nice vector 2, which will give you probability one-half of the Chapeau vector. Essentially, this result of correspondence, does by considering the case of spec-hydron. This corresponds to games with probability one-half. So,
46:02
voilà. So, this is the reality to what is called the Dominique conjecture in convex programming, which is not true in the classical case, and which is true in the tropical case by this way. So, let's consider the special case of polydron, which is a bit understood. So, a tropical polydron,
46:21
well, it is precisely a limit of a image by variation of a classical polydron of a polydron over a physical region. it was nothing. So, you should take a classical polydron in a a polydron in a real piece of theory to take the Dominique image and then deform it when you are thinking
46:41
of converging to a tropical polydron. So, when you have that, you can consider a tropical linear program, which is a state linear inequality, and in other words, it is related to non-archival linear programs. So, the result is that, well, you consider,
47:00
well, polydron over the piece of theory, in the on the consider an image by the variation and so, if the matrices of the matrices A, B are originated in some sense, then you know that the variation is given by a nice configuration by the inequality.
47:21
About this, this is what I said, but there is more of a precise result. That is, the tropical polydron, this is the main thing, the tropical polydron, on the non-archival polydron, there is exactly the same parameter. At least they will have the same product, in some good sense, they have the same engine, etc.
47:42
So, when you have this, and so, you see, this is the future. For instance, this is the conical polydron.
48:01
So, in corresponds to classical polydron, with the large parameter p, on the theorem, is at the extent that we have to see they have the same configuration. So, when you have that, you have the theorem where you have to say that sign genericity is explicit. You have to consider a minor of a matrix, and you can check that you are generic with
48:20
all the permutation which achieve maximum minor. So, you have the same condition, you must have the same sign. So, there is explicit whole of genericity in terms of the optimal problem. Otherwise, if you are not engineering, you have
48:40
this limit doesn't commute with the intersection. I am very close to the end, if my schedule is correct. So, this is how the algorithm is better, because
49:01
when you have an empty of game, you can list it to a linear instance. So, if you had an algorithm to solve the linear problem, you could apply it to the linear instance, simulate it using only variation, and you can solve the linear problem. I like to
49:21
show a bit more about the central path. The way it is done, the central path is algebraic, which is given by the we define the path as
49:40
a log limit of a classical central path. This is a physical linear curve, and it is not so difficult to show that the physical linear
50:08
path is no longer interior of the central path. So, with that we can make a good time example.
50:20
Well, the total curvature of the central path is exponential because the central path is exponential because also it is a classical linear path method. On this example, if a large
50:40
parameter T can do it, and it makes an exponential normal direction, which is bad all the time. I'm happy to answer all the questions. Thank you very much, Stefan.
51:06
Any questions for Stefan? I have one. Yes, please, Gerard. Yes, thank you, Stefan, for your
51:21
account. I am not a specialist, but you were speaking about total curvature. What does it mean exactly? Ah, very good. I think it is not far, two or three slides.
51:41
What is the normal of terms? it is the integral of acceleration, the norm of acceleration, if you move at unit speed on the curve. So, another nice way to
52:00
see that is that become discrete i. So, maybe it will be the total curvature, and that way is defined for motion occur, it will be the supremum over all piecewise linear approximation of the curve, you take poles,
52:21
and you take the sum of angle, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10,
52:46
T11,
53:02
T12, T13, T14, T15, T23, T26,