在线广告的紧凑分配方案（Optimal Online Assignment with Forecasts）

广告分配问题属于运筹中的优化问题。一般情况下，我们期望有个最大化收益，但同时需要保证合约的完成。因此，这是一个带不等式约束的最优化问题。由于广告数量和用户数量很多，因此，求解的难度很高。在这篇文章中，作者推导了原问题的拉格朗日函数的系数之间的关系，大大降低了求解的难度。这里将简要介绍原理和推导过程。

本篇博客内容来自论文：Vee E, Vassilvitskii S, Shanmugasundaram J. Optimal online assignment with forecasts[C]//Proceedings of the 11th ACM conference on Electronic commerce. ACM, 2010: 109-118.

一、背景简介

把展示广告的分配问题看做是一个二部图的问题，可以使得我们在线下求解出一个最优的分配方案。但是这依然有一些问题：

首先，这个二部图$G$很大。当然，目前一般采用抽样的方法从这个图中抽取一个子图来解决问题。但是如果来了一个用户，但是我们没有抽样到，那么我们对这个用户信息毫无所知，这就会对分配造成影响。此外，对于已采样到的用户，我们如何保证它对实际的图来说也是有意义的呢？

第二个问题与服务有关。假设我们使用总体的图$G$求解得到一个完美的解决方案。也没有一个可管理的方案来实施这个最优解。它要求当一个用户到达的时候，我们需要识别出特定的、在预测中的标签，然后调用最优化分配方案。由于$G$有数以百亿的访问和兆亿的边。在实际中，这个最优化方案是无法及时与上百台服务器共同通信的。

最后一个问题是鲁棒性。尽管我们对$G$有比较好的预测，但总不会很完美。实际上我们可能会产生一些不好的甚至是错误的预测。更重要的是，有些用户是我们以前没有遇到过的，对于没见过的用户应该如何优化呢？

本文提出了一种基于$G$的样本来产生紧凑的广告分配方案（a compact allocation plan）来解决上述三个问题。

二、问题描述

假设$G=(I\cup J,E)$，这里的$I$是供应节点，$J$是需求节点。我们的目标是寻找一个分配方案$x \in [0,1]^E$满足需求约束和供应约束。对于每一天边$x\_{ij}$，它的含义是供应节点$i$分配给需求节点$j$的比例。在本问题中，供应节点是用户访问，需求节点是广告。因此，$G$是一个极其不平衡的图，其中$|J|$一般是万级别，而$|I|$则是十亿级别。

2.1、带预测的在线分配问题

在分配问题中，每一个需求节点$j\in J$都需要一定量的供应，因此对于每个需求节点都有一个需求约束。供应的约束则是隐含在图中，主要是供应量需要大于0。特别的，当如下条件被满足的时候，我们称$x$是带预测的在线分配问题（用\mathcal{P}=< G,s,d >表示）的一个可行解：

$$\forall_j \space\space\space \sum_{i\in\Gamma(j)} s_ix_{ij} \geq d_j \space\space\space \text{demand constraints}$$ $$\forall_i \space\space\space \sum_{j\in\Gamma(i)} s_ix_{ij} \leq s_i \space\space\space \text{supply constraints}$$ $$\forall_{(i,j)\in E} \space\space\space x_{ij} \geq 0 \space\space\space \text{non-negativity constraints}$$

这里$\Gamma(i)$表示节点$i$的邻居（即图$G$中$i$节点对应的需求节点集合），$\Gamma(j)$也是类似的。如果$x$是$\mathcal{P}$的一个可行解，那么记作$x\in \mathcal{P}$。

在预处理阶段，需要给定一个问题实例：

$$\mathcal{P'}=< G',s',d >$$

以及一个目标函数：

$$F(s,x)$$

其中，G\`和s\`是$G$和$s$的预测结果。预处理的输出是一个分配方案，用每个需求节点的相关实数来表示。

在在线阶段，我们给定需求节点$J$以及需求量$d$，还需要在预处理阶段产生的分配方案。当$i\in I$到达的时候，我们也会知道$s\_i$以及$\Gamma(i)$。算法必须求出与$j\in \Gamma(i)$相关的分配比例$x\_{ij}$以满足供应约束和需求约束。在线分配方案的目标是产生一个$x\in[0,1]^E$是的$F(s,x)$最小。

2.2、带预测的在线有预算投标（Online Budgeted-Bidders with Forecast）

尽管这篇论文讲的是在线广告分配问题，我们在这也描述一下带预测的在线有预算投标问题。在这里，一个问题实例是指一个二部图$G=(I\cup J,E)$，$I$中包含供应量$s$，对于每个需求节点$j\in J$都有一个预算$B\_j$，对于每一个边$(i,j)\in E$都有一个成本$c\_{ij}$。当满足如下条件的时候，我们说分配方案$x$是可行的：

$$\forall_j \space\space\space \sum_{i\in\Gamma(j)} s_ic_{ij}x_{ij} \leq B_j \space\space\space \text{demand constraints}$$ $$\forall_i \space\space\space \sum_{j\in\Gamma(i)} s_ix_{ij} \leq s_i \space\space\space \text{supply constraints}$$ $$\forall_{(i,j)\in E} \space\space\space x_{ij} \geq 0 \space\space\space \text{non-negativity constraints}$$

注意，在这个问题中，需求约束的数量非常小，而供应约束的数量却很大，每一个供应都对应一个互联网用户的访问。

在数据预处理阶段，我们给出预测的二部图G\`、预测的供应情况s\`以及目标函数$F(s,x)$，预算$B$以及每个连接的成本$c\_{ij}$。预处理阶段需要产生一个分配方案。在在线阶段，算法需要获取分配方案，需求节点以及预算，当供应节点到来的时候，它会找出与满足该供应节点的需求节点，算法需要最终找出满足限制条件下的最有分配结果。

2.3、目标函数（Objective Function）

我们的目标是找到一个特定的目标函数，并最小化，而不是只是找出一个可行的方案。设$F(s,x):R^I\times R^E$是一个凸函数。当如下条件存在且成立的时候，我们称该函数是健壮（well-conditioned）的：

$$\frac{\partial^2}{\partial x^2_{ij}} F(s,x)$$

且所有的$(i,j)\in E$都是正值。同时，某个函数是可分的时候，记作：

$$F(s,x) = \sum_{(i,j)\in E}F_{ij}(s_i,x_{ij})$$

注意，由于二阶导结果为0，因此线性目标函数不是健壮的。当我们的问题是一个线性的目标函数的时候，我们可以首先求出线性目标函数的最优解，然后添加一个线性约束来保证目标函数依然是最优的。在这篇论文中，我们针对的都是健壮的目标函数。

为了使抽样可行，我们还需要对$F$添加一个额外的属性。设$F(s,x):R^I\times R^E\to R$是一个目标函数，其中，对于每一个$x\_{ij}$都是可微的，如果对于每一个$(i,j)\in E$满足如下条件，则$F(s,x)$是无尺度的：

$$\frac{\partial}{\partial x_{ij}}F(s,x) = s_if_{ij}(x)$$

其中$f\_{ij}$与$s$是相互独立的。无尺度的含义是当供应量使用同一个因子进行同一缩放的时候不改变最优结果。如果没有这个条件，使用抽样的方法就会出现问题。

定义1，当目标函数是凸函数、健壮的、可分且无尺度，那么它就是一个结构良好的目标函数。

对于任意一个结构良好的函数，由于$\mathcal{P}$是一个图空间，因此$F(s,x)$，都存在唯一一个全局最小的解决方案$x\in \mathcal{P}$，通常情况下，我们都把最优的解决方案记作：

$$x^* = \arg \min_{x\in\mathcal P} F(s,x)$$

尽管线性目标函数不是一个结构良好的函数，但是这篇论文描述的技术依然可以被扩展后用来解决这个问题，只是需要一点额外的计算。

2.4、鲁棒性

在这里，我们说明下鲁棒性的问题。其实也就是当需求变动了的时候，这个解决方案的变化情况。一般情况下，我们不会去证明生成的分配方案是最优且可行的。一般我们会定义一个变量$\epsilon-goodness$。给定一个问题\mathcal P=&lt; G,s,d >，设$\mathcal P\`=< G,s,(1+\epsilon)d>$是属于问题$\mathcal P$但是每一个需求增加了变成了$(1+\epsilon)d\_j$，因此\mathcal P\`更加难以满足。如果\mathcal P\`是可行的（feasible），那么我们称$\mathcal P$是$\epsilon-feasible$，意味着$\mathcal P$的需求有一定的松弛。

如果$\mathcal P$是$\epsilon-feasible$，那么我们称$\mathcal P$的解决方案$x$是$\epsilon-good$。那么$x$至少不会比\mathcal P\`中的任意一个方案差，即

$$F(s,x)\leq \min_{x' \in \mathcal P'}F(s,x')$$

三、紧凑的分配方案（Compact Allocation Plan）

在这部分，我们将展示这个紧凑方案以及其关键特性。

我们可以通过对每条边进行分数的划分来表示最优的解决方案$x^\*$。在这里我们主要是证明这个最优的解决方案有一个更紧凑的表示。特别地，我们会给出一个函数$\tilde{x}$，在只给定两个需求有关的约束条件下来重建最优的解决方案。在后面我们会证明这个重建的函数依然保留了最优的特性。

定理1、设$G=(I\cup J,E)$是一个二部图，设$F(s,x):R^I\times [0,1]^E\to R$是一个结构良好的函数。那么存在一个连续函数$\tilde{x}(\alpha):R^J\to R^E$，对于任何可行的问题\mathcal{P}=&lt; G,s,d>来说，都存在一个$\alpha^\*\in R^J$，使得$\tilde{x}(\alpha^\*)=\arg\min\_{x\in\mathcal{P}}{F(s,x)}$。

这个定理有个奇怪的地方是不管$I$或者$E$的大小都宣称存在最优解。这个定理的证明来自于最优化的KKT条件，首先我们使用拉格朗日算子改写我们的问题。假设我们用$\alpha\_j$表示第$j$个需求约束的拉格朗日算子，用$\beta\_i$表示第$i$个供应约束的拉格朗日算子，用$\gamma\_{ij}$表示第$ij$个非负约束的拉格朗日算子，那么我们的问题的拉格朗日函数表示：

$$F(s,x) - \sum_{j\in J}\alpha_j(\sum_{i \in\Gamma(j)}s_ix_{ij}-d_j) + \sum_{i\in I}\beta_i(\sum_{j\in \Gamma(i)}s_ix_{ij} - s_i) - \sum_{(i,j)\in E}\gamma_{ij}s_ix_{ij}$$

设$x^\*=\arg\min\_{x\in\mathcal P}\\{F(s,x)\\}$，由于目标函数和所有的约束在$x^\*\in[0,1]$处都可微，那么必然存在$\alpha\_j$、$\beta\_i$和$\gamma\_{ij}$满足KKT条件：

$$\text{For all}\space\space (i,j)\in E, \space\space s_if_{ij}(x^*) -s_i\alpha_j+s_i\beta_i-s_i\gamma_{ij} = 0$$ $$\text{For all}\space\space j, \space\space \alpha_j(\sum_{i\in\Gamma(j)}s_ix^*_{ij}-d_j)= 0$$ $$\text{For all}\space\space i, \space\space \beta_i(\sum_{j\in\Gamma(i)}s_ix^*_{ij}-s_i)= 0$$ $$\text{For all}\space\space (i,j)\in E, \space\space \gamma_{ij}s_ix^*_{ij} = 0$$ $$\text{For all}\space\space (i,j)\in E, \space\space \alpha_j\geq 0,\beta\geq 0, \gamma_{ij}\geq 0$$

第一个条件是平稳，2、3、4是松弛补充，条5是dual-feasibility。重写了之后，我们有：

---

$$\begin{aligned} s_if_{ij}(x^*) -s_i\alpha_j+s_i\beta_i-\gamma_{ij} &= 0 \\ &\\ f_{ij}(x^*) -\alpha_j+s_i\beta_i-\gamma_{ij} &= 0 \\ &\\ f_{ij}(x^*) -\alpha_j+s_i\beta_i &= \gamma_{ij} \\ &\\ f_{ij}(x^*) -\alpha_j+s_i\beta_i &\geq 0 \\ \end{aligned}$$

当$x^\*>0$的时候等号成立。根据上面的KKT条件中的第4条，可以推导如下：

$$x_{ij}^*>0,\gamma_{ij}s_ix^*_{ij} = 0 \to \gamma_{ij}s_i=0$$ $$\gamma_{ij}s_i=0,s_i\neq 0 \to \gamma_{ij}=0$$

---

$$\alpha_j \geq 0$$

当$\sum\_{i \in \Gamma(j)} s\_ix^\*\_{ij} = 0$的时候，等号不成立。

---

$$\beta_i \geq 0$$

当$\sum\_{j \in \Gamma(i)} x^\*\_{ij} = 1$或者$s\_i=0$的时候，等号不成立。

---

一般的，给定对偶问题的解，我们可以还原出原始问题。设$g\_{ij}$是$f\_{ij}$的逆函数。

命题1：假设$x^\*$、$g$、$\alpha$和$\beta\_i$和上面的定义相同，且$s\_i>0$。那么：

$$x_{ij}^* = \max\{0, g_{ij}(\alpha_j-\beta_i) \}$$

证明如下，首先，前面说了，当$x^\*>0$的时候$f\_{ij}(x^\*) -\alpha\_j+ \beta\_i \geq 0$等号成立。即：

$$\begin{aligned} f_{ij}(x^*) -\alpha_j+ \beta_i &= 0 \\ &\\ f_{ij}(x^*) &= \alpha_j- \beta_i \\ &\\ x^* &= g(\alpha_j- \beta_i) \\ \end{aligned}$$

如果$x^\*=0$的时候，我们可以假设$g(\alpha\_j- \beta\_i)>0=x^\*$，也就是说$g(\alpha\_j- \beta\_i)>x^\*$，前面说过$F(s,x)$是凸函数，因此其导数$f\_{ij}$是单调增的，那么：

$$\begin{aligned} f_{ij}(g(\alpha_j- \beta_i)) &> f_{ij}(x^*) \\ &\\ \alpha_j- \beta_i &> f_{ij}(x^*) \\ &\\ f_{ij}(x^*) - \alpha_j + \beta_i &<0 \\ \end{aligned}$$

这个结论与上述结论矛盾。也就是说必然有$g(\alpha\_j- \beta\_i)\leq 0$，那么显然$x^\*=0=\max\\{0, g\_{ij}(\alpha\_j-\beta\_i) \\}$。

为了简便，定义$\tilde{g}\_{ij}(z) = \max\\{0,g\_{ij}(z)\\}$，那么有$x^\*=\tilde{g}\_{ij}(\alpha\_j-\beta\_i)$。

引理1：设$\tilde{g}$、$\alpha\_j$、$\beta\_i$定义如上，假设$s\_i>0$。如果\sum\_{j\in\Gamma(i)}\tilde{g}\_{ij}(\alpha\_j)&lt; 1，那么$\beta\_i=0$。否则的话，$\beta\_i$是满足如下等式的唯一值：

$$\sum_{j\in\Gamma(i)}\tilde{g}_{ij}(\alpha_j-\beta_i) = 1$$

证明：首先考虑\sum\_{j\in\Gamma(i)}\tilde{g}\_{ij}(\alpha\_j)&lt; 1，由于该函数是单增函数，$\beta\_i>0$，因此有：

$$\sum_{j\in\Gamma(i)}\tilde{x}_{ij} = \sum_{j\in\Gamma(i)}\tilde{g}_{ij}(\alpha_j - \beta_i)< 1$$

注意看前面命题1之前最近的一个公式，这两个之间相互矛盾。

四、结论（Overall Algorithm）

将上述内容全部结合到一起我们可以看到，本论文提出的广告分配方案如下。给定问题\mathcal P = &lt; G,s,d>和结构良好的目标函数$F(s,x)$：

1、在预处理阶段，首先抽取图的样本$\tilde P$，然后求出$\alpha^\* \in R^J$使得$\tilde{x}(\alpha^\*)=\arg\min\_{x\in\tilde{P}}\\{F(s,x)\\}$，且$\alpha^\*\_j\leq \alpha\_{max}$。 2、在在线阶段，当一个用户（供应节点）到达的时候，我们已知$s\_i$和$\Gamma(i)$： 　　根据引理1，求出$\beta\_i$ 　　计算分配比例$\tilde{x}\_{ij}(\alpha)=\hat{g}\_{ij}(\alpha\_j-\beta\_i)$

最终我们可以按照上述比例进行广告选择分配即可。