農学生論文賞受覚論文

要約鴇

・−‥二、っこ∴∴一巨、・づ；くこさ、さ∴j‥∴痛㍑高潮十・∴ニー喜一i−ぶb端座別∵ト汗、至い壷−1e（ji．崗吋輿心ie肘極上：… ‥−・、十I（東京工業大学大学院情事隠■【二学研究科数理一計算科学専攻 現所属。同大学院情報理工学研究科数理。計算科学専攻博士後期課程）
指導教官 小島政和教授

且白 ばじめに問題よりも良い下界値を与える緩和を提案した。それは（凱慮‡EP）に視れるお互いに双線形な関係にある変1990年代に入り，主9双対内．酎去による半正憲値計

数ベクトル諾：財のダイアド耶√をより狭い多面体で画問題（SDP）の効率的な解法が理論，実用の両側面近似することに基づいている。

において確立されてきた，その中で，システムと制御の分野では制御系設計に屑いられる線形行列不等式2。ダイアド行列鞘〆の近似（minearⅣはtrix韮mequa、1itさ▼−以下m八且Ⅰ）の重要惟が再第3節の準備として，（飢1‡EP）の非凸性を反映しび指摘されるようになった囲．M朋ほ対象とする制た集合ア‖▼＝（（謎「臥閑′）∈封×原nロー＝開′＝諾即r）を御系の線形モデルであり，SDP によって解くことが多面体で穏和することを考える、まず自明なものとしできる．しかし，より複雑なシステムを考察するには双線形行列不等式（BilinearMaltrixInequalityM以下てはB八Ⅲ）を開いる必要性がここ数年来認識されるように（諾、封、開′）∈原r−×厨 −×厨門川

なった軒別且‡ほ乱入且耳の双線形拡張であり，与えら一丁．− −

J−l．

ノー・／．

れたいくつかの対称行列を双線形結合して得た行列
ア1†、＝が半iE（負仁走値行列であるという不等式のことであ町J≦旦ノエー〜■＋和い守む

町J≧草ブ￡ブ＋星朝一星せ．メ・る。ヨ且揖はむⅣ拍よりも一般的である一方，理論的にJも計算上でも極めて困難な問題（NP困難な問題）に

1＜〜 ＜れ7 1≦ノ≦7Tl．一 一 ￣ 一．J J．ごJ、なり，これまで実用規模の問題を解く数値解法は開発が挙げられる・本論文では，1▼ajirna eたαJ・［5］の補されていなかった。本論文ではB八Ⅲを制約とした最題を用いて，ア什 の凸包は組合わせ理論で良く知適化問題∴凱皿匝有値問題（Bnl臆P）を数理計画法られているブール2次多面体川 を完全2部グラフの立場から解析し，分枝カット法に基づく計算手法を打。．川上で定義したものとアフィン変換を通して一致提案した。

することを示した，しかし，この多面体を完全に記述対称行列麟J∈爵ん×ん（0≦壱≦n；（い；J≦汀）がすること自体はNP困難な問題である．そこで，ニの与えられているとすると，（馴1IEP）は次のように完多面体のファセットの中でも生成しやすいものを飼い式化される：て，（凱JIEP）の緩和問題に追加することを試みた．
具体的には 叶）を変数諾．即．開′の線形関数とする＼ −．・・・・．・〜・●ニ（乱野）∈′〃⊆屈 ×厨川（1）と恥ノて ≦ 恒ノ・J・Å・1裾裾町ノ叫卜虹り・‖，‖）≦わ叶ノ′り≦？ ≠Å一≦n：1≦．ノ≠／≦r可 のような不等

ただし，腰（笹牒）＝∑た1∑罠1右耳ノ勘十∑；≧1∬トβブ0＋式である，それらのファセットはロ（r？2〝J2）個あるた∑ブ≧1封ノ贋夢oJ＋腰00，∬は単位行列，過とのは行列Aがめ，すべてを綬和問題に入れると問題のサイズが大き半正志値行列であることを意味している・（1）は腰り

くなi）短時間で解けない．

を双線形結合して得た行列腰（影，甜）の最大固有値を超立方体封＝転可×［墾，或上で最小化する最適化問

分枝かソト法等においては績和問題の良否がアルゴ題と解釈できる。

佃Ⅸ′せ‡EP）に関しては，分枝限定法等による解法が提案されているr3，弧本論文では従来用いられた緩和詔6（36）3。（恐M耳EP）の緩和問題

リズムの挙動を大きく左右する．（臥肌EP）の緩和問
題としては各双線形項を勒J＝勘狛に置き換え，アヤヰ▼© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

をア汗という多面体で近似することによって
n m k

1Ili11 人

5．f．入∫−β（諾，封，Ⅵ′）と0〈（2）（諾，臥Ⅳ）∈テけ

5 520
6 624

・・・

卜、〔・−という線形問題が考えられる［3ト ただし，月（諾，y）＝月（影，封，lγ），鞘T＝lγとする・（2）はSDPであり，それを解くことによって（BMIEP）の下界値を得ることが分かる．さらにこの問題に第2節で出てきたカッ7 728

肛コ ☆

8 832

☆mト「「∵」−9 936

ト（不等式）を加えることによって，より良い下界値

卜ml101040を得ることが実際できた．

04．分枝カット法

1☆
2435

CPUtime（SeCOnds）

×104

分枝カット法の詳紳をここでは記述しないが，次のような発見的手法を組み入れてアリゴリズムの高速

図1：ランダム問題に村する分枝カット法化を計った：●分枝規則として一般的に使われている2等分割規ト法を提案した．計算機で実装した結果，従来解くこ則を拡張したものを取り入れた．分割した各子問題かとのできなかった中規模の（実用的にも役に立つ規模ら得られる最適値（下界値）をなるべく上げるようにの）問題が解けるようになった．

考慮した方法であり，これによって計算時間が従来よ

参考文献

り最高で約24％短縮できた；●（BMIEP）の下界値を得るにはSDPを解くことになるが，頻繁にSDPを解くことは計算時間の負担［1］M・M・DezaandM・La・urent‥Geometryofcuts

andmetrics（Springer−1 erlagt Berlin．1997）・が大きい．したがって，毎回カットを入れて緩和問題［2］S・Boyd・L・EIGhaoui，E・FeronandV・BalarkrLを解き直すよりも，カットを入れることによってどれishna・n：ム豆meαrmαとr宜∬豆meヴ祝α価eβ窟mβy占feγnαmd

ほど下界値が改善されるかどうかということを事前controltheory（SIAM，Philadelphia．1994）・におおよそ検討し，カットを追加した緩和問題を解くべきかどうかという判断が加えられた；［3］Il・Fujiokaand K・Hoshijima＝Boundsforthe

BMIelgen、▼alue problem−a gOOdlower bound●（RMIEP）の近似解は解く問題のサイズによって2方法［3．4］を組み合わせて用いた．

and a cheapupper bound，TTlanSaCtions ofthe∫oc戌efy oJ血5fr祝mer乙fαmd C川か℃gβれガ慮れeeγ・β 33（1997）616621・

5．数値実験

［4］K・−CL Goh，Mt Gt Safono、▼andG・P・Papa、▼aSL

SDPを解くのにはSDPA4・20［藤沢ら，1998］を用い，DEC AIpha・（599MHz−1GB memory）で数値実験を行った．（B人工IEP）を各サイズごとに7題から20題ランダムに発生した．各問題の大域最適解を算出するのに必要な計算時間を柏形図を用いて図1に要約した．固から分かるように最もサイズの大きい問題は変数ベクトル諾，封の各次元が10と121個の相称行列βり∈R40×40から成る問題であり，約12時間で完全に解けた．

silopoulos： Globaloptimization for trhe bia用nematrixinequalitさ▼PrOblem．Jo71，rnalof Gtobalq咋血流血加朋7（1995）365Ⅶ3弧［5〕Y・Yajima・M・1T・RamanaandP・M・Par（1alos＝パCuts and semidefinite rclaxa．tions for nonconrex

qua・drat・icprograms 、、ResearchReport98−1．DeL
part・OfIndustrialEnglneerlngandManagement．
TokvoInstituteofTechnology，JaInua・ry1998．
［6］第10回RA皿′IPシンポジウム論文集，京大会阻

6． まとめ1998年9月24日−9月25軋

本論文ではBMIを制約とした最適化問題（BMIEP）に対してより優れた緩和とそれに基づく分枝カッ

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

（37）37