拉格朗日对偶性
本文为学习《统计学习方法》一书的学习笔记。
前言
在有约束的最优化问题中，我们可以利用拉格朗日乘子将有约束的最优化问题转化为无约束的最优化问题，之后找到无约束的最优化问题的对偶问题，通过解对偶问题而得到原始问题的解。
原始问题
如下就是一个有约束的最优化问题，$f(x), \ c_i(x), \ h_j(x)$是定义在$R^n$上的连续可微函数：
\begin{align} & \min_x \ f(x) \\ & s.t. \ c_i(x) \le 0, \ i=1,2,...,k \\ & \ \ \ \ \ \ \ h_j(x)=0, \ j=1,2,...,l \end{align}
定义拉格朗日函数，其中$\alpha_i, \beta_j$是拉格朗日乘子，$\alpha_i \ge 0$： $$ L(x, \alpha, \beta)=f(x)+\sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x) $$
显然我们可以得到如下结论： $$ \max_{\alpha, \beta; \alpha_i \ge 0}L(x, \alpha, \beta)=f(x) $$
所以原始优化问题变为如下优化问题： $$ \min_x \ f(x) = \min_x\max_{\alpha, \beta;\alpha_i \ge 0}L(x, \alpha, \beta) $$
通过引入拉格朗日乘子，我们成功的把有约束的最优化问题转化为无约束的最优化问题，我们定义原始问题的最优值： $$ p^*=\min_x \ f(x) = \min_x\max_{\alpha, \beta;\alpha_i \ge 0}L(x, \alpha, \beta) $$
对偶问题
我们定义对偶函数： $$ D(\alpha, \beta) = \min_xL(x, \alpha, \beta) $$
则对偶问题如下： $$ \max_{\alpha, \beta;\alpha_i \ge 0}D(\alpha, \beta)=\max_{\alpha, \beta;\alpha_i \ge 0}\min_xL(x, \alpha, \beta) $$
我们定义对偶问题的最优值： $$ d^*=\max_{\alpha, \beta;\alpha_i \ge 0}D(\alpha, \beta)=\max_{\alpha, \beta;\alpha_i \ge 0}\min_xL(x, \alpha, \beta) $$
因为： $$ D(\alpha, \beta) = \min_xL(x, \alpha, \beta) \le L(x, \alpha, \beta) $$
又因为： $$ L(x, \alpha, \beta) \le \max_{\alpha, \beta;\alpha_i \ge 0}L(x, \alpha, \beta) $$
所以： $$ D(\alpha, \beta) = \min_xL(x, \alpha, \beta) \le \max_{\alpha, \beta;\alpha_i \ge 0}L(x, \alpha, \beta) $$
所以： $$ \max_{\alpha, \beta;\alpha_i \ge 0}\min_xL(x, \alpha, \beta) \le \min_x\max_{\alpha, \beta;\alpha_i \ge 0}L(x, \alpha, \beta) $$
我们可以得到如下结论（可以简单理解为最小值中的最大值一定小于等于最大值中的最小值）： $$ d^* \le p^* $$
在某些条件下，原始问题和对偶问题的最优值相等，$d^* = p^*$，这时可用解对偶问题替代原始问题。
如果函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的（即存在$x$，对所有$i$有$c_i(x)<0$），则存在$x^*, \alpha^*, \beta^*$，使$x^*$是原始问题的解，$\alpha^*, \beta^*$是对偶问题的解，并且
$$ p^*=d^*=L(x^*, \alpha^*, \beta^*) $$
KKT条件
如果函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的（即存在$x$，对所有$i$有$c_i(x)<0$），则$x^*, \alpha^*, \beta^*$分别是原始问题和对偶问题的解的充分必要条件是$x^*, \alpha^*, \beta^*$满足下面的KKT条件：
\begin{align} & \nabla_x L(x^*, \alpha^*, \beta^*) = 0 \\ & \nabla_\alpha L(x^*, \alpha^*, \beta^*) = 0 \\ & \nabla_\beta L(x^*, \alpha^*, \beta^*) = 0 \\ & \alpha_i^* c_i(x^*)=0, \ \ \ i=1,2,...,k \\ & c_i(x^*) \le 0, \ \ \ i=1,2,...,k \\ & \alpha_i^* \ge 0, \ \ \ i=1,2,...,k \\ & h_j(x^*)=0, \ \ \ j=1,2,...,l \end{align}
还没有人评论...