KKT (LICQ)

作者: 馒头and花卷 | 来源:发表于2020-03-22 10:35 被阅读0次

KKT (LICQ)
2018-04-18 开胃学习数学系列 - Duality
机器学习——拉格朗日对偶
给大家介绍两款超级牛逼的算法！SVM · SMO算法！和牛逼也很
机器学习面试001—支持向量机SVM
对偶 KKT
KKT条件
Constrained Optimization - Solvi
kkt条件的推导思路以及八卦
Dual Problem & KKT

H. E. Krogstad, TMA 4180 Optimeringsteori KARUSH-KUHN-TUCKER THEOREM

KKT条件在处理有约束问题的时候很有用, 但是对KKT的适用性一直不是很理解, 看了这篇讲解整理一下.

基本内容

问题
$\tag{1} \min_{x \in \Omega} f(x),$
在等式约束条件:
$\tag{2} c_i(x) = 0, i \in \xi,$
及不等约束条件:
$\tag{3} c_i(x) \ge 0, i \in \mathcal{I}.$
不妨就记
$\Omega = \{x: c_i(x) = 0, i \in \xi, c_i(x)\ge 0, i \in \mathcal{I}\}.$
在不等式约束中, 即只有当我们所寻的极值点 $x^*$ 处, $c_i(x^*)=0, i \in \mathcal{I}$ 称之为激活不等式约束(active inequality constraints), 否则为不激活的, 我们记激活的不等式约束和等式约束为 $\mathcal{A}$ .

注: 均连续可微.

对于任意一个可行点 $x_0$ , 令 $x(t), t\ge 0$ 为一连续路径, 满足 $t\rightarrow 0, x(t) \rightarrow x_0$ ，定义 $d$ 为:
$\frac{x(t) - x_0}{\|x(t)-x_0\|} \mathop{\rightarrow } \limits_{t \rightarrow 0} \frac{d}{\|d\|}.$

有如下性质:
$\tag{8,9} \nabla c_i(x) d = 0, i \in \xi \\ \nabla c_i(x) d \ge 0, i \in \mathcal{I \cap A},$
其中, 我们假设梯度向量为行向量.

证明:
$c_i(x(t)) - c_i(x_0) = \nabla c_i(x_0)(x(t)-x_0) + o(\|x(t)-x_0\|) = 0, i \in \xi$
两边同除以 $\|x(t)-x_0\|$ , 并令 $t \rightarrow 0$ 即可得.
$c_i(x(t)) - c_i(x_0) = \nabla c_i(x_0)(x(t)-x_0) + o(\|x(t)-x_0\|) = c_i(x(t)) \ge 0, i \in \mathcal{I \cap A}$
与上面同样的操作即可得.

我们把这些由路径引导出来的可行方向 $d$ 的集合记为
$\tag{10} \mathcal{T}(x) = \{d: d \: feasible \: di rection \: out \: from \: x\}.$
而记满足 $(8, 9)$ 的一切 $d$ 的集合记为 $\mathcal{F}(x)$ , 显然 $\mathcal{T}(x) \subset \mathcal{F}(x)$ , 且均为锥(即 $d$ 属于此集合, 则 $\alpha d, \alpha > 0$ 也属于此集合).

LICQ 假设

点 $x_0$ 满足LICQ假设, 当
$\tag{14} \{\nabla c_i(x_0)\}, i \in \mathcal{A},$
是线性独立的.
线性不独立: 当集合中存在一个向量能够由其他向量线性表出, 否则称此集合线性独立. 显然这是比线性无关更强的一个概念.

KKT 定理

假设 $x^*$ 是问题(1)在等式约束(2)以及不等式约束(3)的限制下的局部最小值点, 且满足LICQ假设. 则存在 $\lambda_i^*$ 满足:
$\tag{17} \nabla f(x^*) = \sum_{i \in \xi \cup \mathcal{I}} \lambda_i^* \nabla c_i(x^*),$
且
$\tag{18} \begin{array}{lc} (i) & \lambda_i^* \cdot c_i(x^*) = 0, i \in \xi \cup \mathcal{I}, \\ (ii) & \lambda_i^* \ge 0, i \in \mathcal{I}. \end{array}$

KKT定理的证明

记:
$A = \left [ \begin{array}{c} \nabla c_1(x) \\ \vdots \\ \nabla c_m(x) \end{array} \right ]$
属于 $\mathcal{A}$ 的所有 $c_i$ 的梯度的综合表示,
$c(x) = [c_1(x), \ldots, c_m(x)]^T.$

引理A

引理A: 当 $x \in \R^n$ 满足LICQ假设, 则 $\mathcal{T}(x) = \mathcal{F}(x)$ .

证明:
既然 $\mathcal{T}(x) \subset \mathcal{F}(x)$ , 我们只需要证明 $\mathcal{F}(x) \subset \mathcal{T}(x)$ .

下面, $\forall d \in \mathcal{F}(x)$ , 我们将构造 $y(t), t \ge 0$ , 为一连续的起点为 $y(0)=x$ 的路径, 且在 $x$ 的足够小的一个邻域内 $y(t)$ 满足等式约束和不等式约束, 一旦找到这样的 $y(t)$ , 证明也就完成了.

根据假设可知, dim( $A$ ) = $m$ , 则 $A$ 的核的维数为 $dim(N(A))=n-m$ , 我们从核空间中抽取一组基作为行向量构建 $Z'$ , 则
$\tag{24} \left [ \begin{array}{c} A \\ Z' \end{array} \right ]$
是一个非奇异的 $n\times n$ 的方阵.

考虑如下的非线性方程系统(显然有解 $t=0,y=x$ )
$\tag{25} R(y, t) = \left [ \begin{array}{c} c(y) - tAd \\ Z'(y - x -td) \end{array} \right ] = 0.$
关于 $y$ 的加科比行列式为
$\tag{26} \frac{\partial R}{\partial y} |_{t=0} = \left [ \begin{array}{c} A \\ Z' \end{array} \right ],$
非奇异, 所以根据隐函数定理可知, 在 $t$ 足够小的时候, 存在连续可微函数 $y(t)$ , 且 $y(0)=x$ .

既然
$\tag{27} c(y)=c(x) + \nabla c(x)(y-x) + o(\|y-x\|) = A(y-x)+o(\|y-x\|),$
我们有
$\tag{28} 0=R(y(t),t) = \left [ \begin{array}{c} A \\ Z' \end{array} \right ] (y(t)-x-td) + o(\|y(t)-x\|).$

也就是说
$\tag{29} y(t)-x=td+o(\|y(t)-x\|),$
俩边令 $t \rightarrow 0$ , 可知 $y(t)$ 为 $d$ 的一个连续路径.
又结合(25)
$\tag{30} c(y(t))-tAd=0,$
$\tag{31} c_i(y(t))=t\nabla c_i(x)d = \left \{ \begin{array}{ll} 0, & i \in \xi \\ \ge 0 , & i \in \mathcal{I \cap A} . \end{array} \right .$
所以对于任意的 $i \in \mathcal{A}$ , $y(t)$ 是可行路径, 对于未激活的不等式约束, 既然 $y(t)$ 是连续的, 当 $t$ 足够效地时候容易得到 $c_i(y(t)) > 0, i \in \mathcal{I}, i \not \in \mathcal{A}$ . 这样便证明了, $\forall d \in \mathcal{F}(x)$ , 均为可行方向, 故 $\mathcal{F}(x) =\mathcal{T}(x)$ .

Farkas 引理

Farkas 引理: 令 $g$ 和 $\{a_i\}_{i=1}^m$ 为 $n$ 维行向量且
$\tag{33} \mathcal{S} = \{ d \in \mathbb{R}^n; gd<0 , a_id \ge 0, i=1, \ldots, m\},$
则 $\mathcal{S} = \empty$ 当且仅当存在非负向量 $\lambda \in \mathbb{R}^m$ 使得
$\tag{34} g = \sum_{i=1}^m \lambda_i a_i.$

证明:

$\Leftarrow$

$\forall d \in \mathcal{S}$ ,
$0 > gd = \sum_{i=1}^m \lambda_i a_id \ge 0,$
故 $\mathcal{S} = \empty$ .

$\Rightarrow$

若不存在这样的 $\lambda$ , 即对于任意的 $\lambda$ , $g \not =\sum_{i=1}^m \lambda_i a_i$ , 则 $g$ 不能由 $\{a_i\}$ 线性表出. 不妨假设 $\{a_i\}$ 与 $g$ 按序进行施密特正交化过程, 可得 $\{\hat{a}_i\}$ 为 $\{a_i\}$ 的一正交向量组, $h$ 为
$h = g- \sum_i \langle g,\hat{a}_i\rangle \hat{a}_i,$
则
$\langle h, a_i \rangle = 0, \\ \langle h, g \rangle = l \not = 0.$
不妨设 $l<0$ (否则 $h=-h$ ), 则 $h \in \mathcal{S}$ , 这与 $\mathcal{S} = \empty$ 矛盾.

证毕.

定义问题 $\mathcal{P}$ :
$\tag{36} gd < 0, \\ Ad \ge 0.$
定义问题 $\mathcal{D}$ :
$\tag{37} g = \lambda^T A, \lambda \ge 0.$

推论

推论: 要么问题 $\mathcal{P}$ 存在解, 要么 $\mathcal{D}$ 存在解, 二者不能同时成立.

KKT定理的证明

既然 $x^*$ 是一局部极值点, 则
$\tag{38} \nabla f(x^*) d \ge 0, \forall d \in \mathcal{T} (x^*) =\mathcal{F}(x^*),$
将 $\nabla f(x^*)$ 视作Farkas引理中的 $g$ , $A$ 即为我们最开始定义的 $A$ , 则 $\forall Ad \ge 0$ , $d \in \mathcal{F}(x)$ , 这是因为所有等式约束 $c_i(x)=0$ , 都可以变成俩个不等式约束 $c_i(x)\ge0, -c_i(x) \ge 0$ . 这也就是说, 问题 $\mathcal{P}$ 无解, 则 $\mathcal{D}$ 有解, 即存在 $\lambda^* \ge 0$ :
$\tag{39} \nabla f(x^*) = \sum \lambda_i^* \nabla c_i(x^*), \lambda_i^* \ge 0.$
对于任意的 $i \not \in \mathcal{A}$ , 我们只需取 $\lambda_i^*=0$ , (39)依然成立, 同时原定理(18)中的(i)(ii)也同样容易证明.

KKT (LICQ)
H. E. Krogstad, TMA 4180 Optimeringsteori KARUSH-KUHN-TU...
2018-04-18 开胃学习数学系列 - Duality
KKT gradient is 0 x* is the local minimizer
机器学习——拉格朗日对偶
拉格朗日对偶与凸优化、拉格朗日乘子、KKT条件有着密切的联系，KKT条件可以通过朗格朗日对偶推到得到。 ...
给大家介绍两款超级牛逼的算法！SVM · SMO算法！和牛逼也很
KKT 条件先来看如何选取参数。在 SMO 算法中，我们是依次选取参数的：选出违反 KKT 条件最严重的样本点...
机器学习面试001—支持向量机SVM
1. 关于min和max交换位置满足的 d* <= p* 的条件并不是KKT条件 Ans：这里并非是KKT条件，要...
对偶 KKT
注意：从最优解看待对偶和KKT1、原始问题，转化成对偶问题，是为了更简单得到最优解2、强对偶性，代表原始问题的最优...
KKT条件
定义优化问题：的解满足如下条件该条件即KKT条件。解释无约束条件时，局部极值点在梯度为0时取得。例如，当为局...
Constrained Optimization - Solvi
Intuition of KKT finding supporting hyperplane[1] 设定 Lagr...
kkt条件的推导思路以及八卦
kkt条件的推导思路以及八卦 KKT条件是用来判断一个解是否属于一个非线性最优化问题的。这个条件也是推导出来的 ...
Dual Problem & KKT
I have written a note with respect to SVM. Unfortunately ...

KKT (LICQ)

基本内容

LICQ 假设

KKT 定理

KKT定理的证明

引理A

Farkas 引理

推论

KKT定理的证明

相关文章

KKT (LICQ)

2018-04-18 开胃学习数学系列 - Duality

机器学习——拉格朗日对偶

给大家介绍两款超级牛逼的算法！SVM · SMO算法！和牛逼也很

机器学习面试001—支持向量机SVM

对偶 KKT

KKT条件

Constrained Optimization - Solvi

kkt条件的推导思路以及八卦

Dual Problem & KKT

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读