大学数学基礎解説

KKT条件の導出

数理計画法,KKT条件

3598

はじめに

制御工学で非線形計画のKarush-Kuhn-Tucker条件(KKT条件)を触れることがあったのでまとめる。非専門分野なのでご指摘頂けると嬉しいです。

不等式制約と等式制約付き非線形計画のKKT条件

この節では、不等式制約と等式制約付き非線形計画のKKT条件について触れる。KKT条件は、非線形計画問題の最適性の必要条件である。非線形計画は下式で与えるとする。

$\begin{array}{rcl} min & f (x) \\ s . t . & g_{i} (x) \leq 0 \\ (1) & h_{j} (x) = 0 \end{array}$

このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。

$\begin{array}{rclr} (2.1) & \nabla f (x) + \sum_{i = 1}^{m} y_{i} & \nabla g_{i} (x) + \sum_{j = 1}^{l} z_{i} \nabla & h_{j} (x) = 0, \\ (2.2) & h_{j} (x) = 0, \\ (2.3) & g_{i} (x) \leq 0, \\ (2.4) & y_{i} \geq 0, \\ (2.5) & y_{i} g_{i} (x) = 0 \end{array}$

Farkasの補題からのKKT条件の導出

KKT条件をFarkasの補題を用いて導出する。局所最適解近傍に着目してFarkasの補題を用いて導出するのが基本的な方針である。

Farkasの補題

任意の行列 $A$ と任意のベクトル $b$ に対して次の命題がいずれか一方が成り立つ。
(1) $A x = b$ 、 $x \geq 0$ を満たす $x$ が存在する。
(2) $A^{T} y \leq 0$ 、 $b^{T} y > 0$ を満たす $y$ が存在する。

Farkasの補題から簡単な式変形をすることで系１を得る。

次の命題がいずれか一方が成り立つ。
(1) $A u + B v + c = 0$ 、 $u \geq 0$ を満たす $u$ 、 $v$ が存在する。
(2) $A^{T} y \leq 0$ 、 $B^{T} y = 0$ 、 $c^{T} y < 0$ を満たす $y$ が存在する。

$A = [A, B, - B], x = [u, v_{+}, v_{-}]^{T}, v = v_{+} - v_{-}, b = - c$ とおく。Farkasの補題より系１が求まる。

Mangasarizan-Fronovitz制約を想定する(MF制約想定)。

MF制約想定とは
$\nabla h_{j} (x) (j = 1, 2, . . l)$ は1次独立である。 $\nabla g_{i} (x)^{T} s < 0$ かつ $\nabla h_{j} (x)^{T} s = 0$ を満たす $s$ が存在する。ただし、 $I (x) = ｛ i | g_{i} (x) = 0 ｝$ である。

$x^{*}$ を式（１）の局所最適解とする。ただし、 $f$ 、 $h_{j}$ は微分可能であるものとする。このとき、以下を満たす $s$ は存在しない。

$\begin{array}{r} \nabla f (x)^{T} s < 0 \\ \nabla g_{i} (x)^{T} s < 0 \\ (3) & \nabla h_{j} (x)^{T} s = 0 \end{array}$

許容方向 $s$ が存在すると仮定する。 $x^{*}$ が局所最適解であるとする。

不等式制約について、

$\begin{array}{r} g_{i} (x^{*} + α s) = g_{i} (x^{*}) + α \nabla g_{i} (x^{*})^{T} s + o (α) \end{array}$

十分小さい $α$ では $g_{i} (x^{*} + α s) < 0$ であり、不等式制約を満たすことがわかる。

等式制約について

$\begin{array}{r} h_{j} (x^{*} + α s) = h_{j} (x^{*}) + α \nabla h_{j} (x^{*})^{T} s + o (α) \end{array}$

十分小さい $α$ では $h_{j} (x^{*} + α s) = 0$ であり、等式制約を満たすことがわかる。

$x^{*}$ は局所最適解であるので、十分小さい $α$ では下式が成り立つ。

$\begin{array}{r} f (x^{*} + α s) = f (x^{*}) + α f (x^{*})^{T} s \geq f (x^{*}) \end{array}$

しかし、 $\nabla f (x^{*})^{T} s < 0$ なので矛盾する。よって、 $s$ は存在しない。

&&&　KKT条件
$\begin{array}{rclr} (2.1) & \nabla f (x) + \sum_{i = 1}^{m} y_{i} & \nabla g_{i} (x) + \sum_{j = 1}^{l} z_{i} \nabla & h_{j} (x) = 0, \\ (2.2) & h_{j} (x) = 0, \\ (2.3) & g_{i} (x) \leq 0, \\ (2.4) & y_{i} \geq 0, \\ (2.5) & y_{i} g_{i} (x) = 0 \end{array}$

&&&prf KKT条件の導出

式(3)より系1(2)が成り立たないことがわかる。よって、系1(1)が成り立つ。

$\begin{array}{rclr} \nabla f (x) + \sum_{i \in I (x)} y_{i} & \nabla g_{i} (x) + \sum_{j = 1}^{l} z_{i} \nabla & h_{j} (x) = 0 \\ y_{i} \geq 0 \end{array}$

$i \notin I (x)$ のとき $y_{i} = 0$ とおけば、 $y_{i} \nabla g_{i} (x) = 0$ 、 $y_{i} g_{i} (x) = 0$ である。

$\begin{array}{rclr} \nabla f (x) + \sum_{i = 1}^{m} y_{i} & \nabla g_{i} (x) + \sum_{j = 1}^{l} z_{i} \nabla & h_{j} (x) = 0 \\ y_{i} \geq 0 \\ y_{i} g_{i} (x) = 0 \end{array}$

等式制約と不等式制約を満足する必要があることを思い出せば下式を得る。

$\begin{array}{rc} h_{j} (x) = 0, \\ g_{i} (x) \leq 0 \end{array}$

以上より、式（2.1）～(2.5)のKKT条件を得る。

引用

ラグランジュ双対関数からのKKT条件の導出

KKT条件をラグランジュ双対関数を用いて導出する。ラグランジュ双対関数とSlaterの制約に着目して、強双対定理を仮定してKKT条件を導出するのが基本的な方針である。

引用

不等式制約付き非線形計画のKKT条件

この節では、不等式制約付き非線形計画のKKT条件について触れる。
非線形計画は下式で与えるとする。

$\begin{array}{rcl} min & f (x) \\ (4) & s . t . & g_{i} (x) \leq 0 \end{array}$

このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。

$\begin{array}{rcl} (5.1) & \nabla f (x) + \sum_{i = 1}^{m} y_{i} & \nabla g_{i} (x) = 0, \\ (5.2) & g_{i} (x) \leq 0, \\ (5.3) & y_{i} \geq 0, \\ (5.4) & y_{i} g_{i} (x) = 0 \end{array}$

Fritz Johnの定理からのKKT条件の導出

KKT条件をFritz Johnの定理を用いて導出する。
局所最適解近傍に着目してGordanの二者択一の定理を用いてFritz Johnの定理を導出し、その後線形独立制約を想定してKKT条件を導出するのが基本的な方針である。はじめにFritz Johnの定理とGordanの二者択一定理を紹介し、Fritz　Johnの定理を導出する。

Fritz Johnの定理

不等式制約つき問題の局所最適解 $x$ において、 $f$ 、 $g_{i}$ が微分可能ならば、 $(z_{0}, z) \neq (0, 0)$ となる実数 $z_{0}$ と $l$ 次元ベクトル $z$ が存在し、式(6)が成り立つ。

$\begin{array}{rc} z_{0} \nabla f (x) + \sum_{i = 1}^{l} z_{i} \nabla g_{i} (x) = 0, \\ g_{i} (x) \leq 0, \\ z_{i} \leq 0, \\ (6) & z_{i} g_{i} (x) = 0. \end{array}$

Gordanの二者択一定理

任意の行列 $A$ に対して次の命題がいずれか一方が成り立つ。
(1) $A x > 0$ を満たす $x$ が存在する。
(2) $A^{T} y = 0$ 、 $y \geq 0$ 、 $y \neq 0$ を満たす $y$ が存在する。

Fritz Johnの定理の導出

$x^{*}$ が局所最適解ならば式7を満たすベクトル $s$ は存在しない。

$\begin{array}{r} \nabla f (x)^{T} s < 0 \\ (7) & \nabla g_{i} (x)^{T} s < 0, i \in I (x) \end{array}$

式7より、 $A x > 0$ を満たす $x$ は存在しない。
ただし、

$\begin{array}{r} A = (\begin{array}{ccc} - \nabla f (x)^{T} \\ - \nabla g_{1} (x)^{T} \\ ⋮ \\ - \nabla g_{k} (x)^{T} \end{array}) \end{array}$

Gordanの二者択一定理(1)が成り立たないので(2)が成り立つ。つまり、 $A^{T} y = 0$ 、 $y \geq 0$ 、 $y \neq 0$ を満たす $y$ が存在する。

$\begin{array}{r} A^{T} y = (- \nabla f (x), - \nabla g_{1} (x), \dots, - \nabla g_{k} (x)) (\begin{array}{ccc} y_{0} \\ y_{1} \\ ⋮ \\ y_{k} \end{array}) \\ = - y_{0} \nabla f (x) - y_{1} \nabla g_{1} (x) \dots - y_{k} \nabla g_{k} (x) = 0 \end{array}$

まとめると、

$\begin{array}{r} y_{0} \nabla f (x) + \sum_{i \in I (x)} y_{i} \nabla g_{i} (x) = 0 \end{array}$

$i \notin I (x)$ のとき、 $y_{i} = 0$ とおけば、 $y_{i} \nabla g_{i} (x) = 0$ 、 $y_{i} g_{i} (x) = 0$ である。
$i \in I (x)$ のとき $g_{i} (x) = 0$ なので $y_{i} g_{i} (x) = 0$ である。

不等式制約 $g_{i} (x) \leq 0$ を満たす必要があることを思い出せば、Fritz Johnの定理を得る。

$\begin{array}{rc} y_{0} \nabla f (x) + \sum_{i = 1}^{l} y_{i} \nabla g_{i} (x) = 0, \\ g_{i} (x) \leq 0, \\ y_{i} \leq 0, \\ y_{i} g_{i} (x) = 0. \end{array}$

KKT条件の導出

線形独立制約を想定する。Fritz Johnの定理より $y_{0} = 0$ と仮定すると、線形独立制約想定より $y_{i} = 0$ となり矛盾する。よって、 $y_{0} > 0$ である。 $y_{i} = y_{i} / y_{0}$ と改めて書き直せばKKT条件をえる。

$\begin{array}{rcl} \nabla f (x) + \sum_{i = 1}^{m} y_{i} & \nabla g_{i} (x) = 0, \\ g_{i} (x) \leq 0, \\ y_{i} \geq 0, \\ y_{i} g_{i} (x) = 0 \end{array}$