バージョン管理された人

subversionで管理されてます

最適性条件

数学 最適化

最適化問題の最適性条件について

考える問題

考える問題は f: \mathbb{R}^n \to \mathbb{R}, g_i: \mathbb{R}^n \to \mathbb{R} \enspace (i = 1, \cdots, m)として、

\min f(\boldsymbol{x}) \enspace \text{s.t.} \, g_i(\boldsymbol{x}) \leq 0 \enspace (i = 1, \cdots, m)

という最適化問題。 等号条件 h(\boldsymbol{x}) = 0は

h(\boldsymbol{x}) \leq 0, h(\boldsymbol{x}) \geq 0

のように分解すればいいし、右辺に 0でない数値 yがくるような

g(\boldsymbol{x}) \leq y

といった条件は h(\boldsymbol{x}) = g(\boldsymbol{x}) - yとして

h(\boldsymbol{x}) \leq 0

のように変形すればいい。このような問題を制約付き最適化問題という。

許容領域

制約付き最適化問題において、

g_i(\boldsymbol{x}) \leq 0 \enspace (i = 1, \cdots, m)

で表される空間を許容領域とか実行可能領域とかいう。

アートボード 1許容領域
\min f(x) \enspace \text{s.t.} \, g_i(x) \leq 0 \enspace (i = 1, 2)の許容領域の例

局所的最適解

制約付き最適化問題の許容領域を F \subseteq \mathbb{R}^nとして、点 \boldsymbol{x}^* \in Fが

\exists \epsilon > 0, \forall \boldsymbol{x} \in B(\boldsymbol{x}^*, \epsilon) \cap F \implies f(\boldsymbol{x}^*) \leq f(\boldsymbol{x})

を満たすとき、 \boldsymbol{x}^*を局所的最適解(local optimum)という。ただし、 B(\boldsymbol{x}^*, \epsilon) = \{\boldsymbol{y} \mid \lVert\boldsymbol{x} - \boldsymbol{y}\rVert \lt \epsilon\}。

たとえば、 \min x^2 \enspace \text{s.t.} \, |x| \leq 1という問題の局所的最適解は x = 0である。

許容領域
\min x^2 \enspace \text{s.t.} \, |x| \leq 1

この例だと局所最適解は1つなのだけど、局所最適解は1つとは限らず複数個あることがる。たとえば \min \sin(x) \enspace \text{s.t.} \, x \in \lbrack-2\pi, 2\pi\rbrackだと、局所最適解は \pm\frac{\pi}{2}, \pm\frac{3}{2}\piの4つある。

John条件

\min f(\boldsymbol{x}) \enspace \text{s.t.} \, g_i(\boldsymbol{x}) \leq 0 \enspace (i = 1, \cdots, m)の局所最適解を \boldsymbol{x}^*としたとき、 \boldsymbol{x}^*は次の関係を満たすようなベクトル \boldsymbol{\xi} \neq \boldsymbol{0}が存在する:

\begin{array}{l} \xi_0\nabla f(\boldsymbol{x}^*) + \sum_{i=1}^m\xi_i\nabla g_i(\boldsymbol{x}^*) = \boldsymbol{0} \newline \xi_ig_i(\boldsymbol{x}^*) = 0 \enspace (i = 1, \cdots, m) \newline g_i(\boldsymbol{x}^*) \leq 0 \enspace (i = 1, \cdots, m) \newline \xi_i \geq 0 \enspace (i = 0, \cdots, m) \end{array}

このような条件を John条件(John condtion) という。つまり、これを調べれば \boldsymbol{x}^*が局所最適解か調べることができるのだ。しかし、この条件はあまり使われないで次に紹介するKKT条件の方が良く使われる。

KKT条件

カルーシュ・キューン・タッカー条件(karush-Kuhn-Tucker condition) という。ながいし発音しづらいのでKKT条件といわれることの方が圧倒的に多い。具体的にどんな条件かというと

\begin{array}{l} \nabla f(\boldsymbol{x}^*) + \sum_{i=1}^m\lambda_i\nabla g_i(\boldsymbol{x}^*) = \boldsymbol{0} \newline \lambda_ig_i(\boldsymbol{x}^*) = 0 \enspace (i = 1, \cdots, m) \newline g_i(\boldsymbol{x}^*) \leq 0 \enspace (i = 1, \cdots, m) \newline \lambda_i \geq 0 \enspace (i = 1, \cdots, m). \end{array}

John条件の各 \xi_i \enspace (i = 1, \cdots, m)を \xi_0で割ったものを \lambda_iにしたもの。 \boldsymbol{\lambda} = (\lambda_1, \cdots, \lambda_m)^TをKKTベクトルというらしい。あんまりそういう名称聞いたことない。

なんで \xi_0で割ったものを考えるのかというと、 \xi_0 = 0ということは最適性条件が目的関数に一切依存しないという自体を招き、そんな場合はかなり例外的な状況しかないから。理論系だとJohn条件よりもこっちの条件を良く使う。ただ、 \xi_0 = 0の条件を考えてないので、実際にはこの条件は必要条件ではないことに注意しなければいけないが、多くの非常に有用な条件となっている。