拉格朗日对偶性(Lagrance duality) 推导与简单理解

引言在支持向量机和最大熵模型中都会用到拉格朗日对偶性，主要为解决约束最优化问题，通过将原始问题转换为对偶问题求解。为方便理解，遂记录下简单的概念的结论，有理解不当的地方望多提意见~1. 原始问题先从最简单的求函数最小值开始说起：minx∈Rnf(x)\min_{\boldsymbol{x} \in \mathbf{R}^n}f(\boldsymbol{x})求f(x)f

小鹅鹅

19085人浏览 · 2018-01-24 16:34:26

小鹅鹅 · 2018-01-24 16:34:26 发布

引言

在支持向量机和最大熵模型中都会用到拉格朗日对偶性，主要为解决约束最优化问题，通过将原始问题转换为对偶问题求解。为方便理解，遂记录下简单的概念的结论，有理解不当的地方望多提意见~

1. 原始问题

先从最简单的求函数最小值开始说起：

min x \in R n f (x)

求 f(x) <script type="math/tex" id="MathJax-Element-75">f(x)</script>的最小值时 x <script type="math/tex" id="MathJax-Element-76">x</script>的取值，f(x)<script type="math/tex" id="MathJax-Element-77">f(x)</script>在 Rn <script type="math/tex" id="MathJax-Element-78">R^n</script>上连续可微。这时候我们对 f(x) <script type="math/tex" id="MathJax-Element-79">f(x)</script>求导令导数为0就能取到极值了。若此时加入约束如下：

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

其中 f(x),ci(x),hj(x)在Rn <script type="math/tex" id="MathJax-Element-82">f(x),c_i(x),h_j(x)在R^n</script>上连续可微我们称此约束最优化为原始问题，也是拉格朗日对偶性需要解决的问题。
此时我们直接求导是无法解决了，要是可以将约束条件转换为未知变量或许就可以找到答案了。

2. 拉格朗日函数

为了求解原始问题，我们首先引入广义拉格朗日函数(generalized Lagrange function)：

L (x, α, β) = f (x) + \sum i = 1 k α i c i (x) + \sum j = 1 l β j h j (x)

x=(x1,x2,⋯,xn)T∈Rn <script type="math/tex" id="MathJax-Element-84">\boldsymbol{x}=(x_1,x_2,\cdots,x_n)^T \in \mathbf{R}^n</script>，

αi和βj <script type="math/tex" id="MathJax-Element-85">\alpha_i和\beta _j</script>是拉格朗日乘子且

αi≥0 <script type="math/tex" id="MathJax-Element-86">\alpha_i\ge 0</script>
拉格朗日函数虽然一眼看去十分复杂，但是其实它是将所有的限定条件加上新引入的变量(拉格朗日乘子)构成了一个新的函数，这样就将限定条件转换为了未知变量。
此时我们考虑

x <script type="math/tex" id="MathJax-Element-87">x</script> 的函数：

θ P (x) = max α, β : α i \geq 0 L (x, α, β)

P <script type="math/tex" id="MathJax-Element-89">P</script>代表原始问题。
可以证明，如果

x<script type="math/tex" id="MathJax-Element-90">x</script>满足原始问题中约束，那么

θ(x)=f(x) <script type="math/tex" id="MathJax-Element-91">\theta(\boldsymbol{x})=f(\boldsymbol{x})</script>如果 x不满足原始问题中的约束(

ci(x)≤0;hj(x)=0 <script type="math/tex" id="MathJax-Element-92">c_i(x)\le 0;h_j(x)=0</script>)，那么

θ(x)=+∞ <script type="math/tex" id="MathJax-Element-93">\theta(\boldsymbol{x})=+\infty</script>，即：

θ P (x) = {f (x), + \infty, x 满 足 原 始 问 题 约 束 其 他

证明：假设某个 x <script type="math/tex" id="MathJax-Element-95">x</script>不满足原始问题的约束条件，即存在某个i<script type="math/tex" id="MathJax-Element-96">i</script>使得 ci(x)>0 <script type="math/tex" id="MathJax-Element-97">c_i(\boldsymbol{x})\gt0</script>或者存在某个 j <script type="math/tex" id="MathJax-Element-98">j</script>使得hj(x)=0<script type="math/tex" id="MathJax-Element-99">h_j(\boldsymbol{x})=0</script>那么就有：
$θ P (x) = max α, β : α i \geq 0 [f (x) + \sum i = 1 k α i c i (x) + \sum j = 1 l β j h j (x)] = + \infty$ <script type="math/tex; mode=display" id="MathJax-Element-100">\theta_P(\boldsymbol{x})=\max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}\Bigg[f(\boldsymbol{x})+\sum_{i=1}^k \alpha_ic_i(\boldsymbol{x}) + \sum_{j=1}^l\beta_jh_j(\boldsymbol{x})\Bigg]=+\infty</script>
因为若某个 i <script type="math/tex" id="MathJax-Element-101">i</script>使约束ci(x)>0<script type="math/tex" id="MathJax-Element-102">c_i(\boldsymbol{x})\gt0</script>，则可令 αi→+∞ <script type="math/tex" id="MathJax-Element-103">\alpha_i\rightarrow+\infty</script>；
若某个 j <script type="math/tex" id="MathJax-Element-104">j</script>使hj(x)≠0<script type="math/tex" id="MathJax-Element-105">h_j(\boldsymbol{x})\neq0</script>，则可令 βj <script type="math/tex" id="MathJax-Element-106">\beta_j</script>使 βjhj(x)→+∞ <script type="math/tex" id="MathJax-Element-107">\beta_jh_j(\boldsymbol{x})\rightarrow+\infty</script>,而将其余各 αi,βj <script type="math/tex" id="MathJax-Element-108">\alpha_i,\beta_j</script>均取为 0

所以如果考虑极小化问题：

min x θ P (x) = min x max α, β : α i \geq 0 L (x, α, β)

minxmaxα,β:αi≥0L(x,α,β) <script type="math/tex" id="MathJax-Element-110">\min_{\boldsymbol{x}}\max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})</script>称为广义拉格朗日函数的极小极大问题。这样一来，就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。我们定义原始问题最优解：

p * = min x θ P (x)

3. 对偶问题

我们再定义：

θ D (α, β) = min x L (x, α, β)

θD <script type="math/tex" id="MathJax-Element-113">\theta_D</script>，即：

max α, β θ D (α, β) = max α, β min x L (x, α, β)

maxα,βminxL(x,α,β) <script type="math/tex" id="MathJax-Element-115">\max_{\boldsymbol{\alpha,\beta}}\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})</script>为广义拉格朗日函数的极大极小问题( 上一节的是极小极大问题)。这样可以将广义拉格朗日函数的极大极小问题进一步表示为约束最优化问题：

max α, β θ D (α, β) = max α, β min x L (x, α, β) s . t . α i \geq 0, i = 1, 2, \dots, k

d * = max α, β θ D (α, β)

α,β <script type="math/tex" id="MathJax-Element-118">\alpha,\beta</script>，求最优化

x <script type="math/tex" id="MathJax-Element-119">x</script>的解，在确定参数

α,β<script type="math/tex" id="MathJax-Element-120">\alpha,\beta</script>；
原始问题是先固定

x <script type="math/tex" id="MathJax-Element-121">x</script>，求最优化

α,β<script type="math/tex" id="MathJax-Element-122">\alpha,\beta</script>的解，再确定

x <script type="math/tex" id="MathJax-Element-123">x</script>。

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

若原始问题和对偶问题都有最优值，那么

d * = max α, β min x L (x, α, β) \leq min x max α, β : α i \geq 0 L (x, α, β) = p *

证明:
对任意的 x,α,β <script type="math/tex" id="MathJax-Element-402">x,\alpha,\beta</script>有
$min x L (x, α, β) \leq L (x, α, β) \leq max α, β : α i \geq 0 L (x, α, β)$ <script type="math/tex; mode=display" id="MathJax-Element-403">\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})\le L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})\le \max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})</script>
由于原始问题和对偶问题均有最优值，所以：
$min x L (x, α, β) \leq max α, β : α i \geq 0 L (x, α, β)$ <script type="math/tex; mode=display" id="MathJax-Element-404">\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})\le \max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})</script>
即
$d * = max α, β min x L (x, α, β) \leq min x max α, β : α i \geq 0 L (x, α, β) = p *$ <script type="math/tex; mode=display" id="MathJax-Element-405">d^*=\max_{\boldsymbol{\alpha,\beta}}\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})\le\min_{\boldsymbol{x}}\max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})=p^*</script>

也就是说原始问题的最优值不小于对偶问题的最优值，但是我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等，于是可以得出下面的推论：

设 x∗和α∗,β∗ <script type="math/tex" id="MathJax-Element-406">x^*和\alpha^*,\beta^*</script>分别是原始问题和对偶问题的可行解并且 d∗=p∗ <script type="math/tex" id="MathJax-Element-407">d^*=p^*</script>则 x∗和α∗,β∗ <script type="math/tex" id="MathJax-Element-408">x^*和\alpha^*,\beta^*</script>分别是原始问题和对偶问题的最优解。

对偶问题跟原始问题可以看成本来是两个问题，因为优化的顺序不同而会得出两个不一定相关的值（但是 minxmaxyf(x,y)≥maxymaxxf(x,y) <script type="math/tex" id="MathJax-Element-409">\mathop{min}_{x}\mathop{max}_{y}f(x,y) \geq \mathop{max}_{y}\mathop{max}_{x}f(x,y) </script> 还是成立的，直观理解的话高中经常用的二次函数就可以了）。
两者的差值就是duality gap，描述了我用另一种方式刻画问题的时候所造成的误差，强对偶的情况下最优值没有差别。

在最优点处将会满足KKT 条件，但是KKT条件本身并不需要问题满足强对偶。关于KKT条件什么时候不满足，有一种另外的理解是他要求各个函数的梯度张成足够大的空间（因为KKT的最后一条本质上是一个Ax=0的问题）。
所以，当原始问题和对偶问题的最优值相等： d∗=p∗ <script type="math/tex" id="MathJax-Element-410">d^*=p^*</script>时，可以用求解对偶问题来求解原始问题（当然是对偶问题求解比直接求解原始问题简单的情况下），但是到底满足什么样的条件才能使 d∗=p∗ <script type="math/tex" id="MathJax-Element-411">d^*=p^*</script>呢，这就是下面要阐述的 KKT 条件。

5. KTT条件

对原始问题和对偶问题，假设函数 f(x)和ci(x) <script type="math/tex" id="MathJax-Element-134">f(x)和c_i(x)</script>是凸函数, hj(x) <script type="math/tex" id="MathJax-Element-135">h_j(x)</script>为仿射函数，并且不等式约束 ci(x) <script type="math/tex" id="MathJax-Element-136">c_i(x)</script>是严格可行的，则 x∗和α∗,β∗ <script type="math/tex" id="MathJax-Element-137">x^*和\alpha^*,\beta^*</script>分别是原始问题和对偶问题的解的充要条件是 x∗,α∗,β∗ <script type="math/tex" id="MathJax-Element-138">x^*,\alpha^*,\beta^*</script>满足下面的Karush-Kuhn-Tucker(KKT)条件:

∇xL(x∗,α∗,β∗)=0 <script type="math/tex" id="MathJax-Element-139">\nabla_\boldsymbol{x}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0</script>
∇αL(x∗,α∗,β∗)=0 <script type="math/tex" id="MathJax-Element-140">\nabla_\boldsymbol{\alpha}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0</script>
∇βL(x∗,α∗,β∗)=0 <script type="math/tex" id="MathJax-Element-141">\nabla_\boldsymbol{\beta}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0</script>
α∗ici(x∗)=0,i=1,2,⋯,k <script type="math/tex" id="MathJax-Element-142">\alpha_i^*c_i(\boldsymbol{x}^*)=0,\quad i=1,2,\cdots,k</script>
ci(x∗)≤0,i=1,2,⋯,k <script type="math/tex" id="MathJax-Element-143">c_i(\boldsymbol{x}^*)\le0,\quad i=1,2,\cdots,k</script>
α∗i≥0,i=1,2,⋯,k <script type="math/tex" id="MathJax-Element-144">\alpha_i^*\ge0,\quad i=1,2,\cdots,k</script>
hj(x∗)=0,j=1,2,⋯,l <script type="math/tex" id="MathJax-Element-145">h_j(\boldsymbol{x}^*)=0,\quad j=1,2,\cdots,l</script>

关于KKT 条件的理解：前面三个条件是对于各个变量的偏导数为0（这就解释了一开始为什么假设三个函数连续可微，如果不连续可微的话，这里的偏导数存不存在就不能保证），后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。

仿射函数
$f (x) = A x + b$ <script type="math/tex; mode=display" id="MathJax-Element-146">f(\boldsymbol{x})=\boldsymbol{A}\boldsymbol{x}+b</script>
仿射函数就是一个线性函数，其输入是n维向量，参数 A可以是常数，也可以是m×n的矩阵，b可以是常数，也可以是m维的列向量，输出是一个m维的列向量。在几何上，仿射函数是一个线性空间到另一个线性空间的变换。