拉格朗日对偶

首页摘要：

优化问题原问题求解起来往往非常复杂，这个时候需要构建对偶问题来进行求解，如果原问题是凸模型，那么对偶问题的最优解就是原问题的最优解。这篇文章主要介绍拉格朗日对偶方法的来龙去脉。

拉格朗日对偶函数的定义

• 定义

考虑标准优化问题（原问题）：

$$\begin{matrix} minimize & f(x) \hfill \\ subject\ to & h_{i}(x)=0,i=1,2,...m\\ & g_{j}(x)\leq 0,j=1,2,...p\\ \end{matrix}$$

其中，函数$f: R_{n} \rightarrow R $ ，$x \in R^{n}$。那么可以定义拉格朗日函数：

$$L(x,\lambda ,\nu )=f(x)+\sum_{j=1}^{p}\lambda _{j}g_{j}+\sum_{i=1}^{m}\nu _{i}h_{i}$$

进一步，拉格朗日对偶函数可以被定义为：

$$\begin{align*} l(\lambda ,\nu)&= \underset{x \in D}{inf}\; L(x,\lambda ,\nu ) \\ &= \underset{x \in D}{inf}\;f(x)+\sum_{j=1}^{p}\lambda _{j}g_{j}+\sum_{i=1}^{m}\nu _{i}h_{i}\end{align*}$$

这里$inf$ 表示下确界，$D$表示定义域，可以看出$l(\lambda ,\nu)$ 是关于$\lambda ,\nu$ 的仿射函数，也是关于$x$的逐点下确界。既然$l(\lambda ,\nu)$ 是仿射函数，说明无论原问题是否为凸，对偶问题一定为凸。

• 性质

  对偶函数构成了原问题最优解$x^{\star}$的下界，这是因为对于任何$\lambda\geqslant 0$ 、$x \in D$有：

  $$\begin{align*} L(x,\lambda ,\nu )&= f(x)+\sum_{j=1}^{p}\lambda _{j}g_{j}+\sum_{i=1}^{m}\nu _{i}h_{i} \\ &\leq f(x)\end{align*}$$

  上式成立是因为：$\sum_{j=1}^{p}\lambda _{j}g_{j} \leq 0$、$\sum_{i=1}^{m}\nu _{i}h_{i}=0$。所以，

  $$l(\lambda ,\nu)= \underset{x \in D}{inf}\; L(x^{\star},\lambda ,\nu ) \leq L(x^{\star},\lambda ,\nu ) \leq f(x^{\star})$$

弱对偶与强对偶

• 定义

上一节我们得到一个结论就是：$l(\lambda ,\nu) \leq f(x^{\star})$，也就是说，$\underset{\lambda ,\nu}{max}\ l(\lambda ,\nu) \leq f(x^{\star})$ ，这个也称之为对偶问题的最好下界，可以表述成如下优化问题：

$$\begin{matrix}maximize & l(\lambda ,\nu) \hfill\\ subject\ to & \lambda_{j} \geq 0, j=1,2,...,p\end{matrix}$$

这就是原问题的拉格朗日对偶问题，它的最优目标值是$d^{\star}$，且根据前面的结论可以得到$d^{\star} \leq f(x^{\star})$ ，$ f(x^{\star})- d^{\star}$ 称之为对偶间隙。

这里有个有意思的现象是，对偶问题等价于:

$$\underset{\lambda \geq 0 ,\nu}{max}\ \underset{x\in D}{min}\ L(x,\lambda ,\nu )= f(x)+\sum_{j=1}^{p}\lambda _{j}g_{j}+\sum_{i=1}^{m}\nu _{i}h_{i}$$

而原问题可以转化为：

$$f(x^{\star})=\underset{x\in D}{min}\ \underset{\lambda \geq 0 ,\nu}{max}\ L(x,\lambda,\nu )= f(x)+\sum_{j=1}^{p}\lambda _{j}g_{j}+\sum_{i=1}^{m}\nu _{i}h_{i}$$

从上面两个式子可以清楚地看到，其实公式形式上原问题和对偶问题就是对偶的，而正是$min$和$max$两个求优算子的调换造成了对偶间隙，如果原问题是凸的话，这两个求优算子调换之后，原问题和对偶问题的最优值也是相同的。

很自然的想法是，既然对偶问题是凸问题，而且求解也更简单，我们能否根据这个对偶问题的最优目标值来逼近原问题的最优目标值呢？甚至对偶问题的最优目标值就是原问题的最优目标值呢？答案是肯定的。这两种情况分别称之为弱对偶（对偶间隙大于0）和强对偶（对偶间隙等于0）。

• 弱对偶的几何解释

本节我们用一个特殊的几何例子来解释出现弱对偶的原因，强对偶会在下一节进一步用公式来解释。首先构建集合$\Omega =\begin{Bmatrix}
(h_{1}(x),…,h_{m}(x),g_{1}(x)…,g_{p}(x),f(x)) \in R^{m}\times R^{p}\times R | x \in D
\end{Bmatrix}$ ，原问题的最优解可以表示成

$$f(x^{\star})=\begin{Bmatrix}(t|(u,v,t) \in \Omega,u_{j} \leq 0, v_{i}=0\end{Bmatrix}$$

其中，$u$、$v$、$t$分别是不等式约束、等式约束、目标函数的简写符号。拉格朗日函数则可以据此表示成：

$$(\lambda ,\nu,1 )^{T}(u,v,t)= \sum_{j=1}^{p}\lambda _{j}u_{j}+\sum_{i=1}^{m}\nu _{i}v_{i}+t$$

故拉格朗日对偶函数为：

$$l(\lambda ,\nu)=inf\begin{Bmatrix}(\lambda ,\nu,1 )^{T}(u,v,t)|(u,v,t) \in \Omega\end{Bmatrix}$$

即：

$$(\lambda ,\nu,1 )^{T}(u,v,t) \geq l(\lambda ,\nu)$$

这个不等式定义了一个非垂直支撑超平面，之所以称之为非垂直支撑超平面，是因为左项法向量最后一个分量为1.

本节铺垫到此结束，现在基于上述内容用几何解释来说明强对偶。

图1
用只有一个不等式约束的优化问题来说明，可以将集合$\Omega = \{ (h_{1}(x),f(x)|x \in D\}$画在二维平面上，如图1所示，给定$\lambda$，在集合$\Omega$中极小化$(\lambda ,1 )^{T}(u,t)$，得到斜率为$-\lambda$的非垂直支撑超平面。注意只有$u\leq 0$部分（即黄线区域）才是可行域，而$\lambda$必须大于零，所以在$u=0$处取得$l(\lambda ,\nu)=l(\lambda)$的最大值（因为$(\lambda ,\nu,1 )^{T}(u,v,t) \geq l(\lambda ,\nu)$）。橘色直线是不同$\lambda$下$\Omega$的支撑超平面，它们与$t$轴的截距最大值表示拉格朗日对偶函数的最优值，因为$d^{\star}<p^{\star}$，所以是弱对偶。如果原问题是凸函数，一般最优的非垂直超平面都能穿过$p^{\star}$点。

KKT条件

从前面我们可以知道，只要优化问题满足了强对偶要求，那么就找到了优化问题的全局最优解，那么如何公式化表达这个特点呢？基于强对偶的KKT条件可以帮助我们找到和判断全局最优解。

KKT条件是非凸优化问题取得全局最优解的必要条件，而是凸优化问题取得全局最优解的充要条件，换言之，KKT条件可以用来检验非凸优化问题是否取得全局最优解，凸优化问题可以利用KKT条件求解全局最优解。无论在非凸优化问题还是在凸优化问题中，KKT条件都是一样的形式。从前面的介绍可以知道，优化问题如果有全局最优解$x^{\star}$，对于原问题来说，必须满足约束条件：

$$\begin{matrix} & h_{i}(x^{\star})=0,i=1,2,...m\\ & g_{j}(x^{\star})\leq 0,j=1,2,...p\\ \end{matrix}$$

对于拉格朗日对偶函数来说，必须满足：

$$\lambda _{j} \geq 0,j=1,2,...p$$

在全局最优解处，拉格朗日对偶函数的微分为0，这样保证了这是一个极值，公式如下：

$$\nabla f(x^{\star})+\sum_{j=1}^{p}\lambda _{j}\nabla g_{j}(x^{\star})+\sum_{i=1}^{m}\nu _{i}\nabla h_{i}(x^{\star})=0$$

还一个条件是当解是全局最优解时，满足强对偶要求，即原问题最优解和拉格朗日对偶问题最优解相等，两者目标函数要相等，必须满足：

$$\sum_{j=1}^{p}\lambda _{j}g_{j}(x^{\star})=0$$

综上所述，KKT条件为：

$$\left\{\begin{matrix} & h_{i}(x^{\star})=0,i=1,2,...m \hfill& \\ & g_{j}(x^{\star})\leq 0,j=1,2,...p \hfill& \\ & \lambda _{j} \geq 0,j=1,2,...p \hfill& \\ & \nabla f(x^{\star})+\sum_{j=1}^{p}\lambda _{j}\nabla g_{j}(x^{\star})+\sum_{i=1}^{m}\nu _{i}\nabla h_{i}(x^{\star})=0\hfill & \\ & \sum_{j=1}^{p}\lambda _{j}g_{j}(x^{\star})=0 \hfill& \end{matrix}\right.$$

结语

至此，凸优化的对偶问题已经介绍完了，这部分是我认为最难理解的内容，特别是弱对偶的几何解释，但是这部分内容是之后如何求解凸优化问题以及取得全局最优解的利器，KKT条件则是其中的核心方法，后续我将介绍如何用KKT条件大杀四方。