Feb 18, 2020

拉格朗日对偶性

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

原始问题

假设 $f (x), c_{i} (x), h_{j} (x)$ 是定义在 $R^{n}$ 上连续可微函数，最优化问题

x \in R^{n} min f (x) s . t c_{j} \leq 0, i = 1, 2, \dots, k h_{j} (x) = 0, j = 1, 2, \dots, l (1)

引入广义拉格朗日函数

L (x, α, β) = f (x) + i = 1 \sum k α_{i} c_{i} (x) + j = 1 \sum l β_{j} h_{j} (x)

其中， $α_{i}, β_{j}$ 是拉格朗日乘子， $α_{i} \geq 0$ ,考虑 $x$ 的函数：

θ_{p} (x) = α, β : α_{i} \geq 0 max L (x, α, β)

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

θ_{p} (x) = α, β : α_{i} \geq 0 max L (x, α, β) = + \infty

因为若某个i使约束 $c_{i} (x) > 0$ ,则可令 $α_{i} \to + \infty$ ,若某个j使 $h_{j} (x) \neq = 0$ 则可令 $β_{i} \to + \infty$ ,而将其余的 $α_{i}, β_{i}$ 均设为0；因此

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

因此考虑极小化问题

x min θ_{p} (x) = x min α, β : α_{i} \geq 0 max L (x, α, β)

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

p^{*} = x min θ_{p} (x)

称为原始问题的值；

定义

θ_{D} (α, β) = x min L (x, α, β)

再考虑极大化 $θ_{D} (α, β)$ ,即

α, β : α \geq 0 max θ_{D} (α, β) = α, β : α \geq 0 max x min L (x, α, β)

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

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

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

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

d^{*} = α, β : α \geq 0 max θ_{D} (α, β)

称为对偶问题的值；

若原始问题和对偶问题都有最优解，则 $d^{*} \leq p^{*}$ ；
- 推论：设 $x^{*}, α^{*}, β^{*}$ 分别为原始问题和对偶问题的可行解，并且 $d^{*} = p^{*}$ ,则 $x^{*}, α^{*}, β^{*}$ 分别是原始问题和对偶问题的最优解；
假设 $f (x), c_{i} (x)$ 是凸函数， $h_{j} (x)$ 是仿射函数；并且假设不等式约束 $c_{i} (x)$ 是严格可行的(存在x，对所有的i有 $c_{i} (x) \leq 0$ ),则存在 $x^{*}, α^{*}, β^{*}$ ,使 $x^{*}$ 是原始问题的解， $α^{*}, β^{*}$ 是对偶问题的解，且
$p^{*} = d^{*} = L (x^{*}, α^{*}, β^{*})$
假设 $f (x), c_{i} (x)$ 是凸函数， $h_{j} (x)$ 是仿射函数；并且假设不等式约束 $c_{i} (x)$ 是严格可行的,则存在 $x^{*}, α^{*}, β^{*}$ 分别是原始问题和对偶问题的解的充分必要条件是 $x^{*}, α^{*}, β^{*}$ 满足下面的（KKT）条件：

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