拉格朗日对偶性

拉格朗日对偶性

在机器学习中，我们经常会遇到给定某些约束条件求解某个函数最大值或最小值的情况，称之为约束最优化，通常的做法是利用拉格朗日对偶性将原始问题转化为对偶问题，通过解对偶问题进而得到原始问题的解. 在机器学习的很多方法中都有用到此方法，如最大熵模型和SVM.

原始问题

我们假设f(x),ci(x),h(x)f(x),c_i(x),h_(x)f(x),ci​(x),h(​x)是定义在RnR^nRn上的连续可微函数，考虑如下约束最优化问题：

对于最优化问题我们通常转化为求min min⁡x∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l begin{aligned} min_{xin 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}^kalpha_ic_i(x) sum_{j=1}^l beta_jh_j(x)L(x,α,β)=f(x) i=1∑k​αi​ci​(x) j=1∑l​βj​hj​(x)

其中，αi,βjalpha_i,beta_jαi​,βj​是拉格朗日乘子，αi≥0alpha_i geq 0αi​≥0，我们有如下关于xxx的函数： (1.1)θP(x)=max⁡α,β:αi≥0 L(x,α,β)theta_P(x) = max_{alpha,beta:alpha_igeq 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_igeq 0} Big[f(x) sum_{i=1}^kalpha_ic_i(x) sum_{j=1}^l beta_jh_j(x)Big] = infty θP​(x)=α,β:αi​≥0max​[f(x) i=1∑k​αi​ci​(x) j=1∑l​βj​hj​(x)]= ∞

若某个iii使得约束ci(x)>0c_i(x)>0ci​(x)>0，则令αi→ ∞alpha_irightarrow inftyαi​→ ∞，若存在某个hj(x)=0h_j(x)=0hj​(x)=0，则令βjh(x)→ ∞beta_jh_(x)rightarrow inftyβj​h(​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)min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β) min_x theta_P(x) = min_x max_{alpha,beta:alpha_igeq 0}L(x,alpha,beta)tag{1.2} xmin​θP​(x)=xmin​α,β:αi​≥0max​L(x,α,β)(1.2)

我们将 (1.3)min⁡xmax⁡α,β:αi≥0L(x,α,β)min_x max_{alpha,beta:alpha_igeq 0}L(x,alpha,beta)tag{1.3}xmin​α,β:αi​≥0max​L(x,α,β)(1.3) 称为广义拉格朗日函数的极小极大问题. 我们定义原始问题的最优值 (1.4)p∗=min⁡xθP(x)p^* = min_xtheta_P(x)tag{1.4}p∗=xmin​θP​(x)(1.4) 称为原始问题的值.

对偶问题

定义α、βalpha、betaα、β的函数： (2.1)θD(α,β)=min⁡xL(x,α,β)theta_D(alpha,beta) = min_xL(x, alpha,beta)tag{2.1}θD​(α,β)=xmin​L(x,α,β)(2.1) 再考虑极大化θD(α,β)theta_D(alpha, beta)θD​(α,β)，即 (2.2)max⁡α,β:αi≥0θD(α,β)=max⁡α,β:αi≥0min⁡xL(x,α,β) max_{alpha,beta:alpha_igeq 0}theta_D(alpha,beta) = max_{alpha,beta:alpha_igeq 0} min_x L(x,alpha,beta)tag{2.2} α,β:αi​≥0max​θD​(α,β)=α,β:αi​≥0max​xmin​L(x,α,β)(2.2) 我们将 (2.4)max⁡α,β:αi≥0min⁡xL(x,α,β) max_{alpha,beta:alpha_igeq 0} min_x L(x,alpha,beta)tag{2.4} α,β:αi​≥0max​xmin​L(x,α,β)(2.4) 称为广义拉格朗日函数的极大极小问题.

将广义拉格朗日函数的极大极小问题表示为约束最优化问题： (2.5)max⁡α,βθD(α,β)=max⁡α,βmin⁡xL(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_igeq0, i=1,2dots,k end{aligned} ​α,βmax​θD​(α,β)=α,βmax​xmin​L(x,α,β)s.t. αi​≥0, i=1,2…,k​(2.5) 称为原始问题的对偶问题.

原始问题如下： min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β) min_x theta_P(x) = min_x max_{alpha,beta:alpha_igeq 0}L(x,alpha,beta) xmin​θP​(x)=xmin​α,β:αi​≥0max​L(x,α,β)

定义对偶问题的最优值： (2.6)d∗=max⁡α,β:αi≥0θD(α,β)d^* = max_{alpha,beta:alpha_igeq0}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)，对于任意α、β、xalpha、beta、xα、β、x，我们有 θD(α,β)=min⁡xL(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_igeq 0} L(x, alpha, beta) =theta_P(x) θD​(α,β)=xmin​L(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(α,β)≤min⁡xθP(x)max_{alpha,beta:alpha_igeq 0}theta_D(alpha,beta)leq min_xtheta_P(x)α,β:αi​≥0max​θD​(α,β)≤xmin​θP​(x) 即 d∗=max⁡α,β:αi≥0θD(α,β)≤min⁡xθP(x)=p∗ d^* = max_{alpha,beta:alpha_igeq 0}theta_D(alpha,beta)leq min_xtheta_P(x) = p^* d∗=α,β:αi​≥0max​θD​(α,β)≤xmin​θP​(x)=p∗ 对偶问题的最优值应当小于等于原始问题的最优值.

在某些条件下，会出现两者的最优值相等d∗=p∗d^* = p^*d∗=p∗，此时我们就可以用对偶问题替代原始问题，而此时的x∗,α∗、β∗x^*,alpha^*、beta^*x∗,α∗、β∗分别是原始问题和对偶问题的最优解.

(2)我们给出如下

定理(充分条件)

对于原始问题 min⁡x∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l begin{aligned} min_{xin R^n} &amp;f(x)\ s.t. &amp;c_i(x)leq 0, i=1,2,dots,k\ &amp;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⁡α,βmin⁡xL(x,α,β)s.t. αi≥0, i=1,2…,k begin{aligned} &amp;max_{alpha,beta}theta_D(alpha,beta) = max_{alpha,beta} min_x L(x,alpha,beta)\ &amp;s.t. alpha_igeq0, i=1,2dots,k end{aligned} ​α,βmax​θD​(α,β)=α,βmax​xmin​L(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)&lt;0c_i(x)&lt;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\ Δx​L(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∗)=0alpha_i^*c_i(x^*) = 0αi∗​ci​(x∗)=0称为KKt的对偶互补体哦阿健，由此条件可知：若α∗&gt;0alpha^* &gt; 0α∗>0，则ci(x∗)=0c_i(x^*) = 0ci​(x∗)=0.

参考资料

李航《统计学习方法》