罰金法(penalty method)とは、制約付きの最小化問題を、制約が満たされない度合いに応じた罰の項 $\mu p(x)$ を目的関数に足した制約なしの問題の列で近似して解く方法である。目的関数と罰金関数が連続で、最適値以下の目的関数の値をとる点の集合が有界なら、$\mu\to\infty$ で最小点の集積点は最適解で、最適値に収束する。滑らかな罰金では、目的関数の勾配が 0 でない最適解は有限の重みでは得られないが、絶対値の罰金では、Lagrange 関数を最小にする乗数より大きい重みで最小点の全体が最適解の全体に一致する。内側から近づく障壁法も、実行可能集合がコンパクトで内部の閉包に等しければ収束する。
前提知識: 数理最適化, 目的関数, Karush–Kuhn–Tucker条件
罰金法(penalty method)とは、制約付きの最小化問題を、制約が満たされない度合いに応じた罰(ペナルティ)の項を目的関数に足した制約なしの問題の列で近似して解く方法である。罰の重み $\mu$ を大きくしていくと、罰金を足した関数の最小点は(thm-pen-convergence の仮定のもとで)最適解の集合に近づく。罰の項が実行可能集合の外で働くので外点法とも呼ばれ、実行可能集合の内側から近づく 障壁法(内点法の基本形)と対になる。
制約付きの問題を制約なしの問題に直せば、勾配降下法・Newton 法などの制約なしの解法がそのまま使える。代わりに考えるべきことは 3 つある。重みを大きくしたとき本当に最適解に近づくか(thm-pen-convergence)、有限の重みで最適解そのものが得られるか(滑らかな罰金ではふつう得られない:prop-pen-smooth。絶対値の罰金では、Lagrange 関数を最小にする乗数があれば、それより大きい重みで得られる:thm-pen-exact)、内側から近づく障壁法でも同じことが言えるか(thm-pen-barrier)である。
以下、$f\colon\mathbb{R}^n\to\mathbb{R}$ と空でない集合 $X\subset\mathbb{R}^n$ について、問題
$$
\text{(P)}\qquad\text{最小化 } f(x)\quad\text{条件 } x\in X
$$
を考え、その最適値を $p^*:=\inf_{x\in X}f(x)$、最適解の全体を $X^*$ と書く。
連続関数 $p\colon\mathbb{R}^n\to[0,\infty)$ で、$p(x)=0$ と $x\in X$ が同値であるものを、$X$ の 罰金関数 という。$\mu>0$ について
$$
Q_\mu(x):=f(x)+\mu\,p(x)\qquad(x\in\mathbb{R}^n)
$$
とおく。$\mu_k\to\infty$ となる正の数の列をとり、各 $k$ で $Q_{\mu_k}$ を $\mathbb{R}^n$ 全体で最小化して (P) を近似する方法を 罰金法 という。
罰金関数があれば $X=p^{-1}(0)$ は閉集合である。$X$ が不等式と等式
$$
X=\{x\in\mathbb{R}^n\mid g_i(x)\le0\ (1\le i\le m),\ h_j(x)=0\ (1\le j\le l)\}
$$
($g_i,h_j$ は連続)で与えられるとき、$g_i^+(x):=\max(g_i(x),0)$ として、次がよく使われる罰金関数である。
$f$ と罰金関数 $p$ を連続とし、$\mu_k>0$、$\mu_k\to\infty$ とする。各 $k$ で $x_k$ が $Q_{\mu_k}$ の $\mathbb{R}^n$ 全体での最小点であるとし、集合 $K:=\{x\in\mathbb{R}^n\mid f(x)\le p^*\}$ が有界であるとする。このとき次が成り立つ。
$x\in X$ なら $p(x)=0$ なので、$x_k$ の最小性から $f(x_k)\le Q_{\mu_k}(x_k)\le Q_{\mu_k}(x)=f(x)$ である。$x\in X$ について下限をとると
$$
f(x_k)\le Q_{\mu_k}(x_k)\le p^*\qquad\text{(a)}
$$
である。$Q_{\mu_k}(x_k)$ は実数なので $p^*>-\infty$ で、$X\ne\emptyset$ なので $p^*< \infty$ である。(a) より $x_k\in K$ であり、$K$ は連続関数 $f$ の劣位集合として閉、仮定により有界なのでコンパクトである。
1:$x_{k_l}\to\bar x$ とする。$\bar x\in K$ なので $f(\bar x)\le p^*$ である。$c:=\min_Kf$ とおくと、(a) から $\mu_{k_l}p(x_{k_l})\le p^*-f(x_{k_l})\le p^*-c$ なので $p(x_{k_l})\le(p^*-c)/\mu_{k_l}\to0$ で、$p$ の連続性から $p(\bar x)=0$、すなわち $\bar x\in X$ である。よって $f(\bar x)\ge p^*$ で、$f(\bar x)=p^*$ となり $\bar x$ は最適解である。$K$ はコンパクトなので集積点はあり、$X^*\ne\emptyset$ である。
2:$(f(x_k))$ の任意の部分列は、$K$ のコンパクト性からさらに $x_{k}$ が収束する部分列をもち、1 によりその極限で $f$ の値は $p^*$ である。よって $f(x_k)\to p^*$ である。(a) から $0\le\mu_kp(x_k)\le p^*-f(x_k)\to0$、$f(x_k)\le Q_{\mu_k}(x_k)\le p^*$ から $Q_{\mu_k}(x_k)\to p^*$ である。
3:そうでないとすると、$\delta>0$ と部分列で $\operatorname{dist}(x_{k_l},X^*)\ge\delta$ となるものがある。さらに部分列をとって収束させると、極限は 1 により $X^*$ の点で、距離が $0$ に近づくことに反する。$\square$
$K$ の有界性は、たとえば $f(x)\to\infty$($\lvert x\rvert\to\infty$)なら成り立つ。この定理では $\mu_k$ の単調性を仮定していない。$\mu_k$ が単調に増えるときに $p(x_k)$ が単調に減り $f(x_k)$ が単調に増えることは、非線形計画法 の定理「罰金法の収束」が 2 次の罰金について示している(その証明は $p$ が罰金関数であることしか使わない)。
罰金法の弱点は、$\mu$ を大きくすると $Q_\mu$ が実行可能集合の境界に沿って急な谷をもち、数値的に解きにくくなることである(非線形計画法 の節「罰金法」の後半)。有限の $\mu$ で最適解そのものが得られれば、この問題は起きない。しかし、罰金関数が滑らかだとそれは望めない。
$x^*\in X$ で $f$ と罰金関数 $p$ が微分可能であるとする。このとき $\nabla p(x^*)=0$ であり、すべての $\mu>0$ で $\nabla Q_\mu(x^*)=\nabla f(x^*)$ である。とくに $\nabla f(x^*)\ne0$ なら、どの $\mu>0$ についても $x^*$ は $Q_\mu$ の局所最小点でない。
$p\ge0$ かつ $p(x^*)=0$ なので、$x^*$ は $p$ の最小点であり、微分可能な関数の最小点では勾配が $0$ である。よって $\nabla Q_\mu(x^*)=\nabla f(x^*)+\mu\nabla p(x^*)=\nabla f(x^*)$ である。局所最小点では勾配が $0$ なので、$\nabla f(x^*)\ne0$ なら $x^*$ は $Q_\mu$ の局所最小点でない。$\square$
制約が効いている最適解では、ふつう $\nabla f(x^*)\ne0$ である($\nabla f(x^*)=0$ なら制約がなくても停留点である)。そのとき 2 次の罰金 $p_2$ では、どの有限の $\mu$ でも最適解は得られない。一方、絶対値の罰金 $p_1$ は境界で微分できず、この命題は当てはまらない。実際、Lagrange 関数を最小にする乗数があれば、それより大きい重みで正確になる。KKT 条件を満たす乗数というだけでは足りない。$f(x)=-x^2$、$h(x)=x$ では $x^*=0$、$\nu=0$ が KKT 条件を満たすが、$-x^2+\mu\lvert x\rvert$ はどの $\mu$ でも下に有界でない。
$X$ を上の $g_i,h_j$ で与えられる集合とし、$p_1$ を絶対値の罰金とする。$x^*\in X$、$\lambda\in\mathbb{R}^m$、$\nu\in\mathbb{R}^l$ が
$$
\lambda_i\ge0,\qquad\lambda_ig_i(x^*)=0\ (1\le i\le m),\qquad L(x^*)=\min_{x\in\mathbb{R}^n}L(x),\quad L(x):=f(x)+\sum_i\lambda_ig_i(x)+\sum_j\nu_jh_j(x)
$$
を満たすとし、$\bar\mu:=\max\bigl(\lambda_1,\dots,\lambda_m,\lvert\nu_1\rvert,\dots,\lvert\nu_l\rvert\bigr)$ とおく($m=l=0$ なら $\bar\mu:=0$)。
$h_j(x^*)=0$ と $\lambda_ig_i(x^*)=0$ より $L(x^*)=f(x^*)$ である。任意の $x\in\mathbb{R}^n$ で $L(x)\ge f(x^*)$ なので
$$
f(x)\ge f(x^*)-\sum_i\lambda_ig_i(x)-\sum_j\nu_jh_j(x)\ge f(x^*)-\sum_i\lambda_ig_i^+(x)-\sum_j\lvert\nu_j\rvert\lvert h_j(x)\rvert
$$
である($\lambda_i\ge0$ と $g_i\le g_i^+$、$-\nu_jh_j\le\lvert\nu_j\rvert\lvert h_j\rvert$ を使った)。両辺に $\mu p_1(x)$ を足すと
$$
f(x)+\mu p_1(x)\ge f(x^*)+\sum_i(\mu-\lambda_i)g_i^+(x)+\sum_j(\mu-\lvert\nu_j\rvert)\lvert h_j(x)\rvert\qquad\text{(b)}
$$
である。
1:$x\in X$ なら $p_1(x)=0$ で、(b) の右辺の和は $0$ なので $f(x)\ge f(x^*)$ であり、$x^*$ は最適解である。$\mu\ge\bar\mu$ なら (b) の右辺の和は $0$ 以上で、$f(x)+\mu p_1(x)\ge f(x^*)=f(x^*)+\mu p_1(x^*)$ である。
2:$\mu>\bar\mu$ とする。1 から $f+\mu p_1$ の最小値は $f(x^*)$ である。$\hat x$ が最小点なら、(b) から $\sum_i(\mu-\lambda_i)g_i^+(\hat x)+\sum_j(\mu-\lvert\nu_j\rvert)\lvert h_j(\hat x)\rvert\le0$ で、係数がすべて正なので $g_i^+(\hat x)=0$、$h_j(\hat x)=0$、すなわち $\hat x\in X$ である。すると $f(\hat x)=f(\hat x)+\mu p_1(\hat x)=f(x^*)=p^*$ で、$\hat x\in X^*$ である。逆に $\hat x\in X^*$ なら $p_1(\hat x)=0$、$f(\hat x)=p^*=f(x^*)$ なので $\hat x$ は最小点である。$\square$
仮定は「$x^*$ が乗数 $(\lambda,\nu)$ について Lagrange 関数の最小点である」ことで、凸性は仮定していない。$f$・$g_i$ が微分可能な凸関数で $h_j$ が 1 次式なら、Karush–Kuhn–Tucker条件 を満たす点 $(x^*,\lambda,\nu)$ はこの仮定を満たす($\lambda\ge0$ なので $L$ は凸で、勾配が $0$ の点で最小になる)。不等式制約だけのとき、$\sum_i\lambda_ig_i^+\le\bigl(\sum_i\lambda_i\bigr)p_\infty$ なので、同じ証明で、最大値の罰金 $p_\infty$ は $\mu>\sum_i\lambda_i$ で同じ意味で正確である。
問題「最小化 $x$ 条件 $x\ge1$」($g(x)=1-x$)の最適解は $x^*=1$ で、$L(x)=x+\lambda(1-x)$ が $\mathbb{R}$ で最小値をもつのは $\lambda=1$ のときだけなので $\bar\mu=1$ である。
罰金法の近似解は実行可能集合の外にあることが多い(ex-pen-one-dim の 1)。実行可能でない点では目的関数が定義されない問題や、途中の解をそのまま使いたい問題では、内側から近づく方法がほしい。不等式制約だけの場合に、境界に近づくと $+\infty$ に発散する項を足すのが障壁法である。
以下、$g_1,\dots,g_m\colon\mathbb{R}^n\to\mathbb{R}$ を連続とし、$X:=\{x\mid g_i(x)\le0\ (\forall i)\}$、$S:=\{x\mid g_i(x)< 0\ (\forall i)\}$ とおく。$S$ の上の関数
$$
B(x):=-\sum_{i=1}^m\log\bigl(-g_i(x)\bigr)
$$
を 対数障壁 という(BV04 §11.2.1, p. 563)。$\varepsilon>0$ について $f+\varepsilon B$ を $S$ の上で最小化し、$\varepsilon\to0$ とするのが(対数障壁による)障壁法 である。
$f,g_i$ を連続とし、$X$ はコンパクト、$S$ は空でなく、$X$ は $S$ の閉包に等しいとする。
$X$ はコンパクトで $S\ne\emptyset$ なので、$M:=\max_{x\in X}\max_i\lvert g_i(x)\rvert$ は正の実数である。$x\in S$ では $0< -g_i(x)\le M$ なので、各 $i$ で $-\log(-g_i(x))\ge-\log M$ であり、
$$
B(x)\ge-m\log M\qquad(x\in S)\qquad\text{(c)}
$$
である。
1:$s\in S$ を 1 つとり、$\gamma:=f(s)+\varepsilon B(s)$、$T:=\{x\in S\mid f(x)+\varepsilon B(x)\le\gamma\}$ とおく。$T\ni s$ は空でなく、$X$ に含まれるので有界である。$T$ が閉集合であることを示す。$x_l\in T$、$x_l\to x$ とすると、$X$ は閉なので $x\in X$ である。ある $i$ で $g_i(x)=0$ だったとすると、$-\log(-g_i(x_l))\to\infty$ で、(c) と同じく残りの項は $-\log M$ 以上なので $B(x_l)\to\infty$ である。$f(x_l)\ge\min_Xf$ なので $f(x_l)+\varepsilon B(x_l)\to\infty$ となり、$\le\gamma$ に反する。よって $x\in S$ で、$S$ の上で連続な $f+\varepsilon B$ の値は $\gamma$ 以下、すなわち $x\in T$ である。$T$ はコンパクトなので $f+\varepsilon B$ は $T$ の上で最小値をとり、それは $S$ の上での最小値である。
2:$x_k\in S\subset X$ で $X$ はコンパクトなので、集積点があり $X$ に属する。$x_{k_l}\to\bar x$ とし、$f(\bar x)>p^*$ と仮定する。$X$ はコンパクトなので $f(x^\circ)=p^*$ となる $x^\circ\in X$ があり、$x^\circ$ は $S$ の閉包の点で $f$ は連続なので、$f(y)< f(\bar x)$ となる $y\in S$ がある。$x_{k}$ の最小性と (c) から
$$
f(x_{k})-\varepsilon_{k}m\log M\le f(x_{k})+\varepsilon_{k}B(x_{k})\le f(y)+\varepsilon_{k}B(y)
$$
で、$k=k_l$ として $l\to\infty$ とすると $f(\bar x)\le f(y)$ となり、$f(y)< f(\bar x)$ に反する。よって $f(\bar x)=p^*$ で、$\bar x\in X$ なので最適解である。$f(x_k)\to p^*$ は、任意の部分列が収束する部分列をもつことから prf-pen-convergence の 2 と同様に従う。$\square$
$f$・$g_i$ が微分可能な凸関数なら、最小点での値の誤差は $f(x_k)-p^*\le m\varepsilon_k$ と評価できる(非線形計画法 の定理「障壁法の精度」の $t=1/\varepsilon$ の場合)。上の定理は凸性を仮定しない代わりに、収束の速さは述べない。「$X$ は $S$ の閉包」という仮定は、実行可能集合が内側の点の極限で尽くされることで、これがないと障壁法は内側から届かない最適解を見落とす(反例の表の 5 行目)。
| 罰金法 | 障壁法 | |
|---|---|---|
| 近似解の位置 | 多くは実行可能集合の外 | 実行可能集合の内側($S$) |
| 扱える制約 | 等式・不等式 | 内側の点をもつ不等式 |
| 必要な初期点 | 任意 | $S$ の点 |
| 有限の重みでの正確さ | 絶対値の罰金で、Lagrange 関数を最小にする乗数より大きい重みなら正確(thm-pen-exact) | $\varepsilon>0$ では最小点が $S$ にあるので、最適解が境界にあれば得られない |
thm-pen-convergence・thm-pen-exact・thm-pen-barrier の仮定を 1 つずつ外す。
| 外す仮定 | 例 | 成り立たなくなること |
|---|---|---|
| thm-pen-convergence の「$K$ が有界」 | $n=1$、$f=0$、$p(x)=\bigl((-x)^+\bigr)^2$、$x_k=k$ | $(x_k)$ が集積点をもつ |
| thm-pen-exact の 2 の「$\mu>\bar\mu$」($\mu=\bar\mu$ にする) | $f(x)=x$、$g(x)=1-x$、$\mu=1$ | 罰金関数の最小点が実行可能 |
| thm-pen-exact の「Lagrange 関数の最小点となる乗数がある」 | $f(x)=x$、$h(x)=x^2$ | 有限の $\mu$ で $x^*$ が $f+\mu p_1$ の最小点 |
| thm-pen-barrier の「$X$ がコンパクト」 | $f(x)=-x$、$g(x)=-x$ | $f+\varepsilon B$ が最小値をとる |
| thm-pen-barrier の「$X$ は $S$ の閉包」 | $f(x)=x$、$g(x)=x^2(x-1)(x-2)$ | 集積点が (P) の最適解 |
1 行目:$X=[0,\infty)$ で $p$ はその罰金関数、$p^*=0$ で $K=\mathbb{R}$ は有界でない。$Q_\mu=\mu p$ の最小値は $0$ で、$x_k=k\in X$ は最小点である。$(x_k)$ は集積点をもたない(最適解はすべての $x\ge0$ で、存在はする)。
2 行目:$x^*=1$、$\lambda=1$ は $L(x)=x+(1-x)=1$ を最小にし、$\bar\mu=1$ である。$\mu=1$ で $x+(1-x)^+$ は $x\le1$ で値 $1$ をとるので、$x=0$ も最小点だが、$0\notin X$ である。
3 行目:$X=\{0\}$、$x^*=0$ である。$L(x)=x+\nu x^2$ は、$L'(0)=1\ne0$ なので、どの $\nu$ でも $0$ で最小にならない。$f+\mu p_1=x+\mu x^2$ の最小点は $-\frac1{2\mu}\ne0$ である。
4 行目:$X=[0,\infty)$ はコンパクトでない。$S=(0,\infty)$ で $X$ はその閉包である。$-x-\varepsilon\log x\to-\infty$($x\to\infty$)なので最小値をとらない。
5 行目:$g(x)$ は $x< 0$、$0< x< 1$、$x>2$ で正、$x=0,1,2$ で $0$、$1< x< 2$ で負なので、$X=\{0\}\cup[1,2]$ はコンパクトで $S=(1,2)$、その閉包は $[1,2]\ne X$ である。thm-pen-barrier の 1 の証明はこの仮定を使わないので、最小点 $x_k\in(1,2)$ はある。その集積点は $[1,2]$ にあって $f\ge1$ だが、$p^*=f(0)=0$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する