1. 引言：探寻新的优化基础图元
1.1 半代数世界的计算壁垒
在现代运筹学与数学规划的理论体系中，由多项式等式和不等式定义的可行域扮演着核心角色。这些“基础图元”通过有限次逻辑运算（交、并、补）构成的集合，即半代数集（semi-algebraic sets），能够描述从线性规划到非凸多项式优化等极为广泛的问题 [1]。这种普适性为理论分析提供了统一的语言，但也带来了巨大的计算代价。当前，分析这些由多项式定义的世界主要沿循两条路径，然而，这两条路径都最终通向了某种形式的计算困境，从而激发了学界寻找全新基础图元的探索。
第一条路径是精确但棘手的几何分解。以柱形代数分解（Cylindrical Algebraic Decomposition, CAD）为代表，该方法在理论上为任何由多项式定义的问题提供了完整的解决方案。其核心思想是将高维空间精确地剖分为有限个拓扑简单的“单元格”，在每个单元格内部，所有相关多项式都保持恒定的符号 [1]。然而，CAD的理论完备性是以巨大的计算复杂度为代价的。该算法在最坏情况下的计算复杂度是关于变量数量的双指数级，这使得其在优化领域的直接应用几乎不存在，更多地是作为一种理论工具 [1]。
第二条路径是近似但易于爆炸的代数松弛。以平方和（Sum-of-Squares, SoS）/Lasserre层级为代表，该方法放弃了对可行域的精确几何分解，转而从代数上构造一系列越来越紧的凸松弛 [1]。通过将非负多项式约束加强为“是一个平方和多项式”，原非凸问题可以被转化为一个半定规划问题（Semidefinite Program, SDP），而SDP存在多项式时间解法。尽管SoS/Lasserre层级在理论上极为强大，但它同样面临着“维度灾难”的挑战。在第
这两条路径揭示了一个深刻的困境：我们被迫在理论上完美但计算上无望的精确几何分解（CAD），与实践中更可行但仍受制于组合爆炸的代数逼近（SoS）之间做出选择。这种两难局面表明，问题的根源可能在于基础图元本身。多项式虽然表达能力强大，但其复杂的非线性结构内生性地导致了分析工具的复杂性。这正是探索更具良好计算性质的新基础图元的根本动因。
1.2 作为范式转移的热带几何
为了突破半代数世界的计算壁垒，一个激进但富有成效的思想是彻底改变运算规则本身。热带几何（Tropical Geometry）正是这样一种理论，它通过用一套新的代数系统——热带半环（tropical semiring）——替换传统的实数域，从而将复杂的代数几何问题转化为更易于处理的分段线性和组合问题 [1, 2]。
热带几何的基石是其独特的算术规则。最常用的形式是“最小-加”代数（min-plus algebra），其定义在集合
- 热带加法：
- 热带乘法：
相应地，“最大-加”代数（max-plus algebra）将热带加法定义为
下表总结了半代数范式与热带几何范式在优化问题上的核心特征对比。
表1：优化范式对比
| 特征 | 半代数几何 (当前主流) | 热带几何 (新兴路径) |
|---|---|---|
| 基础图元 | 多项式 | 热带多项式 (线性函数的最小/最大值) |
| 几何对象 | 光滑/奇异的代数簇 | 分段线性的多面体复形 |
| 核心计算工具 | 柱形代数分解 (CAD) / 平方和 (SoS) 层级 | 热带线性系统/特征值求解器 |
| 主要计算特性 | 双指数级 / 高阶多项式组合爆炸 | 通常为 |
2. 热带优化研究的版图
热带几何在运筹优化领域的研究可以被清晰地划分为三个既独立发展又相互关联的主要分支。这三个分支代表了三种利用热带几何的不同哲学：作为分析工具、作为建模语言，以及作为解释框架。
分支 A：经典算法的分析 (Analysis of Classical Algorithms) 该分支将热带几何作为一种新颖的分析透镜，用于审视和理解经典（非热带）优化算法的内在复杂性和行为。它并不直接解决热带问题，而是通过“热带化”一个经典问题，揭示其潜在的组合结构。这一方向的标志性成就是对线性规划（LP）内点法复杂性的深刻分析。
分支 B：直接的热带优化 (Direct Tropical Optimization) 该分支致力于构建一个原生的热带优化理论体系。在这里，问题从一开始就在热带半环中被表述和求解。研究重点包括发展热带线性代数、建立热带线性规划（TLP）的对偶理论，以及设计求解这些原生热带问题的算法。许多经典的组合优化问题，如最短路径和调度，都可以在这个框架下得到自然的表述。
分支 C：机器学习的连接 (The Machine Learning Nexus) 该分支探索了热带几何与现代机器学习，特别是深度学习之间深刻的、结构性的等价关系。研究发现，使用修正线性单元（ReLU）激活函数的前馈神经网络在数学上等价于一个热带有理函数。这一发现为理解神经网络的“黑箱”行为提供了强有力的几何与组合工具，催生了对网络表达能力、决策边界和模型压缩等问题的新见解。
这三个分支虽然关注点不同，但共享同一个核心思想：通过从经典代数到热带代数的转换，将复杂的非线性或连续问题转化为更易于分析和处理的分段线性与组合问题。它们共同构成了热带几何在运筹优化领域的研究全景图。
3. 主要学派的深度剖析
3.1 复杂性分析学派：线性规划的热带放大镜
这一学派的卓越贡献在于，它展示了热带几何不仅能解决“热带”问题，更能为经典的连续优化问题提供深刻的洞见。其焦点集中在线性规划（LP）的一个核心未解之谜：强多项式时间算法的存在性。
3.1.1 强多项式时间问题与中心路径
长期以来，运筹学界一直在寻找一个“强多项式时间”的LP算法，即算法的算术运算次数仅由变量数
3.1.2 热带中心路径的引入与分析
Allamigeon、Benchimol、Gaubert和Joswig等人的开创性工作，通过引入“热带中心路径”的概念，从根本上解决了上述问题 [10, 11, 12, 13]。其核心方法论如下：
- 参数化与赋值： 他们构造了一个依赖于参数
的LP族 。通过将这个问题置于一个包含参数 的Puiseux级数域（一种非阿基米德域）上，他们可以利用该域上的“赋值”（valuation）操作，将连续的中心路径映射到一个分段线性的对象上。 - 热带中心路径的定义： 这个分段线性的极限对象，就是“热带中心路径” [1, 6, 7]。它本质上是在对数坐标下观察经典中心路径的极限行为，从而剥离了其连续几何特性，仅保留了其核心的组合结构。
- 组合复杂性作为下界： 热带中心路径由有限段线性片段构成。研究者证明，当参数
足够大时，经典中心路径的迭代次数和总曲率，都可以由热带中心路径的线性片段数量（即“拐点”数量）来提供一个严格的下界 [6, 7]。
3.1.3 “又长又弯”的构造与结论
通过一个精巧的归纳法，他们构造出的
- 连续版Hirsch猜想被证伪： 由于总曲率被热带路径的片段数所下界，因此存在总曲率随维度指数增长的LP实例。
- 对数障碍内点法非强多项式时间： 同样，算法的迭代次数也具有指数级的下界，从而证明了这类主流的内点法并非强多项式时间的。
这一系列工作充分展示了热带几何作为分析工具的威力。它通过一种“退量化”的视角，将一个复杂的连续优化问题（LP）的算法路径，转化为一个更简单的组合对象（热带中心路径），并通过分析这个组合对象的复杂性，反过来为原问题的算法复杂性提供了深刻且确凿的界限。
3.2 直接表述学派：最大-加世界中的优化
与将热带几何作为分析工具不同，该学派致力于在热带半环的框架内直接建立和求解优化问题。这一方向的研究历史悠久，与离散事件动态系统、图论和调度理论等领域紧密相关 [3, 5, 14]。
3.2.1 热带线性代数与对偶理论
该学派的理论基石是热带线性代数。研究者们定义了热带环境下的矩阵运算、线性方程组和特征值问题等 [4, 5]。在此基础上，热带线性规划（Tropical Linear Programming, TLP）被定义为在热带线性约束下，最大化（或最小化）一个热带线性目标函数的问题 [4]。一个核心的理论成果是热带线性规划的强对偶定理，该定理证明了在原始问题和对偶问题之间不存在对偶间隙（duality gap）[4, 5, 15]。
3.2.2 核心算法挑战：求解热带线性系统
求解形如
- 与博弈论的等价性： 求解这类系统被证明等价于在图中寻找特定策略的平均收益博弈（mean payoff games）问题 [8, 15, 16]。这一深刻的联系将热带优化与理论计算机科学中的一个重要领域连接起来，使得两个领域的算法和思想可以相互借鉴。
- 复杂的复杂性状态： 求解热带线性系统问题属于
复杂性类 [1, 17]。这个事实意义重大：一方面，它暗示该问题不太可能是NP完全的，因为这会意味着 ，这是一个大多数理论计算机科学家不相信的猜想；另一方面，尽管有强烈的证据表明多项式时间算法应该存在，但至今尚未被发现。目前已知的算法，如Grigoriev的算法，都是伪多项式时间的，其运行时间依赖于输入系数的大小 ，而非仅仅是其比特长度 [18, 19]。寻找一个真正的多项式时间算法是该领域最重要的公开难题。
3.2.3 扩展与应用
该学派的研究也扩展到了整数和非线性领域。热带整数线性规划（TILP）已被证明具有良好的性质，其原始问题和部分对偶问题存在直接解 [4, 15]。此外，针对目标函数为热带多项式或更复杂形式的优化问题，也已发展出基于变量消去法（类似于Fourier-Motzkin消去）或专门的下降算法 [1, 16, 20]。
在应用层面，许多经典的运筹优化问题本质上就是热带的。图中的最短路径问题可以被完美地用“最小-加”代数下的矩阵乘法来表述；项目管理中的关键路径法（CPM）和许多动态规划问题则天然地对应于“最大-加”代数 [1, 3, 21]。这使得热带几何成为描述和解决这类组合优化问题的优雅而强大的语言。
3.3 机器学习连接：神经网络的几何本质
近年来，一个令人兴奋的研究方向揭示了热带几何与深度学习之间深刻的内在联系。这一发现为原本被视为“黑箱”的神经网络提供了强有力的理论分析工具。
3.3.1 数学等价性：ReLU网络与热带有理函数
核心发现是：一个使用修正线性单元（Rectified Linear Unit, ReLU）激活函数的前馈神经网络，其所计算的函数在数学上等价于一个热带有理函数（即两个热带多项式的商）[1, 22, 23, 24]。
- ReLU作为热带多项式： ReLU函数
本身就是一个简单的热带多项式，即 （在max-plus代数中）。 - 网络作为函数复合： 由于神经网络是通过复合大量的仿射变换和ReLU激活函数而构建的，其最终所表达的函数必然是一个连续分段线性函数，而这类函数正是热带几何的核心研究对象。
这一等价性并非巧合或类比，而是一种严格的数学对应。它表明，深度学习在工程实践的演化过程中，无意间发现并利用了一种本质上是热带的计算模型。
3.3.2 决策边界作为热带超曲面
这一数学等价性带来了深刻的几何后果。对于一个训练好的分类神经网络，其复杂的决策边界可以被精确地理解为一个热带超曲面 [1, 23, 25]。这个超曲面将输入空间剖分为一个多面体复形（polyhedral complex），其中每一个多面体（胞腔）精确对应于网络函数的一个线性区域。对这个多面体复形的几何与组合性质的分析，为理解网络的行为提供了全新的视角。例如，可以使用热带几何中的佐诺托普（zonotope）等概念来刻画这些线性区域的结构 [23, 25]。
3.3.3 在机器学习理论中的应用
这种几何视角正在催生大量前沿研究，将经典的几何与组合数学工具应用于分析深度学习模型：
- 表达能力与复杂性： 通过计算网络对应的多面体复形的线性区域数量，可以为网络的表达能力和模型复杂性提供一个定量的、几何化的度量 [1, 24]。
- 网络剪枝： 可以将网络剪枝问题重新表述为一个几何问题：移除那些对决策边界（即热带超曲面）的几何形状贡献很小的神经元或权重，从而在不显著影响性能的前提下压缩模型 [1, 25]。
- 鲁棒性与对抗性攻击： 对抗性攻击可以被理解为寻找一种微小的输入扰动，使得输入点能够跨越决策边界多面体的一个面，从而改变分类结果。对决策边界局部几何的理解，有助于设计对这类攻击更具鲁棒性的网络结构 [1, 9]。
这一学派的研究为深度学习的理论基础提供了坚实的数学基石，将一个经验驱动的领域与一个深刻的数学理论联系起来，为未来的模型分析和设计开辟了新的道路。
4. 综合与比较分析
对上述三个主要研究学派的深入剖析揭示了热带几何在优化领域扮演的多重角色。它们的目标、方法和面临的挑战各不相同，共同构成了一幅丰富而多样的研究图景。下表对这三个学派进行了系统的比较。
表2：热带优化研究学派的比较分析
| 特征 | 复杂性分析学派 | 直接表述学派 | 机器学习连接 |
|---|---|---|---|
| 主要目标 | 分析经典算法的内在复杂性 | 建立并求解原生的热带优化问题 | 解释和分析ReLU神经网络的行为 |
| 核心热带工具 | 热带中心路径 | 热带对偶理论 / 线性系统求解器 | 热带有理函数 / 热带超曲面 |
| 贡献性质 | 理论复杂性下界 (分析性) | 新的算法与优化理论 (构造性) | 解释性框架与新视角 (描述性) |
| 关键瓶颈/挑战 | 将分析结果转化为新算法设计 | 为 | 将理论洞见转化为实用的ML改进 |
| 主要发表领域 | 顶尖优化/计算理论期刊 (SIAM Review, SIAM J. on Optimization) | 运筹/代数/离散数学期刊 (JOTA, DAM) | 顶尖机器学习会议 (NeurIPS, ICML, ICLR) |
这种比较清晰地表明，这三个学派并非相互竞争，而是互为补充。复杂性分析学派展示了热带几何作为一种强大抽象工具的“向外”应用潜力；直接表述学派则致力于构建一个自洽的“向内”的理论体系；而机器学习的连接则是一个“意外的发现”，揭示了热带结构在现代计算模型中的普遍存在性。
5. 研究缺口识别
基于以上分析，当前热带几何与运筹优化的交叉研究领域存在以下几个明显的缺口：
-
核心算法缺口： 这是最关键且被反复提及的缺口。为求解一般热带线性系统（以及与之等价的平均收益博弈）设计一个（强）多项式时间算法，仍然是该领域的“圣杯”问题。现有伪多项式时间算法的局限性，阻碍了直接热带优化方法在处理大规模、系数范围广泛的实际问题时的应用 [1, 17]。
-
从分析到综合的转化缺口： 复杂性分析学派的工作虽然深刻，但其成果主要是“否定性”的（证明了某类算法不是强多项式时间的）。如何将从热带中心路径等分析工具中获得的洞见，转化为设计新的、性能更好的经典LP算法的指导原则，目前尚无明确路径。这形成了一个从理论分析到算法综合的鸿沟。
-
机器学习理论到实践的转化缺口： 尽管热带几何为ReLU网络提供了优美的几何解释，但这些理论洞见在多大程度上能指导实际的机器学习工程实践，仍是一个开放问题。例如，如何设计一种“热带几何感知”的正则化项或优化器，使其在训练过程中能够利用或塑造出更优的决策边界几何结构，从而在准确性、鲁棒性或泛化能力上取得可验证的提升，这方面的研究尚处于起步阶段。
-
热带凸优化理论的统一缺口： 目前直接表述学派的研究大多集中在热带线性规划上。一个更广泛、更统一的热带凸优化理论体系尚未完全建立。虽然已有工作触及了热带凸集（如热带多面体）和某些特殊凸函数（如L-凸函数）[16]，但缺乏像经典凸优化那样成熟的理论框架（如次梯度、共轭函数、Fenchel对偶等）。建立这样一套理论，有望将许多离散的组合优化问题置于一个统一的凸优化框架下进行分析和求解。
6. 初步研究设想
针对上述识别出的核心算法缺口，提出一个具体的研究问题。
研究问题： 面向结构化实例的热带线性系统多项式时间求解算法研究
问题阐述： 与其直接挑战为一般热带线性系统设计通用多项式时间算法这一极其困难的公开问题，本研究建议将焦点缩小到在运筹学应用中频繁出现的结构化实例上。许多源自调度、网络流或离散事件系统建模的问题，其对应的热带线性系统（或平均收益博弈图）往往具有特殊的图结构，例如稀疏性、低树宽（low treewidth）、近似平面性或特定的社群结构。
本研究的核心设想是，能否借鉴图算法和数值线性代数领域的思想，为这些具有特殊结构的实例开发专门的多项式时间算法。具体可以探索以下路径：
- 图分解方法： 对于具有低树宽或类似分解性质的图，研究是否可以应用动态规划或分治策略来求解相应的平均收益博弈。
- 组合预处理器： 借鉴数值计算中预处理器的思想，研究是否可以设计一种组合预处理技术（如通过图稀疏化或谱方法），将一个结构化的热带系统转化为一个“更容易解”的等价系统，然后再应用现有的伪多项式时间算法。
- 参数化复杂性： 从参数化复杂性的角度分析该问题。以图的某个结构参数（如反馈顶点集大小）为参数，设计固定参数可解（FPT）算法。
潜在价值： 这项研究的价值在于其高度的现实意义和理论意义。
- 实践价值： 即便不能解决一般情况下的问题，一个针对广泛存在的结构化实例的高效多项式时间算法，也将是该领域的重大突破。它将使得直接热带优化方法能够应用于更大规模的实际问题，从而将优雅的理论模型转化为实用的优化工具。
- 理论价值： 该研究可能为解决一般性问题提供新的思路。通过理解特定图结构如何导致问题变得“易解”，可能会揭示出解决一般问题所需的关键性质或不变量，为最终攻克这个
难题铺平道路。这代表了一条从特殊到一般的、务实的研究路径，旨在弥合当前理论与应用之间的鸿沟。
7. 参考文献
Allamigeon, X., Benchimol, P., Gaubert, S., & Joswig, M. (2015). Tropicalizing the simplex algorithm. SIAM Journal on Discrete Mathematics, 29(2), 751-795. [13]
Allamigeon, X., Benchimol, P., Gaubert, S., & Joswig, M. (2018). Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry, 2(1), 140-178. [13]
Allamigeon, X., Benchimol, P., Gaubert, S., & Joswig, M. (2021). What tropical geometry tells us about the complexity of linear programming. SIAM Review, 63(1), 123-164. [9, 10, 11, 26]
Butkovič, P., & MacCaig, M. (2019). On tropical linear and integer programs. Journal of Optimization Theory and Applications, 180, 1011-1026. [4]
Davydow, A. (2013). New algorithms for solving tropical linear systems. arXiv preprint arXiv:1309.5206. [17]
De Wolff, T., & Telen, S. (2024). TropNNC: Structured Neural Network Compression Using Tropical Geometry. arXiv preprint arXiv:2409.03945. [1]
Grigoriev, D., & Podolskii, V. V. (2018). Complexity of solving tropical linear systems. Computational Complexity, 27(1), 81-112. [18, 19, 27]
Joswig, M., & Loho, G. (2020). A combinatorial abstraction of tropical linear programming. The Electronic Journal of Combinatorics, 27(2), P2-51. [8]
Krivulin, N. (2014). Tropical optimization problems with application to project scheduling with minimum makespan. arXiv preprint arXiv:1403.0268. [21]
Krivulin, N. (2021). Algebraic solution of tropical polynomial optimization problems. Mathematics, 9(19), 2472. [20]
Maragos, P., Charisopoulos, V., & Papadakis, A. (2021). Tropical geometry and machine learning. Proceedings of the IEEE, 109(5), 831-860. [1]
Naitzat, G., Zhitomirskii, L., & Lim, L. H. (2020). On the decision boundaries of deep neural networks: A tropical geometry perspective. arXiv preprint arXiv:2002.08838. [25]
Serrano, F., & Yoshida, R. (2023). Tropical geometric tools for machine learning: The TML package. arXiv preprint arXiv:2309.01082. [1]
Skomra, M. (2025). Combinatorial algorithm for tropical linearly factorized programming. arXiv preprint arXiv:2507.07596. [16]
Srivastava, S., Murali, P., & Lerman, G. (2024). Tropical decision boundaries for neural networks are robust against adversarial attacks. arXiv preprint arXiv:2402.00576. [1]
Tošić, P., & Stanić, M. (2024). Graph neural networks are tropical rational signomial maps. In Advances in Neural Information Processing Systems. [24]
Zhang, L., Naitzat, G., & Lim, L. H. (2018). Tropical geometry of deep neural networks. In International Conference on Machine Learning (ICML) (pp. 5824-5832). PMLR. [22, 23]