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

作者: ArronZhang1997 | 来源:发表于2021-05-24 01:28 被阅读0次

机器学习——拉格朗日对偶
简单易懂的拉格朗日对偶法和KKT条件
【转】拉格朗日对偶
拉格朗日乘数法
SVM(2) 之线性可分支持向量机学习方法
支持向量机优化2020-03-19
拉格朗日对偶
如何分摊秘密（七）
拉格朗日乘子法和 KKT 条件
西瓜书笔记02：支持向量基

问题描述

假设要解决的优化问题为：
$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

机器学习——拉格朗日对偶
拉格朗日对偶与凸优化、拉格朗日乘子、KKT条件有着密切的联系，KKT条件可以通过朗格朗日对偶推到得到。 ...
简单易懂的拉格朗日对偶法和KKT条件
问题描述假设要解决的优化问题为：约束条件为问题的简单改写我们现在需要用一个函数来写出上面问题的等价问题。也就...
【转】拉格朗日对偶
拉格朗日对偶本文承接上一篇约束优化方法之拉格朗日乘子法与KKT条件，将详解一些拉格朗日对偶的内容。都是一些在优...
拉格朗日乘数法
拉格朗日乘数法在求解函数最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karu...
SVM(2) 之线性可分支持向量机学习方法
上一篇大概讲了一下拉格朗日对偶法以及KKT条件，这一篇推导一下SVM的公式。下一篇举个例子，差不多就结束了。线性...
支持向量机优化2020-03-19
1、拉格朗日对偶问题求解 2、支持向量机优化求解通过拉格朗日对偶问题求解得到支持向量机的最优解导数代表的是变化...
拉格朗日对偶
Lagrange优化问题：标准形式的优化问题（原问题）：其中，自变量。设问题的定义域是非空集...
如何分摊秘密（七）
十、拉格朗日插值法本节介绍拉格朗日插值法，学过的读者请略过。从数值分析的角度来看，拉格朗日插值法常被描述成是用...
拉格朗日乘子法和 KKT 条件
这篇博文中直观上讲解了拉格朗日乘子法和 KKT 条件，对偶问题等内容。首先从无约束的优化问题讲起，...
西瓜书笔记02：支持向量基
支持向量基 @[拉格朗日乘子法|对偶问题|KKT条件|核函数|hinge损失] 存在多个超平面将样本划分的情况下，...