第 155 题：约束优化，预算消耗约束的拉格朗日松弛？
题目
约束优化，预算消耗约束的拉格朗日松弛？
完整讲解
一、约束优化问题
在推荐/广告中常有约束：如预算消耗不超过某上限、某类目曝光占比不低于某下限。形式为
\(\min_\theta \mathcal{L}(\theta),\quad \text{s.t.}\quad g_j(\theta) \le 0,\ j=1,\ldots,J.\)
例如 $g = \text{预算消耗} - B$，要求 $g \le 0$。直接解带约束优化在 DNN 与在线场景下较难，常用拉格朗日松弛转为无约束或近似问题。
二、拉格朗日松弛
拉格朗日函数：
\(\mathcal{L}(\theta, \lambda) = \mathcal{L}(\theta) + \sum_j \lambda_j g_j(\theta),\quad \lambda_j \ge 0.\)
原始问题 $\min_\theta \max_{\lambda \ge 0} \mathcal{L}(\theta, \lambda)$ 与原始约束问题在凸等条件下等价。对偶：先对 $\theta$ 最小化、再对 $\lambda$ 最大化；或交替：固定 $\lambda$ 更新 $\theta$（梯度下降主损失+约束惩罚）、固定 $\theta$ 更新 $\lambda$（若 $g_j>0$ 则增大 $\lambda_j$ 以加大惩罚）。
三、预算消耗约束的用法
- 约束：$g = \sum \text{消耗} - B \le 0$（总消耗不超预算）。将 $g$ 写入拉格朗日项 $\lambda g$，则 $\lambda$ 可视为「预算影子价格」：预算紧时 $g$ 常为正、$\lambda$ 会增大，使 loss 更惩罚「高消耗」的决策，从而压低消耗。
- 在线/迭代：每步或每天更新 $\theta$（模型参数）与 $\lambda$（拉格朗日乘子）。$\lambda$ 的更新可用梯度上升：$\lambda \leftarrow \lambda + \eta \cdot g$（若 $g>0$ 则增 $\lambda$），或用 PID 等控制律使 $g$ 趋近 0。这样无需显式解约束优化，通过迭代自动逼近可行解。
- 与 pacing 的关系：广告中的 budget pacing 常等价于一个约束（消耗速率 $\le$ 目标）；拉格朗日乘子 $\lambda$ 对应 pacing 的「价格」或调节因子。
四、注意点
- 非凸时拉格朗日与原始问题不一定等价，但工程上仍常用作启发式：通过调 $\lambda$ 控制约束违反程度。
- $\lambda$ 的初值与步长影响收敛；可设 $\lambda$ 上下界避免爆炸。
面试要点
- 能写出拉格朗日函数 $\mathcal{L} + \sum \lambda_j g_j$ 及 $\lambda \ge 0$，并说明原始问题与 min-max 形式。
- 能说清预算约束 $g = \text{消耗} - B$、$\lambda$ 为影子价格；交替更新 $\theta$ 与 $\lambda$、$\lambda$ 用梯度或 PID 更新。
- 能提及与 pacing 的关系、非凸时的启发式用法。
记忆要点
- 约束 $g_j \le 0$；拉格朗日 $\mathcal{L} + \sum \lambda_j g_j$，$\lambda_j \ge 0$。
- 预算约束：$g = \text{消耗} - B$；$\lambda$ 增大则惩罚消耗；交替更 $\theta$ 与 $\lambda$。
- $\lambda$ 更新：$g>0$ 时增 $\lambda$（梯度或 PID）；与 pacing 对应。