13 - Constrained Optimization - KKT Condition 2

05 Jul 2015 Comments

上一篇文章中介绍了 constrained optimization，为了求解 local minimum，引入了 feasible direction 和 descent direction 的概念，并且给出了对应于 inequality constraint 的 first order KKT condition 用于求解 inequality constraint 条件下的 local minimum

本文主要包含以下几个方面内容

讨论针对 equality constraint 的 KKT condition
给出同时包含 inequality 和 equality constraint 的 KKT condition
对 [2] 中推理 KKT condition 的过程给出大纲

关于 equality constraint 的 KKT condition 不太适合从 feasible direction 和 descent direction 的角度来讲，需要引入 tangent 的概念，其实不管是 inequality 还是 equality constraint 的 KKT condition 都可以从 tangent 的角度来讲解，并且感觉也更严谨，但是我先看得 NPTEL 的视频，这个视频中不是这么讲的，关于如何从 tangent 入手讲解 KKT condition 可以参考 [2]，这本书中关于 constrained optimization 的理论讲解更全也更严谨，我的这篇文章也参考了 [2]，关于 [2] 中 KKT Condition 的推导过程的大纲在本文最后有给出，了解了大纲读懂推导过程就容易多了

Tangent

给定 $\b{x} \in \c{X}$，如果存在一个序列 $\b{z}_k \in \bb{R}^n$ 不断靠近 $\b{x}$，同时存在另一个序列 $t_k \in \bb{R}, t_k \ra 0 \;\text{as}\; k \ra \infty$ 使得 $\lim_{k \ra \infty} \frac{\b{z}_k - \b{x}}{t_k} = \b{d} \tag{1}$ 则 $\b{d}$ 被称为点 $\b{x}$ 的 tangent，点 $\b{x}$ 处所有 tangent 构成的集合被称为 tangent cone，记为 $\c{T}(\b{x})$

举个例子（来自 [2]），令 $\c{X} = \left\{(x_1, x_2) \left| x_1^2 + x_2^2 = 2 \right.\right\}$ 即 $\c{X}$ 是一个圆，则对于点 $(-\sqrt{2}, 0)$，可以定义如下 $\b{z}_k, t_k$

$\b{z}_k = (-\sqrt{2 - 1/k^2}, -1/k)^T, t_k = \Vert \b{z}_k - \b{x} \Vert$

易算出 $\b{d} = (0, -1)^T$ 为 $\b{x}$ 处的 tagent，如下图所示

其中绿色虚线表示序列 $\b{z}_k$。下面我们给 $\c{T}(\b{x})$ 代数化的表示

如果 $\b{x}$ 是一个 regular point，即 $\nabla e_i(\b{x}), i = 1, \cdots, m$ linear independent，则 $\c{T}(\b{x}) = \left\\{\b{d} \left| \nabla e_i(\b{x})^T\b{d} = 0, \; i = 1, \cdots, m\right.\right\\} \tag{2}$

关于这个定理的证明在 [2] 中有详细给出，这里不做细讲，参考上面那个图，我们可以有个直观上的理解

Nessary Condition for Local Minimum

这里简单回顾一下 little-o notation，如果 $\lim_{x\ra a}\frac{f(x)}{g(x)} = 0$，则记 $f(x) = o(g(x))$，这里 $a$ 可以是 $\infty$，也可以是 $0$ 或者其他数。$o$ 可以读作 “smaller than”，即 $f(x)$ smaller than $g(x)$，$o(g(x))$ 就用来表示所有 $x\ra a$ 情况下小于 $g(x)$ 的函数

如果 $\b{x}^*$ 是 local minimum 且是 regular point，则 $\nabla f(\b{x}^*)^T \b{d} \geq 0 \; \forall \b{d} \in \c{T}(\b{x}^\*) \tag{3}$

Proof

根据公式 1，我们知道，存在 $\{\b{z}_k\}, \{t_k\}$ 使得 $\b{d}$ 满足
$\b{z}_k = \b{x}^* + t_k\b{d} + o(t_k)$
注意 $o(t_k)$ 根据上下文不同可以理解为一个 scalar 也可以是一个 vector，根据 Taylor series
$\begin{align*} f(\b{z}_k) = & f(\b{x}^*) + (\b{z}_k - \b{x^\*})^T \nabla f(\b{x}^\*) + o(\Vert \b{z}_k - \b{x}^* \Vert^2) \\\\ = & f(\b{x}^*) + (t_k\b{d} + o(t_k))^T \nabla f(\b{x}^\*) + o(\Vert \b{z}_k - \b{x}^* \Vert^2) \end{align*}$
当 $k$ 足够大时，$\b{z}_k$ 无限接近于 $\b{x}^$，$o(\Vert \b{z}_k - \b{x}^ \Vert^2)$ 相比一次项就可以忽略不计了，同时 $o(t_k)$ 相比 $t_k$ 也越来越小了。也就是我总能找到一个足够大的 $k$，使得 $ (t_k\b{d} + o(t_k))^T \nabla f(\b{x}^) + o(\Vert \b{z}_k - \b{x}^* \Vert^2) $ 的大小由 $t_k\b{d}^T \nabla f(\b{x}^)$ 决定

因此如果 $\b{d}^T \nabla f(\b{x}^) < 0$，我总能找到一个足够大的 $k$ 使得 $ (t_k\b{d} + o(t_k))^T \nabla f(\b{x}^) + o(\Vert \b{z}_k - \b{x}^* \Vert^2) < 0$，即 $f(\b{z}_k) < f(\b{x}^)$，这样我们就找到了一个比 $\b{x}^$ 更小的 local minimum，与前提矛盾，因此如果 $\b{x}^*$ 是 local minimum，则必有 $\nabla f(\b{x}^*)^T \b{d} \geq 0$ $\EOP$

First Order KKT Condition for Equality Constrain

结合公式 2 和 3，我们得到如下结论

如果 $\b{x}^*$ 是 local minimum 同时是 regular point，则 $\left\\{\b{d} \left| \nabla f(\b{x}^*)^T \b{d} < 0, \nabla e_i(\b{x}^\*)^T \b{d} = 0, i = 1, \cdots, m\right.\right\\} = \emptyset \tag{4}$

看到这里，你似乎可以把 $\{\nabla e_i(\b{x}^*)^T \b{d} = 0\}$ 理解为 feasible direction，但我觉得这么做不严谨，比如对于 $x_1^2 + x_2^2 = 2$ 这个 equality constraint，这么定义出来的 $\b{d}$ 显然不是 feasible direction，[2] 中把这个集合叫做 linearized feasible direction，这个就严谨了很多

根据 4，我们可以得到如下 equality constraint 对应的 KKT condition

如果 $\b{x}^$ 是 local minimum 且是 regular point，则存在 $\bs{\mu}^* = (\mu_1^, \cdots, \mu_m^*)^T \in \bb{R}^m$ 使得 $\nabla f(\b{x}^*) + \sum_{i=1}^m \mu_i^\* \nabla e_i(\b{x}^\*) = \b{0} \tag{5}$

注意到和 inequality constraint 的不同，$\mu_i^*$ 这里可以是任意实数，而不用 $\geq 0$

下面给出定理证明，这里的证明采用的是 NPTEL 视频中的做法。证明前简单回顾一些关于 $\lim$ 和 $\infty$ 的知识。我们知道 $\lim_{x\ra 0} 1/x = \infty$，这个等式的意思不是真的存在 $\infty$ 这样的数，而是表示给定任意一个大的数 $k$，我总可以找到一个足够小的 $x$ 使得 $1/x > k$，同理 $\lim_{x\ra\infty} 1/x = 0$ 表示给定任意小的数 $k$，我总能够找到一个足够大的 $x$ 使得 $1/x < k$。没有任何一个数可以 $\geq \infty$，所有的数都是 $< \infty$，$\infty$ 只是一个概念，不是一个具体的数

$a \geq b, b < 0 \Lra a \geq 0$，因为 $a \geq b \Lra a \geq \lim_{b\ra 0^-} = 0$，用直白的话说，给定任意接近 $0$ 的 $b$，$a$ 都必须比它大，为了达到这个需求， $a$ 肯定不能 $< 0$，因为一旦 $a < 0$，我总能找到足够小的 $b$ 比你更小

Proof:

首先定义两个集合，令
$\begin{align*} C_1 = & \left\\{(y_1, \b{y}_2) \left| y_1 = \nabla f(\b{x}^*)^T \b{d}, \b{y}_2 = (\nabla e_1(\b{x}^*)^T \b{d}, \cdots, \nabla e_m(\b{x}^\*)^T\b{d}) \; \forall \b{d} \in \bb{R}^n\right. \right\\} \\\\ C_2 = & \left\\{(y_1, \b{y}_2) \left| y_1 < 0, \b{y}_2 = \b{0} \right.\right\\} \end{align*}$
则等式 4 等价于
$C_1 \cap C_2 = \emptyset$
易于验证 $C_1, C_2$ 都是 convex set，根据 Convex Set 中关于 seperating hyperplane 的定理可知，如果两个集合交集为空，则必存在一个 hyperplane 能 seperate 这两个集合，也就是存在 $(u_0, \b{u}) \in \bb{R}^{m+1}$ 使得
$u_0 \nabla f(\b{x}^*)^T\b{d} + \sum_{i=1}^m u_i \nabla e_i(\b{x}^\*)^T \b{d} \geq u_0 y_1 + \b{u}^T\b{y_2} = u_0 y_1 \;\; \forall \b{d} \in \bb{R}^n$
如果 $u_0 < 0$ 则该不等式不能成立，因为给定任意 $\b{d}$，不等式左边都能得出一个实数，这个实数不可能 $\geq u_0 y_1, \; \forall y_1 \in \bb{R}^-$，我总能找到一个足够小的 $y_1$ 使得 $u_0 y_1$ 超过任意大的一个数。更数学一点的说法就是 $\lim_{y_1 \ra -\infty} u_0 y_1 = \infty$，没有任何一个数可以 $\geq \infty$，所以如果 $u_0 < 0$ 上述不等式不成立，因此 $u_0 \geq 0$

由于 $\lim_{y_1 \ra 0^-} u_0 y_1 = 0$，所以
$u_0 \nabla f(\b{x}^*)^T\b{d} + \sum_{i=1}^m u_i \nabla e_i(\b{x}^\*)^T \b{d} \geq 0 \;\; \forall \b{d} \in \bb{R}^n$
令 $\b{d} = -(u_0 \nabla f(\b{x}^) + \sum_{i=1}^m u_i \nabla e_i(\b{x}^))$，则
$-\left\Vert u_0 \nabla f(\b{x}^*)^T + \sum_{i=1}^m u_i \nabla e_i(\b{x}^*) \right\Vert^2 \geq 0$
我们知道 norm 必然是 $\geq 0$ 的，所以必有
$u_0 \nabla f(\b{x}^*)^T + \sum_{i=1}^m u_i \nabla e_i(\b{x}^\*) = \b{0}$
由于 $\b{x}^$ 是 regular point，也就是 $\nabla e_i(\b{x}^*)$ linear independent，所以如果 $u_0 = 0$，则必有 $\b{u} = \b{0}$，而 $u_0$ 和 $\b{u}$ 不能同时为 $0$，因此 $u_0 \neq 0$，这样等式两边统除以 $u_0$，并令 $\bs{\mu}^ = \b{u} / u_0$，有
$\nabla f(\b{x}^*)^T + \sum_{i=1}^m \mu_i^\* \nabla e_i(\b{x}^\*) = \b{0}$
到此也就得到了上面的 KKT condition $\EOP$

First Order KKT condition for General Constrained Optimization

现在 equality 和 inequality constraint 都分别讲完了，把它们综合一下给出 General Constrained Optimization 的 first order KKT condition。General Constrained Optimization 的形式如下

$\begin{align*} \min \;& f(\b{x}) \\\\ \st \; & h_j(\b{x}) \leq 0 \; j = 1\cdots l \\\\ & e_i(\b{x}) = 0 \; i = 1\cdots m \end{align*}$

如果 $\b{x}^*$ 是 local minimum 且是 regular point，则 $\begin{align*} \nabla f(\b{x}^*) + \sum_{j=1}^l \l_j^\* \nabla h_j(\b{x}^\*) + \sum_{i=1}^m \mu_i^* \nabla e_i(\b{x}^\*) = 0 \\\\ \l_j^* h(\b{x}^\*) = 0, \; j = 1, \cdots, l \\\\ \l_j^* \geq 0, \; j = 1, \cdots, l \\\\ \end{align*}$

这里的 regular point 要同时考虑 equality 和 inequality constraint，即 $\left\{\nabla h_j(\b{x}^) \; j \in \left\{ j: h_j(\b{x}^*) = 0\right\}\right\} \cup \left\{ \nabla e_i(\b{x}^) \; i \in \left\{ 1, \cdots, m\right\} \right\}$ linear independent

满足上述条件的点 $(\b{x}^*, \bs{\l}^*, \bs{\mu}^*)$ 被称为 KKT point

如果定义 Lagrange function $\c{L}(\b{x}, \bs{\l}, \bs{\mu}) = f(\b{x}) + \sum_{j=1}^l \l_j h_j(\b{x}) + \sum_{i=1}^m \mu_i e_i(\b{x})$，则有 $\nabla_{\b{x}} \c{L}(\b{x}^*, \bs{\l}^*, \bs{\mu}^*) = 0$

另外对于 Convex Programming，first order KKT condition 是 $\b{x}^*$ 为 global minimum 的 necessary and sufficient condition，证明与上一篇文章最后一节中给出的类似

其实我没太理解为什么可以直接合并两种 KKT condition 得到上面的 KKT condition，下面给出一种帮助理解的思路，但不是证明，我觉得这个还是需要证明一下的，不是那么显而易见的，但我没想出怎么证

抛开所有的 gradient, optimization 什么的都不管，其实 inequality 和 equality constraint 对应的 KKT condition 的推导过程核心就是如下两个部分

$\begin{align*} \left\\{\b{d} \left| \b{g}^T\b{d} < 0, \b{c}_i^T \b{d} < 0 \right.\right\\} = \emptyset & \Lra \b{g} + \sum_i \l_i \b{c}_i = 0, \; \l_i \geq 0 \tag{6}\\\\ \left\\{\b{d} \left| \b{g}^T\b{d} < 0, \b{c}_i^T \b{d} = 0 \right.\right\\} = \emptyset & \Lra \b{g} + \sum_i \l_i \b{c}_i = 0, \; \l_i \in \bb{R} \tag{7} \end{align*}$

上面的推导对任意的 $\b{g}, \b{c}_i, \b{d} \in \bb{R}^n$ 都是成立的（$\b{c}_i$ 间需要 linear independent），而包含两种 constraint 的问题就相当于

$\left\\{\b{d} \left| \begin{align*} & \b{g}^T\b{d} < 0 \\\\ & \b{c}_i^T \b{d} < 0 \; \forall i \in \c{I} \\\\ & \b{c}_i^T \b{d} = 0 \; \forall i \in \c{E} \end{align*} \right.\right\\} = \emptyset \Lra \b{g} + \sum_i \l_i \b{c}_i = 0, \; \l_i \geq 0 \; \forall i \in \c{I} \tag{8}$

把问题组织成 6,7,8 的形式感觉会容易理解一些，但我还是觉得需要一个证明怎么从 6,7 推出 8 成立，我没想出来。[2] 中直接解决 8 的问题，不是先证明 6,7 成立，所以感觉更严谨一些

关于 [2] 中 KKT Condition 的推导过程

这里记录 [2] 中关于 KKT Condition 的推导过程的大纲，细节直接看书

整个推导过程大体是这样（注意 [2] 的 inequality constraint 是表示成 $\geq 0$ 的形式，并且所有 constraint 都统一用 $c_i(\b{x})$ 表示，这里就按他的表示法来说明）

首先证明如果 $\b{x}$ 为 regular point，则其 tangent cone $\c{T}(\b{x})$ 可以表示为
$\c{T}(\b{x}) = \left \\{\b{d} \left| \begin{align*} & \b{d}^T \nabla c_i(\b{x}) = 0, \; \forall i \in \c{E} \\\\ & \b{d}^T \nabla c_j(\b{x}) \geq 0, \; j \in \c{A}(\b{x}) \cap \c{I} \end{align*} \right. \right \\}$
其中 $\c{E}$ 表示所有 equality constraint 的下标集合，$\c{I}$ 表示所有 inequality constraint 的下标集合
然后证明如果 $\b{x}^*$ 是 local minimum，则 $\b{d}^T \nabla f(\b{x}^*) \geq 0, \; \forall \b{d} \in \c{T}(\b{x})$
根据上面 2 个结论可以推出，对于 local minimum $\b{x}^*$
$\left \\{\b{d} \left| \begin{align*} & \b{d}^T \nabla f(\b{x}^*) < 0 \\\\ & \b{d}^T \nabla c_i(\b{x}) = 0, \; \forall i \in \c{E} \\\\ & \b{d}^T \nabla c_j(\b{x}) \geq 0, \; j \in \c{A}(\b{x}) \cap \c{I} \end{align*} \right. \right \\} = \emptyset$
然后利用 Farka’s Lemma 推出
$\nabla f(\b{x}^*) - \sum_{i\in\c{E}\cup\c{I}} \l_i \nabla c_i(\b{x}) = 0$
[2] 中提到的 Farka’s Lemma 跟我在 Convex Set 中记录的 Farka’s Lemma 不太一样，我写的那个可以认为是 [2] 的一个 special case，[2] 中的 Farka’s Lemma 有点感觉像是为推导 KKT condition 而专门定制的

Reference

[Optimization Problems with Constraints] (https://www.tu-ilmenau.de/fileadmin/media/simulation/Lehre/Vorlesungsskripte/Lecture_materials_Abebe/NLP_Notes.pdf)
Numerical Optimization by Jorge Nocedal & Stephen J. Wright
[Lagrange Multipliers and the Karush-Kuhn-Tucker conditions] (http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf)
[Calculus/Infinite Limits/Infinity is not a number] (https://en.wikibooks.org/wiki/Calculus/Infinite_Limits/Infinity_is_not_a_number)
[Less than infinity or Less or Equal to infinity] (http://math.stackexchange.com/questions/170313/less-than-infinity-or-less-or-equal-to-infinity)