要約・-学生論文賞受賞論文

LinearTimeAlgorithmsf
orConvexProgramming
吉羽要直(東京大学大学院工学系研究科計数工学専攻現所属:日本銀行)
指導教官伏見正則教授

最終過程て壮 B は求めたかった最小包囲球になる.

1.はじめに次に最小ノルム点問題を考える.原点と母点群とをn1固の制約を持つきまぎまな

分ける分離平面がなければ原点が最小ノルム点である.

nlこ関し線形時間の計算量を持

そこで分離平面があったとすると，最小ノルム点は原つアルゴリズムを構成することである.ここでは 2 種

点から最も遠い分離平面への垂線の足になっているこ類の線形時間アルゴリズムを扱う.とがわかる.したがって最速分離平面を求めればよい.

本論文の主な目的は ，凸計画問題に対して ，

1 つは最悪の計算量が n に関し線形となるアルゴリズムであり，もう 1つは，アルゴリズムの中に乱数を発生させるステップを含むランダマイズドアルゴリズムであり，その中でも特に n に関し線形の期待計算量を持つものを考える.
n制約 ，d変数の線形計画問題を LP (n , d) と略記することにする.

ところが，次のことが示せる.

定理

2.
1 最遠分離超平面問題は，原点を中心とした反転で，原点を通る最小包囲球問題に帰着する.

以上より，固定点を通る最小包四球問題を解く手続

ききえ構成できれば，最小包囲球問題も最小ノルム点問題も解〈手続きを構成できることがわかる.そこで

2. 最小包囲球問題と最小ノルム点問題

この手続きを構成する.その前に少し問題のクラスをd次元ユークリッド空間 Rd上に n偶の母点ρ; (i= 1 ,拡張しておく.仮想的に (d+ 1) 次元空間を考え，そ2 ,… , n) が与えられた時，その n個の母点を含む半径の中の d次元超平面に注目していると考える.各母点最小の球を求める問題を「母点数 n， 次元 d の最小包囲ρz は，この超平面上にあるのではなく球問題J (SEB(d， 凡) )といい ，だけ浮いているところに位置していると考える.これx と z を変数として次のように定式化できる.

SEB (d ， 凡)

I 下駄 J h; の分により仮想的には (d+ 1) 次元であるが，Immlmlze Z.

I̲.

LsubjecttoIlx‑P.Wsz(k=1, .・" n).

(1)

d 次元超平面上だけで考えることができる(ただ，下駄を考慮する必要がある).このような問題を d 次元下駄っき l 点

一方 ， Rd上に nイ闘の母点が与えられた時，その n個の固定最小包囲球問題 (GOPF) と呼ぶ. GOPF も，普通母点のなす凸包の中で原点からのユークリッド距離がの最小包囲球問題と同様に，注目する母点群を増やし最小になる点を求める問題を「母点数 n， 次元 d の最小ていき，その母点群の最小包囲球を更新していくといノルム点問題J(MNP(d , Pn))と呼ぶ.

うアルゴリズムて解いてみる.現在得られている球のこれら 2 つの問題に対し，母点数例こ関して期待線外に新たに注目する母点があれば，その母点は周上に形時間の計算量を持つアルゴリズムを LP に対するあるので下駄っき 2 点固定最小包囲球問題になる.とSeidel[3J の線形時間アルゴリズムをもとに構成する

ころが定理2.2 よりこの問題は次元が 1 つ下がった[7].まず，母点 [ρu … ， PnJ をランダムに並べ換えてGOPF になることがわかる.次元を下げるときには，下駄を増やしていくだけで済む.ここがポイントである.

おく.

まず最小包囲球問題を考える.ム ， P2 だけに注目した最小包閤球B を作る.九 (k= 3 , …, n) を加えていアルゴリズムの詳細は本論文に疑似コードを使って示きれている.

き ， p.<~B ならば，固定点九を通りム (i= 1 ,…, k- 1)を囲む最小半径の球を求め B とする過程を反復する.

48© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

定理

2.
2(l +1) 制約 ，d 次元の 2 点固定下駄付き最小包囲球問題は ， 1制約，(d‑1) 次元の 1 点固定下駄付き最小包囲球問題に変換できる.

SEB(d , Pn ) , MNP(d , Pn ) , rl+1 制約 ，ン関数h(x)=ax+b に対する符合とは ， h(x*) の符合であるとする.また ，k個の r 変数アフィン関数 h;(x)=a;x+bi(i=1 ,… , k) に対し，そのうちの少なくともきて，これらのアルゴリズムの期待計算量を評価する.

(n , d) の最適解を f とする.アフィ解くべき CQP

d 次元の GOPFJ を解くのに要する期待計算量をそれぞれ T

k/2 個の符合を定める手続き MS(k , r)と，任意のアフィン関数h に対しその符合を返す手続き ORACLEを導入する.

(n , d) , T(n , d) , S (l, d) とする.あらかじめ母点CQP(μ) に手続き MS (~， d) を適用すると，実を並べ換えておいたことから，次の漸化不等式が成立は不必要だった制約を少なくともす個除ける.場合にすることがわかる.

よっては，変数の数d も減らせる.そこで，再帰的にd+1S(n-1 ， d) ,T(n , d) sT(n‑1 , d)+O(d)+ 一五2o.

CQP(守 ， d') ( μ d) を解く.最終的には，制約はT(n ， d)

1 個以下になって ，ζ O(n，d) 十 S(n， d) ,S (l, d) ζ S (l -1， d)+O(d)O(d 3 ) で解ける.手続き MS(k ，d) は手続き ORACLE を 9 (d-l) 回使うと構成でき，手続十子{O(ld) +S (I -1 , d •)}き ORACLEは (d- 1) 変数の CQP を 1 回 ，(d‑l)

これから，適当な境界条件のもとで，数学的帰納法に変数の LP を 2 回解〈手続きであり，再帰的に書くことより次の定理が成立することが示せる.

ができる.

定理

2.
3 これらのアルゴリズムは， SEB (d , Pn ) ,MNP (d ， Pn )をそれぞれO(n(d+l)(d+1)!) ,o(ndd!) の期待計算量で計算する.
アルゴリズム浦IJ 約 ，(d- 1)変数の LP を 3 図解く手続きとなる.

CQP(n ,LP(n, d) を解くのに要する計算量をそれぞれ T

このアルゴリズムの計算量を評価する.

(n , d) , T (n , d) とすると，T(n , d)sO(nd 3 gd- 1 )+gd- 1 T(n , d‑1)+げ-'T(n， d-l) 十 T(れ d)，d変数の凸 2 次計画問題を CQP (n , d) と略

T (n , d)sO(nd 3 g d - 1 )+3 ・ gd- 1 T(n ， d-1)

+T(まμ)，記する.

式(1)のように定式化される最小包囲球問題は，新たに y=llxW-z という変数を導入するとという漸化不等式が成立し，数学的帰納法によりアルゴリズムは CQP (n , d) を最悪でも O(η3(d+ l)')の計算量[凶nimize IlxW‑y ,で解くことがわかる. Dyerのアルゴリズムはかなり複…

subjectto -2PkX+Y ζ ー IlpkW (k=1 , , n)のように CQP (n , d+1)のアルゴリズムを構成できる.ただし，手続き ORA­

CLE はd) ,3. 凸 2 次計画問題に対する線形時間LP(n ， d) に対しでも CQP (n , d) と同様に変形できる.

第 2 節て最小ノルム点問題は最遠分離平面問題に帰着できることを述べた.分離平面を ux= 1 とすると，原点からこの分離平面までユークリ y ドノルムが耐となることから，最遠分離平面問題は，[山ize IluW,
subjectto uあ注 1 ( =1 ,…, n)

CQP(n , d) になることがわかる.したがって， CQP(n , d) に対して例こ関し最悪でも線形と定式化でき，の計算量を持つアルゴリズムを構成すれば，最小包囲球問題に対しでも最小ノルム点問題に対しても，母点雑であるが，本論文では疑似コードを与えインプリメントしやすく記述している.

4. 拡張
最小包囲球問題は施設配置問題に応用されるが，この際の拡張として，各母点仇に重み Wk が与えられた次の問題を考えることがある.

[…悶 z，subjecttowkllx‑PkW ζ z (k=1,… , n)

この問題は，[nmzsubjecttoaiXS bi(iε N)，数削こ関し最悪でも線形の計算量を持つアルゴリズムa}x ζ Mj ε E)，を構成できる.そこで， Dyer[2JtzTQ+ω +bsOの LPに対する線形時間アルゴリズムをもとに， CQP に対してこのようなアルゴリズムを構成する.
1994 年 1 月号のように定式化される凸計画問題のクラスに属する問© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

49題である.このクラスは，CQP (n , d)を含んで、いる

参考文献

ことに注意する.本論文ではこのクラスの問題に対し，Seidel [3J やWelzl [8J のアルゴリズムをもとに， 0[1] K.L.Clarkson:“ A LasVagasalgor
ithmfor(nd!d 3 ) の期待計算量を持つランダマイズドアルゴリ

linear programming when thedimensionis

ズムを構成した.

small ,"Proceedings 0/the29th /E
EE S)I1ゆ0-n銘柄を扱う最適ポートフォリオ選択問題として，過去 d 期のデータで収益率を推定する Mean-Vari­siu
montheFoundations0/ComputerScience,pp̲452-456 , 1988.

ance モテ。ルを考える.この問題は Rd上に与えられた n.Dyer:“On amultidimensionaIsearch[2J M.E個の母点のなす凸包の中の点で，かつ，与えられた超IideantechniqueanditsapplicationstotheEuc

平面の上にものっている点のうち，原点、からのユークournal onone‑
centre problem ," SIAM Jl15 (1986) , pp.725‑
738.
Computing, Vo.

リッド距離が最小になる点、を求める問題に帰着する[6].

この問題についても最遠分離平面問題に相当す

CQP (n , d) に帰. Seidel[3J R“ Small-dimensional linearproｭ

着できる.したがって，扱 7 銘柄数に関して最悪でもgrammingandconvexhullsmadeeasy ," Disｭcrete& Computa抑制 1 Geometη， Vol.6 (1991),

期待値でも線形時聞の計算量を持つアルゴリズムを構

pp.4
23‑444.

る同値な問題を考えることができ，成できることがわかる.

5. 計算機実験とアニメーション
本論文では，いくつかの計算機実験とアニメーショ[4J K.SekitaniandY.Yamamoto: “ A recursiveaIgorithmforfindingtheminimumnormpointIosestpointsi
ntwoinapolytopsandap
airofcathematical Programming , topolytopes ," M.
appearンも行なっている.

LP (n , d) に対して， Seidel のアルゴリズム[5J K.SekitaniandY.Yamamoto:“ A recursive[3J と， Clarksonによる別のランダマイズドアルゴリ

aIgorithmforfindingthe minimumcoveringsphereofapolytopsandtheminimumcovering

まず，

ズム[l J をとりあげ，この 2 つのアルゴリズムの計算

また，第 2 節で示したアルゴリズムに対しでも計算

apanJournal0/spheresofseveralpolytopes," Jlndustr
ialandAρρlied Mathematics , toappear.

機実験を行ない，理論的な評価どおり母点数に関して[6J H.Takehara:“An interiorpointa
Igorithm

平均的に線形な計算時聞を持ち，特に低次元では十分forIargescaleprotfoliooptimization ," MTEC高速であることを確認した.

Paper , N.
o T923 , MTB Investment
992.
TechnologyInstitute , Co. , Ltd. , 1

機実験結果を単体法との比較実験を含めて示した.

L杓 rking

最小包囲球問題および最小ノルム点問題に対する第2 節で示したアルゴリズムや，

Sekitani and.Iwata ,and T.Matsui:“ Ran[7J T.Yoshiba , S

Yamamoto[4 ， 5J によるアルゴリズムの挙動を視覚化

domized algorithmsforfindingthesmallest

するアニメーションプログラムも作成し，アルゴリズ

cIosingbaIIandtheminimumnormpoint,"en
METR 92-15 , Department ofMathematical

ムの理解を助けられるようにしている.

これらの計算機実験およびアニメーションの詳細は本論文に記述されている.

niver
ｭEngineerin
gandInfor
mationPhysics, U
992.
sityofTokyo , December1ncIosin
gdisks(balls[8J E.Welzl:“Smallest eand ellipsoids)," New TrenGおinComputerScience , Lecture Notes in Computer Science555 , p
p.359-370 , Springer-Verlag, 1
991.

50© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ