近接定理の証明

なお、第3.4.3節では連続緩和のL^♮凸関数Gの例としてgの閉凸包による連続化を挙げた が、関数値の計算に多くの計算量がかかるため、連続緩和法には適さない。

集合

K :={p∈Rⁿ |p^∗−n1≤p≤p^∗+n1}

を考える．Kはコンパクト集合であるので，Kに含まれる任意の数列は，収束部分列をもち，

極限点もKに含まれる．整数k≥1について，

sk = 2^k, psk ∈argmin_Zgsk, psk

sk

∈K とおく．数列{^p_s^sk_k }から収束部分列{^p_s^ski

ki }をとることができる。このとき

ilim→∞

ps_ki

ski

=p^′∈K とおく．Gの連続性より，

ilim→∞G(ps_ki

ski

) =G( lim

i→∞

ps_ki

ski

) =G(p^′)

となる．このとき、粗い格子が細かい格子の部分集合を成すことから、{G(^p_s^ski

ki )}は単調減少 数列

G(psk1

sk1

)≥G(psk2

sk2

)≥ · · · ≥G(ps_ki

ski

)≥ · · · であり，

G(p^′)≤G(p₂ki

2^ki ) = ming₂ki (i∈Z, i≥1) (3.19) であることに注意する．（この事実は下で用いる。）

次に，上で定めたp^′についてG(p^′) = minGつまりp^′∈argmin_RGであることを、背理 法を用いて証明する．そのために，G(p^′)>minGであると仮定し，ε0:=G(p^′)−minG >0 とおく．p^′′ ∈argmin_RGを任意に固定する．このとき、任意のδ > 0に対して、ある整数 n^′∈ {ki|i= 1,2, . . .}と

b0=⌊p^′′⌋, bk ∈ {0,1}ⁿ (k= 1,2, . . . , n^′) を満たす数列{bk}^{が存在して，}

q:=

n^′

∑

k=0

bk

2^k (3.20)

が|p^′′−q|< δを満たす．ここで2^n′q∈Zとなることに注意する．一方、Gの連続性により，

∀ε^′ >0,∃δε^′ >0 :|x−y|< δε^′ ⇒ |G(x)−G(y)|< ε^′ (3.21) が成り立つ．さて，式(3.21)においてx=p^′′,ε^′= ^ε₂⁰ に対して定まるδε^′をδとする。この δに対して式(3.20)で定まるqは、|p^′′−q|< δε^′ を満たすので|G(p^′′)−G(q)|< ^ε₂⁰ とな り、G(q)<minG+ ^ε₂⁰ が成り立つ。したがって

ming₂n′ ≤G(q)<minG+ ε0

2 <minG+ε0=G(p^′)

となり，式(3.19)に矛盾する．これよりG(p^′) = minGが証明された．すなわち、p¯として p^′= lim

i→∞

ps_ki

ski

がとれる。

3.5.2 連続緩和の近接定理（逆）の証明

定理3.13の証明. 定理3.12を逆方向に用いるため，まずG:Rⁿ→R∪ {+∞}が唯一の最小 解p¯∈Rⁿをもつ場合を考える．このとき，すべてのp^∗∈argmin_Zgが

p^∗−n1≤p¯≤p^∗+n1

を満たすことが，定理3.12より直ちにわかる．また，この条件を満たすp^∗∈argmin_Zgが必 ず存在することもわかる．

次に、Gが唯一の最小解をもつとは限らない一般の場合を考える。この場合には、Gを摂動 して上の場合に帰着させる。最小解p¯∈argmin_RGを任意に1つ定めて，任意のε >0に対 して，関数Gε :Rⁿ→R∪ {+∞}と関数gε :Zⁿ→R∪ {+∞}を

Gε(p) :=G(p) +ε

∑n i=1

(p(i)−p(i))¯ ² (p∈Rⁿ), gε(p) :=Gε(p) (p∈Zⁿ)

と定義する．関数Gε と関数gεは，L^♮凸関数である。明らかに、Gεは唯一の最小解p¯をも つ。さて，十分に小さなεを定めたとき，gε の最小化元p^∗_ε ∈argmin_Zgε がgの最小解とな ることを示そう．Gの実効定義域は有界であると仮定したので，

K˜_∞ = max{∥p−q∥∞ |p,q∈dom_RG} が存在する。

g(p^′) = min{g(p)|p∈dom_Zg\argmin_Zg}

とする．すなわち、g(p^′)はgの最小値とは異なる2番目に小さい値である。摂動のパラメー タεを

0< ε < g(p^′)−ming nK˜_∞²

を満たす値に定める．p^∗_ε ∈argmin_Zgεとp∈argmin_Zgに対して gε(p^∗_ε)≤gε(p)

であるので、gεの定義を適用すると g(p^∗_ε)≤g(p) +ε

∑n i=1

{(p(i)−p(i))¯ ²−(p^∗_ε(i)−p(i))¯ ²}

の成り立つことがわかる．ここで，p∈argmin_Zgよりg(p^∗_ε) ≥g(p)であるから、最後の和 の項は非負である．したがって，

g(p^∗_ε)≤g(p) + g(p^′)−ming nK˜_∞²

∑n i=1

{(p(i)−p(i))¯ ²−(p^∗_ε(i)−p(i))¯ ²}

< g(p) +g(p^′)−ming=g(p^′)

表3.1.実装したL^♮凸関数最小化アルゴリズム

表記 アルゴリズム

SD 最急降下法(第3.2.1節) SCALING スケーリング法(第3.3.4節) RELAX 提案する連続緩和法(第3.4.5節)

が成り立つ．ここでg(p^′)は2番目に小さい値であったから、g(p^∗_ε)が最小値であること、す なわちp^∗_ε ∈argmin_Zgであることがわかる．

連続関数の最小解が唯一の場合の事実を適用することによって、p^∗_ε ∈argmin_Zgが p^∗_ε−n1≤p¯≤p^∗_ε+n1

を満たすことが証明される。