next up previous
Next: 5 次週予告 Up: 計算天文学 II 第8回 最適化(1) Previous: 3 連続関数の最適化

4 制約つき最適化

大抵の問題では、目的関数の定義域が実数全体ということはない。例えば、銀 河の回転曲線から質量分布を求めようというときには、質量はどこでも正でな ければならない。

このような制約にはいろんな場合があるが、制約が等式の場合はラグランジュ の未定乗数法が使えるのでこれは省略する。不等式の場合は話が難しくなる。

問題によっては厳密にできる場合もあるが、ここではペナルティ法というもの を紹介しておく。これは、


\begin{displaymath}
g_i(x) \ge 0, \quad i = 1, 2, ...,n
\end{displaymath} (20)

という制約のもとで $f(x)$ を最小化せよという問題を、 $f$$g_i$ を適 当に組み合わせて作った関数を制約なしで最小化せよという問題に置き換える。 具体的には、$\{g_i(x)\}$を、
\begin{displaymath}
\{g_i(x)\} = \cases{0, &$(g_i(x)\ge 0)$,\cr
g_i(x), & otherwize
}
\end{displaymath} (21)

つまり、制約条件を満たせば 0 、そうでなければ 0 でないような関数として
\begin{displaymath}
F(x) = f(x) + p\sum\{g_i(x)\}^2
\end{displaymath} (22)

を最小化する。で、答が求まる度にパラメータ $p$ の値を適当に大きくして いって、こちらの条件に見合う解になったら止める。

この方法では、制約条件のところに解があるとそれに境界の外側から近付く。 このために外点法と呼ばれる。内点法というのもあって、これは $F$

\begin{displaymath}
F(x) = f(x) + p\sum\frac{1}{g_i(x)}
\end{displaymath} (23)

とする。こちらでは、 $p$ を小さくするにしたがって領域の内側から真の解に近付く。



Jun Makino
平成16年12月6日