POCS法における最悪収束の例

はじめに

「連続最適化アルゴリズム(飯塚秀明著)」を輪講で読んでいて、POCS法の収束について議論になったのでその覚書です。POCS法が最悪収束する時の例とその収束の様子を示します。

POCS法

最適化の文脈で、凸実行可能問題（convex feasibility problem）と呼ばれる問題があります。これは、複数の閉凸集合 $C_i \subset \mathbb{R}^d$ が与えられたとき、それらすべてに属する点 $x$、すなわち

\[x^* \in \bigcap_{i=1}^m C_i\]

を見つける問題です。目的関数を最小化する通常の最適化問題とは異なり、与えられたすべての制約を満たす点を一つ見つけること自体が目的です。共通部分が空でない、すなわち

\[\bigcap_{i=1}^m C_i \neq \varnothing\]

である場合、この問題は実行可能であるといいます。

この問題を解く手法の一つがPOCS(Projections Onto Convex Sets)法です。POCS法は、$P_i$を$C_i$への射影とすると

\[x_{k+1} = P_1 P_2 \cdots P_m(x_k)\]

として点列を作ります。要するに、それぞれの閉凸集合へ次々射影していくだけです。POCS法は実装は単純ですが、この点列は$x^*$に収束することが証明できます。また、その収束が

\[\lVert x_K - P_1 P_2 \cdots P_m(x_K)\rVert \sim O(1/\sqrt{K})\]

つまり反復回数の平方根で収束することが示されます。

凸実行可能問題の例

凸実行可能問題の簡単な例として、二次元ユークリッド空間における円の共通部分を探す問題を考えましょう。

今、二次元ユークリッド空間に二つの円C1、C2が与えられているとします。円C1の内部の点の集合を$C_1$、C2の内部を$C_2$としましょう。C1、C2の中心間の距離は、それぞれの半径の和より小さい、すなわち必ず共通部分を持つとします。この共通部分の点の座標をPOCS法で求めてみましょう。

適当な初期点$\boldsymbol{v}_0 = (x_0, y_0)$を取ります。まず、制約$C_1$への射影$P_1$は、単に現在の点から円C1への垂線を下ろすことに対応します。つまり、現在の点からC1の中心へ線分を引き、円との交点を次の点とします。同様に$P_2$は、次の点からC2への垂線を下ろす操作に対応します。

これを適当な円で実行すると、ほぼ1、2回の操作で円の共通部分を見つけることができます。

例えば以下の例では、射影2回、すなわち1度の反復で共通部分上の点を見つけることができます。

円を増やしても、ほとんどの場合において1度ないし2度の反復で全ての集合の共通部分を見つけることができます。しかし、POCS法の収束は反復回数$K$に対して$O(1/\sqrt{K})$と比較的遅いはずです。どういう時に収束が遅くなるのでしょうか？

実は、二つの円がほぼ接している状態を考えると、この反復が有限回では収束しなくなります。

この時に収束が最悪のケースである$O(1/\sqrt{K})$となるので、それを示すのが本稿の目的です。

収束解析

簡単のため、C1、C2ともに半径1の円としましょう。そして接している条件を考えます。 円C1の中心を$O1$、C2の中心を$O2$としましょう。$k$回目の操作により、C1上に点$\boldsymbol{v}_k$が取られたとします。この時、$O1$と$\boldsymbol{v}_k$を結ぶ線と中心間を結ぶ線のなす角度を$\theta_k$とします。

この点に射影$P_2$を適用すると、円C2上に新たな点が取られます。POCS法としては、さらにもう一度$P_1$を適用して1ステップですが、今回のケースでは対称性からこれを$\boldsymbol{v}_{k+1}$としてもかまいません(ステップ数が2倍になるだけです)。

さて、先程の点と$O2$を結ぶ線が円の中心間を結ぶ線のなす角度を$\theta_{k+1}$と定義しましょう。

$\boldsymbol{v}_{k}$から$O1 O2$上におろした垂線を$Q$とします。

$\boldsymbol{v}_k$、$Q$、$O2$からなる三角形を考えると、

\[\tan \theta_{k+1} = \frac{\sin \theta_k}{2 - \cos \theta_k}\]

という関係があることがわかります。この式から、$\theta_k$が$k$に対して単調減少関数であり、$k \to \infty$で$\theta_k \to 0$となることもすぐにわかります。

$\theta_k$どのように収束するかを調べるために、まず$x_k = \cos \theta_k$として、$x_k$の漸化式にしてみます。

すると、

\[x_{k+1} = \frac{2 - x_k}{\sqrt{5 - 4 x_k}}\]

を得ます。$0 < x_k < 1$であり。$k \to \infty$で$x_k \to 1$なので、

\[x_k = 1 - \varepsilon_k\]

としましょう。$\varepsilon_k$が満たす漸化式は

\[\varepsilon_{k+1} = 1 - \frac{1 + \varepsilon_k}{\sqrt{1 + 4 \varepsilon_k}}\]

となります。$|\varepsilon_k| \ll 1 $として2次まで展開すると、 \(\varepsilon_{k+1} \sim \varepsilon_k - 4 \varepsilon_k^2\)

を得ます。ここから、

\[\varepsilon_k \sim \frac{1}{4k}\]

を得ます。

もともと

\[x_k \equiv \cos \theta_k \equiv 1 - \varepsilon_k\]

でしたから、

\[\theta_k^2 \sim 2 \varepsilon_k\]

です。以上から、$K$回目のステップにおける角度の収束が

\[\theta_K \sim \frac{1}{\sqrt{2K}} = O(1/\sqrt{K})\]

と、$O(1/\sqrt{K})$となることがわかりました。

まとめ

「連続最適化アルゴリズム(飯塚秀明著)」の演習7.1で4つの円についてPOCS法を適用する問題があったのですが、数値的にいろいろ試しても有限回で不動点を見つけてしまうため、「どういう時に$O(1/\sqrt{K})$になるんだろう？」と言ったら、森田さん(smorita)がその例を見つけて収束解析をしてくれたので、せっかくなのでまとめておきました。

POCS法は最悪ケースでは$O(1/\sqrt{K})$ですが、実装が単純な上に多くの場合で非常に速く収束するのでいろいろ使えそうですね。