参数定义
参数 | 含义 |
---|
τij | 采用折扣j时冒泡i(包含该冒泡的本身特征)的发单率增量 |
ecr(j) | 采用折扣j时冒泡发单率(忽略冒泡i下标)(j=0时不补贴) |
cri | 冒泡i的发单完单率 |
τjr(xi) | 折扣j给冒泡i带来的gmv增量 |
τjc(xi) | 折扣j给冒泡i带来的cost增量 |
B | 补贴预算 |
优化模型
minf(Z)=−i=0∑N−1j=0∑Mτjr(xi)⋅zijs.ti=0∑N−1j=0∑Mτjc(xi)⋅zij≤B
拉格朗日函数
minL(Z,λ)=−[i=0∑N−1j=0∑M(τjr(xi)−λτjc(xi))⋅zij]−λ⋅B
拉格朗日对偶函数
原问题目标函数和约束都为凸函数,满足强对偶条件,转为求解
λ≥0maxZ∈DminL(Z,λ)
其中D为原问题决策变量的定义域
当λ和B固定时,该问题实际上为一个连续背包问题,此时:
zij∗=zijargmaxj=0∑M(τjr(xi)−λτjc(xi))⋅zijji∗=jargmax(τjr(xi)−λτjc(xi))
其中:
τjr(xi)−λτjc(xi)
即为连续背包问题中的weightjvaluej ,补贴策略选择τjr(xi)−λτjc(xi)最大的即可
求解
因此,我们要对该问题求解,应该分成两步:
- 给定补贴率s
- 通过一些算法求出最优的B∗和λ∗
- 在求B和λ的迭代过程中,根据每个B和λ,快速求出对应的策略
Tips
不同的补贴率对应不同的预算B,对每个补贴率求出最优的λ,作为字典供线上使用
对于每种补贴率下的预算B,它和gmv相关,在补贴率确定的情况下,通过某种算法确定gmv,固定gmv就等同于固定了B,此时通过三分法求解λ∗
λ的实际意义是边界ROI,B越少的情况下,λ越大,B越多的情况下,λ越小