KKT (LICQ)

基本内容
- LICQ 假设
- KKT 定理
KKT定理的证明

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

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

基本内容

问题

[ ag{1} min_{x in Omega} f(x), ]

在等式约束条件:

[ ag{2} c_i(x) = 0, i in xi, ]

及不等约束条件:

[ ag{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), tge 0)为一连续路径, 满足(t ightarrow 0, x(t) ightarrow x_0)，定义(d)为:

[frac{x(t) - x_0}{|x(t)-x_0|} mathop{ ightarrow } limits_{t ightarrow 0} frac{d}{|d|}. ]

有如下性质:

[ ag{8,9} abla c_i(x) d = 0, i in xi \ abla c_i(x) d ge 0, i in mathcal{I cap A}, ]

其中, 我们假设梯度向量为行向量.

证明:

[ c_i(x(t)) - c_i(x_0) = abla c_i(x_0)(x(t)-x_0) + o(|x(t)-x_0|) = 0, i in xi ]

两边同除以(|x(t)-x_0|), 并令(t ightarrow 0)即可得.

[ c_i(x(t)) - c_i(x_0) = abla 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)的集合记为

[ ag{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假设, 当

[ ag{14} { abla c_i(x_0)}, i in mathcal{A}, ]

是线性独立的.
线性不独立: 当集合中存在一个向量能够由其他向量线性表出, 否则称此集合线性独立. 显然这是比线性无关更强的一个概念.

KKT 定理

假设(x^*)是问题(1)在等式约束(2)以及不等式约束(3)的限制下的局部最小值点, 且满足LICQ假设. 则存在(lambda_i^*)满足:

[ ag{17} abla f(x^*) = sum_{i in xi cup mathcal{I}} lambda_i^* abla c_i(x^*), ]

且

[ ag{18} egin{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 [ egin{array}{c} abla c_1(x) \ vdots \ abla c_m(x) end{array} ight ] ]

属于(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'), 则

[ ag{24} left [ egin{array}{c} A \ Z' end{array} ight ] ]

是一个非奇异的(n imes n)的方阵.

考虑如下的非线性方程系统(显然有解(t=0,y=x))

[ ag{25} R(y, t) = left [ egin{array}{c} c(y) - tAd \ Z'(y - x -td) end{array} ight ] = 0. ]

关于(y)的加科比行列式为

[ ag{26} frac{partial R}{partial y} |_{t=0} = left [ egin{array}{c} A \ Z' end{array} ight ], ]

非奇异, 所以根据隐函数定理可知, 在(t)足够小的时候, 存在连续可微函数(y(t)), 且(y(0)=x).

既然

[ ag{27} c(y)=c(x) + abla c(x)(y-x) + o(|y-x|) = A(y-x)+o(|y-x|), ]

我们有

[ ag{28} 0=R(y(t),t) = left [ egin{array}{c} A \ Z' end{array} ight ] (y(t)-x-td) + o(|y(t)-x|). ]

也就是说

[ ag{29} y(t)-x=td+o(|y(t)-x|), ]

俩边令(t ightarrow 0), 可知(y(t))为(d)的一个连续路径.
又结合(25)

[ ag{30} c(y(t))-tAd=0, ]

[ ag{31} c_i(y(t))=t abla c_i(x)d = left { egin{array}{ll} 0, & i in xi \ ge 0 , & i in mathcal{I cap A} . end{array} ight . ]

所以对于任意的(i in mathcal{A}), (y(t))是可行路径, 对于未激活的不等式约束, 既然(y(t))是连续的, 当(t)足够效地时候容易得到(c_i(y(t)) > 0, i in mathcal{I}, i ot in mathcal{A}). 这样便证明了, (forall d in mathcal{F}(x)), 均为可行方向, 故(mathcal{F}(x) =mathcal{T}(x)).

Farkas 引理

Farkas 引理: 令(g)和({a_i}_{i=1}^m)为(n)维行向量且

[ ag{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) 使得

[ ag{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 ot =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 angle hat{a}_i, ]

则

[langle h, a_i angle = 0, \ langle h, g angle = l ot = 0. ]

不妨设(l<0)(否则(h=-h)), 则(h in mathcal{S}), 这与(mathcal{S} = empty)矛盾.

证毕.

定义问题(mathcal{P}):

[ ag{36} gd < 0, \ Ad ge 0. ]

定义问题(mathcal{D}):

[ ag{37} g = lambda^T A, lambda ge 0. ]

推论

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

KKT定理的证明

既然(x^*)是一局部极值点, 则

[ ag{38} abla f(x^*) d ge 0, forall d in mathcal{T} (x^*) =mathcal{F}(x^*), ]

将( abla 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):

[ ag{39} abla f(x^*) = sum lambda_i^* abla c_i(x^*), lambda_i^* ge 0. ]

对于任意的(i ot in mathcal{A}), 我们只需取(lambda_i^*=0), (39)依然成立, 同时原定理(18)中的(i)(ii)也同样容易证明.