特色项目
摘要（TL;DR）：本案例研究展示了 LinkedIn 如何通过开发基于 GPU 加速的 PyTorch 版本，重新架构其分布式线性规划求解器 DuaLip，以应对 Web 应用等领域的超大规模优化挑战。从以 CPU 为核心的架构迁移至此，实现了数量级的速度提升和高效的多 GPU 扩展，同时降低了工程开销。
引言
现代互联网平台不仅能进行预测，还能做出决策。在 LinkedIn 这样的公司，这些决策为大规模 Web 应用的智能行为提供了支持。
在幕后，这些系统中的许多问题最终都会归结为一个看似简单的问题：
在拥有数百万（或数十亿）个选项的情况下，如何在满足约束条件下采取最优行动？
这就是线性规划（LP）的用武之地，它作为一种基础数学框架，用于在约束条件下优化目标。在 LinkedIn 的规模下，这些线性规划问题可能涉及数亿用户和数万亿个决策变量，且包含稀疏但结构高度复杂的约束矩阵。传统的线性规划求解器（如单纯形法和内点法）历史上一直是优化领域的主力。然而，它们依赖矩阵分解或基更新，这在超大规模场景下会带来高昂的内存和计算成本。因此，它们往往无法高效处理现代 Web 规模的问题。
商业挑战
我们的目标是在相互竞争的目标下优化大规模决策系统。
例如：
- 将职位与潜在求职者进行匹配。
- 在排名或推荐系统中平衡多个业务指标。
- 优化发送给用户的邮件数量。
这些本质上是具有挑战性的优化问题，改善一个指标（例如点击率）可能会损害另一个指标（例如投诉率）。从形式上讲，这些问题被表达为线性规划：
- 目标：最大化业务价值（例如参与度、收入）。
- 约束：强制执行限制（例如预算、公平性、频率）。
关键瓶颈在于可扩展性：随着问题规模的扩大，要在生产环境中支持快速、可重复的优化，需要同时兼顾内存和时间效率，并保持稳定性和解的质量的实现方案。
近年来，一阶方法已成为解决此类大规模线性规划问题的实用替代方案。与经典方法不同，这些方法仅依赖梯度信息，避免了昂贵的矩阵分解，使其核心操作主要集中在矩阵-向量乘法上。特别是原始-对偶（primal-dual）形式已被证明非常有效：它们将线性规划重构为鞍点问题，并迭代更新原始变量和对偶变量直至收敛，通常能为生产系统提供足够精确的解。
这一研究方向催生了新一代的大规模求解器，包括谷歌的 PDLP 和 LinkedIn 的 DuaLip。DuaLip 尤其是一个基于岭正则化对偶上升法和一阶优化的分布式求解器。它利用了匹配问题的可分解结构，并结合加速梯度更新及高效的投影算子，能够扩展到超大规模的问题。
虽然 DuaLip 证明了一阶方法可以处理生产环境下的 Web 规模线性规划，但其最初基于 Scala/Spark 栈的实现本质上仍受限于 CPU。这限制了它充分利用现代硬件加速器的能力。此外，其基于模式绑定、模板驱动的接口使得扩展到新的问题形式变得困难，减缓了应对不断变化的用例的迭代速度。
受这些局限性的驱动，我们使用 PyTorch 和 GPU 加速重新架构了 DuaLip 求解器栈，从而推出了 DuaLip-GPU，这是一个面向工业级优化的现代、灵活且可扩展的系统。
LinkedIn 如何使用 PyTorch
为了应对这些挑战，我们提出了 DuaLip-PyTorch，将其作为大规模优化的核心执行引擎——不仅仅是深度学习引擎。该系统围绕算子级的数组/张量编程模型（采用 PyTorch 的“运行时定义”范式）构建，而不是任务级的“调用求解器”API。
具体而言，热路径（hot path）表现为在稀疏矩阵-向量运算和分块投影上的显式数据流，由轻量级最大化器进行编排。这种设计界限是刻意为之的：它暴露了主导运行时间的内核，实现了对稀疏布局和投影算子的灵活选择，并能自然地映射到 GPU 执行——且无需修改核心优化循环。
使用 PyTorch 解决 AI 挑战
PyTorch 提供了原生的 GPU 加速、适用于稀疏和密集计算的灵活张量抽象，以及用于梯度计算的高效矩阵-向量运算。这些功能共同使得大规模线性规划求解在结构上看起来类似于神经网络训练，但使用了针对优化优化的原语。在 LinkedIn，这些特性帮助解决了三大系统和优化挑战。
首先，包含数万亿变量的超大规模线性规划问题通过稀疏张量运算和批量投影内核实现，从而在 GPU 上实现高效执行。
其次，分布式优化通过在 GPU 之间划分变量，同时通过诸如 all-reduce 和广播等集合通信模式复制和同步对偶变量来实现，从而允许在设备之间进行近乎线性的扩展。
第三，通过行归一化和缩放以改善条件数、正则化延续策略以及包括 AGD 和 FISTA 变体在内的可扩展一阶优化方法，提高了收敛速度。这些改进在保持精度的同时显著缩短了求解时间。
图 1. Dualip-Pytorch 的高层架构
使用 PyTorch 的优势
使用 PyTorch 使 LinkedIn 能够：
- 在基于 CPU 的系统基础上实现数量级的速度提升。
- 从单 GPU 高效扩展到多 GPU 系统。
- 支持灵活、可扩展的线性规划形式。
- 降低新优化问题的工程开销。
- 将机器学习和优化融合到一个统一的栈中。
最重要的是，它通过围绕 GPU 高效的稀疏线性代数重构求解器，实现了以前无法实现的规模下的生产级优化。
DuaLip-Pytorch 中的主要计算由重复的稀疏矩阵-向量乘法和投影更新组成，这些计算可以自然地映射到高吞吐量的 GPU 执行中。通过将这些操作表示为 PyTorch 中的批处理张量内核，并利用同步集合通信将其分发到多个 GPU，该系统与原始基于 CPU 的实现相比，显著降低了每次迭代的求解时间。
图 2. 相比理想情况（线性线）的 GPU 数量加速曲线。所有 GPU 位于同一个节点上。
图 3. Scala 与 Pytorch 在速度和相对误差方面的比较。Pytorch 求解器（8 个 GPU）在每次迭代的运行时间上表现出显著优势（快 75 倍）。
了解更多
更多信息
- DuaLip-GPU 技术报告：https://arxiv.org/abs/2603.04621
- 开源实现：https://github.com/linkedin/DuaLip