预备知识
令 (X) 表示一个变量组(向量) ((x_1, x_2, cdots, x_n))
考虑一个处处可导的函数 (f(X)), 为了方便描述, 这里以二元函数为例
对于微分, 考虑在初始点处固定x移动y产生的变化量, 是和先将x移动dx,然后固定x移动y产生的变化量是相等的
那么有全微分公式 (df = frac{partial f}{partial x}dx + frac{partial f}{partial y}dy)
定义 (
abla f(x, y)) 为点 ((x, y)) 上的梯度方向向量(平面上的这些向量构成一个向量场)
梯度方向向量指向让(df)最大的方向. 也即使 ((frac{partial f}{partial x},frac{partial f}{partial y})cdot(dx, dy)) 最大的 ((dx, dy))
要投影最长, 同向自然最优, 因此偏导组成的向量((frac{partial f}{partial x},frac{partial f}{partial y}))就是梯度方向向量
同理考虑 (df=0) 的方向(等高线), 投影为0, 这说明等高线的方向与梯度的方向垂直
高维的情况同理
拉格朗日乘数法
考虑这么一个问题:
(~~max f(X))
(s.t.~~g_k(X) = 0, forall k in [1,m])
考虑 (f(X)) 在什么时候取得局部极大值:
考虑往某个方向微移, 若满足这样移动不影响任何一个 (dg), 那么必须要有 (df=0)
否则如果存在 (df
eq 0) , 必然 (<0, >0) 都会出现 (考虑反向微移), 就不是局部极值点了
考虑把 (dx_1, dx_2,cdots dx_n) 这种东西看作变量
把 (
abla g_1,
abla g_2, cdots
abla g_m) 以及 (
abla f) 都横着放在矩阵里看作若干个方程
之前的条件就等价于: 前 (m) 条方程蕴含了最后一条方程
也即 (
abla f) 可以被 (
abla g_1cdots
abla g_m) 线性表示
令(L(X,Lambda) = f(X) + sum_{k=1}^m lambda_k g_k(X))
我们只需求解 (
abla L(X,Lambda) = 0) 即可
这样我们对 (n) 个变量分别求偏导即可得到 (n) 个方程
加上 (g) 的 (m) 个方程 (恰好是对(lambda)分别求偏导)
总共 (n+m) 个方程.
KKT条件
考虑这么一个问题:
(~~max f(X))
(s.t.~~h_k(X)ge 0, forall k in [1, m])
令 (L(X, Lambda) = f(x) + sum_{k=1}^m lambda_k h_k(X), lambda_k ge 0)
因为(lambdage 0, hge 0), 所以 (f(X) = min_{Lambdage 0} L(X,Lambda))
原问题等价于 (max_X min_{Lambdage 0} L(X,Lambda))
考虑对偶问题 (min_{Lambdage 0}max_X L(X, Lambda))
显然(L(X, Lambda)ge f(X)), 则有 (max_X L(X, Lambda) ge max f(X))
对偶问题对所有的这些值取 (min), 仍然是 (ge max f(X))
设原问题极值点在 (X^{*}), 对偶问题极值点在 (Lambda^{*})
则有 (max_X L(X, Lambda^{*}) ge f(X^{*}) + sum_{k=1}^m lambda^{*}_k h_k(X) ge f(X^{*}))
假设强对偶性满足, 上面的不等号都要变成等号
限制了 : (lambda^{*}_k h_k(X) = 0) 以及 (
abla L(X^{*}, Lambda^{*})=0)
结论好记: KTT条件只比拉格朗日乘数多了两个限制, (lambda_k h_k(X) = 0, lambda_kge 0)
在哪些问题上满足强对偶性, 详见wiki
自己姿势水平不够, 这个坑可能不那么快能填上了
另外, 考虑如果在原问题加上等式限制, 就再补上拉格朗日乘数即可, 不难发现, 不影响这里的证明