>>16631591
>Yes, there are deep and powerful connections between tropical geometry/algebra and linear programming. For specific classes of optimization problems (especially those related to dynamic programming, shortest paths, scheduling, mean payoff games), tropical algebra provides a natural framework and effective solution methods that link directly to LPs.

>Specific LP Classes: Certain classes of problems that can be formulated as LPs are also naturally described and solved using tropical algebra. A prime example is finding the optimal average cost (or payoff) in deterministic games or Markov decision processes (Mean Payoff Games). These problems can be formulated as LPs, but algorithms like Karp's algorithm or value iteration, which have strong tropical interpretations, are often more direct or insightful.
>Value Iteration & Bellman Equations: The Bellman equations used in dynamic programming often resemble tropical matrix-vector multiplication when looking for optimal values. Value iteration corresponds to repeated application of these tropical operations. Dynamic programming problems can sometimes be cast as LPs.
>Duality and Legendre-Fenchel Transform: There are deep connections between LP duality, convex analysis (especially the Legendre-Fenchel transform), and tropical geometry/algebra. Tropical geometry provides a combinatorial, piecewise-linear view of these concepts.
>Combinatorial Structure: Tropical geometry excels at revealing the underlying combinatorial structure of optimization problems. Since the optimal solutions to LPs occur at the vertices of a polyhedron (a combinatorial object), tropical methods can sometimes provide insights into this structure.

Back | Go to board

Board:

/sci/

Thread:

Wait, so I can just use tropical geometry to solve linear programs using algebra? Excuse me, but what the fuck?