↖  每天赚1万美元的Polymarket钱包-2: 数学 策略-3 #整数 ..

每天赚1万美元的Polymarket钱包-2: 数学 策略-3

第三章：Frank-Wolfe 算法——让理论变成可执行的代码

好，现在你知道了：要算最优套利，就要做 Bregman 投影。

但问题是——直接计算 Bregman 投影是不可行的。
为什么？因为无套利空间（边际多面体 M）有指数级多的顶点。标准的凸优化方法需要访问完整的约束集，也就是枚举每一个合法结果。我们刚才说了，这在规模化场景下是不可能的。

Frank-Wolfe 的核心思想

Frank-Wolfe 算法 [7] 的天才之处在于：

它不试图一次性搞定整个问题，而是一步一步逼近答案。

它的工作方式是这样的：

第一步： 从一个小的已知合法结果集合开始。
第二步： 在这个小集合上做优化，找到当前最优解。
第三步： 用整数规划找到一个新的合法结果，加入集合。
第四步： 检查是否足够接近最优解。如果不够，回到第二步。

每一轮迭代，集合只增加一个顶点。即使跑了 100 轮，你也只需要追踪 100 个顶点——而不是 2^63 个。

Frank-Wolfe 迭代过程

想象你在一个巨大的迷宫里找出口。

暴力方法是把每条路都走一遍。

Frank-Wolfe 的方法是：先随便走一条路，然后在每个岔路口问一个”向导”（整数规划求解器）：   “从这里开始，哪个方向最可能通向出口？”

然后朝那个方向走一步。你不需要探索整个迷宫，只需要在每个关键节点做出正确的选择。

整数规划求解器：每一步的”向导”

Frank-Wolfe 的每一轮迭代都需要解一个整数线性规划问题。这在理论上是 NP 困难的（也就是”没有已知的快速通用算法”）。

但现代求解器，比如 Gurobi [8]，对于结构良好的问题可以高效求解。
研究团队用的是 Gurobi 5.5。实际求解时间 [2]：

• 早期迭代（少量比赛已结束）：不到 1 秒
• 中期（30-40 场比赛已结束）：10-30 秒
• 后期（50+ 场比赛已结束）：不到 5 秒

为什么后期反而更快？ 因为随着比赛结果确定，可行解空间在缩小。变量更少，约束更紧，求解更快。

梯度爆炸问题和 Barrier Frank-Wolfe

标准的 Frank-Wolfe 有一个技术问题：当价格接近 0 的时候，LMSR 的梯度会趋向负无穷。这会导致算法不稳定。

解决方案是 Barrier Frank-Wolfe：

不在完整的多面体 M 上优化，而是在一个稍微”收缩”的版本 M’ 上优化。收缩参数 ε 会随着迭代自适应地减小——开始时离边界远一点（稳定），后来逐渐逼近真实边界（精确）。
研究表明，实际操作中 50 到 150 轮迭代就足够收敛 [2]。

真实表现

论文里有一个关键发现 [2]：

在 NCAA 锦标赛的前 16 场比赛中，Frank-Wolfe 做市商（FWMM）和简单的线性约束做市商（LCMM）表现差不多——因为整数规划求解器还太慢。

但在 45 场比赛结束后，第一次成功的 30 分钟投影完成了。

从那以后，FWMM 在盘口定价上比 LCMM 好了 38%。

转折点就是：当结果空间缩小到整数规划能在交易时间窗口内完成求解的时候。

FWMM 就像一个学生，考试前半段还在热身，但一旦进入状态，就开始碾压。

LCMM 是那个一直稳定发挥但天花板有限的学生。

关键区别是：FWMM 有更强的”武器”（Bregman 投影），只是需要时间来”装弹”（等求解器跑完）。

(未完待续, To be contd.)
 

本页Url