概述
求多元函数 $f(x)$ 在满足 $g_i(x)=0$ 的极值。设一个乘数 $\lambda$，求下面多元函数的极值
例 求 $y=\frac{1}{x}$ 到原点最近的点。
即在满足 $g(x,y)=xy-1=0$ 的条件下，最小化 $f(x,y)=x^2+y^2$。
设乘数 $\lambda$，最小化 $f(x,y,\lambda)=f(x,y)+\lambda g(x,y)=x^2+y^2+\lambda xy-\lambda$。
分别对 $x,y,\lambda$ 求导，令导数为 $0$，得到
解得
线性规划对偶可以得到方便的机械化方法。不会证明，下面只讲方法。
将线性约束转化为 $… \le 0$ 的形式。
对每个约束设一个乘数 $\lambda$，若求 $\min$ 那么限制 $\lambda \ge 0$，否则限制 $\lambda \le 0$。
将约束乘乘数写入最优化函数，即求 $L(x,\lambda)$ 的最值。将 $L(x,\lambda)$ 转化为以 $x$ 为主元的形式，通过限制系数使得 $L(x,\lambda)$ 不会取到 $\infty/-\infty$。
将 $\min/\max$ 取反，将带 $x$ 的项删去得到新的最优化函数。
需要将下式对偶
改写为
设乘数 $f_e,F$ 得到
为防止取到 $\infty$，将系数限制为 $\le 0$，得到对偶
将 $f_e,F$ 取反得到
对于一般的拉格朗日对偶，最优化函数满足凸优化和 slater 条件是强对偶的充分条件。
例题
1.[NOI2012] 骑行川藏
贪心，令 $\sum_{i} s_ik_i(v_i-v’_i)^2=E$ 即可。
用拉格朗日乘数法，得到
对于给定的 $\lambda$，通过 $(1)$ 式计算 $v_i$ 并带入 $(2)$ 式判断即可。发现 $\lambda$ 递增时 $v_i$ 递减，二分 $\lambda$ 即可。时间复杂度 $O(n\log^2V)$。