拉格朗日对偶性

导言

拉格朗日对偶性尝尝用于带约束的最优化问题。这个原理的简化版本在高中数学中就出现过,当时称作拉格朗日乘数法。先回顾一下拉格朗日乘数法的基本形式:
$$
\min\limits_{x}f(x)=0\quad s.t.\quad g(x)=0
$$
找到$x$使得$f(x)$最小,且满足$g(x)=0$。我们引入拉格朗日乘子构造新的函数:
$$
L(x,\lambda) = f(x) + \lambda g(x)
$$
接着令两个偏导数为0
$$
\left\lbrace
\begin{align}
\frac{\partial L}{\partial x} &=0 \newline
\frac{\partial L}{\partial \lambda} &= 0
\end{align}
\right.
$$
求解出$x$和$\lambda$即可。
事实上,最后这一步求导然后另其等于0叫做KKT(Karush-Kuhn-Tucker)条件,当然完整的版本更加复杂一些。在本文中依然不会证明KKT条件,所以想要了解这样做的依据是什么的小伙伴们可能要失望了。不过接下来,我将展开说明更为普适的拉格朗日对偶性。

拉格朗日对偶性

原始问题

$$
\begin{align}
\min\limits_{x \in \textbf{R^n}} f(x) & \newline
s.t. c_i(x) & \leqslant 0, i=1,2,\ldots,k\newline
h_j(x) & =0, j=1,2,\ldots,l
\end{align}
$$

广义拉格朗日函数

$$
L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)
$$
$\alpha_i$和$\beta_j$是拉格朗日乘子,规定$\alpha_i \geqslant 0$(为什么会这样规定,下面会解释)。
构造一个函数
$$
\theta_P(x) = \max\limits_{\alpha,\beta:\alpha_i \geqslant 0}L(x,\alpha,\beta)
$$
下标$P$表示原始问题。
可以看出,如果$x$违反原始问题的某个约束条件,即存在某个$i$使得$c_i(w)>0$或者存在某个$j$使得$h_j(w) \neq 0$,那么就有
$$
\theta_P(x) = + \infty
$$
因为存在$c_i(x)>0$的话,可另对应的$\alpha_i \rightarrow +\infty$(这里就说明了为什么规定$\alpha_i \geqslant 0$,因为不作此规定的话,即使满足$c_i(x)<0$的条件,也可以取$\alpha_i \rightarrow -\infty$从而让整个$\theta_P = +\infty$);存在$h_j(x) \neq 0$的话,可令对应的$\beta_jh_j(x)->+\infty$,最后让其余所有$\alpha_i$,$\beta_j$取0。
如果满足所有约束,则$\theta_P(x)=f(x)$
所以有
$$
\theta_P(x)=
\begin{cases}
f(x), & x满足原始问题约束 \newline
+\infty, & 其他
\end{cases}
$$
与最初的原始问题等价的形式就是:
$$
\min\limits_x \theta_P(x) = \min\limits_x \max\limits_{\alpha, \beta: \alpha_i \geqslant 0}L(x, \alpha, \beta)
$$

$$
p^* = \min\limits_x\theta_P(x)
$$
称为原始问题的值。

对偶问题

定义
$$
\theta_D(\alpha, \beta) = \min\limits_xL(x, \alpha, \beta)
$$
定义对偶问题的最优值
$$
d^* = \max\limits_{\alpha, \beta: \alpha_i \geqslant 0} \theta_D(\alpha, \beta)
$$

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

$$
d^* \leqslant p^* $$

KKT条件

$$
\begin{align}
\nabla_xL(x, \alpha, \beta) & = 0 \newline
\nabla_\alpha L(x, \alpha, \beta) & = 0 \newline
\nabla_\alpha L(x, \alpha, \beta) & = 0 \newline
\alpha_i c_i(x) &= 0, i=1,2,\ldots,k \newline
c_i(x) & \leqslant 0, i=1,2,\ldots,k \newline
\alpha_i & \geqslant 0, i=1,2,\ldots,k \newline
h_j(x) &= 0, j=1,2,\ldots,l
\end{align}
$$

KKT条件给出了求解的方法。其中,上面第4条式子称为KKT的对偶互补条件。由此条件克制:若$\alpha_i$>0,则$c_i(x)=0$。

标签: none

添加新评论