拉格朗日对偶性

在最优化问题中常常会用到拉格朗日对偶性将原始问题转化为对偶问题，通过求解对偶问题来求解原始问题，例如最大熵模型、支持向量机等，作为基础支撑知识，在此做一个简单的总结描述

原始问题

假设f(x),ci(x),hj(x)f(x),c_i(x),h_j(x)是定义在RnR^n上连续可微函数，最优化问题

min⁡x∈Rnf(x)s.tcj≤0,i=1,2,⋯ ,khj(x)=0,j=1,2,⋯ ,l(1)\begin{aligned} \min_{x\in R^n}\quad f(x) \\ s.t \quad c_j\leq0,\quad i=1,2,\cdots,k \\ h_j(x)=0,\quad j= 1,2,\cdots,l \tag{1} \end{aligned}

引入广义拉格朗日函数

L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)L(x,\alpha,\beta)=f(x)+\sum^k_{i=1}\alpha_ic_i(x)+\sum^l_{j=1}\beta_jh_j(x)

其中，αi,βj\alpha_i,\beta_j是拉格朗日乘子，αi≥0\alpha_i\geq 0,考虑xx的函数：

θp(x)=max⁡α,β:αi≥0L(x,α,β)\theta_p(x)\quad=\max_{\alpha,\beta:\alpha_i\geq0}\quad L(x,\alpha,\beta)

这里，下表P表示原始问题；假设给定某个x，如果违反原始问题的约束条件，就有

θp(x)=max⁡α,β:αi≥0L(x,α,β)=+∞\theta_p(x)\quad=\max_{\alpha,\beta:\alpha_i\geq0}\quad L(x,\alpha,\beta)=+\infty

因为若某个i使约束ci(x)>0c_i(x)>0,则可令αi→+∞\alpha_i\rightarrow+\infty,若某个j使hj(x)≠0h_j(x)\neq 0则可令βi→+∞\beta_i\rightarrow+\infty,而将其余的αi,βi\alpha_i,\beta_i均设为0；因此

θp(x)={f(x),x满足原始问题约束+∞,其他\begin{aligned} \theta_p(x)=\begin{cases} f(x),x\text{满足原始问题约束} +\infty,\text{其他} \end{cases} \end{aligned}

因此考虑极小化问题

min⁡xθp(x)=min⁡x max⁡α,β:αi≥0 L(x,α,β)\min_x\theta_p(x)=\min_x\,\max_{\alpha,\beta:\alpha_i\geq0}\,L(x,\alpha,\beta)

他和（1）是等价的；问题min⁡x max⁡α,β:αi≥0 L(x,α,β)\min_x\,\max_{\alpha,\beta:\alpha_i\geq0}\,L(x,\alpha,\beta)称为广义拉格朗日函数的极小极大问题，这样就把原始最优化问题表示为广义拉格朗日函数的极小极大值问题。为了方便定义原始问题的最优解

p∗=min⁡xθp(x)p^*=\min_x\theta_p(x)

称为原始问题的值；

对偶问题

定义

θD(α,β)=min⁡xL(x,α,β)\theta_D(\alpha,\beta) = \min_xL(x,\alpha,\beta)

再考虑极大化θD(α,β)\theta_D(\alpha,\beta),即

max⁡α,β:α≥0θD(α,β)=max⁡α,β:α≥0min⁡xL(x,α,β)\max_{\alpha,\beta:\alpha\geq0}\theta_D(\alpha,\beta)= \max_{\alpha,\beta:\alpha\geq0}\min_xL(x,\alpha,\beta)

称为广义拉格朗日函数的极大极小问题；

于是广义拉格朗日函数的极大极小问题表示为约束优化问题：

max⁡α,β:α≥0θD(α,β)=max⁡α,β:α≥0min⁡xL(x,α,β)s.t.αi≥0,i=1,2,⋯ ,k\begin{aligned} \max_{\alpha,\beta:\alpha\geq0}\theta_D(\alpha,\beta)= \max_{\alpha,\beta:\alpha\geq0}\min_xL(x,\alpha,\beta) \\ & s.t. \alpha_i\geq0,i=1,2,\cdots,k \\ \end{aligned}

称为原始问题的对偶问题，定义对偶问题最优值

d∗=max⁡α,β:α≥0θD(α,β)d^*=\max_{\alpha,\beta:\alpha\geq0}\theta_D(\alpha,\beta)

称为对偶问题的值；

原始问题和对偶问题的关系

  • 若原始问题和对偶问题都有最优解，则d∗≤p∗d^*\leq p^*；

    • 推论：设x∗,α∗,β∗x^*,\alpha^*,\beta^*分别为原始问题和对偶问题的可行解，并且d∗=p∗d^*=p^*,则x∗,α∗,β∗x^*,\alpha^*,\beta^*分别是原始问题和对偶问题的最优解；

  • 假设f(x),ci(x)f(x),c_i(x)是凸函数，hj(x)h_j(x)是仿射函数；并且假设不等式约束ci(x)c_i(x)是严格可行的(存在x，对所有的i有ci(x)≤0c_i{(x)}\leq0),则存在x∗,α∗,β∗x^*,\alpha^*,\beta^*,使x∗x^*是原始问题的解，α∗,β∗\alpha^*,\beta^*是对偶问题的解，且

    p∗=d∗=L(x∗,α∗,β∗)p^*=d^*=L(x^*,\alpha^*,\beta^*)

  • 假设f(x),ci(x)f(x),c_i(x)是凸函数，hj(x)h_j(x)是仿射函数；并且假设不等式约束ci(x)c_i(x)是严格可行的,则存在x∗,α∗,β∗x^*,\alpha^*,\beta^*分别是原始问题和对偶问题的解的充分必要条件是x∗,α∗,β∗x^*,\alpha^*,\beta^*满足下面的（KKT）条件：

特别指出，式（c.22）称为KKT的对偶互补条件，由此条件可知：若$a_i^*>0$,则$c_i(x^*)=0$;