はじめに
お仕事の関係で、関数推定に関する論文を読んでいると「外点ペナルティ関数法」というものが出てきました。
ペナルティ関数法とはなんぞやと、今野・山下の『非線形計画法』を当たってみると、変換法という「制約付き最適化問題を制約なし最適化問題の列に変換して、後者を解くことによって前者の解を得ようとする方法」の一種であるようです。
…なるほど、わからん！！
ということで、この記事ではペナルティ関数法とその数学的な原理を説明します。証明も書いています！
記事の流れとしては、はじめに外点・内点・混合ペナルティ関数法がどのように定式化されるかを見ていきます。
次いで、その方法に従えばある条件のもとでは元の最適化問題の解が得られることを数学的に証明します。
具体例については別記事で、それぞれの方法の性質の証明とともに述べる予定です（が、検索すれば十分たくさん出てくるので書かないかもしれません）。
1. ペナルティ関数法の定式化
1.1 外点ペナルティ関数法
外点ペナルティ関数法では、関数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ と閉集合 $S \subset \mathbb{R}^n$ に対する、以下の制約付き最適化問題(P)を考えます。
$$
(\mathrm{P}) \quad
\begin{cases}
\mathrm{最小化} &\quad f(x) \\
\mathrm{条件} &\quad x \in S
\end{cases}
$$
定義（外点ペナルティ関数）
関数 $\Psi: \mathbb{R}^n \rightarrow \mathbb{R}$ が $S \subset \mathbb{R}^n$に関する外点ペナルティ関数であるとは、$\Psi$ が連続関数であって、以下の条件を満たすことをいいます。
$$
\begin{cases}
\Psi (x) = 0 &\quad (x \in S) \\
\Psi (x) > 0 &\quad (x \notin S)
\end{cases}
$$
定義（最適化問題(P)に対する拡張目的関数）
関数 $\Psi: \mathbb{R}^n \rightarrow \mathbb{R}$ を $S$ に関する外点ペナルティ関数とするとき、以下で定義される関数 $F_{\Psi}:\mathbb{R}^n \times \mathbb{R} \rightarrow \mathbb{R}$ を(P)に対する拡張目的関数といいます。
$$
F_{\Psi}(x, r) := f(x) + r \Psi (x)
$$
この定義のもと、無限大に発散する狭義単調増加な正数列$\{ r^k \}_{k \in \mathbb{N} } \subset \mathbb{R}$ に対して、拡張目的関数に対する制約なし最適化問題の列：
$$
(\mathrm{P_k}) \quad
\begin{cases}
\mathrm{最小化} &\quad F_{\Psi}(x, r^k) \\
\mathrm{条件} &\quad x \in \mathbb{R}^n
\end{cases}
$$
を考えることができます。このとき、適当な条件のもとで、最適化問題(P_k)の列に対する最適解の列 $\{ x^k \} \subset \mathbb{R}^n $ は $k \rightarrow \infty$ のとき元の最適化問題(P)の最適解 $x^{*} \in S$ に収束することが示せます（次章を参照）。したがって、制約付き最適化問題(P)を解くには、制約なし最適化問題の列(P_k)を解いていけばよいということになります。このようにして最適化問題(P)を解く方法を外点ペナルティ関数法あるいは外点法といいます。
1.2 内点ペナルティ関数法
内点ペナルティ関数法では、関数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ と、$\mathrm{int}(T) \neq \emptyset,~ \mathrm{cl}(\mathrm{int}(T)) = T$ なる $T \subset \mathbb{R}^n$ に対する、以下の制約付き最適化問題(Q)を考えます。
$$
(\mathrm{Q}) \quad
\begin{cases}
\mathrm{最小化} &\quad f(x) \\
\mathrm{条件} &\quad x \in T
\end{cases}
$$
以下では、上記の $\mathrm{int}(T) \neq \emptyset,~ \mathrm{cl}(\mathrm{int}(T)) = T$ という仮定を内点法の仮定と呼ぶことにします。内点法の仮定は $T$ の任意の点に $T$ の内点を通って近づけることを意味しています。
定義（内点ペナルティ関数）
$T \subset \mathbb{R}^n$ は内点法の仮定を満たすとします。関数 $\Phi: \mathrm{int}(T) \rightarrow \mathbb{R}$ が $T$ に関する内点ペナルティ関数であるとは、$\Phi$ が連続関数であって、以下の条件を満たすことをいいます。
$$
\begin{cases}
\Phi (x) \geq 0 &\quad (~ x \in \mathrm{int}(T) ~) \\
\Phi (x) \rightarrow \infty &\quad (~ x \rightarrow \partial T ~)
\end{cases}
$$
ここで、$\partial T := \mathrm{cl}(T) \setminus \mathrm{int}(T) = T \setminus \mathrm{int}(T)$ は $T$ の境界であり、$\Phi (x) \rightarrow \infty ~~ ( x \rightarrow \partial T )$ とは、任意の $z \in \partial T$ と $x_k \rightarrow z$ なる任意の点列 $\{ x_k \}_{k \in \mathbb{N}} \subset \mathrm{int}(T)$ について $\Phi(x_k) \rightarrow \infty ~~ (k \rightarrow \infty )$となることをいいます。
定義（最適化問題(Q)に対する拡張目的関数）
$T \subset \mathbb{R}^n$ は内点法の仮定を満たすとします。関数 $\Phi: \mathrm{int}(T) \rightarrow \mathbb{R}$ を $T$ に関する内点ペナルティ関数とするとき、以下で定義される関数 $F_{\Phi}:\mathrm{int}(T) \times \mathbb{R} \rightarrow \mathbb{R}$ を(Q)に対する拡張目的関数といいます。
$$
F_{\Phi}(x, t) := f(x) + t \Phi (x)
$$
この定義のもと、0に収束する狭義単調減少な正数列$\{ t^k \}_{k \in \mathbb{N} } \subset \mathbb{R}$ に対して、拡張目的関数に対する制約なし最適化問題の列：
$$
(\mathrm{Q_k}) \quad
\begin{cases}
\mathrm{最小化} &\quad F_{\Phi}(x, t^k) \\
\mathrm{条件} &\quad x \in \mathrm{int}(T)
\end{cases}
$$
を考えることができます。このとき、適当な条件のもとで、最適化問題(Q_k)の列に対する最適解の列 $\{ x^k \} \subset \mathrm{int}(T) $ は $k \rightarrow \infty$ のとき元の最適化問題(Q)の最適解 $x^{*} \in T$ に収束することが示せます（次章を参照）。したがって、制約付き最適化問題(Q)を解くには、制約なし最適化問題の列(Q_k)を解いていけばよいということになります。このようにして最適化問題(Q)を解く方法を内点ペナルティ関数法あるいは内点法といいます。
1.3 混合ペナルティ関数法
混合ペナルティ関数法では、関数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ および $S \cap \mathrm{int}(T) \neq \emptyset$ なる閉集合 $S \subset \mathbb{R}^n$ と内点法の仮定を満たす $T \subset \mathbb{R}^n$ に対する、以下の制約付き最適化問題(M)を考えます。
$$
(\mathrm{M}) \quad
\begin{cases}
\mathrm{最小化} &\quad f(x) \\
\mathrm{条件} &\quad x \in S \cap T
\end{cases}
$$
定義（最適化問題（M）に対する拡張目的関数）
関数 $\Psi: \mathbb{R}^n \rightarrow \mathbb{R}$ を $S$ に関する外点ペナルティ関数とし、関数 $\Phi: \mathrm{int}(T) \rightarrow \mathbb{R}$ を $T$ に関する内点ペナルティ関数とします。このとき、以下で定義される関数 $F_{\Psi, \Phi}:\mathrm{int}(T) \times \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ を(M)に対する拡張目的関数といいます。
$$
F_{\Psi, \Phi}(x, r, t) := f(x) + r \Psi(x) + t \Phi (x)
$$
この定義のもと、無限大に発散する狭義単調増加な正数列 $\{r^k \}$ と 0 に収束する狭義単調減少な正数列 $\{ t^k \}$ に対して、拡張目的関数に対する制約なし最適化問題の列：
$$
(\mathrm{M_k}) \quad
\begin{cases}
\mathrm{最小化} &\quad F_{\Psi, \Phi}(x, r^k, t^k) \\
\mathrm{条件} &\quad x \in \mathrm{int}(T)
\end{cases}
$$
を考えることができます。このとき、適当な条件のもとで、最適化問題(M_k)の列に対する最適解の列 $\{ x^k \} \subset \mathrm{int}(T) $ は $k \rightarrow \infty$ のとき元の最適化問題(Q)の最適解 $x^{*} \in S \cap T$ に収束することが示せます（次章を参照）。したがって、制約付き最適化問題(M)を解くには、制約なし最適化問題の列(M_k)を解いていけばよいということになります。このようにして最適化問題(M)を解く方法を混合ペナルティ関数法あるいは混合法といいます。
注意
- $T = \mathbb{R}^n$ かつ $\Phi = 0$ とすると混合ペナルティ関数法は外点ペナルティ関数法と一致します。
- $S = \mathbb{R}^n$ かつ $\Psi = 0$ とすると混合ペナルティ関数法は内点ペナルティ関数法と一致します。
2. ペナルティ関数法の原理
この章では混合ペナルティ関数法について以下の定理を証明します。すぐ上の注意のように置くことで外点法、内点法でも同じ定理が成り立つことに注意してください。
定理１
$f:\mathbb{R}^n \rightarrow \mathbb{R}$ は連続であるとします。また、$S \cap \mathrm{int}(T) \neq \emptyset$ なる閉集合 $S \subset \mathbb{R}^n$ と内点法の仮定（$\mathrm{int}(T) \neq \emptyset$, $\mathrm{cl}(\mathrm{int}(T)) = T$）を満たす $T \subset \mathbb{R}^n$ について、最適化問題(M)の最適解で $\mathrm{cl}(S \cap \mathrm{int}(T))$ に属するものが存在するとします。さらに、すべての $k$ について最適化問題($M_k$)は最適解$x^k$をもつと仮定します。このとき、以下のことが成り立ちます。
- $\{ x^k \}$ の任意の集積点$\hat{x}$は最適化問題(M)の解
- $\lim_{k \rightarrow \infty} r^k \Psi(x^k) = 0$
- $\lim_{k \rightarrow \infty} t^k \Phi(x^k) = 0$
1の証明
$\{ x^k \}$の部分列で$\hat{x}$に収束するものが取れます。この部分列を改めて$\{x^k\}$と表すことにしましょう。
(a) $\hat{x} \in S \cap T$の証明：
まず、問題($M_k$)は $\mathrm{int}(T)$ で解を探すので各 $k$ について $x^k \in \mathrm{int}(T) \subset T$ であり、仮定より $T$は閉集合であるため $\hat{x} \in T$です。次に、$\hat{x} \notin S$ であるとします。すると外点ペナルティ関数の定義より $ \Psi(\hat{x}) > 0$となり、$r^k \rightarrow \infty$ であるので、$\Psi$の連続性と合わせて
$$
\lim_{k \rightarrow \infty} r^k \Psi(x^k) = \infty
$$
となります。また、$f$と$\Phi$の連続性により$\hat{x}$のある近傍上で$f$と$t^k \Phi$は下に有界となるので、結局
$$
\lim_{k \rightarrow \infty} F(x^k, r^k, t^k) = \infty
$$
がわかります。一方で、仮定より$S \cap \mathrm{int}(T) \neq \emptyset$なので$\bar{x} \in S \cap \mathrm{int}(T)$を取ることができ、$\Psi(\bar{x}) = 0$ かつ $0 \leq \Phi(\bar{x}) < \infty$ となります。すると、$t^k \rightarrow 0$ より、
$$
\lim_{k \rightarrow \infty} F(\bar{x}, r^k, t^k) = f(\bar{x}) < \infty
$$
となるので、十分大きいある$k$について
$$
F(x^k, r^k, t^k) > F(\bar{x}, r^k, t^k)
$$
となります。これは $x^k$ が 最小化問題($M_k$)の最適化であることに反します。よって、$x \in S$ となります。
(b) $\hat{x}$の最適性の証明：
$\hat{x}$が問題(M)の最適解でないと仮定して矛盾を導きましょう。仮定から問題(M)は最適解$x^{*} \in \mathrm{cl}(S \cap \mathrm{int}(T))$をもちます。このとき、閉包の定義から任意の $\delta > 0$ について $B_n(x^{*}, \delta) \cap S \cap \mathrm{int}(T) \neq \emptyset$ となります。いま、$f(x^{*}) < f(\hat{x})$であり、$f$は連続ですので、ある $\delta > 0$ が存在して、
$$
f(x^{*}) \leq f(x) < f(\hat{x}) ~~~~(\forall x \in B_n(x^{*}, \delta) \cap S \cap \mathrm{int}(T))
$$
となります。そこで、$\bar{x} \in B_n(x^{*}, \delta) \cap S \cap \mathrm{int}(T)$ を固定すると、$\Psi(\bar{x}) = 0$ かつ $0 \leq \Phi(\bar{x}) < \infty$となり、$t^k \rightarrow 0$ と $f(x^k) \leq F(x^k, r^k, t^k)$ と $x^k \rightarrow \hat{x}$ により、
$$
\lim_{k \rightarrow \infty} F(\bar{x}, r^k, t^k) = f(\bar{x}) < f(\hat{x}) \leq \liminf_{k \rightarrow \infty} F(x^k, r^k, t^k)
$$
となります。よって、ある$k$が存在して
$$
F(\bar{x}, r^k, t^k) < F(x^k, r^k, t^k)
$$
となります。これは $x^k$ が最小化問題($M_k$)の最適解であることに反します。
2, 3の証明
2, 3のうち少なくともひとつが成り立たないと仮定しましょう。一般に、数列$\{a_k\}$ について$a_k \rightarrow \alpha$ となるとき、任意の$\{b_k\} \subset \mathbb{R}$に対して
$$
\limsup_{k \rightarrow \infty} (a_k + b_k) = \alpha + \limsup_{k \rightarrow \infty} b_k
$$
が成り立つ（補足参照）ので、
$$
\limsup_{k \rightarrow \infty} F(x^k, r^k, t^k) = f(\hat{x}) + \limsup_{k \rightarrow \infty} (r^k \Psi(x^k) + t^k \Phi(x^k))
$$
となります。したがって、$0 \leq r^k \Psi(x^k), t^k \Phi(x^k)$ に注意すると、ある $\varepsilon > 0$ が存在して、
$$
\limsup_{k \rightarrow \infty} F(x^k, r^k, t^k) > f(\hat{x}) + \varepsilon
$$
となります。一方、問題(M)の最適解 $x^{*} \in \mathrm{cl}(S \cap \mathrm{int}(T))$ をとると、$f$ の連続性により $\delta > 0$ が存在して
$$
f(x^{*}) + \varepsilon > f(x) ~~~~(\forall x \in B_n(x^{*}, \delta) \cap S \cap \mathrm{int}(T))
$$
となります。そこで、$B_n(x^{*}, \delta) \cap S \cap \mathrm{int}(T) \neq \emptyset$ の元 $\bar{x}$ を固定すると、最適性より $f(\hat{x}) = f(x^{*})$ なので
$$
\limsup_{k \rightarrow \infty} F(x^k, r^k, t^k) > f(\hat{x}) + \varepsilon = f(x^{*}) + \varepsilon > f(\bar{x}) = \lim_{k \rightarrow \infty} F(\bar{x}, r^k, t^k)
$$
となります。よって、ある $k$ について
$$
F(x^k, r^k, t^k) > F(\bar{x}, r^k, t^k)
$$
となりますが、これは $x^k$ の最適性に反します。
3. 数学的な補足
3.1 上極限、下極限の定義と性質
実数列 $\{a_n \}$ の上極限 $\limsup_{n \rightarrow \infty} a_n$ と 下極限 $\liminf_{n \rightarrow \infty} a_n$ はそれぞれ以下のように定義されます。
- $\limsup_{n \rightarrow \infty} a_n := \inf_{k \in \mathbb{N}} (\sup_{n \geq k} a_n) $
- $\liminf_{n \rightarrow \infty} a_n := \sup_{k \in \mathbb{N}} (\inf_{n \geq k} a_n) $
これらは実数の連続性により無限大を許せば常に存在します。
さて、上極限と下極限が等しいときに極限値が存在し上極限と等しくなり、その逆も成り立つことについてはググってもらえばすぐに証明が見つかるので、ここでは以下の事実を証明しましょう。
事実
実数列 $\{ a_n \}$ が収束するとき、任意の実数列 $\{ b_n \}$について
$$
\limsup_{n \rightarrow \infty} (a_n + b_n) = \lim_{n \rightarrow \infty} a_n + \limsup_{n \rightarrow \infty} b_n.
$$
証明
まず、任意の $k \in \mathbb{N}$ と 任意の自然数 $n \geq k$ について
$$
a_n + b_n \leq \sup_{j \geq k} a_j + \sup_{j \geq k} b_j
$$
ですので
$$
\limsup_{n \rightarrow \infty} (a_n + b_n) = \inf_{m \in \mathbb{N}}\sup_{j \geq m} (a_j + b_j) \leq \sup_{j \geq k} (a_j + b_j) \leq \sup_{j \geq k} a_j + \sup_{j \geq k} b_j ~~~~~(*)
$$
となります。ここで、任意の実数列 $\{ c_n\}$ に対して、$\{ \sup_{j \geq m} c_j \}$ は $\mathbb{R} \cup \{ \infty, -\infty \}$ において収束し、
$$
\lim_{m \rightarrow \infty} ( \sup_{j \geq m} c_j ) = \inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j ~(= \limsup_{n \rightarrow \infty} c_n)
$$
となることを示しましょう。まず、任意の $m \in \mathbb{N}$ に対して、$\sup_{j \geq m} c_j = \infty$ なる場合は両辺とも $\infty$ として等式が成り立ちます。$\{ \sup_{j \geq m} c_j \}$ が下に有界でない場合、$\{ \sup_{j \geq m} c_j \}$ は単調減少なので両辺 $-\infty$ として等式が成り立ちます。それ以外の場合では、$-\infty < \inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j$ ですので、任意の $\varepsilon > 0$ に対して $N \in \mathbb{N}$ が存在して、
$$
\sup_{j \geq N} c_j < \inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j + \varepsilon
$$
となります。したがって、任意の $n \geq N$に対して
$$
\inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j \leq \sup_{j \geq n} c_j \leq \sup_{j \geq N} c_j < \inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j + \varepsilon
$$
となり、$\inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j < \infty$より
$$
0 \leq \sup_{j \geq n} c_j - \inf_{m \in \mathbb{N}} \sup_{j \geq m} c_j < \varepsilon
$$
なので等式が成り立ちます。そこで、$(*)$ において $k \rightarrow \infty$ として、
$$
\limsup_{n \rightarrow \infty} (a_n + b_n) \leq \limsup_{n \rightarrow \infty} a_n + \limsup_{n \rightarrow \infty} b_n = \lim_{n \rightarrow \infty} a_n + \limsup_{n \rightarrow \infty} b_n
$$
となります。ただし、最後の等号に $\{ a_n \}$ が収束することを使いました。同様に、
$$
\begin{align}
\limsup_{n \rightarrow \infty} b_n
&= \limsup_{n \rightarrow \infty} ( (a_n + b_n) - a_n) \\
&\leq \limsup_{n \rightarrow \infty} (a_n + b_n) + \limsup_{n \rightarrow \infty} (-a_n) \\
&= \limsup_{n \rightarrow \infty} (a_n + b_n) + \lim_{n \rightarrow \infty} (-a_n) \\
&= \limsup_{n \rightarrow \infty} (a_n + b_n) - \lim_{n \rightarrow \infty} a_n
\end{align}
$$
となります。よって、
$$
\lim_{n \rightarrow \infty} a_n + \limsup_{n \rightarrow \infty} b_n \leq \limsup_{n \rightarrow \infty} (a_n + b_n) \leq \lim_{n \rightarrow \infty} a_n + \limsup_{n \rightarrow \infty} b_n
$$
となり、所望の等式が得られました。
4. 参考文献
- 今野浩、山下浩. 非線形計画法. 日科技連.