原始问题

假设 $f(x),g(x)$ 是定义在 $R^n$ 上的连续可微函数，原始问题如下所示：

$\underset{x}{min}f(x)\ \ s.t. g(x)\leq0 \ \ (1)$

引进广义拉格朗日函数

$L(x,\lambda) = f(x) +\lambda g(x)\ \ \lambda\geq0 \ \ (2)$

那么原始问题等价于如下问题

$\underset{x}{min}\ \underset{\lambda:\lambda\geq0}{max}L(x,\lambda)\ \ (3)$

即

$\underset{x}{min}f(x) \ \ s.t. \ \ g(x)\leq0 \Leftrightarrow \underset{x}{min}\ \underset{\lambda:\lambda\geq0}{max}L(x,\lambda) \ \ (4)$

这是因为如果约束条件不满足，即 $g(x)\geq0$ , 那么总可以找到一个 $\lambda$ 使得 $L(x,\lambda)\geq f(x)$ ,即

$\underset{\lambda:\lambda\geq0}{max}L(x,\lambda)\geq f(x)$

在这种情况下，式(4)成立；如果 $g(x)\leq 0$ , $L(x,\lambda) = f(x)$ ,式(4)同样成立。通过式(4)将原来的极小问题，转化为广义拉格朗日的极小极大问题。我们定义原始问题的最优值为原始问题的值。

$p^* = \underset{x}{min}\ \underset{\lambda:\lambda\geq 0 }{max}L(x, \lambda) \ \ (5)$

对偶问题

将原始问题极小极大顺序互换后的极大极小问题称为原始问题的对偶问题,如下所示

$\underset{\lambda:\lambda\geq 0}{max}\ \underset{x}{min}\ L(x, \lambda) \ \ (6)$

定义对偶问题的最优值为对偶问题的值。

$d^* = \underset{\lambda:\lambda\geq 0}{max}\ \underset{x}{min}\ L(x, \lambda) \ \ (7)$

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

假设函数 $f(x)$ 是凸函数，并且不等式

是严格可行的，则 $x^*,\lambda^*$ 分别是原始问题和对偶问题的解的充分必要条件是以下的Karush-Kuhn-Tucker(KKT)条件成立：

$\nabla_xL(x^*, \lambda^*) = 0$

$\nabla_{\lambda}L(x^*, \lambda^*) = 0$

$\lambda^*g(x^*) = 0$

$g(x^*)= 0" style="background-color:#ffffff;font-family:arial;font-size:15px;line-height:24px;text-indent:30px;$

$\lambda^*\geq 0" style="background-color:#ffffff;font-family:arial;font-size:15px;line-height:24px;text-indent:30px;$

参考文献

1.李航．统计学习方法：清华大学出版社，2012：225-228