A Dynamic Near-Optimal Algorithm for Online Linear Programming

在线优化在计算机科学、运筹学和管理科学领域引起了越来越多的关注。 在许多实际问题中，数据不是从一开始就暴露出来的，而是以在线的方式出现的。 例如，在在在线收入管理中，消费者按顺序到达，每个人都需要一个商品子集（例如，多航班或在酒店停留一段时间），并提供投标价格。 根据要求，卖方需要决定是接受还是拒绝投标，总体目标是在满足资源限制的同时最大化收入。 类似地，在线路由问题中，网络容量管理器从用户那里接收了一系列具有网络预期用途的请求，每个请求都有特定的用途。 他的目标是分配网络容量，最大化社会福利。 网上拍卖、网上关键词匹配、网上线关键词匹配、在线包装等在线收入管理和资源分配中。 请参考在线优化文献及其近期发展概述 Borodin 和 El-Yaniv (1998)、Buchbinder 和 Naor (2009a) 以及 Devanur (2011)。 在上述示例中，这个问题可以表示为在线规划 (LP) 问题。 (有时，人们会考虑相应的整数计划。虽然我们的讨论集中在这些问题上 LP 放松，但我们的结果自然会扩展到整数规划。请参见本方面的讨论 5.2 节。）在线 LP 以线性规划为问题 约束矩阵和目标函数中的相应系数逐列显示基本形式。 在需观察未来数据，观察输入后必须立即做出决定。 准确地说，我们考虑以下(离线)线性程序: (1) 在线 LP 问题的目标是选择 xt 使目标函数 Pn t=1 txt 最大化。 本文提出了解决方案 LP 性能好的算法。 为了定义算法的性能，我们首先需要假设输入参数。 我们在本文中采用以下随机置换模型： 假设 1. 列 aj(有目标系数 j）随机到达。 列组 4a1 1 a2 10 0 01 和 5 一开始可以被不利选择。 但是，4a1 1 a2 10 0 01 和 5 到达顺序均匀分布在所有排列上。 假设 2. 我们先验地知道列的总数 n。 许多现有的在线文献都采用了随机排列模型(对相关文献的综合回顾，请参见第一次 1.3 节）。 采用最坏情况分析和假设输入分布已知之间的中间路径。 对输入不确定性完全稳定的最坏情况进行分析，评估算法是基于算法在最坏情况下输入的性能(例如，见 Mehta 等人 2005，Buchbinder 和 Naor 2009b）。 然而，这使得这个问题的性能界限非常悲观：没有比最佳离线解决方案更好的在线算法 O41/n5 近似更好（Babaioff et al. 2008）。 相比之下，虽然先验输入分布可以在很大程度上简化问题，但分布的选择非常关键。如果实际输入分布与假设不一致，性能将受到影响。 具体来说，假设 1 比假设列是独立于某些（可能未知的）分布绘制的要弱。 事实上，人们可以看到它 n.i.d. 首先，从基本分布中提取列作为 n 样本，然后随机排列。 因此，如果输入数据是 i.i.d 我们提出的算法及其性能也将适用于绘制。 从某些分布。 假设 2 这是必要的，因为我们需要使用数量 n 在我们的算法中学习阈值价格的历史长度。 事实上，如 Devanur 和 Hayes (2009) 所示，任何算法都必须接近最佳性能。 然而，这个假设可以放宽到 n 最多的近似知识 1 ± … 乘法误差） ，不影响我们的结果。 在线算法的竞争力定义如下： 定义 1. 令 OPT 表示离线问题 (1) 最优目标值。 如果使用A获得的在线解的期望值至少是最佳离线解的c因子，那么在线算法a在随机替换模型中具有竞争力。 那是， () 期望取自 110 0 01 n 均匀随机排列，xt 是算法 A 当输入按顺序到达时，制作第一个 t 个决策。 在本文中，我们在上述两个假设和 b 在下界条件下，提出了在线线线性规划 (2) 近似最优算法。 我们还将我们的结果扩展到以下更一般的在线线优化问题，每次都有多维决策： ? 考虑一系列 n 个非负向量 f1 1f2 1 0 0 0 1fn ∈ k ，mn 个非负向量 gi1 1 gi2 1 0 0 0 1 gin ∈ 601 17 k 1 i = 11 0 0 0 1 m 和 K = 8x ∈ k 2 x T e ? 11 x ? 09（我们使用 e 表示所有 1 个向量）。 线性规划是选择x1 10 0 01 xn来求解 () 在相应的在线问题中，给出以前的问题 t ?1 个决策 x1 10 0 01 xt?1 ，每次我们选一个 k 维决策 xt ∈ k ，满足 (3) 使用到时间 t 的知识。 目标是在整个时间范围内最大化 Pn j=1 f T j xj。 请注意，问题 (2) 是问题 (3) 特例，其中 k = 1。 1.1. 具体应用 下面，我们将在线展示 LP 模型的一些具体应用。 这些例子只是该模型广泛应用的一小部分。 1.1.1 网上背包/秘书问题。 在线研究本文 LP 一维版的问题通常被称为在线背包或秘书问题。 在这些问题上，决策者面临着一系列的选项，每个选项都有一定的成本和价值。他必须在线选择子集，以最大化总价值，而不违反成本约束。 这个问题的应用出现在很多情况下，比如雇佣工人，安排工作，在赞助搜索拍卖中出价。 随机排列模型已广泛应用于该问题的研究(见 Kleinberg 2005、Babaioff 等人 2007 以及后续的参考资料)。 在这些论文中，要么为有限大小的问题获得恒定的竞争比，要么为大问题提出接近最佳算法。 在本文中，我们研究了将这个问题扩展到更高的维度，并提出了一种接近最佳算法。 1.1.2 线路由问题。 考虑一个由 m 连接条边的计算机网络； 每条边 i 有界容量(带宽) bi 。 网上到达的请求很多，每个请求都需要网络 ∈ m 部分容量，以及请求的效用或价格。 决策者的离线问题由以下整数程序提出： () 可以在 Buchbinder 和 Naor (2009b)、Awerbuch 在其他人中找到讨论这个问题。 (1993)，以及参考资料。 请注意，这个问题也是以网上包装的名义研究的。 1.1.3 在线 Adwords 问题。 销售在线广告一直是谷歌、雅虎等许多互联网公司的主要收入来源。因此，提高广告分配系统的性能对这些公司来说变得极为重要，因此过去一直受到研究界的极大关注 十年。 在文献中，大多数研究使用在线匹配模型，如参考 Mehta 等人。 (2005)、Goel 和 Mehta (2008)、Devanur 和 Hayes (2009)、Karande 等人。 (2011)、Bahmani 和 Kapralov (2010)、Mahdian 和 Yan (2011)、Feldman 等人。 (2010, 2009b) 和 Feldman 等人。 （2009a）。 在这 n 在线搜索查询和 m 每个投标人(广告商)都有每日预算 bi。 第一，根据每个搜索关键字的相关性 i 投标人将查询 j 出价一定的 ij，展示其广告和搜索结果。3 对于第 j 一个查询，决策者(即搜索引擎)必须 选择一个 m 维向量 xj = 8xij9 m i=1 ，其中 xij ∈ 801 19 表示第 j 查询是否分配给第 i 个投标人。 相应的离线问题可以表达为： (4) (4) 的 LP 放松是一般在线 LP 问题 (3) 其中一个特例 fj = ?j , gij = ijei 其中 ei 是除第 i 个条目的 1 所有零的第 i 单位向量。 在文献中，随机安排假设最近因其易处理性和通用性而引起了极大的兴趣。 恒定竞争算法和接近最优算法已经提出。 我们将在 §1.3 进行更全面的回顾。 1.2 关键思想和主要结果 本文的主要贡献是在随机排列模型下以接近最佳竞争比解决在线问题 LP 问题算法。 基于以下观察：离线线性程序的最优解 x ? 最优对偶可以在很大程度上解决 p ? ∈ m 确定，对应 m 不等式约束。 作为阈值价格，最优对偶解使 x ? j > 0 仅当 j ? p ?T aj 时。 我们的在线算法从一些初始输入中学习阈值价格向量。 然后利用价格向量来确定后期决策。 然而，我们的算法不是只计算一次价格向量，而是等到最初…n 步骤或到达，然后计算每次历史翻倍时的新价格向量，即时间…n1 2…n1 4…n10 0 0 等等。 我们表明，在右输入的大小下，我们的算法具有随机排列模型 1 - O4…5 的竞争力。 我们的主要结果精确地表述如下： 定理 1. 对于任何 … > 我们的在线算法和随机替换模型中的在线线线性规划 (2) 相比具有 1?O4…5 对于所有输入，竞争力使 (5) 陈述定理 1 另一种方法是我们的算法 1 ? O4√ mlog n/B5 的竞争比。 我们在§3 它证明了定理 1。 注意定理1的条件取决于logn，当n很大的时候，远远不能满足每个人的需求。 Kleinberg (2005) 证明了 B ? 1/…2 是在 B 获得秘书问题 1 ? O4…5 竞争比必要，这是在线的 LP 问题的一维对应物，所有 t 的 at = 1。 因此，定理 1 中对……依赖性接近最佳。 在下一个定理中，我们证明任何在线算法都需要依赖 m 接近最佳解决方案。 它的证明将现在§4。 定理 2. 对于随机置换模型中的在线 LP 问题 (2) 的任何算法，存在一个实例使得其竞争比小于 1 − ì4…5 当 () 或者等价地，没有算法可以实现比 1 − ì4√ logm/B5 更好的竞争比。 我们还将我们的结果扩展到 (3) 中介绍的更一般的模型：定理 3。对于任何 … > 0，我们的算法对于随机排列模型中的一般在线 LP 问题 (3) 具有 1 - O4…5 的竞争力，对于所有 输入，例如： (6) 现在我们对定理 1 和定理 3 中的条件进行一些说明。首先，条件仅取决于右侧输入 bi 并且与 OPT 的大小或目标系数无关。 并且通过随机排列模型，它们也独立于输入数据的分布。 从这个意义上说，我们的结果在输入数据的不确定性方面非常稳健。 特别是，我们的结果的一个优点是在算法实施之前条件是可检查的，这与 OPT 或目标系数方面的条件不同。 即使仅就 bi 而言，如定理 2 所示，对 … 的依赖已经是最优的，并且对 m 的依赖是必要的。 关于对 n 的依赖，我们只需要 B 的阶数为 log n，远小于投标总数 n。 实际上，对于一些小问题，条件可能很严格。 但是，如果预算太小，不难想象没有任何在线算法可以做得很好。 相反，在输入量很大的应用中（例如在线广告词问题中，估计一个大型搜索引擎每天可以接收数十亿次搜索，即使我们专注于特定类别，这个数字也可以 仍然是数百万）和相当大的右侧输入（例如，广告商的预算），条件不难满足。 此外，定理1和定理3中的条件只是理论结果； 即使条件不满足，我们的算法的性能可能仍然非常好（如 Wang 2012 中的一些数值测试所示）。 因此，我们的结果具有理论和实践意义。 最后，我们用以下推论结束本节： 推论 1. 在在线 LP 问题 (2) 和 (3) 中，如果约束系数的最大入口不等于 1，那么我们的定理 1 和 3 仍然成立，有 条件 (5) 和 (6) 替换为 () 其中，对于每一行 i，a¯i = maxj 8aij9 in (2)，或 a¯i = maxj 8gij^9 in (3)。

1.3 相关工作 在线算法的设计和分析一直是计算机科学、运筹学和管理科学界广泛关注的话题。 最近，随机排列模型越来越受欢迎，因为它避免了对抗性输入模型的悲观下界，同时仍然捕获了输入的不确定性。 在该模型下研究了各种在线算法，包括秘书问题 (Kleinberg 2005, Babaioff et al. 2008)、在线匹配和 adwords 问题 (Devanur and Hayes 2009, Feldman et al. 2009a, Goel and Mehta 2008, Mahdian and 严 2011，Karande 等人。 2011, Bahmani and Kapralov 2010) 和在线打包问题 (Feldman et al. 2010, Molinaro and Ravi 2014)。 在这项工作中，获得了两种类型的结果：一种实现了独立于输入参数的恒定竞争比； 另一个侧重于输入较大时算法的性能。 我们的论文属于第二类。 在下面的文献综述中，我们将重点放在这类工作上。 在随机置换模型中实现接近最优性能的第一个结果是由 Kleinberg (2005) 提出的，其中针对一维多选秘书问题提出了 1 − O41/ √ B5 竞争算法。 作者还证明了他的算法达到的 1 − O41/ √ B5 的竞争比对于这个问题是最好的。 我们的结果将他的工作扩展到具有竞争力 1−O4√ mlog n/B5 的多维案例。 虽然问题看起来很相似，但由于是多维结构，我们的分析需要不同的算法和不同的技术。 具体来说，Kleinberg (2005) 递归地应用了经典秘书算法的随机版本，同时我们根据 LP 对偶理论维持价格，并具有固定的价格更新时间表。 我们还证明，对于多维问题，没有任何在线算法可以实现比 1 − ì4√ logm/B5 更好的竞争比。 据我们所知，这是第一个表明依赖维度 m 的必要性的结果，以实现该问题的最佳竞争率。 它清楚地指出，高维确实增加了这个问题的难度。 Devanur 和 Hayes (2009) 研究了一种基于 LP 的方法来解决在线广告词问题。 在他们的方法中，他们解决了一个线性程序一次，并利用它的双重解决方案作为阈值价格来做出未来的决策。 作者证明了他们算法的竞争比为 1 - O4 3 p maxm2 log n/OPT5。 在我们的工作中，我们考虑了一个更通用的模型，并开发了一种算法，以精心选择的速度更新对偶价格。 通过使用动态更新，我们实现了仅取决于 B: 1 − O4√ mlog n/B5 的竞争比率。 这在实践中很有吸引力，因为可以在问题解决之前检查 B，而 OPT 不能。 此外，我们表明我们的结果对 B 的依赖性是最佳的。 尽管我们的算法与他们的想法相似，但我们算法的动态特性需要更精细的设计和分析。 我们还回答了我们应该多久更新一次双重价格的重要问题，并表明可以使用动态学习算法进行重大改进。 最近，费尔德曼等人。 (2010) 研究了一个更一般的在线打包问题，该问题允许选择集的维度在每个时间段内变化（对 (3) 的进一步扩展）。 他们提出了一种一次性学习算法，该算法实现了取决于右侧 B 和 OPT 的竞争比率。 并且对 B 的依赖性为 1 - O4√3 mlog n/B5。 因此，与他们的竞争比率相比，我们的结果不仅消除了对 OPT 的依赖，而且提高了对 B 的依赖。 table 1 我们表明，这种改进是使用动态学习的结果。 最近，Molinaro 和 Ravi (2014) 研究了同样的问题并获得了 1 − O4p m2 logm/B5 的竞争比。 他们算法的主要结构（特别是他们获得平方根而不是三次根的方式）是从本文中修改的。 他们进一步使用一种新颖的覆盖技术来消除竞争比率中对 n 的依赖，代价是增加 m 的数量级。 相比之下，我们提出了从立方根到平方根的改进以及如何消除对 OPT 的依赖。 Kleinberg (2005)、Devanur 和 Hayes (2009)、Feldman 等人的结果比较。 (2010)、Molinaro 和 Ravi (2014)，这项工作如表 1 所示。 除了随机排列模型，Devanur 等人。 （2011）研究了他们所谓的对抗性随机输入模型下的在线资源分配问题。 该模型概括了从 i.i.d 绘制列的情况。 分配; 但是，它比随机排列模型更严格。 特别是，他们的模型不允许输入序列中可能存在许多“冲击”的情况。 对于这个输入模型，他们开发了一种算法，可以实现 1 − O4max8 √ logm/B1 p max logm/OPT95 的竞争比率。 他们的结果很重要，因为它实现了对 m 的近乎最优的依赖。 然而，对 OPT 的依赖和更强的假设使其无法直接与我们的结果进行比较，并且他们的算法使用的技术与我们的完全不同。 在运筹学和管理科学界，针对各种在线收益管理和资源分配问题的动态最优定价策略一直是一个重要的研究课题； 研究包括 Elmaghraby 和 Keskinocak (2003)、Gallego 和 van Ryzin (1997, 1994)、Talluri 和 van Ryzin (1998)、Cooper (2002) 以及 Bitran 和 Caldentey (2003)。 在 Gallego 和 van Ryzin (1997, 1994) 以及 Bitran 和 Caldentey (2003) 中，到达过程被认为是价格敏感的。 然而，正如 Cooper (2002) 所评论的，这个模型可以简化为一个价格独立的到达过程，在泊松到达下具有可用性控制。 我们的模型可以进一步被视为可用性控制模型的离散版本，该模型也被用作 Talluri 和 van Ryzin (1998) 的基础模型，并在 Cooper (2002) 中进行了讨论。 使用的想法门槛或“出价”价格并不新鲜。 它由 Williamson (1992) 和 Simpson (1989) 提出，并在 Talluri 和 van Ryzin (1998) 中进一步研究。 在 Talluri 和 van Ryzin (1998) 中，作者表明投标价格控制政策是渐近最优的。 然而，他们假设了到达过程的知识，因此价格是通过使用分布信息“预测”未来而不是像我们在论文中所做的那样从过去的观察中“学习”来获得的。 Cooper (2002) 讨论了使用 LP 找到双重最优投标价格的想法，其中也实现了渐近最优。 但是同样，假设到达过程是已知的，这使得分析完全不同。 本文在几个方面做出了贡献。 首先，我们研究了一个通用的在线 LP 框架，扩展了许多先前工作的范围。 并且由于其动态学习能力，我们的算法是无分布的——除了随机到达顺序和条目总数之外，假设没有关于输入分布的知识。 此外，我们不是只学习一次价格，而是提出了一种动态学习算法，可以随着更多信息的披露而更新价格。 这种算法的设计回答了 Cooper (2002) 提出的问题，即应该多久以及何时更新价格？ 我们通过证明以几何时间间隔（不太频繁也不太频繁）更新价格是最佳的，从而明确回答了这个问题。 因此，我们提出了一种精确量化的动态价格更新策略。 此外，我们为这个问题提供了一个重要的下限，这是同类问题中的第一个，表明问题的维度增加了它的难度 在我们的分析中，我们应用了许多可能近似正确学习的标准技术，特别是集中范围和覆盖论点。 我们的动态学习与学习问题中使用的“加倍技巧”有着相似的想法。 然而，与通常应用于未知时间范围的加倍技巧不同（Cesa-Bianchi 和 Lugosi 2006），我们表明，在经过精心设计的固定时间范围内以几何速度更新价格也可以提高性能 算法。 1.4 论文结构 本文的其余部分安排如下。 在 §§2 和 3 中，我们展示了我们的在线算法，并证明它在温和的输入条件下实现了 1−O4…5 的竞争比。 为了使讨论清晰易懂，我们从第 2 节开始使用更简单的一次性学习算法。 尽管对这个更简单算法的分析将有助于展示我们的证明技术，但在此设置中获得的结果比通过我们的动态学习算法获得的结果要弱，这在第 3 节中进行了讨论。 在第 4 节中，我们给出了定理 2 的详细证明，关于在我们的主要定理中使用下限条件的必要性。 在第 5 节中，我们介绍了我们研究的几个扩展。 我们在第 6 节中得出结论 2 一次性学习算法 在本节中，我们提出了一种用于在线 LP 问题的一次性学习算法 (OLA)。 我们考虑以下偏线性规划，仅在输入上定义直到时间 s = …n（为了便于表示，在不失一般性的情况下，我们假设 …n 在整个分析过程中是一个整数）： (7) (8) 令 4p^1 y^5 为 (8) 的最优解。 请注意，p^ 具有每种资源价格的自然含义。 对于任何给定的价格向量 p，我们定义分配规则 xt 4p5 如下： (9) 我们现在陈述我们的 OLA： 算法 OLA（一次性学习算法） 1 初始化 xt = 0，对于所有 t ¶ s。 p^ 定义如上。 2 对于 t = s +11 s +210 0 01 n，如果 aitxt 4p^5 ¶ bi − Pt−1 j=1 aijxj 对于所有 i，设 xt = xt 4p^5； 否则，设置 xt = 0。输出 xt 。 在 OLA 中，我们使用前…n 个到达来学习对偶价格向量。 然后，在每次 t > …n 时，只要不违反任何约束，我们就使用这个双重价格来决定当前的分配并执行这个决定。 该算法的一个吸引人的特点是它要求我们只求解一个定义在…n 个变量上的小型线性程序。 请注意，(7) 的右侧被因子 1 - … 修改。 这种修改保证了分配 xt 4p5 很可能不会违反约束。 这个技巧也用在第 3 节中，我们在其中研究动态学习算法。 在下一小节中，我们证明以下关于 OLA 的竞争比的命题，它依赖于比定理 1 更强的条件：命题 1。对于任何 … > 0，OLA 是 1−6… 对在线线性规划 (2 ) 在随机置换模型中，对于所有输入，使得 () 2.1 竞争比率分析 观察 OLA 一直等到时间 s = …n，然后将时间 t 的解设置为 xt 4p^5，除非它违反约束。 为了证明其竞争力，我们遵循以下步骤。 首先，我们证明如果 p ∗ 是 (1) 的最优对偶解，则 8xt 4p ∗ 59 接近原始最优解 x ∗ ； 即，学习对偶价格足以确定一个接近的原始解决方案。 然而，由于这些列是以在线方式显示的，我们无法在决策期间获得 p*。 相反，在我们的算法中，我们使用 p^ 作为替代。 然后我们证明 p^ 是 p ∗ 的一个很好的替代品： (1) 很有可能，xt 4p^5 满足线性规划的所有约束； (2) P t txt 4p^5 的期望值接近最优离线值。 在开始分析之前，我们在讨论中做出以下简化的技术假设： 假设 3. 问题输入处于一般位置——即，对于任何价格向量 p——最多可以有 m 列使得 p T at = 吨。 假设 3 不一定适用于所有输入。 然而，正如 Devanur 和 Hayes (2009) 所指出的，人们总是可以通过添加一个随机变量 Žt 在区间 601 ‡7 上均匀分布来随机扰动 t 任意少量‡。 这样，在概率为 1 的情况下，在 p T at = t 中，没有 p 可以同时满足 m + 1 个方程，并且可以使这种扰动对目标的影响任意小。 在这个假设下，我们可以利用线性规划（1）的互补条件来获得以下引理。 引理 1. xt 4p * 5 ¶ x * t 对于所有 t，并且在假设 3 下，x * t 和 xt 4p * 5 的差异不超过 m 个 t 值。 证明。 考虑离线线性规划 (1) 及其对偶（令 p 表示与第一组约束相关的对偶变量，yt 表示与约束 xt ¶ 1 相关的对偶变量）： (10) 根据互补松弛条件，对于原始问题 (1) 的任何最优解 x ∗ 和对偶的最优解 4p ∗ 1 y ∗ 5，我们必须有： () 如果 xt 4p * 5 = 1，通过 (9)，t > 4p * 5 T at 。 因此，通过 (10) 中的约束，y * t > 0，最后，通过最后的互补性条件，x * t = 1。因此，对于所有 t，我们有 xt 4p * 5 ¶ x * t。 但是，如果 t < 4p ∗ 5 T at ，那么我们必须同时具有 xt 4p ∗ 5 和 x ∗ t = 0。因此，如果 4p ∗ 5 T at 6= t ，则 xt 4p ∗ 5 = x ∗ t 。 在假设 3 下，最多有 m 个 t 值，使得 4p ∗ 5 T at = t 。 因此，x * t 和 xt 4p * 5 的差异不超过 m 个 t 值。 ƒ 引理 1 表明，如果已知最优对偶解 p * 到 (1)，则通过我们的决策策略获得的 xt 4p * 5 接近最优离线解。 然而，在我们的在线算法中，我们使用从前几个输入中学习到的样本对偶价格 p^，这可能与最优对偶价格 p∗ 不同。 剩下的讨论试图表明样本对偶价格 p 对我们的目的来说是足够准确的。 在下文中，我们经常使用这样一个事实，即随机顺序假设可以解释为前 s 个输入是均匀随机样本，而无需从 n 个输入中替换大小 s。 我们用 S 表示大小为 s 的样本集，用 N 表示大小为 n 的完整输入集。 我们从引理 2 开始，这表明使用样本对偶价格构造的原解 xt 4p^5 很有可能是可行的： 引理 2. 使用样本对偶价格构造的原解是线性规划 (1) 的可行解 概率很高。 更准确地说，概率为 1 - …， () 给定 B ¾ 6mlog4n/…5/…3。 证明。 考虑任何固定价格 p 和 i。 当且仅当 p 是样本集 S 的 (8) 的最优对偶价格，但 Pn t=1 aitxt 4p5 > bi 时，我们说样本 S 对 p 和 i 是“坏的”。 首先，我们表明对于每个固定的 p 和 i，坏样本的概率很小。 然后我们对所有不同的价格进行联合约束，以证明学习到的价格 p^ 很有可能使得 Pn t=1 aitxt 4p^5 ¶ bi 对于所有 i。 首先，我们固定 p 和 i。 定义 Yt = aitxt 4p5。 如果 p 是 S 上样本线性程序的最优对偶解，将引理 1 应用于样本问题，我们有 () 其中 x 是 S 上的样本线性程序的原始最优解。现在我们考虑这个 p 和 i 的坏样本的概率： () 此外，我们有 () 其中 „ = …/4m · n m5。 倒数第二步遵循 Hoeffding-Bernstein 的无放回抽样不等式（附录 A 中的引理 10），将 Zt , t ∈ S 视为来自 Zt , t ∈ N 的无放回样本。 我们还使用了 0 ¶ Zt ¶ 1 对于所有 t 的事实； 因此，P t∈N 4Zt − Z¯5 2 ¶ P t∈N Z 2 t ¶ bi （因此引理 10 中的‘ 2 R 可以由 bi 界定）。 最后，最后一个不等式是由于对 B 所做的假设。 接下来，我们对所有不同的 p 进行联合约束。 我们称两个价格向量 p 和 q 不同当且仅当它们产生不同的解； 即，8xt 4p59 6= 8xt 4q59。 请注意，我们只需要考虑不同的价格，否则所有 Yt 都是完全相同的。 请注意，每个不同的 p 的特征在于通过超平面在 m+1 维空间中将 n 个点（在 9 n t=1 处为 8 t 1 ）唯一分离。 根据计算几何的结果，此类不同价格的总数最多为 n m（Orlik 和 Terao 1992）。 对 n m 个不同的价格进行联合约束，并且 i = 110 0 01 m，我们得到了想要的结果。 ƒ 我们表明，xt 4p^5 很有可能是一个可行的解决方案。 在下文中，我们将证明它也是一个近乎最优的解决方案。 引理 3. 使用样本对偶价格构造的原始解是线性规划 (1) 的高概率近似最优解。 更准确地说，概率为 1 - …， () 给定 B ¾ 6mlog4n/…5/…3。 证明。 证明基于两个观察。 首先，8xt 4p^59n t=1 和 p^ 满足所有互补条件，因此是以下线性规划的最优原始和对偶解： (11) 其中 b^ i = P t∈N aitxt 4p^5 在 p^i > 0 的情况下，b^ i = max8 P t∈N aitxt 4p^51 bi 9，如果 p^i = 0。 其次，我们证明如果 p^i > 0，则概率为 1−…, b^ i ¾ 41−3…5bi 。 为了证明这一点，设 p^ 是集合 S 上的样本线性程序的最优对偶解，x^ 是最优原始解。 由线性规划的互补条件，如果 p^i > 0，则第 i 个约束必须满足相等。 也就是说，P t∈S aitx^t = 41−…5…bi 。 然后，通过引理 1 和 B = mini bi ¾ m/… 2 的条件，我们有 () 然后，使用 Hoeffding-Bernstein 不等式进行无放回抽样，以类似于引理 2 的证明的方式，我们可以证明（详细证明在附录 A.2 中给出），给定 B 的下界，有概率 至少 1 - …，对于所有 i 使得 p^i > 0： (12) 结合 p^i = 0 的情况，我们知道所有 i 的概率为 1−…, b^ i ¾ 41−3…5bi。 最后，观察到只要 (12) 成立，给定 (1) 的最优解 x ∗，41 - 3…5x ∗ 将是 (11) 的可行解。 因此，(11) 的最优值至少为 41 − 3…5OPT，相当于说 () 因此，在整个周期内采用的在线解决方案的目标值接近最优。 然而，在 OLA 中，在学习周期 S 期间没有做出任何决策，只有来自周期 8s + 110 0 01 n9 的决策对目标值有贡献。 以下引理将样本线性程序 (7) 的最优值与离线线性程序 (1) 的最优值联系起来，将限制学习期的贡献： 引理 4. 令 OPT4S5 表示 样本 S 上的线性程序 (7) 和 OPT4N 5 表示 N 上的离线线性程序 (1) 的最优值。 然后， () 证明。 令 4x ∗ 1p ∗ 1 y ∗ 5 和 4x^1p1 y^5 分别表示 N 上的线性程序 (1) 和 S 上的样本线性程序 (7) 的最优原始解和对偶解。 () 注意 S ⊆ N，因此 4p ∗ 1 y ∗ 5 是 S 上线性规划的对偶的可行解。因此，由弱对偶定理： () 现在，我们准备证明命题 1：命题 1 的证明。使用引理 2 和 3，概率至少为 1 − 2…，以下事件发生： () 也就是说，决策 xt 4p^5 是可行的，并且在整个周期 8110 0 01 n9 上采用的目标值接近最优。 用 E 表示这个事件，其中 P 4E5 ¾ 1 − 2…。 我们有引理 2-4： () 其中 I4·5 是指示函数，第一个不等式是因为在 E 下，xt = xt 4p^5，倒数第二个不等式使用 xt 4p^5 ¶ x^t 的事实，这是引理 1 的结果

§2 中讨论的算法使用前…n 个输入来学习阈值价格，然后将其应用于剩余时间范围。 尽管该算法有其自身的优点——特别是，它只需要求解一个定义在…n 个变量上的小型线性程序——B 所需的下限比定理 1 中声明的下限强…因子。 在本节中，我们提出了一种改进的动态学习算法（DLA），它将实现定理 1 中的结果。 DLA 不会只计算一次价格，而是在每次历史翻倍时更新价格，也就是说，它会在时间 t = …n1 2…n1 4…n10 0 0 学习一个新价格。 准确地说，让 p^表示在输入上定义的以下部分线性程序的最优对偶解，直到时间 () 其中数字集 h定义如下： () 此外，对于任何给定的对偶价格向量 p，我们定义与 (9) 中相同的分配规则 xt 4p5。 我们的动态学习算法如下： 算法 DLA（动态学习算法） 1 初始化 t0 = …n。 为所有 t ¶ t0 设置 xt = 0。 2 重复 t = t0 + 11 t0 + 21 0 0 0 (a) 设置 x^t = xt 4p^ 5. 这里 = 2 r …n 其中 r 是最大整数使得 < t 3 (b) 如果 aitx^t ¶ bi − Pt−1 j=1 aijxj 对于所有 i，则设 xt = x^t ； 否则，设置 xt = 0。输出 xt 。 请注意，我们在整个时间范围内更新了双重价格向量“log2 41/…5”次。 因此，DLA 需要更多的计算。 然而，正如我们接下来展示的那样，它需要 B 的较弱下限来证明相同的竞争比率。 这种改进背后的直觉如下。 最初，在 = …n，h = √ … > …。 因此，我们在开始时有较大的松弛，并且约束满足的大偏差参数（如引理 2）需要 B 上的较弱条件。随着 t 增加，增加并且 h减少。 但是，对于较大的 值，样本量较大，使得 B 上的较弱条件足以证明相同的误差界限。 此外，h下降得足够快，因此目标值的整体损失并不显着。 正如人们将看到的，仔细选择数字 h在证明我们的结果中起着重要作用。 3.1 竞争比率分析 DLA 的分析以与 OLA 类似的方式进行。 然而，这里需要证明每个时期所学价格的更强结果。 在下文中，我们假设 … = 2 -E 并让 L = 8…n1 2…n1 0 0 0 1 2 E-1 …n9。 引理 5 和 6 与 §2 中的引理 2 和 3 平行，但需要 B 上的较弱条件：引理 5。对于任何 … > 0，概率为 1 - …： () 给定 B = mini bi ¾ 410mlog 4n/…55/…2。 证明。 证明类似于引理 2 的证明，但需要更仔细的分析。 我们在此提供一个简短的大纲，并在附录 B.1 中提供详细的证明。 首先，我们固定 p、i 和 。 这一次，当且仅当 p = p^ （即 p 是当前到达订单下的学习价格）但 P2 t=+1 aitxt 4p^ 5 > 4/n5bi . 通过使用 Hoeffding-Bernstein 不等式进行无放回抽样，我们证明在 B 上的条件下，对于任何固定的 p、i 和 ，“坏”排列的概率小于 „ = …/4m·n·m·E5。然后通过取 工会约束所有不同的价格，所有项目 i 和时期 ，引理被证明。 ƒ 在下文中，我们使用 LPs 4d5 表示在不等式约束中设置为 d 的直到时间 s 的变量上定义的偏线性规划。 那是， () 并让 OPTs 4d5 表示 LPs 4d5 的最佳目标值。 引理 6. 对于所有 ∈ L，概率至少为 1 - …： () 给定 B = mini bi ¾ 410mlog 4n/…55/…2。 证明。 令 b^ i = P2j=1 aijxj 4p^ 5 对于 i 使得 p^ i > 0，并且 b^ i = max8 P2 j=1 aijxj 4p^ 51 4425/n5bi 9，否则。 那么解对 48xt 4p^ 592 t=1 1 p^ 5 满足所有互补条件； 因此，它们是线性规划 LP2 4b^5 的最优解（分别是原始解和对偶解）： () 这表示 () 现在我们分析比值b^i/42bi/n5。根据 b^ i 的定义，对于 i 使得 p^ i = 0，b^ i ¾ 2bi/n。 否则，使用类似于引理 5 证明的技术，我们可以以概率 1 - … 证明，对于所有 i， (14) (14) 的详细证明见附录 B.2。 引理来自 (14)。 ƒ 接下来，与引理 4 类似，我们证明以下引理将样本线性程序的最优值与离线线性程序的最优值联系起来：引理 7. 对于任何 () 引理 7 的证明与引理 4 的证明完全相同； 因此，我们省略了它的证明。 现在我们准备证明定理 1。 定理证明 1. 观察在线解在时间 t ∈ 8 + 110 0 01 29 的输出是 xt 4p^ ` 5，只要不违反约束条件。 根据引理 5 和 6，概率至少为 1 − 2…： () 用 E 表示这个事件，其中 P 4E5 ¾ 1 − 2…。 在线算法实现的预期目标值可以如下限定： () 第三个不等式来自引理 6； 倒数第二个不等式来自引理 7； 最后一个不等式源于以下事实： ()

在本节中，我们证明定理 2； 即，条件 B ¾ ì4logm/…2 5 是任何在线算法实现 1 − O4…5 的竞争比率所必需的。我们通过构造 (1) 的实例来证明这一点，其中包含 m 个项目和每个项目的 B 个单元，使得没有 在线算法可以实现 1 − O4…5 的竞争比，除非 B ¾ ì4logm/…2 5。 在此构造中，我们将 0-1 向量 at 称为需求向量，将 t 称为利润系数。 假设某个整数 z 的 m = 2 z。 我们将构造 z 对需求向量，使得每对中的需求向量相互补充并且不共享任何项目。 然而，每组由每对中的一个向量组成的 z 向量将共享至少一个公共项。 为此，请考虑 2z 个可能的长度为 z 的布尔字符串。 第 j 个布尔字符串表示 j = 110 0 01 m = 2 z 的第 j 个项目（为了说明目的，我们在后面的讨论中从 0 开始索引项目）。 让 sij 表示第 j 个字符串的第 i 位的值。 然后我们构造一对需求向量 vi 1wi ∈ 801 19 m，通过设置 vij = sij, wij = 1 - sij。 表 2 说明了 m = 8 (z = 3) 的这种结构： 注意向量 vi 1wi 1 i = 110 0 01 z 是相互补充的。 考虑通过为每个 i = 110 0 01 z 选择两个向量 vi 和 wi 中的一个而形成的任何 z 需求向量集合。 然后通过设置 sij = 1 如果这个集合有向量 vi 和 0 如果它有向量 wi 来形成一个位串。 然后这个集合中的所有向量共享对应于布尔字符串的项。 例如，在表2中，需求向量v3、w2和w1共享项目44＝“100”5，需求向量w3、v2和v1共享项目34＝“011”5，以此类推。 现在，我们构建了一个实例，该实例由利润系数为 4 的 B/z 输入和需求向量 vi 组成，每个 i = 11 0 0 0 1 z。 • qi 输入，利润为 3 和需求向量 wi ，对于每个 i，其中 qi 是二项式 (2B/z1 1/2) 之后的随机变量。 • √ B/4z 输入，利润为 2，需求向量为 wi，对于每个 i。 • 2B/z - qi 输入，利润为 1，需求向量为 wi，对于每个 i。 使用构造中确保的需求向量的属性，我们证明了以下主张： table 2 权利要求 1. 令 ri 表示构造示例的任何 1-… 竞争解决方案接受的类型为 wi 的向量的数量。 那么，它必须持有 () 证明。 令 OPT 表示离线问题的最优值。 并让 OPTi 表示从第 i 类接受的需求中获得的利润。 令 topwi 4k5 表示前 k 个输入与需求向量 wi 的利润之和。 然后 () 令 OPT d 为接受类型为 wi 的 ri 向量的解决方案的目标值。 首先，请注意 P i ri ¶ B。这是因为所有 wi 共享一个公共项目，并且该项目最多有 B 个单元可用。 令 Y 为 8i2 ri > B/z9 的集合， X 为剩余的 i； 即，X = 8i 2 ri ¶ B/z9。 然后，我们证明接受的 vi s 总数不能超过 B - P i∈Y ri + Y B/z。 显然，集合 Y 的贡献不能超过 Y B/z vi s。 让 S ⊆ X 贡献剩余的 vi。 现在考虑集合 Y 中的所有 wi 和集合 S 中的所有 wi 共有的项目（通过构造至少存在一个这样的项目）。 由于该项目只有 B 个单位可用，因此 S 贡献的 vi 总数不能超过 B − P i∈Y ri 。 因此，接受的 vi s 的数量小于或等于 B - P i∈Y ri + Y B/z。 表示 P = P i∈Y ri -Y B/z，M = XB/z− P i∈X ri 。 然后 P 1M ¾ 0 和目标值 () 由于 OPT ¶ 7B，这意味着 P +M 必须小于 7…B 才能获得 1 - … 或更好的近似比。 ƒ 这里是剩余证明的简要描述。 通过构造，对于每个 i，恰好有 2B/z 个需求向量 wi，其利润系数为 1 和 3； 其中，每个取值 1 或 3 的概率相等。从前面的主张来看，要获得接近最优的解决方案，必须选择 wi 类型的接近 B/z 需求向量。 因此，如果 431wi 5 输入的总数大于 B/z，那么选择任何 421wi 5 将导致与最优利润相比利润损失 1； 如果 431wi 5 输入的总数小于 B/z - √ B/4z，则拒绝任何 421wi 5 将导致利润损失 1。 使用中心极限定理，在任何一步，这两个事件都可能发生以恒定的概率。 因此，对于 421wi 5 的每个决定都可能导致具有恒定概率的损失，这导致每个 i 的总预期损失为ì4√ B/z5，即总损失为ì4√ zB5。 如果要接受的 wi 的数量不完全是 B/z，则这些 √ B/z 决策中的一些可能不是错误的，但如上面的主张，这种情况不能超过 7…B。 因此，在线解决方案的期望值为 ONLINE ¶ OPT - ì4√ zB - 7…B50 由于 OPT ¶ 7B，要获得 41 - …5 近似因子，我们需要 ì4p z/B - 7…5 ¶ 7… ⇒ B ¾ ì4z/…2 5 = ì4log4m5/…2 50 这样就完成了定理 2 的证明。本证明中使用的步骤的详细说明见附录 C。

5.1 在线多维线性规划 我们考虑以下更一般的在线线性程序，在每个步骤中具有多维决策 xt ∈ k，如 §1 中的 (3) 中所定义： (15) 我们的在线算法基本保持不变（如 §3 中所述），现在定义如下 xt 4p5： () 这里 er 是单位向量，在第 r 个条目处为 1，否则为 0。 我们在算法中任意打破关系。 使用 (15) 的互补性条件和定理 3 中假设的 B 的下界条件，我们可以证明以下引理。 4 证明与一维情况的证明非常相似，并在附录 D 中提供。 引理 8. 令 x ∗ 和 p ∗ 分别是 (15) 的最优原始解和对偶解。 那么 x ∗ t 和 xt 4p ∗ 5 最多有 m 个 t 值不同。 引理 9. 当且仅当 xt 4p5 6= xt 4q5 对于某个 t 时，定义 p 和 q 是不同的。 那么最多有 n mk 2m 个不同的价格向量。 有了上述引理，定理 3 的证明将与定理 1 的证明完全相同。 5.2 在线整数规划 根据 (9) 中 xt 4p5 的定义，我们的算法总是输出整数解。 由于竞争比分析将在线解与相应 LP 松弛的最优解进行比较，因此定理 1 中的竞争比也适用于在线整数规划。 §5.1 中介绍的一般在线线性程序也有同样的观察结果，因为它也输出整数解 5.3 通过列采样快速求解大型线性程序 除了在线问题外，我们的算法还可以应用于解决（离线）线性程序太大而无法明确考虑所有变量的问题。 与一次性在线学习解决方案类似，可以随机抽取…n 个变量，并使用这个较小程序的对偶解决方案 p^ 将变量 xj 的值设置为 xj 4p^5。 这种方法与用于求解大型线性程序的列生成方法非常相似（Dantzig 1963）。 我们的结果首次对通过随机选择列子集来减小线性程序大小的方法所实现的近似进行严格分析。

在本文中，我们在假设随机到达顺序和右侧输入的一些温和条件下，为一般类别的在线 LP 问题提供了一种 1−O4…5 竞争算法。 我们使用的条件与最优目标值、目标系数和输入数据的分布无关。 我们的 DLA 通过以几何时间间隔动态更新阈值价格向量来工作，其中从前一时期显示的列中学习到的双重价格用于确定当前时期的顺序决策。 我们的动态学习方法可能有助于为其他问题设计在线算法。 未来的研究还有很多问题。 一个重要的问题是当前对右手输入 B 大小的限制是否严格。 正如我们所展示的，我们的算法和下限之间存在差距。 通过一些数值实验，我们发现我们算法的实际性能接近下限（见 Wang 2012）。 但是，我们无法证明这一点。 填补这一空白将是未来研究的一个非常有趣的方向。