楕円体法とは？

組合せ最適化輪講
4.4 楕円体法
担当：M2 津山竣太郎
楕円体法(ellipsoid method)
楕円体法とは？
・Iudin and Nemirovkii[1976],Shor[1977]により非線形最適化
分野で開発された手法
・それをベースとして、LPを多項式時間で解くアルゴリズムが
Kachiyanにより1979年に提案された
・LPの多項式時間アルゴリズムとしては史上初、「線形計画問題は
多項式時間で解けるのか」という疑問への肯定的な解決となった
・ただし一般には単体法の方が効率的
(なお、理論上も実用上も十分優れている、つまり十分実用的な最悪
多項式時間アルゴリズムが後々開発されている)
楕円体法(ellipsoid method)
多項式時間アルゴリズムの基本的な発想
「ある多面体𝑷 = {𝒙 ∈ 𝑹𝒏 |𝒂𝒙 ≤ 𝜷}が空であるか否かを判定する手法」
をサブルーチンに用いる
・主LP、双対LPがともに実行可能かをチェックする
(一方が実行可能でなければ最適解はない)
・多面体を与える不等式の内任意の一つ𝑎𝑥 ≤ 𝛽を𝑎𝑥 = 𝛽と
置き換えたLPが実行可能かをチェックする
・答えがyesでもnoでもそれに応じて不等式を1つ減らせる(らしい)
⇒(不等式の個数)回の繰り返しを実行すれば最適解が求まる
(詳しくは4.5でやってくれます！)
楕円体法(ellipsoid method)
「ある多面体𝑷 = {𝒙 ∈ 𝑹𝒏 |𝒂𝒙 ≤ 𝜷}が空であるか否かを判定する手法」
のアイディア
・Pを完全に含むような十分大きい楕円体を考える
・その中心がPに含まれる⇒「yes」を出力して終了
・中心がPに含まれないなら、楕円体から「 Pを含まない領域」を一部
切り捨てて領域を小さくする
・「Pが空でないならばこれくらいの体積があるはず」と言えるサイズ
になるまで繰り返す
・繰り返してもPの点が見つからない⇒「no」を出力して終了
(今回学ぶ楕円体法を応用することでこれが実現できる！)
(詳しくは4.5でやってくれます！)
楕円体法(ellipsoid method)
では、肝心の今回の内容(楕円体法)でやることは……？
・𝑷を完全に含むような大きい球から始める
・球の中心がPに含まれるかをチェック(含まれれば終わり)
・含まれない時、中心を通りPを一方のみに含むような超平面を見つ
け、Pを完全に含む半楕円を得る
・その半楕円を含む最小の楕円体を求める
・以上を十分な回数繰り返す
(大きい球、十分な回数は
事前に知っているものと仮定する)
・←中心
P
・←中心
・←中心
この場合yes
楕円体法(ellipsoid method)
定義4.12
𝑛 × 𝑛対称正定値行列Aを用いて𝐸 𝐴, 𝑥 = {𝑧 ∈ 𝑅𝑛 : 𝑧 − 𝑥 𝑇 𝐴−1 𝑧 −
楕円体法(ellipsoid method)
後でちゃんと使うので念のため……
𝐴を𝑛 × 𝑛実対称行列、𝑧を𝑛個の実数を成分に持つベクトルとした時、
∀𝑧 ≠ 0に対して𝑧 𝑇 𝐴𝑧 > 0となるような𝐴は、正定値である。
これは、 𝐴の全ての固有値が正であることと同値。
∀𝑧 ≠ 0に対して𝑧 𝑇 𝐴𝑧 ≥ 0となるような𝐴は、半正定値である。
これは、 𝐴の全ての固有値が非負であることと同値。
また、𝐴 = 𝑋 𝑇 𝑋なる行列𝑋が存在することとも同値。
楕円体法(ellipsoid method)
定義
ベクトル𝑥のユークリッドノルムを| 𝑥 |と表記する
また、行列Aのノルムは、
𝐴 ≔ max{ 𝐴𝑥 : 𝑥 = 1}と定義する
特に対称行列Aでは| 𝐴 |は固有値の絶対値の最大値に等しく、
𝐴 = max{𝑥 𝑇 𝐴𝑥: 𝑥 = 1}が成立する。
(後者から 𝐴 = max
𝑥 𝑇 𝐴𝑥
𝑥𝑇𝑥
⇒
𝑥 𝑇 𝐴𝑥
𝑥𝑇𝑥
≤ | 𝐴 |が言えることに注意)
楕円体法(ellipsoid method)
半楕円体の求め方
半楕円体𝐸 ′ = {𝑧 ∈ 𝐸 𝐴, 𝑥 : 𝑎𝑧 ≥ 𝑎𝑥}を含む最小の楕円体𝐸 𝐴′ , 𝑥 ′ )は、
E’の𝐿𝑜𝑤𝑛𝑒𝑟 − 𝐽𝑜ℎ𝑛楕円体と呼ばれておりそれは、
𝐴′
=
𝑛2
𝑛2 −1
𝑥′ = 𝑥 +
𝑏=
1
𝐴−
1
𝑏,
𝑛+1
𝑎𝑇 𝐴𝑎
2
𝑏𝑏 𝑇
𝑛+1
,
𝐴𝑎
𝐸′の𝐿𝑜𝑤𝑛𝑒𝑟 − 𝐽𝑜ℎ𝑛楕円体
を満たすことが知られている。
(ここで、𝑏で平方根の計算が
必要なので、丸め誤差の考慮が必要)
𝐸′
アルゴリズム4.4 楕円体法(Ellipsoid Method)
有理数𝑅 ≥ 2) 有理数ベクトル𝑥0 ∈ 𝑄𝑛
入力：自然数𝑛 ≥ 2 , 𝑁
出力：楕円体𝐸 𝐴𝑁 , 𝑥𝑁 )
①𝑝 ≔ ⌈6𝑁 + log 9𝑛3 ⌉とおく。
𝐼を𝑛 × 𝑛単位行列とし、𝐴0 ≔ 𝑅2 𝐼とおく。𝑘 ≔ 0とおく。
②任意の𝑎𝑘 ∈ 𝑄 𝑛 ＼{𝟎}を選ぶ。
③𝑏𝑘 ≔
1
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
𝑥𝑘+1 : ≈
∗
𝑥𝑘+1
𝐴𝑘+1 : ≈
𝐴∗𝑘+1
𝐴𝑘 𝑎𝑘 とおき、
{𝑧 ∈ 𝐸 𝐴, 𝑥 : 𝑎𝑧 ≥ 𝑎𝑥}の𝐿𝑜𝑤𝑛𝑒𝑟 − 𝐽𝑜ℎ𝑛楕円体
𝐴′
=
𝑛2
𝑛2 −1
2
𝐴 − 𝑛+1 𝑏𝑏𝑇 ,
1
𝑥 ′ = 𝑥 + 𝑛+1 𝑏,
≔ 𝑥𝑘 +
≔
1
𝑏 ,
𝑛+1 k
2𝑛2 +3
2𝑛2
𝐴𝑘 −
𝑏=
1
𝑎𝑇 𝐴𝑎
2
𝑏𝑘 𝑏𝑘𝑇 )
𝑛+1
𝐴𝑎
とおく。
④𝑘 ≔ 𝑘 + 1とおく。If 𝑘 < 𝑁 then ②へ行く else 終了する
(: ≈は、𝐴𝑘+1 であることを考慮しながら各成分について
2進𝑝桁まで正しく計算することを意味する)
アルゴリズム4.4 楕円体法(Ellipsoid Method)
入力：自然数𝑛 ≥ 2 , 𝑁
有理数𝑅 ≥ 2) 有理数ベクトル𝑥0 ∈ 𝑄𝑛
出力：楕円体𝐸 𝐴𝑁 , 𝑥𝑁 )
𝑁回の反復のどの段階でも、𝐸 𝐴𝑘 , 𝑥𝑘 ∩ {𝑧: 𝑎𝑘 𝑧 ≥ 𝑎𝑘 𝑥𝑘 }を含む最小の楕円
体を”少しだけ”拡大した近似楕円体𝐸 𝐴𝑘+1 , 𝑥𝑘+1 が計算される。
では、𝑎𝑘 をどう選ぶか？入力の𝑁, 𝑅をどうやって与えるのか？
については4.5でやってくれます！
この章では
「逐次計算される各𝐸𝑘 = 𝐸 𝐴𝑘 , 𝑥𝑘 )が確かに楕円体となり、
生じる数の絶対値は最大でも𝑅2 2𝑁 + 2𝑠𝑖𝑧𝑒
𝑥0
未満であること」
「各反復で、楕円体は前の反復の半楕円体と𝐸0 との共通部分を含むこと」
「各反復で、楕円体は一定割合で減少すること」の3つを示す。
楕円体法(ellipsoid method)
𝑁回の反復のどの段階でも、𝐸 𝐴𝑘 , 𝑥𝑘 ∩ {𝑧: 𝑎𝑘 𝑧 ≥ 𝑎𝑘 𝑥𝑘 }を含む最小の楕円
体を”少しだけ”拡大した近似楕円体𝐸 𝐴𝑘+1 , 𝑥𝑘+1 が計算される
では、各反復で𝑎𝑘 をどう選ぶのか？入力の𝑁, 𝑅をどう与えるのか？
については4.5でやってくれます！
この章では
「逐次計算される各𝐸𝑘 = 𝐸 𝐴𝑘 , 𝑥𝑘 )が確かに楕円体となり、
生じる数の絶対値は最大でも𝑅2 2𝑁 + 2𝑠𝑖𝑧𝑒
𝑥0
未満であること」
「各反復で、楕円体は前の反復の半楕円体と𝐸0 との共通部分を含むこと」
「各反復で、楕円体は一定割合で減少すること」の3つを示す。
補題4.13 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟏])
行列𝐴0 , 𝐴1 , ⋯ , 𝐴𝑁 は正定値である。さらに𝑘 = 0,1, ⋯ , 𝑁に対して
𝑥𝑘 ≤ 𝑥0 + 𝑅2𝑘 ,
𝐴𝑘 ≤ 𝑅2 2𝑘 ,
𝐴−1
≤ 𝑅−2 4𝑘
𝑘
である。
証明
𝑘についての帰納法で示す。
𝑘 = 0のときは
𝐴0 = 𝑅2 𝐼,
𝐴0 = 𝑅2 ≤ 𝑅2 20 ,
𝐴−1
= 𝑅−2 ≤ 𝑅−2 40
0
であり、明らか。
さて、まず単純な計算により
𝐴∗𝑘+1 −1
=
2𝑛2
2𝑛2 +3
𝐴−1
𝑘
+
2
⋅
𝑛−1
𝑇
𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
) が成立することを確認する。
単純な計算(さくっと)
1
𝑏𝑘 ≔
𝐴∗𝑘+1
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
=
2𝑛2
2𝑛2 +3
𝐴−1
𝑘
=
=
𝐴−1
𝑘
=𝐼+
𝐴𝑘 𝑎𝑘 かつ𝐴∗𝑘+1
2𝑛2 +3
2𝑛2
𝐴𝑘 −
𝐴−1
𝑘
2
⋅
𝑛−1
+
⋅
⋅𝐴 +
2
𝑛−1
−
𝐴𝑘 −
2
𝑏𝑘 𝑏𝑘𝑇 )かつAk の対称性より、
𝑛+1
𝑇
𝐴𝑘 𝑎𝑘 𝑎𝑘
𝐴𝑘
2
⋅ 𝑇
)が成立する。
𝑛+1
𝑎𝑘 𝐴𝑘 𝑎𝑘
𝑇
𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
𝑇
𝑎𝑘 𝑎𝑘
2
𝑇𝐴 𝑎
𝑛−1 𝑎𝑘
𝑘 𝑘
𝑇
𝑎𝑘 𝑎𝑘
2
𝑘
𝑇𝐴 𝑎
𝑛−1 𝑎𝑘
𝑘 𝑘
+
≔
2𝑛2 +3
2𝑛2
𝐴∗𝑘+1
⋅ 𝐴𝑘 −
⋅
2
4
− 2
𝑛+1
𝑛 −1
𝑇
𝐴𝑘 𝑎𝑘 𝑎𝑘
𝐴𝑘
2
⋅ 𝑇
𝑛+1
𝑎𝑘 𝐴𝑘 𝑎𝑘
⋅ 𝐴𝑘 −
⋅
2
𝑛+1
⋅ 𝐴−1
𝑘
⋅
𝑇
𝐴𝑘 𝑎𝑘 𝑎𝑘
𝐴𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
𝑇
𝑎𝑘 𝑎𝑘
𝐴𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
=𝐼
後ろから掛ける場合も同様に成立(飛ばします)
−
𝑇
𝑎𝑘 𝑎𝑘
4
𝑇𝐴 𝑎
𝑛2 −1 𝑎𝑘
𝑘 𝑘
⋅
𝑇
𝐴𝑘 𝑎𝑘 𝑎𝑘
𝐴𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
補題4.13 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟏])
行列𝐴0 , 𝐴1 , ⋯ , 𝐴𝑁 は正定値である。さらに𝑘 = 0,1, ⋯ , 𝑁に対して
𝑥𝑘 ≤ 𝑥0 + 𝑅2𝑘 ,
𝐴∗𝑘+1 −1
𝐴∗𝑘+1
=
2𝑛2
2𝑛2 +3
𝐴−1
𝑘
𝐴−1
≤ 𝑅−2 4𝑘
𝑘
𝐴𝑘 ≤ 𝑅2 2𝑘 ,
+
2
⋅
𝑛−1
𝑇
𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
)より
−1 は正定値行列と半正定値行列の和となる。
よって 𝐴∗𝑘+1
である。
∵𝐴が半正定値⇔
𝐴 = 𝑋 𝑇 𝑋なる𝑋の
存在と同値！
−1 は正定値であり、同様に𝐴∗
𝑘+1 も正定値となる。
半正定値行列に対して 𝐴 ≤ | 𝐴 + 𝐵 |が成立するので、
𝐴∗𝑘+1
=
2𝑛2 +3
2𝑛2
𝐴𝑘 −
2
𝑏𝑘 𝑏𝑘𝑇
𝑛+1
≤
2𝑛2 +3
2𝑛2
𝐴𝑘 ≤
11 2 𝑘
𝑅 2
8
行列𝐴𝑘+1 − 𝐴∗𝑘+1 はどの要素も絶対値が高々2−𝑝 となり、
そのノルムは高々𝑛2−𝑝 ≤ 1となる。
𝐴𝑘+1 ≤ 𝐴∗𝑘+1 + 𝐴𝑘+1 − 𝐴∗𝑘+1 ≤
∵𝑝 ≔ ⌈6𝑁 + log 9𝑛3 ⌉
11 2 𝑘
𝑅 2
8
+ 𝑛2−𝑝 ≤ 𝑅2 2𝑘+1
補題4.13 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟏])
行列𝐴0 , 𝐴1 , ⋯ , 𝐴𝑁 は正定値である。さらに𝑘 = 0,1, ⋯ , 𝑁に対して
𝑥𝑘 ≤ 𝑥0 + 𝑅2𝑘 ,
𝐴𝑘 ≤ 𝑅2 2𝑘 ,
𝐴−1
≤ 𝑅−2 4𝑘
𝑘
である。
任意の𝑛 × 𝑛対称正定値行列𝐴はある𝑛 × 𝑛対称正定値行列𝐵を用いて
𝐴 = 𝐵𝐵と書けることは、線形代数でよく知られている事実である。
それを用いて𝐴𝑘 = 𝐵𝐵とすると、
𝑏𝑘 =
=
𝐴𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
=
𝐵𝑎𝑘 𝑇 𝐴𝑘 𝐵𝑎𝑘
𝐵𝑎𝑘 𝑇 𝐵𝑎𝑘
𝑇 𝐴2 𝑎
𝑎𝑘
𝑘 𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
≤
=
𝑇 𝐵) 𝐵𝐵) 𝐵𝑎 )
𝑎𝑘
𝑘
𝑇 𝐵) 𝐵𝑎 )
𝑎𝑘
𝑘
𝐴𝑘 ≤ 𝑅2𝑘−1
帰納法の仮定より、
1
𝑏𝑘
𝑛+1
1
𝑅2𝑘−1
𝑛+1
𝑥𝑘+1 ≤ 𝑥𝑘 +
≤ 𝑥0 + 𝑅2𝑘 +
∗
+ 𝑥𝑘+1 − 𝑥𝑘+1
+ 𝑛2−𝑝 ≤ 𝑥0 + 𝑅2𝑘+1
補題4.13 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟏])
行列𝐴0 , 𝐴1 , ⋯ , 𝐴𝑁 は正定値である。さらに𝑘 = 0,1, ⋯ , 𝑁に対して
𝑥𝑘 ≤ 𝑥0 + 𝑅2𝑘 ,
𝐴∗𝑘+1 −1
=
𝐴∗𝑘+1 −1
2𝑛2
2𝑛2 +3
≤
2𝑛2
2𝑛2 +3
≤
2𝑛2
2𝑛2 +3
|
≤
2𝑛2
2𝑛2 +3
| 𝐴−1
𝑘 |+
≤
𝑛+1
|
𝑛−1
𝐴−1
𝑘
𝐴−1
𝑘 |
≤ 3𝑅−2 4𝑘
が得られる。
𝐴−1
𝑘
|+
𝐴𝑘 ≤ 𝑅2 2𝑘 ,
+
2
⋅
𝑛−1
𝐴−1
𝑘
𝑇
𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
+
| 𝐴−1
𝑘 |)
である。
)と 𝑎𝑘 𝑎𝑘𝑇 = 𝑎𝑘𝑇 𝑎𝑘 より、
𝑇
𝑎𝑘
𝑎
2
⋅ 𝑇 𝑘 )
𝑛−1 𝑎𝑘 𝐴𝑘 𝑎𝑘
𝑇
𝑎𝑘
𝐵𝐴−1
𝐵𝑎
2
⋅ 𝑇 𝑘 𝑘)
𝑛−1
𝑎𝑘 𝐵𝐵𝑎𝑘
2
⋅
𝑛−1
𝐴−1
≤ 𝑅−2 4𝑘
𝑘
補題4.13 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟏])
行列𝐴0 , 𝐴1 , ⋯ , 𝐴𝑁 は正定値である。さらに𝑘 = 0,1, ⋯ , 𝑁に対して
𝑥𝑘 ≤ 𝑥0 + 𝑅2𝑘 ,
𝐴−1
≤ 𝑅−2 4𝑘
𝑘
𝐴𝑘 ≤ 𝑅2 2𝑘 ,
である。
𝜆を𝐴𝑘+1 の最小固有値とし、𝑣をノルム 𝑣 = 1の対応する固有ベクトルと
する。
対称行列𝐶を用いて𝐴∗𝑘+1 = 𝐶𝐶とすれば、
𝜆 = 𝑣 𝑇 𝐴𝑘+1 𝑣 = 𝑣 𝑇 𝐴∗𝑘+1 𝑣 + 𝑣 𝑇 𝐴𝑘+1 − 𝐴∗𝑘+1 𝑣
=
𝑣 𝑇 𝐶𝐶𝑣
𝑣𝑇𝐶
≥
1
3
−1
𝐴∗𝑘+1
𝐶𝑣
𝐴∗𝑘+1
+ 𝑣 𝑇 𝐴𝑘+1 − 𝐴𝑘+1
−1 −1
∗
𝑣
− 𝐴𝑘+1 − 𝐴∗𝑘+1
> 𝑅2 4−𝑘 − 𝑛2−𝑝
≥ 𝑅 2 4−
(∵2−𝑝 ≤
𝑘+1
1 −𝑘
4 )
3𝑛
よって𝜆 > 0が示されたため𝐴𝑘+1 は正定値である。さらに、
𝐴𝑘+1
−1
1
𝜆
= ≤ 𝑅−2 4𝑘+1
が成立する。
[証明終了]
楕円体法(ellipsoid method)
OK!
「逐次計算される各𝐸𝑘 = 𝐸 𝐴𝑘 , 𝑥𝑘 )が確かに楕円体となり、
生じる数の絶対値は最大でも𝑅2 2𝑁 + 2𝑠𝑖𝑧𝑒
𝑥0
未満であること」
「各反復で、楕円体は前の反復の半楕円体と𝐸0 との共通部分を含むこと」
「各反復で、楕円体は一定割合で減少すること」の3つを示す。
続いて、
補題4.14
𝑘 = 0, ⋯ , 𝑁 − 1に対して、𝐸𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が成立する。
の成立を示す。
𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 , 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 を満たす点𝑥すべてが
𝑥 − 𝑥𝑘+1
𝑇
𝐴𝑘+1
−1
𝑥 − 𝑥𝑘+1 ≤ 1を満たすことを示せば良い。
補題4.14
1
𝑏𝑘 =
𝐴𝑘 𝑎𝑘 , 𝑏𝑘𝑇 =
1
𝑎𝑘𝑇𝐴𝐴𝑘𝑘𝑎𝑘
𝐴𝑎
𝑘𝑘
𝑘𝑎
𝑎𝑘𝑇 𝐴𝑘 より、
𝑇
𝑎𝑘 − 1に対して、𝐸
𝑎𝑘𝑇 𝐴𝑘 𝑎𝑘𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が成立する。
𝑘 = 0,𝑎⋯
𝑘 𝐴,𝑘𝑁
−1 =
𝐴
𝑏𝑘𝑇−1
𝑘𝐴𝑏
証明
𝑘𝑘 𝑏𝑘
𝐴
=−1
𝑘
𝐴−1
𝑘=
𝑎𝑘𝑇𝑎𝐴𝑘𝑇𝑘𝐴𝑎𝑘𝑘𝑎𝑘
=1
𝑎 𝑘𝑇𝐴𝑘 𝑎𝑘
𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 が𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 を満たすとする。まず、
𝑏𝑎𝑘𝑇𝑘𝑎𝑘𝑇𝑎𝑏𝑘𝑇∗𝑏𝑘 𝑇𝑎𝑘 𝑎𝑎∗𝑘𝑇𝑘𝑇 𝐴𝑘 −1𝐴𝑘 𝑎𝑎𝑘𝑘 𝑎𝑘𝑇∗
𝐴𝑎𝑘𝑎
𝑥𝑇𝑇− 𝑥𝑘+1
= =𝑇 𝐴𝑘+1⋅ ⋅ 𝑥𝑇− 𝑥𝑘+1
=⋅ ) 𝑘 𝑘 = 1
𝑎𝑎𝑘 𝑘𝐴𝐴𝑘 𝑘𝑎𝑎𝑘 𝑘 𝑎𝑘 𝐴𝑘 𝑎𝑇 𝑘
𝑇𝑎𝑘 𝐴𝑘 𝑎𝑘
𝑇𝑇
𝑎
𝐴
𝑎
𝑎
𝐴𝐴𝑘 𝑎𝑎𝑘
𝑎
𝐴
𝑎
𝑎
𝑇
𝑇
2
𝑘
𝑘
𝑘
𝑘
𝑘
𝑘
𝑘
2𝑛
1
−1 𝑘 𝑘2 𝑘 𝑎𝑘 𝑎𝑘
=
=
2𝑛2 +3
2𝑛2
2𝑛2 +3
+
=
𝑥−
1
𝑛+1 2
2𝑛2
2𝑛2 +3
+
𝑥 − 𝑥𝑘 −
𝑥𝑘 𝑇 𝐴−1
𝑘
𝑏𝑘𝑇 𝐴−1
𝑘 𝑏𝑘
𝑥−
1
𝑛+1 2
𝑛+1
𝑏𝑘
+
𝑥𝑘 𝑇 𝐴−1
𝑘
1+
2
𝑛−1
−
𝐴𝑘 +
𝑥 − 𝑥𝑘 +
⋅
𝑇𝐴 𝑎
𝑛−1 𝑎𝑘
𝑘 𝑘
2
𝑛−1
𝑇
𝑏𝑘𝑇 𝑎𝑘 𝑎𝑘
𝑏𝑘
2
⋅ 𝑇
𝑛−1
𝑎𝑘 𝐴𝑘 𝑎𝑘
𝑥 − 𝑥𝑘 +
−
2
𝑛−1
2 𝑥−𝑥𝑘 𝑇 𝑎𝑘
𝑛+1
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
𝑥−
) 𝑥 − 𝑥𝑘 −
𝑇
𝑇 𝑎𝑘 𝑎𝑘
𝑥𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
2 𝑥−𝑥𝑘 𝑇
𝑛+1
𝑥−
1+
2
))
𝑛−1
𝑥 − 𝑥𝑘
𝐴−1
𝑘 𝑏𝑘
𝑇
𝑎𝑘 𝑎𝑘
𝑇
𝑥𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
1
𝑏 )
𝑛+1 𝑘
+
2
⋅
𝑛−1
𝑥 − 𝑥𝑘
𝑇
𝑎𝑘 𝑎𝑘
𝑏𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
))
補題4.14
𝑘 = 0, ⋯ , 𝑁 − 1に対して、𝐸𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が成立する。
証明
𝑥 ∈ 𝐸𝑘 であるので、 𝑥 − 𝑥𝑘 𝑇 𝐴−1
𝑘 𝑥 − 𝑥𝑘 ≤ 1がいえる。(∵楕円の定義)
𝑡≔
𝑇
𝑎𝑘
𝑥−𝑥𝑘
∗
𝑥 − 𝑥𝑘+1
≤
2𝑛2
2𝑛2 +3
+
≤
と略記すると、
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
𝑇
𝑥−
1
𝑛+1 2
2𝑛2
2𝑛2 +3
𝐴∗𝑘+1
2
𝑛−1
2
𝑡2
𝑛−1
が得られる。
∗
𝑥 − 𝑥𝑘+1
𝑥𝑘 𝑇 𝐴−1
𝑘
1+
1+
−1
−
+
𝑥 − 𝑥𝑘 +
2
𝑛−1
2 𝑥−𝑥𝑘 𝑇 𝑎𝑘
𝑛+1
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
1
𝑛2 −1
−
2
𝑡)
𝑛−1
𝑥−
1+
𝑇
𝑎𝑘 𝑎𝑘
𝑇
𝑥𝑘
𝑇
𝑎𝑘
𝐴𝑘 𝑎𝑘
2
))
𝑛−1
𝑥 − 𝑥𝑘
補題4.14
𝑘 = 0, ⋯ , 𝑁 − 1に対して、𝐸𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が成立する。
𝑇 −1
𝑏𝑘𝑇 𝐴−1
𝑘 𝑏𝑘 = 1かつ𝑏𝑘 𝐴𝑘 𝑥 − 𝑥𝑘 = 𝑡であることから、
1 ≥ 𝑥 − 𝑥𝑘 𝑇 𝐴−1
𝑘 𝑥 − 𝑥𝑘 )
2
2
= 𝑥 − 𝑥𝑘 − 𝑡𝑏𝑘 𝑇 𝐴−1
𝑘 𝑥 − 𝑥𝑘 − 𝑡𝑏𝑘 + 𝑡 ≥ 𝑡 ⇒ 𝑡 ≤ 1
また、𝑎𝑘 𝑥 − 𝑎𝑘 𝑥𝑘 ≥ 0 ⇒ 0 ≤ 𝑡
ゆえに0 ≤ 𝑡 ≤ 1が成立する。よって、
𝑥−
∗
𝑇
𝑥𝑘+1
𝐴∗𝑘+1 −1
𝑥−
∗
𝑥𝑘+1
≤
2𝑛4
2𝑛4 +𝑛2 −3
あとは丸め誤差の評価ができればOKだが、実はその誤差は高々
1
になる。
9𝑛2
(三角不等式等々のごり押しと補題4.13の素直な適用なので省略)
補題4.14
𝑘 = 0, ⋯ , 𝑁 − 1に対して、𝐸𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が成立する。
𝑥 − 𝑥𝑘+1
𝑇
∗
≤ 𝑥 − 𝑥𝑘+1
≤
𝐴𝑘+1
𝑇
−1
𝐴∗𝑘+1
2𝑛4
1
+
2𝑛4 +𝑛2 −3
9𝑛2
𝑥 − 𝑥𝑘+1
−1
∗
𝑥 − 𝑥𝑘+1
+ 丸め誤差)
≤1
ゆえに𝐸𝑘+1 ⊇ {𝑥 ∈ 𝐸𝑘 ∩ 𝐸0 : 𝑎𝑘 𝑥 ≥ 𝑎𝑘 𝑥𝑘 }が示される。
[証明終了]
楕円体法(ellipsoid method)
OK!
「逐次計算される各𝐸𝑘 = 𝐸 𝐴𝑘 , 𝑥𝑘 )が確かに楕円体となり、
生じる数の絶対値は最大でも𝑅2 2𝑁 + 2𝑠𝑖𝑧𝑒
𝑥0
未満であること」
「各反復で、楕円体は前の反復の半楕円体と𝐸0 との共通部分を含むこと」
「各反復で、楕円体は一定割合で減少すること」の3つを示す。
最後に、
補題4.15(𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒔𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟖])
𝑘 = 0, ⋯ , 𝑁 −
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
1に対して、
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
の成立を示す。
<𝑒
−
1
5𝑛
が成立する。
補題4.15 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒔𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟖])
𝑘 = 0, ⋯ , 𝑁 −
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
1に対して、
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
<𝑒
1
−5𝑛
が成立する。
証明
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
det 𝐴𝑘+1
det 𝐴𝑘
=
2𝑛2 +3
2𝑛2
まず、𝐴∗𝑘+1
=
det 𝐴∗𝑘+1
2𝑛2 +3
2𝑛2
=
ここで、
𝑇
𝑎𝑘 𝑎𝑘
𝐴𝑘
𝑇𝐴 𝑎
𝑎𝑘
𝑘 𝑘
det 𝐴∗𝑘+1
=
𝐴𝑘 −
det 𝐴𝑘+1
det 𝐴∗𝑘+1
det 𝐴𝑘
2
𝑏𝑘 𝑏𝑘𝑇
𝑛+1
=
𝑛
det 𝐴𝑘 ⋅ det 𝐼 −
を評価する。
2𝑛2 +3
𝐴𝑘
2𝑛2
𝑇
𝐴𝑘
2 𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑛+1 𝑎𝑘
𝑘 𝑘
𝐼−
𝑇
𝐴𝑘
2 𝑎𝑘 𝑎𝑘
𝑇𝐴 𝑎
𝑛+1 𝑎𝑘
𝑘 𝑘
が成立する。
はrank1の行列なので、1が0以外の唯一の固有値である。
行列式は固有値の積であるので、
det 𝐴∗𝑘+1
det 𝐴𝑘
=
より、
2𝑛2 +3
2𝑛2
𝑛
1−
2
𝑛+1
3
2𝑛
<𝑒 𝑒
2
−𝑛
=e
1
−2𝑛
が成立する。
補題4.15 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒔𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟖])
𝑘 = 0, ⋯ , 𝑁 −
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
1に対して、
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
任意の行列𝐵でdet 𝐵 ≤ 𝐵
det 𝐴𝑘+1
det 𝐴∗𝑘+1
= det 𝐼 + 𝐴∗𝑘+1
≤ 𝐼 + 𝐴∗𝑘+1
≤
𝐼 +
−1
−1
≤ 1+
≤𝑒
1
10𝑛
𝐴∗𝑘+1
−1
≤ 3𝑅−2 4𝑘 より、
𝐴𝑘+1 − 𝐴∗𝑘+1 )
⋅ 𝐴𝑘+1 −
≤ 1 + 𝑅−2 4𝑘+1 ) ⋅ 𝑛2−𝑝 )
が成立する。
が成立することと
𝐴𝑘+1 − 𝐴∗𝑘+1
𝐴∗𝑘+1 −1
𝑛
1
10𝑛2
𝑛
<𝑒
1
−5𝑛
𝑛
𝐴∗𝑘+1
𝑛
𝑛
(∵2−𝑝
≤
4
10𝑛3 4 𝑁
≤
𝑅2
)
10𝑛3 4 𝑘+1
補題4.15 (𝑮𝒓𝒐𝒕𝒔𝒄𝒉𝒆𝒍, 𝑳𝒐𝒗𝒂𝒔𝒛 𝒂𝒏𝒅 𝑺𝒄𝒉𝒓𝒊𝒋𝒗𝒆𝒓 [𝟏𝟗𝟖𝟖])
𝑘 = 0, ⋯ , 𝑁 −
det 𝐴∗𝑘+1
det 𝐴𝑘
det 𝐴𝑘+1
det 𝐴∗𝑘+1
≤e
−
≤𝑒
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
1に対して、
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
<𝑒
1
−5𝑛
が成立する。
1
2𝑛
1
10𝑛
の二つを示した。これらを用いることで、
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘+1
𝑣𝑜𝑙𝑢𝑚𝑒 𝐸𝑘
=
が示される。
det 𝐴𝑘+1
det 𝐴𝑘
=
det 𝐴∗𝑘+1
det 𝐴𝑘
[証明終了]
det 𝐴𝑘+1
det 𝐴∗𝑘+1
≤𝑒
1
−5𝑛
楕円体法(ellipsoid method)
「逐次計算される各𝐸𝑘 = 𝐸 𝐴𝑘 , 𝑥𝑘 )が確かに楕円体となり、
生じる数の絶対値は最大でも𝑅2 2𝑁 + 2𝑠𝑖𝑧𝑒
𝑥0
未満であること」
「各反復で、楕円体は前の反復の半楕円体と𝐸0 との共通部分を含むこと」
「各反復で、楕円体は一定割合で減少すること」
の3つを示した。
以上の事実を用いて、
任意の線形計画問題に対して最適解を与える
多項式時間アルゴリズムを構成することができる。
(続きは4.5でやってくれます！)
(終わり)

Download Report