拉格朗日对偶性
拉格朗日对偶性
在机器学习中，我们经常会遇到给定某些约束条件求解某个函数最大值或最小值的情况，称之为约束最优化，通常的做法是利用拉格朗日对偶性将原始问题转化为对偶问题，通过解对偶问题进而得到原始问题的解. 在机器学习的很多方法中都有用到此方法，如最大熵模型和SVM.
原始问题
我们假设f(x),ci(x),h(x)f(x),c_i(x),h_(x)f(x),ci(x),h(x)是定义在RnR^nRn上的连续可微函数，考虑如下约束最优化问题：
对于最优化问题我们通常转化为求min minx∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l \begin{aligned} \min_{x\in R^n}\ \ \ \ &f(x)\\ s.t.\ \ \ \ &c_i(x)\leq 0,\ \ \ i=1,2,\dots,k\\ &h_j(x) = 0,\ \ j=1,2,\dots, l \end{aligned} x∈Rnmin s.t. f(x)ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l 我们称这个约束最优化问题为原始问题.
根据高等数学的相关知识可知，对于约束最优化的最常用解法是采用拉格朗日乘数法，将其转化为无约束的函数进而求其最值.
因此我们引入广义拉格朗日函数(generalized Lagrange function)： L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x) L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k\alpha_ic_i(x) + \sum_{j=1}^l \beta_jh_j(x)L(x,α,β)=f(x)+i=1∑kαici(x)+j=1∑lβjhj(x)
其中，αi,βj\alpha_i,\beta_jαi,βj是拉格朗日乘子，αi≥0\alpha_i \geq 0αi≥0，我们有如下关于xxx的函数： (1.1)θP(x)=maxα,β:αi≥0 L(x,α,β)\theta_P(x) = \max_{\alpha,\beta:\alpha_i\geq 0}\ L(x, \alpha, \beta)\tag{1.1}θP(x)=α,β:αi≥0max L(x,α,β)(1.1) 下标PPP表示原始问题.
假设给定某个xxx，若xxx违反原始问题的约束条件，即存在某个iii使得ci(w)>0c_i(w)>0ci(w)>0或者存在某个jjj使得hj(x)≠0h_j(x)\neq 0hj(x)̸=0，那么有
θP(x)=maxα,β:αi≥0[f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)]=+∞ \theta_P(x) = \max_{\alpha,\beta:\alpha_i\geq 0} \Big[f(x) + \sum_{i=1}^k\alpha_ic_i(x) + \sum_{j=1}^l \beta_jh_j(x)\Big] = + \infty θP(x)=α,β:αi≥0max[f(x)+i=1∑kαici(x)+j=1∑lβjhj(x)]=+∞
若某个iii使得约束ci(x)>0c_i(x)>0ci(x)>0，则令αi→+∞\alpha_i\rightarrow + \inftyαi→+∞，若存在某个hj(x)=0h_j(x)=0hj(x)=0，则令βjh(x)→+∞\beta_jh_(x)\rightarrow + \inftyβjh(x)→+∞.
我们可以这样理解，拉格朗日函数相当于构造了一个含参函数，在满足约束条件的情况下，这个函数的值总是小于等于目标函数f(x)f(x)f(x). 而我们此时选取合适的参数α、β\alpha、\betaα、β令该函数最大可使等号成立，即令L(x,α,β)=f(x)L(x,\alpha,\beta) = f(x)L(x,α,β)=f(x)；若不满足约束条件，则总存在α、β\alpha、\betaα、β使得该函数趋向于+∞+\infty+∞.
这里的max\maxmax就是选取参数α、β\alpha、\betaα、β的过程.
即 θP(x)={f(x),x满足原始问题约束+∞,其他 \theta_P(x) = \begin{cases} f(x),&x满足原始问题约束\\ +\infty, &其他 \end{cases} θP(x)={f(x),+∞,x满足原始问题约束其他
至此，我们用一个无约束的函数替代了原来的约束项，接下来我们进一步考虑求解目标函数f(x)f(x)f(x)的最小化.
根据之前的理解，我们很容易得出，求解f(x)f(x)f(x)的最小化等价于求解θP(x)\theta_P(x)θP(x)最小化： (1.2)minxθP(x)=minxmaxα,β:αi≥0L(x,α,β) \min_x \theta_P(x) = \min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta)\tag{1.2} xminθP(x)=xminα,β:αi≥0maxL(x,α,β)(1.2)
我们将 (1.3)minxmaxα,β:αi≥0L(x,α,β)\min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta)\tag{1.3}xminα,β:αi≥0maxL(x,α,β)(1.3) 称为广义拉格朗日函数的极小极大问题. 我们定义原始问题的最优值 (1.4)p∗=minxθP(x)p^* = \min_x\theta_P(x)\tag{1.4}p∗=xminθP(x)(1.4) 称为原始问题的值.
对偶问题
定义α、β\alpha、\betaα、β的函数： (2.1)θD(α,β)=minxL(x,α,β)\theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta)\tag{2.1}θD(α,β)=xminL(x,α,β)(2.1) 再考虑极大化θD(α,β)\theta_D(\alpha, \beta)θD(α,β)，即 (2.2)maxα,β:αi≥0θD(α,β)=maxα,β:αi≥0minxL(x,α,β) \max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\geq 0} \min_x L(x,\alpha,\beta)\tag{2.2} α,β:αi≥0maxθD(α,β)=α,β:αi≥0maxxminL(x,α,β)(2.2) 我们将 (2.4)maxα,β:αi≥0minxL(x,α,β) \max_{\alpha,\beta:\alpha_i\geq 0} \min_x L(x,\alpha,\beta)\tag{2.4} α,β:αi≥0maxxminL(x,α,β)(2.4) 称为广义拉格朗日函数的极大极小问题.
将广义拉格朗日函数的极大极小问题表示为约束最优化问题： (2.5)maxα,βθD(α,β)=maxα,βminxL(x,α,β)s.t. αi≥0, i=1,2…,k \begin{aligned} &\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{\alpha,\beta} \min_x L(x,\alpha,\beta)\tag{2.5}\\ &s.t.\ \ \ \ \alpha_i\geq0,\ \ \ i=1,2\dots,k \end{aligned} α,βmaxθD(α,β)=α,βmaxxminL(x,α,β)s.t. αi≥0, i=1,2…,k(2.5) 称为原始问题的对偶问题.
原始问题如下： minxθP(x)=minxmaxα,β:αi≥0L(x,α,β) \min_x \theta_P(x) = \min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta) xminθP(x)=xminα,β:αi≥0maxL(x,α,β)
定义对偶问题的最优值： (2.6)d∗=maxα,β:αi≥0θD(α,β)d^* = \max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\tag{2.6}d∗=α,β:αi≥0maxθD(α,β)(2.6)
原始问题与对偶问题的关系
(1)若原始问题和对偶问题都有最优值， 对于式(1.1)(2.1)(1.1)(2.1)(1.1)(2.1)，对于任意α、β、x\alpha、\beta、xα、β、x，我们有 θD(α,β)=minxL(x,α,β)≤L(x,α,β)≤maxα,β:αi≥0 L(x,α,β)=θP(x) \theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta)\leq L(x,\alpha,\beta)\leq \max_{\alpha,\beta:\alpha_i\geq 0}\ L(x, \alpha, \beta) =\theta_P(x) θD(α,β)=xminL(x,α,β)≤L(x,α,β)≤α,β:αi≥0max L(x,α,β)=θP(x) 即 θD(α,β)≤θP(x)\theta_D(\alpha,\beta)\leq \theta_P(x)θD(α,β)≤θP(x) 且原始问题和对偶问题都有最优值，所以 maxα,β:αi≥0θD(α,β)≤minxθP(x)\max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta)\leq \min_x\theta_P(x)α,β:αi≥0maxθD(α,β)≤xminθP(x) 即 d∗=maxα,β:αi≥0θD(α,β)≤minxθP(x)=p∗ d^* = \max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta)\leq \min_x\theta_P(x) = p^* d∗=α,β:αi≥0maxθD(α,β)≤xminθP(x)=p∗ 对偶问题的最优值应当小于等于原始问题的最优值.
在某些条件下，会出现两者的最优值相等d∗=p∗d^* = p^*d∗=p∗，此时我们就可以用对偶问题替代原始问题，而此时的x∗,α∗、β∗x^*,\alpha^*、\beta^*x∗,α∗、β∗分别是原始问题和对偶问题的最优解.
(2)我们给出如下
定理(充分条件)
对于原始问题 minx∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l \begin{aligned} \min_{x\in R^n}\ \ \ \ &f(x)\\ s.t.\ \ \ \ &c_i(x)\leq 0,\ \ \ i=1,2,\dots,k\\ &h_j(x) = 0,\ \ j=1,2,\dots, l \end{aligned} x∈Rnmin s.t. f(x)ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l 和对偶问题 maxα,βθD(α,β)=maxα,βminxL(x,α,β)s.t. αi≥0, i=1,2…,k \begin{aligned} &\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{\alpha,\beta} \min_x L(x,\alpha,\beta)\\ &s.t.\ \ \ \ \alpha_i\geq0,\ \ \ i=1,2\dots,k \end{aligned} α,βmaxθD(α,β)=α,βmaxxminL(x,α,β)s.t. αi≥0, i=1,2…,k 假设f(x)、ci(x)f(x)、c_i(x)f(x)、ci(x)是凸函数，hj(x)h_j(x)hj(x)是仿射函数，并且假设不等式约束ci(x)c_i(x)ci(x)是严格可行的，即存在xxx，使得所有的ci(x)<0c_i(x)<0ci(x)<0，
则存在x∗,α∗,β∗x^*,\alpha^*,\beta^*x∗,α∗,β∗使得x∗x^*x∗是原始问题的解，α∗,β∗\alpha^*,\beta^*α∗,β∗是对偶问题的解，且 p∗=d∗=L(x∗,α∗,β∗)p^*=d^* = L(x^*,\alpha^*,\beta^*)p∗=d∗=L(x∗,α∗,β∗)
KKT
如上给出的是求解的充分条件，通常情况下，我们求解问题时，只需要满足假设，即可通过该方法将原始问题转化为对偶问题求解.
对于给定假设，x∗,α∗、β∗x^*,\alpha^*、\beta^*x∗,α∗、β∗分别是原始问题和对偶问题的解的必要条件是，x∗,α∗,β∗x^*,\alpha^*,\beta^*x∗,α∗,β∗满足 Karush-Kuhn-Tucker(KKT) 条件: ΔxL(x∗,α∗,β∗)=0ΔαL(x∗,α∗,β∗)=0ΔβL(x∗,α∗,β∗)=0αi∗ci(x∗)=0,i=1,2,…,kci(x∗)≤0,i=1,2,…,kαi≥0,i=1,2,…,khj(x∗)=0,i=1,2,…,l \Delta_xL(x^*,\alpha^*,\beta^*) = 0\\ \Delta_{\alpha}L(x^*,\alpha^*,\beta^*) = 0\\ \Delta_{\beta}L(x^*,\alpha^*,\beta^*) = 0\\ \alpha_i^*c_i(x^*) = 0, i=1,2,\dots,k\\ c_i(x^*) \leq 0, i=1,2,\dots,k\\ \alpha_i \geq 0, i=1,2,\dots,k\\ h_j(x^*) = 0, i=1,2,\dots,l\\ ΔxL(x∗,α∗,β∗)=0ΔαL(x∗,α∗,β∗)=0ΔβL(x∗,α∗,β∗)=0αi∗ci(x∗)=0,i=1,2,…,kci(x∗)≤0,i=1,2,…,kαi≥0,i=1,2,…,khj(x∗)=0,i=1,2,…,l 其中αi∗ci(x∗)=0\alpha_i^*c_i(x^*) = 0αi∗ci(x∗)=0称为KKt的对偶互补体哦阿健，由此条件可知：若α∗>0\alpha^* > 0α∗>0，则ci(x∗)=0c_i(x^*) = 0ci(x∗)=0.
参考资料
李航《统计学习方法》