12 - Constrained Optimization - KKT Condition 1

30 Jun 2015 Comments

这篇文章主要包含如下几个方面的内容

• 首先介绍了什么是 Constrained Optimization
• 然后给出 Constrained Optimization 条件下 global 和 local minimum 的概念
• 之后为了计算 local minimum，引入 feasible direction 和 descent direction
• 之后介绍了对应于 inequality constraint 的 first order KKT condition
• 最后介绍了 Convex Programming 的概念

Constrained Optimization

Constrained Optimization 可以表示为

$$\begin{align*} \min \; f(\b{x}) \\\\ \st \; \b{x} \in \c{X} \end{align*} \tag{1}$$

其中 $\c{X} \subseteq \bb{R}^n$ 表示 $\b{x}$ 允许的取值。可以将 $\c{X}$ 进一步细化成如下一般形式

$$\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 \\\\ & \b{x} \in S \end{align*} \tag{2}$$

其中 $h_j(\b{x})$ 表示 inequality constraint，$e_i(\b{x})$ 表示 equality constraint，$S \in \bb{R}^n$

Global and Local Minimum

下面是 constrained optimization 情况下 global 和 local minimum 的定义

如果 $\b{x}^*$ 满足

$$f(\b{x}^*) \leq f(\b{x}) \; \forall \b{x} \in \c{X} \tag{3}$$

则 $\b{x}^*$ 为 global minimum，如果不等号严格成立，则 $\b{x}^*$ 为 strict global minimum

如果存在 $\epsilon > 0$ 使得 $\b{x}^*$ 满足

$$f(\b{x}^*) \leq f(\b{x}) \; \forall \b{x} \in B(\b{x}^\*, \epsilon) \cap \c{X} \tag{4}$$

则 $\b{x}^*$ 为 local minimum，如果不等式严格成立，则 $\b{x}^*$ 为 strict local minimum

下图给出了 local 和 global minimum 的例子

$\c{X} = [a, b]$，其中 $a, x_1, x_2, x_3$ 都是 local minimum，$x_1$ 是 global minimum。从中可以看出 unconstrained optimization 中关于 local minimum 必然有 $f’(\b{x}) = 0$ 的 necessary condition 不再成立（$f’(a)$ 显然不等于 $0$），那我们如何能从数学上对 constrained optimization 中的 local minimum 进行刻画呢？

Feasible and Descent Direction

首先我们来看两个概念：feasible direction 和 descent direction

令 $\b{x} \in \c{X}, \b{d} \in \bb{R}^n \neq \b{0}$，如果存在 $\delta_1 > 0$ 使得 $\b{d}$ 满足

$$\b{x} + \a\b{d} \in \c{X} \;\; \forall \a \in (0, \delta_1) \tag{5}$$

则 $\b{d}$ 被称为为 feasible direction

• 令 $\c{F}(\b{x})$ 表示在 $\b{x}$ 点的所有 feasible direction 的集合

令 $\b{x} \in \c{X}, \b{d} \in \bb{R}^n \neq \b{0}$，如果存在 $\delta_2 > 0$ 使得 $\b{d}$ 满足

$$f(\b{x} + \a\b{d}) < f(\b{x}) \;\; \forall \a \in (0, \delta_2) \tag{6}$$

则 $\b{d}$ 被称为 descent direction

• 令 $\c{D}(\b{x})$ 表示在 $\b{x}$ 点的所有 descent direction 的集合

下面我们从 $\c{F}(\b{x})$ 和 $\c{D}(\b{x})$ 出发对 local minimum 做初步刻画

定理 1：如果 $\b{x}^* \in \c{X}$ 为 local minimum，则有 $\c{F}(\b{x}^*) \cap \c{D}(\b{x}^*) = \emptyset$

• Proof:

  假设 $\c{F}(\b{x}^) \cap \c{D}(\b{x}^*) \neq \emptyset$，则存在 $ \b{d} \in \c{F}(\b{x}^) \cap \c{D}(\b{x}^*)$，也就是

  • $\exists \delta_1 > 0, \forall \a \in (0, \delta_1), \b{x}^* + \a\b{d} \in \c{X}$
  • $\exists \delta_2 > 0, \forall \a \in (0, \delta_2), f(\b{x}^* + \a\b{d}) < f(\b{x}^*)$

  令 $\delta = \min(\delta_1, \delta_2), \a \in (0, \delta), \b{y} = \b{x}^* + \a\b{d}$，则有 $f(\b{y}) < f(\b{x}^*), \b{y} \in \c{X}$，也就是在 $\c{X}$ 中找到了比 $f(\b{x}\^*)$ 更小的 $f(\b{y})$

  因此，如果 $\b{x}^$ 为 local minimum，则必有 $\c{F}(\b{x}^*) \cap \c{D}(\b{x}^) = \emptyset$ $\EOP$

下面我们将从这个定理出发找到一种 local minimum 的代数表示方法（只有找到了 代数表示法我们才能计算出 local minimum）

Descent Direction in Algebraical Way

定理 2：定义 $\tilde{\c{D}}(\b{x}) = \{\b{d}: \nabla f(\b{x})^T \b{d} < 0 \}$，则有 $\tilde{\c{D}}(\b{x}) \subseteq \c{D}(\b{x})$

• Proof:

  $f(\b{x})$ 在点 $\b{x}$ 处沿 $\b{d}$ 方向的方向导数为

  $$\underset{\a \rightarrow 0^+}{\lim} \frac{f(\b{x} + \a\b{d}) - f(\b{x})}{\a} = \nabla f(\b{x})^T \b{d}$$

  这里我们只考虑 $\a > 0$ 的情况。如果 $f(\b{x})^T \b{d} < 0$，也就意味着 $f(\b{x} + \a\b{d}) < f(\b{x})$，即 $\b{d} \in \c{D}(\b{x})$，所以 $\tilde{\c{D}}(\b{x}) \subseteq \c{D}(\b{x})$ $\EOP$

根据定理 1 和定理 2，如果 $\b{x}^*$ 是 local minimum，则有 $\c{F}(\b{x}) \cap \tilde{\c{D}}(\b{x}) = \emptyset$

Feasible Direction For Inequality Constrain

我们首先看一下 inequality constraint 情况下 feasible direction 的表示。考虑下图

后面的圆圈线表示 $f(\b{x})$ 的 contour line，绿色阴影部分表示 $\c{X}$，边界分别对应 $h_j(\b{x}) = 0, j = 1, 2, 3$，$\c{X}$ 即为 $h_j(\b{x}) \leq 0$ 的交集，图中给出了三个点，其中点 A 处于两个边界的交点，在这个点有 $h_1(\b{x}) = 0, h_2(\b{x}) = 0$，这时我们称 $h_1, h_2$ 为点 A 的 active constraint，记为 $\c{A}(\b{x}) = \{1, 2\}$，对于点 C，$\c{A}(\b{x}) = \{3\}$，对于点 B，$\c{A}(\b{x}) = \emptyset$

通过观察，我们发现 feasible direction 和 active constraint 之间存在密切联系

• 对于点 A

  $\c{F}(\b{x})$ 包含 $\b{d}_1, \b{d}_2$ 之间的向量，其中 $\nabla h_1(\b{x})^T \b{d}_1 = 0$，$\nabla h_2(\b{x})^T \b{d}_2 = 0$，对于 $\b{d}_1, \b{d}_2$ 之间的向量都有 $\nabla h_1(\b{x})^T \b{d}_1 < 0$，$\nabla h_2(\b{x})^T \b{d}_2 < 0$，因此 $\c{F}(\b{x})$ 可以表示为 $\{\b{d}: \nabla h_j(\b{x})^T \b{d} < 0, j \in \c{A}(\b{x}) = \{1, 3\} \}$

• 对于点 C

  $\c{F}(\b{x})$ 包含 $\b{d}_3, \b{d}_4$ 之间向量，同上可知 $ = \{\b{d}: \nabla h_j(\b{x})^T \b{d} < 0, j \in \c{A}(\b{x}) = \{3\} \}$

• 对于点 B

  所有向量都是 feasible direction，因此 $\c{F}(\b{x}) = \bb{R}^n$

定理 3：定义 $\tilde{\c{F}}(\b{x}) = \{ \b{d}: \nabla h_j(\b{x})^T \b{d} < 0, j \in \c{A}(\b{x})\}$，则有 $\tilde{\c{F}}(\b{x}) \subseteq \c{F}(\b{x})$

• Proof:

  给定 $\b{x} \in \c{X}$，如果 $\b{d} \in \tilde{\c{F}}(\b{x})$，则

  • 对于 $j \in \c{A}(\b{x})$ 的 $h_j(\b{x})$

    因为 $\nabla h_j(\b{x})^T \b{d} < 0$，所以 $\b{d}$ 对于 $h_j(\b{x})$ 为 descent direction，则 $\exists \delta_1 > 0, h_j(\b{x} + \a\b{d}) < h_j(\b{x}), \; \forall \a \in (0, \delta_1)$，即 $h_j(\b{x} + \a\b{d}) < 0$，所以 $\b{x} + \a\b{d} \in \c{X}$

  • 对于 $j \notin \c{A}(\b{x})$ 的 $h_j(\b{x})$

    因为 $h_j(\b{x}) \in \c{C}^0$ 且 $h_j(\b{x}) < 0$，所以 $\exists \delta_2 > 0, h_j(\b{x} + \a\b{d}) < 0, \; \forall \a \in (0, \delta_2)$，即 $\b{x} + \a\b{d} \in \c{X}$

  综上所述，如果定义 $\delta = \min(\delta_1, \delta_2)$，则 $\b{x} + \a\b{d} \in \c{X}, \; \forall \a \in (0, \delta)$，所以 $\b{d}$ 为 feasible direction，所以 $\tilde{\c{F}}(\b{x}) \subseteq \c{F}(\b{x})$ $\EOP$

根据定理 1，2 和 3，我们可以得到如下推论

定理 4：如果 $\b{x}^*$ 为 local minimum，则 $\tilde{\c{F}}(\b{x}) \cap \tilde{\c{D}}(\b{x}) = \emptyset$

由于 $\tilde{\c{F}}(\b{x})$ 和 $\tilde{\c{D}} (\b{x})$ 都是通过代数形式表示的，我们就可以基于这个推论来求解 local minimum 了。另外要注意，这个只是个 nessesary condition，不是 sufficient condition

First Order KKT Condition for Inequality Constrain

把定理 4 展开有

$$\\{\b{d}: \nabla h_j(\b{x}^*)^T \b{d} < 0, j \in \c{A}(\b{x}^\*) \\} \cap \\{\b{d}: \nabla f(\b{x}^*)^T \b{d} < 0 \\} = \emptyset \tag{7}$$

如果记 $A = \begin{pmatrix} \nabla f(\b{x}^)^T \\ \cdots \\ h_j(\b{x}^*)^T \\ \cdots \end{pmatrix}$，其中 $j \in \c{A}(\b{x}^)$，$A \in \bb{R}^{(1 + |\c{A}(\b{x}^*)|) \times n}$，那公式 7 等价于

$$\\{\b{d}: A\b{d} < 0\\} = \emptyset$$

换句话说就是 $A\b{d} < 0$ 无解。根据 Convex Set 这篇文章中 Farka’s Lemma 的推论，我们有

$\exists \l_0, \l_j \geq 0, j \in \c{A}(\b{x}^*)$ 且 $\l$ 不同时为 $0$，使得 $\l_0 \nabla f(\b{x}^*) + \sum_{j\in \c{A}(\b{x}^\*)} \l_j \nabla h_j(\b{x}^*) = \b{0} \tag{8}$

公式 8 存在这么个问题，如果存在非 $\b{0}$ $(\l_1, \cdots, \l_l)^T \geq 0$ 使得 $\sum_j \l_j \nabla h_j(\b{x}^) = 0$，那 $\l_0$ 直接设置成 $0$ 就好了，这时候无论 $\nabla f(\b{x}^)$ 取什么值都不影响等式 8 成立，也就是 $f(\b{x})$ 已经不再重要了，这是我们希望避免的。为此，我们要求 $\nabla h_j(\b{x}^*)$ 之间 linear independent，这样就避免掉了 $\l_0 = 0$ 的情况，因为如果 $\l_0 = 0$，则必有 $\l_j = 0$ 才能使等式 8 成立，而这跟等式 8 成立的前提相违背

给定点 $\b{x}$，如果 $\nabla h_j(\b{x}), j \in \c{A}(\b{x})$ 之间 linear independent，则点 $\b{x}$ 被称为 regular point

所以我们要求 $\b{x}^*$ 是 regular point

那现在既然 $\l_0 \neq 0$，等式 8 两边统除以 $\l_0$，并定义 $\l_j^* = \l_j / \l_0, j \in \c{A}(\b{x})$，则有 $ \nabla f(\b{x}^) + \sum_{j\in \c{A}(\b{x}^)} \l_j^* \nabla h(\b{x}^*) = 0 $，更进一步，如果令 $\l_j^* = 0, \; \forall j \notin \c{A}(\b{x}^)$，则有 $ \nabla f(\b{x}^*) + \sum_j \l_j^ \nabla h(\b{x}^*) = 0, \; j = 1, \cdots, l$，这样我们就有了 First Order KKT Condition

如果 regular point $\b{x}^$ 是 local minimum，则存在 $\bs{\l}^ = \{\l_1^*, \cdots, \l_l^* \}$ 使得 $\begin{align*} \nabla f(\b{x}^*) + \sum_{j=1}^l \l_j^\* \nabla h(\b{x}^\*) = 0 \\\\ \l_j^* h_j(\b{x}^\*) = 0, \; j = 1, \cdots, l \\\\ \l_j^* \geq 0 \; j = 1, \cdots, l \end{align*}$

这里的第二个等式是这样，如果 $j \in \c{A}(\b{x}^)$，则 $h_j(\b{x}^*) = 0$，因此 $\l_j^ h_j(\b{x}^*) = 0$，如果 $j \notin \c{A}(\b{x}^)$，$\l_j^* h_j(\b{x}^*) = 0$ 就相当于要求 $\l_j^ = 0$

• 点 $(\b{x}^*, \bs{\l}^*)$ 被称为 KKT point
• $\c{L}(\b{x}, \bs{\l}) = f(\b{x}) + \sum_{j=1}^l \l_j h_j(\b{x})$ 被称为 Lagrangian function，$\l_j$ 被称为 Lagrange multiplier。上面第一个等式就等价于 $\nabla_{\b{x}} \c{L}(\b{x}, \bs{\l}^*)|_{\b{x} = \b{x}^*} = 0$
• $\l_j^* h_j(\b{x}^*) = 0$ 被称为 Complementary Slackness Condition

另外注意，这个 condition 只是 necessary condition，不符合上述 condition 的点也可能是 local minimum

Example

举个例子

$$\begin{align*} \min \; & x_1^2 + x_2^2 \\\\ \st \; & x_1 + x_2 \geq 1 \\\\ & x_2 \leq 0 \end{align*}$$

• Solution:

  定义 Lagrangian function $\c{L}(\b{x}, \bs{\l}) = x_1^2 + x_2^2 + \l_1 (1 - x_1 - x_2) + \l_2 x_2$

  \begin{align} & \frac{\p \c{L}}{\p x_1} = 2x_1 - \l_1 = 0 \
  & \frac{\p \c{L}}{\p x_2} = 2x_2 - \l_1 + \l_2 = 0 \
  & \l_1(1 - x_1 - x_2) = 0 \
  & \l_2 x_2 = 0 \end{align}

  从最后一个等式我们知道，要么 $\l_2 = 0$ 要么 $x_2 = 0$

  • 如果 $x_2 = 0$，则有 $x_1 = 1, \l_1 = 2, \l_2 = -2$
  • 如果 $\l_2 = 0$，则有 $x_1 = x_2 = \frac{1}{2}, \l_1 = 1$

  其中第一种情况由于 $\l_2 < 0$ 所以不可行，第二种情况符合条件， 也就是这个问题的解

Convex Programming Problem

如果公式 2 满足如下条件

• $f(\b{x})$ 是 convex function
• $h_j(\b{x})$ 是 convex function
• $e_i(\b{x})$ 是 affine function，即 $e_i(\b{x}) = \b{a}_i \b{x} + b_i$
• $S$ 是 convex set

则 2 又被称为 Convex Programming Problem，根据 convex function 的性质可知 $\c{X}$ 是个 convex set

对于 Convex Programming Problem，如果 $\b{x}^$ 为 regular point, 则 First Order KKT Condition 是 $\b{x}^$ 为 global minimum 的 nessesary and sufficient condition

• Proof:

  由于 $f(\b{x})$ 是 convex function，所以

  $$f(\b{x}) \geq f(\b{x}^*) + \nabla f(\b{x}^\*)^T (\b{x} - \b{x}^\*)$$

  由于 $\l_j^* \geq 0, h_j(\b{x}) \leq 0$，同时 $h_j(\b{x})$ 也是 convex function 所以有

  $$\begin{align*} f(\b{x}) \geq & f(\b{x}) + \sum_j \l_j^* h_j(\b{x}) \\\\ \geq & f(\b{x}^*) + \nabla f(\b{x}^\*)^T (\b{x} - \b{x}^\*) + \sum_j \l_j^* (h(\b{x}^\*) + \nabla h(\b{x}^\*)^T (\b{x} - \b{x}^\*)) \\\\ = & f(\b{x}^*) + \sum_j \l_j^\* h(\b{x}^\*) + (\nabla f(\b{x}^*) + \sum_j \l_j^\* \nabla h(\b{x}^\*))^T (\b{x} - \b{x}^\*) \\\\ = & f(\b{x}^*) \end{align*}$$

  也就是 $f(\b{x}) \geq f(\b{x}^), \;\forall \b{x} \in \c{X}$，所以 $\b{x}^$ 为 global minimum $\EOP$