BSD：Auction with ROI constraints

之前关于BSD的讨论：https://www.jianshu.com/p/5edf15c787ed [1]

问题建模Modeling：

• 类似[1]中的方案，此处为以无偏winning rate建模的方式最优化期望收益）
  当然，这种modeling的一大问题是，真实的成功率与无偏随机数据是有差距的，因为我们出价与市场价并不互相独立。
• 形式化：
  为utility，为预估的用以计算roi的收益。
  
  s.t.1：
  s.t.2：
  得到：
  

Solution:

KKT condition：

• 对偏导为0：
  （1）
  给定win函数:
  （2）
  其中为拟合成功率的常数
  求导可得：
  （3）
  将（2）（3）带入（1）化简可得：
  
  解得：

• 原约束与系数约束：
  
  
  

• budegt互补松弛条件：
  

• roi互补松弛条件：
  

参数解法：

• Qualification-LICQ：因为，所以当且仅当在其解处，激活条件对（此处即）梯度向量时满足LICQ。
  很显然
  1、在只有一个限制条件激活时，只要极值处限制条件对的导数不为0，则这个条件就是满足的。
  2、在多个限制条件激活时，肯定是不满足的。
  

• Qualification-SC：对于多条件激活。判定是否满足SC，即优化目标与限制函数，是否都是convex的。判断方式需要求其二阶变分则满足SC。
  为了简化问题，我们可以将当前假设的解带入，即在当前假设下，是否满足SC。
  带入式子（2）得到如下：
  （4），根据成功率函数的图像，是恒小于0的。
  
  
  Convexity of functional：[1]
  a、目标函数的二阶变分：
  
  带入拟合出来的常数，在实际区间上积分大于等于0
  b、预算限制的二阶变分：
  
  
  带入拟合出来的常数，其积分显然大于等于0
  c、ROI限制的二阶变分：
  
  
  带入拟合出来的常数，其积分也显然大于等于0
  所以，由此可以得出，当前问题在两个约束都生效时，满足SC

• 情况0：
  则，明显不满足条件。

• 情况1：
  这种情况下，等价于只有budget预算限制。
  所以将的解带入（将带入，其中仅包含），解如下问题即可：
  
  观察解的形式与的形式，可轻易得出与预算消耗成反比
  在这个问题中，由于无论如何变化，排序是不变的。所以可以直接将数据带入，求方程的数值解即可。
  当然，由于本身也是单调的，通过二分搜索也可以较容易地获得数值解。

• 情况2：
  类似地，将的解带入，求解ROI刚好满足的状态即可。
  
  得到 ，可以看出就是u的反向权重。越大，越倾向于用g（收益）来排序，即参与竞价的ad的越大，且总体出价越低（成本低），则ROI越大。
  所以ROI对单调递增，可以通过二分搜索以获得数值解。
  （这种情况下，由于的变化会影响排序，所以无法将数值全部带入直接求其数值解，当然，改写整个方程，将排序过程加入也是可以的，但是求解速度也并不一定会很快）

• 情况3：
  条件：如果上述两种方式求解出来分别的ROI，Budget不满足边界条件的（即都超出边界）。
  此时两个KKT乘子都不为0，
  即最优解在ROI刚好满足，Budget也刚好满足的边界上，KKT multiplier等价于Lagrangine multiplier。
  将带入松弛条件（同拉格朗日，等式约束，即偏导为0），求解如下方程组：
  
  化简后无特殊形式，不易求出解析解可由数值解法解出。
  当然，这个方程组求解的最大问题同样在于，由于会影响排序，所以很难直接用传统的数值优化的方程组解法得到解。（TODO）

问题分析：

以下分析针对我们对泛函最优化的解法其中的排序问题的讨论。
由于增加了ROI限制情况下，本身目标为u，限制目标的函数g。

和都跟流量具体的分布相关。

和的数值，本身会影响排序。从而影响我们最优化问题中的具体的数值分布。

虽然在当前体系下，由于其单调性（单约束），我们能搜索出最优解，但是其预估本身的误差会影响排序的结果（从而影响不同下和的分布，导致计算出来的roi与budget都有偏差）。

通俗点解释：
1、如果和相同，由于biding函数是对其单调递增的，所以我们离线模拟时只需要得到按u排序top1即可，搜索不同的参数时，也不影响排序。

2、如果和不同，则参数的变化会影响其顺序，所以我们离线模拟的时候需要记录每次竞价的候选列表。计算复杂度大大提升。

Refer:
[1]
INTEGRALS WHICH ARE CONVEX FUNCTIONALS