闲话
LP 系列精神续作！
以及没人想到我会在 12.31 更闲话吧！哈哈哈背刺！
明天闲话就是 23.01.01 了！激动激动
41，43，47。数素数吧——素数是谁也无法分割的数字。
《ハローマリーナ(Hello Marina)》Vo. 歌愛ユキ & 初音ミク By. 稲葉曇
也是很符合冬日气氛的一首歌，就像是在寂寥的深空下望着远方的样子。
但是我脑海中浮现的景色是深夜路灯旁半暗的地方，所以没有远方的景色，大抵只是一些远山的孤影。
积雪融化了。但这意味着冬天的如何呢？伤痕也许也在心底刻下了，但未来又会如何呢？
这首歌拥有着这样的两面性，希望读到这里的人可以听一听。
线性规划的拉格朗日对偶
首先说一下一般的拉格朗日对偶。其实就是拉格朗日乘子法。这段是抄论文的，他的语言我看不太懂。
假设 \(f(x), g(x)\) 均为关于 \(x\) 的函数，此时要求 \(\max f(x) \text{ s.t. } g(x) \le 0\)。我们引入拉格朗日乘子 \(\lambda\)，记 \(L(\lambda, x) = \max f(x) - \lambda g(x)\)，有原式的最大值 \(\le \min L(\lambda, x)\)。
\(L(\lambda, x)\) 关于 \(\lambda\) 是凸的。也就是说，
\[\begin{aligned} & L(a\lambda_1 + (1 - a)\lambda_2, x) \\ = \ & f(x) - (a\lambda_1 + (1 - a)\lambda_2)g(x) \\ = \ & a(f(x) - \lambda_1g(x)) + (1 - a)(f(x) + \lambda_2g(x)) \\ \le \ & aL(\lambda_1, x) + (1 - a)L(\lambda_2, x) \end{aligned}\]然后对给定的 \(x\) 我们可以二分斜率 / 三分求最小值。
然后是线性规划的拉格朗日对偶。
考虑一个线性规划的标准形式。我们令 \(\bm f(\bm x) = \bm c^{\mathsf T} \bm x,\ \bm g(\bm x) = A\bm x - \bm b,\ \bm \lambda = \bm y^{\mathsf T}\)。那么得到
\[\begin{aligned} & \max_{\bm x \ge 0} \bm f(\bm x) \\ \le \ & \min_{\bm y \ge 0} \max_{\bm x \ge 0} \bm c^{\mathsf T} \bm x - \bm y^{\mathsf T}(A\bm x - \bm b) \\ = \ & \min_{\bm y \ge 0} \max_{\bm x \ge 0} \bm (c^{\mathsf T} - \bm y^{\mathsf T}A)\bm x + \bm y^{\mathsf T} \bm b \\ = \ & \min_{\bm y \ge 0} \bm y^{\mathsf T} \bm b \qquad \text{ s.t. } (c^{\mathsf T} - \bm y^{\mathsf T}A) \le 0 \end{aligned}\]可以发现若 \(c^{\mathsf T} - \bm y^{\mathsf T}A > 0\) 则 \(\max\) 的部分能取到 \(\inf\)，不会被 \(\min\) 统计，因此抛弃即可。可以发现这样得到的形式就是正常的对偶形式。
这玩意没用啊 始末状态相同？需要注意的是，这里的空间曲线积分和路径有关（
我们发现，这过程是拉格朗日乘子法的形式。众所周知，拉乘的作用是将约束条件整合入求极值条件中，因此这个做法理论上能够帮助我们去除线性规划的一些约束条件。看不懂例题。
可以发现，过程中出现了 \(\min \max f(x)\) 的形式。想到网络流模型，我们也可以将这一点看作模型，通过拉格朗日对偶转化。
给定一张二分图 \((U, V)\)，\(u\to v\) 的边权为 \(w_{u, v}\)。有 \(k\) 个互不相交的集合 \(U_i\)，可以用 \(b_i\) 的代价让所有 \(u\to v \text{ s.t. } u\in U_i\) 的边权加 \(1\)。我们希望最大化最小权值完美匹配（右侧完全匹配）的权 - 花费的代价。
\(|U| \le 100, |V|\le 1000\)。
我们令 \(\lambda_i\) 为第 \(i\) 个集合加权的次数，\(f_{u,v}\) 表示 \(u\to v\) 是否在结果完美匹配 \(f\) 中。容易写出
\[\max_{\bm \lambda \ge \bm 0}\min_{|f| = |V|} \sum_{i = 1}^k\left(\sum_{u\in U_i}\sum_{u\to v} (w_{u, v} + \lambda_i)f_{u,v} - b_i \lambda_i\right) \]即
\[\max_{\bm \lambda \ge \bm 0}\min_{|f| = |V|} \sum_{(u, v)} w_{u,v} f_{u,v} - \sum_{i = 1}^k\left(\sum_{u\in U_i}\sum_{u\to v} f_{u,v} - b_i\right)\lambda_i \]这 \(\min \max\)。我们将 \(\bm \lambda\) 看作拉格朗日乘子，\(\sum_{u\in U_i}\sum_{u\to v} f_{u,v} - b_i\) 看作约束条件，则这个就是拉格朗日对偶卡在一半的形式，对偶得到
\[\begin{aligned} \min_{|f| = |V|} \quad & \sum_{(u, v)} w_{u,v} f_{u,v} \\ \text{s.t.}\quad & \forall i,\ \sum_{u\in U_i}\sum_{u\to v} f_{u,v} \le b_i \end{aligned}\]由于 \(U_i\) 两两不相交，约束即为对于 \(U_i\) 内的点流量总和不超过 \(b_i\)。求最小费用的完美匹配，跑最小费用流即可。
还有最后一个问题，\(\bm \lambda\) 的整数限制在最后不见了。但是可以知道，整数费用流问题以及它的对偶一定存在整数最优解（证明详见论文）。因此拉格朗日乘子（即对偶变量）能取得整数最优解，因此该做法正确。
稍晚时候会实现一下。
标签：max,min,闲话,sum,mathsf,22.12,bm,31,lambda From： https://www.cnblogs.com/joke3579/p/chitchat221231.html