简单易懂的拉格朗日对偶法和KKT条件

2021-05-24 本文已影响0人 ArronZhang1997

问题描述

假设要解决的优化问题为：
$min f_{0}(x) \tag{1}$
约束条件为 $f_{i}(x) <= 0 \quad {\forall}i \in 1,2,3...,m\tag{2}$

问题的简单改写

我们现在需要用一个函数来写出上面问题的等价问题。也就是要把约束条件跟目标函数写进一个函数中，把这个函数记作 $J(x)$ ,那么 $J(x)$ 可以写作：

$\begin{aligned} J(x) =& \begin{cases} f_{0}(x), \quad & if \quad f_{i}(x) \leq 0 \quad \forall i \\ +\infty, & otherwise \\ \end{cases} \\ =& f_{0}(x) + \sum_{i} I[f_{i}(x)] \\ \end{aligned}$

这里的 $I[u]$ 是个无穷阶跃函数,其表达式为:
$\begin{align} I(u) =& \begin{cases} 0, \quad &if \quad u \leq 0 \tag{5} \\ +\infty, & otherwise\ \end{cases} \end{align}$

如果 $f_{i}(x)$ 大于0, 由于阶跃函数 $I[f_{i}(x)]$ 取值为正无穷, 那么函数不可能在这时取到极小值. 如果 $f_{i}(x)$ 小于等于0, 那么 $I[f_{i}(x)]$ 值为0,求 $J(x)$ 最小值就是求 $f_{0}(x)$ 的最小值.注意到此时的 $f_{i}(x)$ 小于等于0,因此完全和原问题等价.

至此已经把求原问题最小值成功写成求该函数最小值了.

改写成连续可导形式

不难发现, 这个函数不是连续可导的函数, 因此不好进行极值的求解 (连续可导函数可通过让导数值为0来求极值).我们需要进一步把函数转化成一个连续函数的等价形式.

不连续的原因是函数 $I(u)$ 造成的,如何去改写 $I(u)$ 呢?

一个最简单的方法把 $I(u)$ 给松弛成 $\lambda u$ , $\lambda \geq 0\$ .假设 $\lambda = 0.6$ 如下图所示:

无穷阶跃函数I(u)和线性松弛λu
显然,

\lambda u

是

I(u)

的一个下界,这个结论对于任意

\lambda \geq 0\

都是成立的.

现在可以把 $J(x)$ 中的 $I(u)$ 替换为 $\lambda u$ ,新的函数由于引入的新的参数 $\lambda$ ,因此不能用一个字母来表示,于是记作:
$L(x,\lambda) = f_{0}(x) + \sum_{i} \lambda_{i}f_{i}(x) \tag{6}$
那么这个函数该如何跟之前的 $J(x)$ 等价呢?
我们注意到如果 $f_{i}(x)>0$ 时 $\lambda_{i}f_{i}(x)$ 取值为 $+\infty$ , $f_{i}(x)\leq0$ 时 $\lambda_{i}f_{i}(x)$ 取值为 $0$ , 那么 $\lambda_{i}f_{i}(x)$ 的效果将跟 $I[f_{i}(x)]$ 完全相同. 要实现这一步,只需要把 $L(x,\lambda)$ 写成 $\underset{\lambda}{max} L(x,\lambda)$ 即可.也就是把(6)式中的 $\lambda$ 看作变量, $x$ 看作常量求(6)式的最大值. 如果 $f_{i}(x)>0$ 那么 $\lambda$ 取值为 $+\infty$ 时 $L(\lambda)$ 最大,如果 $f_{i}(x)\leq0$ , 那么 $\lambda_{i}f_{i}(x)$ 的值 $\leq 0$ , 当且仅当 $\lambda = 0$ 时取到 $0$ ,才能使 $L(\lambda)$ 最大.因此, $J(x)$ 的等价函数为 $\underset{\lambda}{max} L(x,\lambda)$ . 原问题等价为 $min J(x)$ 也就是 $\underset{x}{min}{\,} \underset{\lambda}{max} L(x,\lambda)$ . 其中 $\underset{x}{min}$ 表示把 $x$ 看作变量求函数的最小值.

对偶问题

注意到求 $\underset{x}{min}{\,}\underset{\lambda}{max} L(x,\lambda)$ 与求原问题等价, 都不好进行求解. 但是,如果我们考虑调换求极值的顺序, 也就是先把 $x$ 看作变量求函数的最小值, 再把 $\lambda$ 看作变量求函数的最大值. 那么问题就变成:
$\underset{\lambda}{max}{\,}\underset{x}{min} L(x,\lambda) = \underset{\lambda}{max} {\,}g(\lambda) \tag{7}$
这个问题跟原问题是不等价的,它被称为原问题的对偶问题. 虽然不等价, 但是对偶问题的最优值是原问题最优值的一个下界,证明如下:

$L(x, \lambda) \leq J(x) \forall \lambda \geq 0$

$\Rightarrow \min _{x} L(x, \lambda) = g(\lambda) \leq \min _{x} J(x)=: p^{\star}$

$\Rightarrow d^{\star} =\max _{\lambda} g(\lambda) \leq p^{\star} \tag{8}$

第一项是因为 $\lambda u \leq I[u]$ , 第二项就是把 $x$ 看作变量同时取极小值, $p^{\star}$ 是原问题的最优值. 第三项是因为由第二项可知 $g(\lambda)$ 的所有值都小于等于 $p^{\star}$ ,因此, $g(\lambda)$ 的最大值, 也就是对偶问题的最优值 $d^{\star}$ 是小于等于 $p^{\star}$ 的.所以对偶问题的最优值是原问题最优值的一个下界.
$g(\lambda)$ 根据凸优化的相关理论是一个凹函数, 因此容易求解.具体证明可参考:https://github.com/ShiqinHuo/Numerical-Optimization-Books/blob/master/Convex%20Optimization%20Boyd.pdf.

当问题具有强对偶性时, $d^{\star} = p^{\star}$ . 若 $d^{\star} < p^{\star}$ 则问题具有弱对偶性.一般来说,几乎所有的凸优化问题都满足强对偶性.比如SVM中, 它的损失函数就是凸函数, 我们几乎就能断定它是一个强对偶的问题.

KKT条件

对于一个没有约束的凸优化问题, 只需要对函数的梯度求导并令其为0即可. 对于由约束的凸优化问题而言, 它的最优解一定满足KKT条件. 第一个条件如下所示:
$\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x} f_{i}\left(x^{\star}\right)=0 \tag{9}$
这个条件可以解释为目标函数和约束函数的梯度必须平行且相反, 如下图所示:

假设目标函数为

f_{0}(x)=(x_1-1.1)^{2}+(x_2+1.1)^{2}

，不等值约束为

f_{1}(x)=x_{1}^2+x_{2}^{2}−1

,如图所示, 最小值点取在

f_{0}(x)

梯度的反方向和约束条件

f_{1}(x)

梯度的方向上. 值得注意的是,如果

f_{0}(x)

最小值落在可行域内,约束将不起作用,

\lambda

取值为

0

,上面的等式依然成立,求极小值的方法就是直接令

f_{0}(x)

梯度为

0

根据(8)式我们有:
$f_{0}\left(x^{\star}\right)=g\left(\lambda^{\star}\right)=\min _{x} L\left(x, \lambda^{\star}\right) = f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) \leq f_{0}\left(x^{\star}\right) \tag{10}$

最右边的不等式成立的原因为 $\lambda_{i} \geq 0,f_{i}(x^{\star}) \leq 0$ .(10)式成立的条件只有取等号, 因此我们得到了第二个KKT条件:
$\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i\tag{11}$
综上, 在不等式约束下凸优化问题的所有KKT条件包括:
$\lambda_{i} \geq 0$

$f_{i}(x^{\star}) \leq 0$

$\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x}f_{i}\left(x^{\star}\right) =0$

$\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i$

参考资料

[1] David Knowles,Lagrangian Duality for Dummies,November 13, 2010
[2] 瑞典皇家理工学院（KTH）“统计学习基础”课程的KKT课件：http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf