1. No category

農学生論文賞受覚論文
要約鴇
・−‥二、っこ∴∴一巨、・づ；くこさ、さ∴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
ト（不等式）を加えることによって，より良い下界値
を得ることが実際できた．
4．分枝カット法
卜ml
101040
0
1
☆
2
3
4
5
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）・
におおよそ検討し，カットを追加した緩和問題を解く
べきかどうかという判断が加えられた；
●（RMIEP）の近似解は解く問題のサイズによって
2方法［3．4］を組み合わせて用いた．
5．数値実験
［3］Il・Fujiokaand K・Hoshijima＝“Boundsforthe
BMIelgen、▼alue problem−a gOOdlower bound
and a cheapupper bound”，TTlanSaCtions ofthe
∫oc戌efy oJ血5fr祝mer乙fαmd C川か℃gβれガ慮れeeγ・β 33
（1997）616621・
［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時間で完全
に解けた．
6． まとめ
silopoulos：“Globaloptimization for trhe bia用ne
matrixinequalitさ▼PrOblem”．Jo71，rnalof Gtobal
q咋血流血加朋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シンポジウム論文集，京大会阻
1998年9月24日−9月25軋
本論文ではBMIを制約とした最適化問題（BMIE
P）に対してより優れた緩和とそれに基づく分枝カッ
2000年1月号
（37）37