本文包含对线性规划的直观理解，不严谨，后续有新的问题/理解持续更新
- 参考链接：
- 运筹学中应该如何理解互补松弛性。这条性质又该如何运用?
- 第4章 对偶理论和敏感度分析
- 线性规划对偶问题的定义，有什么直觉上的解释吗？：原始问题到对偶问题最好的一种很简洁的解释
- 互联网广告算法漫谈——浅谈广告中的出价技术。注意：该参考链接中没有把预算约束相关的互补松弛定理写出来，且2.3中存在一些较为明显的小bug，但整体求解思路和结论没问题
原始问题
- 问题描述：
- 假设你是一个木匠有200单位的木头和90单位的时间
- 木匠可以制作桌子或者椅子
- 桌子成本为5单位木头+2单位时间，售价10元
- 椅子成本为2单位木头+1单位时间，售价3元
- 目标：在已有资源情况下，最大化收入，应该生产多少桌子和椅子？
- 问题形式化描述:
- 假设应该生产 \(x_1\) 把桌子和 \(x_1\) 把椅子
$$
\begin{align}
\max \ \ 10x_1 &+ 3x_2 \\
5x_1 + 2x_2 &<= 200 \\
3x_1 + \ \ x_2 &<= 90 \\
x_1,x_2 &>= 0 \\
\end{align}
$$
- 假设应该生产 \(x_1\) 把桌子和 \(x_1\) 把椅子
- 作图法可求得最优解为 \(x_1^* = 30, x_2^*=0\)，此时最大收益为300
- 在二维坐标轴上先画出可行域，然后按照目标直线斜率找到最优点
对偶问题
- 对偶问题描述：
- 上述原始问题可以换一个视角看
- 假设现在你是一个原材料收购商（想要以最低价格收购木匠的原材料）
- 目标：对单位木头和单位时间进行出价，以最低的价格买完木匠的资源（假设木匠愿意卖出的前提是收购上出价的最小值不小于木匠原始问题中收益的最大值）
- 实际上最好是刚好等于木匠原始问题的最大收益
- 对偶问题形式化描述
$$
\begin{align}
\min \ \ 200p_1 &+ 90p_2 \quad – 总付款 \\
5p_1 + 3p_2 &>= 10 \quad – 一张桌子的资源售价不低于一张桌子的收益 \\
2p_1 + \ \ p_2 &>= 3 \quad – 一张椅子的资源售价不低于一张椅子的收益 \\
p_1,p_2 &>= 0 \quad – 售价不为负数 \\
\end{align}
$$ - 其中 \(p_1, p_2\) 分别称为单位木头和单位时间的影子价格
- 作图法可求得最优解为 \(p_1^* = 0, p_2^* = 3.3\)，此时最小支付金额为300
互补松弛定理的理解
从原始问题的约束视角出发
等价于从对偶问题的解出发
- 对偶问题中，最优解是 \(p_1^* = 0, p_2^* = 3.3\)
- \(p_1^* = 0\) 意味着我们的木材过量了，其实不需要这么多木材，原始问题中，最优解对应的木材约束是松的（ \(5x_1^* + 2x_2^*=150 < 200\) ）
- \(p_2^* = 3.3\) 说明时间资源非常紧俏，原始问题中，最优解对应的时间约束是紧的（ \(3x_1^* + \ \ x_2^* = 90\) ）
- 对应互补松弛的含义：
- 如果在最优条件下一个约束不等式是松的（木材），那么这个约束对应的影子价格为0
- 反过来说，如果某个约束对应的影子价格严格大于0，那么这个约束不等式一定是紧的
- 总的来说，原始问题的约束和对偶问题变量(影子价格)总有一个要为0
从对偶问题的约束视角出发
等价于从原始问题的解出发
- 原始问题中，最优解是 \(x_1^* = 30, x_2^*=0\)
- \(x_1^* = 30\) 意味着桌子非常合算，应该多生产桌子，对偶问题中，桌子约束是紧的（ \(5p_1^* + 3p_2^* = 10\) ）
- \(x_2^*=0\) 以为这椅子不合算，不应该生产椅子，对偶问题中，椅子的约束是松的（ \(2p_1^* + \ \ p_2^* = 3.3 > 3\) ）
- 补充互补松弛的含义：
- 如果在对偶最优条件下一个约束不等式是松的（椅子），那么这个约束对应的原始问题变量最优解（ \(x_2^*\) ）为0
- 反过来说，如果某个原始问题变量（桌子）对应的解（ \(x_1^*\) ）严格大于0，那么对偶问题中这个约束不等式一定是紧的
- 总的来说，对偶问题的约束和对应原始问题变量总有一个要为0
互补松弛定理的公式化
$$
(5p_1^* + 3p_2^* - 10)x_1^* = 0 \\
(2p_1^* + p_2^* - 3)x_2^* = 0 \\
(5x_1^* + 2x_2^* - 200)p_1^* = 0 \\
(3x_1^* + x_2^* - 90)p_2^* = 0 \\
$$
附录：USCB推导
- 《A Unified Solution to Constrained Bidding in Online Display Advertising》——论文阅读
- 这篇文章的约束很多，每个商家都有自己的约束
- 推导时用到的对偶变换和互补松弛定理均可由论文推导得出【有时间再详细推导】
附录：BCB推导（单约束）
- 《Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising》——论文原文
- 这篇文章中的问题定义比较简单，整体只有一个预算约束
- 上述结果详细的推导可以参考：
- 智能出价——BCB求解
- 互联网广告算法漫谈——浅谈广告中的出价技术。注意：该参考链接中没有把预算约束相关的互补松弛定理写出来，且2.3中存在一些较为明显的小bug，但整体求解思路和结论没问题
- 推导结果 \(bid = \frac{v_i}{\lambda}\) 与常用的方法(RL-MPCA)结果不一致，但可以证明本质是等价的
- 这篇文章中的问题定义比较简单，整体只有一个预算约束
附录：CPC约束推导（单约束）
- 问题描述：单位置、二价拍卖，且CPM计费场景，CPC约束下最大化商家点击量
- 推导过程可参考论文Bid Optimization by Multivariable Control in Display Advertising
- 基本推导思路：先通过拉格朗日乘子法得到最优解的形式（这里先忽略边际条件 \(0\le x_i \le 1\) ），再将原始问题转换成对偶问题，进一步分情况讨论得到最终解
- 问题定义
$$
\begin{align}
&\max \sum_i x_i \cdot ctr_i \\
\text{s.t.} &\quad \frac{\sum_i x_i \cdot wp_i}{\sum_i x_i \cdot ctr_i} \le cpc \\
&\quad 0 \le x_i \le 1, \forall i
\end{align}
$$ - 第一步：推导最优出价形式：
- 写出拉格朗日函数并求导：
$$\mathcal{L}(x, \lambda, \mu) = - \sum_i x_i \cdot ctr_i + \lambda \left(\sum_i x_i \cdot wp_i - \sum_i x_i \cdot ctr_i \cdot cpc\right) + \sum_i \mu_i (x_i - 1)$$ - 对任意的 \(x_i\) 求导有：
$$ \frac{\partial \mathcal{L}(x, \lambda, \mu)}{\partial x_i} = - \sum_i ctr_i + \lambda \sum_i wp_i - \lambda \sum_i ctr_i \cdot cpc + \sum_i \mu_i $$ - 令上述导数为0有（\(\mu_i\) 来自边界条件 \(0\le x_i \le 1\)，为了得到最优解形式，接下来先忽略边界条件，最后会证明在满足边界条件下，该形式也是最优的）：
$$
\begin{align}
wp_i &= \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda} \\
&= \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i
\end{align}
$$- 所以我们令出价等于下面的形式：
$$bid_i = \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i$$
- 所以我们令出价等于下面的形式：
- 写出拉格朗日函数并求导：
- 第二步：验证最优出价形式：
- 原始问题对应的对偶问题为：
$$
\begin{align}
&\mathop{\min}_{\lambda, r_i} \sum_i r_i \\
\text{s.t.} &\quad \lambda(wp_i - cpc\cdot ctr_i) + r_i \ge ctr_i \quad \text(1)\\
&\quad \lambda \ge 0 \\
&\quad r_i \ge 0, \forall i
\end{align}
$$ - 互补松弛条件:
$$
\begin{align}
x_i(\lambda(wp_i - cpc\cdot ctr_i) + r_i - ctr_i) = 0 \quad &\text{(2)} \\
r_i(x_i - 1) = 0, \forall i \quad &\text{(3)}
\end{align}
$$ - 将最优出价公式 \(bid_i = \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda}\) 带入公式(2)可得：
$$ x_i(\lambda(wp_i - bid_i) + r_i) = 0$$- 当 \(x_i \gt 0\) 时，有 \(wp_i - bid_i = -\frac{r_i}{\lambda} \lt 0\)，进一步推得 \(bid_i \ge wp_i\)
- 当 \(x_i = 0\) 时，由公式(3)有 \(r_i = 0\)；将最优出价公式 \(wp_i = \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda}\) 带入公式(1)可得 \(\lambda(wp_i - bid_i) + r_i \ge 0\)，进一步推得 \(wp_i - bid_i \ge 0\)，即\(bid_i \le wp_i\)
- 证毕
- 原始问题对应的对偶问题为：
- 如何理解最优出价形式？
$$
\begin{align}
bid_i = \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i = \color{red}{(\frac{1}{\lambda \cdot cpc} + 1)} \cdot cpc \cdot ctr_i
\end{align}
$$- 二价计费场景中 ，计费比未知，所以引入了一个大于 1 的出价系数:
$$ k = \color{red}{\frac{1}{\lambda \cdot cpc} + 1} $$- 用来提升出价以做到目标CPC达成（可以证明，在整个周期内流量足够多的情况下，如果实际CPC小于目标CPC，则此时一定不是点击最大化的出价策略）
- 实际使用中，由于 \(1\) 是全局固定值，商家的 \(cpc\) 是商家粒度的固定值，\(\lambda\) 是商家粒度的变量，可以合并成一个变量即可（\(\lambda\) 和 \(k\) 是一一对应的），最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
$$ bid_i = \color{red}{k} \cdot cpc \cdot ctr_i $$
- 如果竞争环境非常激烈，计费比趋近于1（同时考虑预估值准确），此时每次出价都按照 \(\color{red}{bid_i = cpc \cdot ctr_i} \)，可保证投放周期内实际CPC的期望刚好等于目标CPC，\(\color{red}{k=1}\) 就是最优的出价策略
- 调控系数的其他功能 ：从推导来看，系数 \(k\) 可以用于补足二价计费的Gap；在实际应用中，这个 k 值还可以解决 CTR 均值预估值不准确的问题，比如CTR预估过高 ，\(k\) 会小于1 ，从而保证不超成本
- 可以注意到：在这个假设下有矛盾点，\(k < 1\) 时对应的 \(\lambda < 0\)，并不满足对拉格朗日乘子的要求，但不用担心，这里实际上 \(k = k_1 \cdot k_2\)，其中，由 \(\lambda\) 导出的 \(k_1\) 依然是大于1的，用来调平CTR预估值 \(k_2\) 是小于1的，实际上，\(\lambda \geq 0\) 始终成立
- 二价计费场景中 ，计费比未知，所以引入了一个大于 1 的出价系数:
附录：oCPC场景约束推导（单约束）
- 问题描述1：单位置、二价拍卖，且CPC计费场景，CPS约束下最大化商家订单量
- 实际上，本问题中与上文单位置拍卖的CPM计费场景，CPC约束下最大化商家点击量非常相似，仅需把对应的参数替换一下即可（\(ctr_i \rightarrow cvr_i\)，\(cpc \rightarrow cps\)），于是有最优出价形式是：
$$
\begin{align}
wp_i = \frac{1 + \lambda \cdot cps}{\lambda} \cdot cvr_i = \color{red}{(\frac{1}{\lambda \cdot cps} + 1)} \cdot cps \cdot cvr_i
\end{align}
$$- 出价系数：
$$ k = \color{red}{\frac{1}{\lambda \cdot cps} + 1} $$ - 注：实际使用中，同上描述，最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
$$ bid_i = \color{red}{k} \cdot cps \cdot cvr_i $$
- 出价系数：
- 问题描述2：单位置、二价拍卖，且CPC计费场景，ROI约束下最大化商家Revenue
- 此时可以进一步表达为如下形式（\(cvr_i \rightarrow cvr_i\cdot rev_i\)，\(cps \rightarrow rate = \frac{1}{ROI}\)， ）：
$$
\begin{align}
wp_i &= \frac{1 + \lambda \cdot 1/ROI}{\lambda} \cdot cvr_i \cdot rev_i \\
&= \frac{ROI + \lambda}{\lambda \cdot ROI} \cdot rev_i \cdot cvr_i \\
&= \frac{ROI + \lambda}{\lambda} \cdot \frac{rev_i \cdot cvr_i}{ROI} \\
&= \color{red}{(\frac{ROI}{\lambda} + 1)} \cdot \frac{rev_i \cdot cvr_i}{ROI} \\
\end{align}
$$- 出价系数：
$$ k = \color{red}{\frac{ROI}{\lambda} + 1}$$ - 注：实际使用中，同上描述，最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
$$ bid_i = \color{red}{k} \cdot \frac{rev_i \cdot cvr_i}{ROI} $$
- 出价系数：
附录：紧约束和松约束
- 紧约束（Tight Constraint）和松约束（Slack Constraint）是描述约束条件对可行解集影响的两个概念
- 紧约束指的是那些在其边界上限制了最优解的约束条件。换句话说，如果改变某个约束条件会直接影响到最优解的位置或值，那么这个约束条件就是紧的。例如，在线性规划问题中，如果一个不等式约束以“=”的形式满足于最优解处，那么这个约束就是紧约束。紧约束对于确定最优解至关重要，因为它们直接定义了最优解所在的位置
- 松约束则指的是那些在最优解处并没有起到实际限制作用的约束条件。也就是说，即使这些约束不存在，也不会改变问题的最优解。这类约束条件提供了额外的空间，但在这个空间内的点并不会比边界上的点更优。因此，松约束的存在不会影响最终的优化结果，但在某些情况下，它们可能为寻找最优解提供便利或增加灵活性。