双対自己平行な正定対称行列集合についての考察
紀田 馨 はじめに

半正定値計画（Semidefinite Programming 以下SDP）問題は信号処理、通信など も含むシステム制御工学に対して、幅広い適用範囲を持ち、近年は組み合わせ最 適化などへの応用もよく研究されている。このSDP問題の求解の為のアルゴリズムを 考える上で、その数学的な性質を調べる事は有用である。 そこで、本研究は以下に示すA.B.C.を目的とする。

研究目的A

SDP問題の求解には反復計算が必要であるが、近年の研究の結果その可能領域 が双対自己平行であるなら反復計算なしで解ける事が明らかになった。 本研究ではこの考え方に基づいてそれを公式化する事を目指す。

研究目的B

双対自己平行な正定対称行列の具体例として、原点を通るものについては、 Jordan subalgebra (以下JSと記す)である事が必要十分条件になっている。 そこで本研究では原点をとらないものの具体例の構築を目指す。 なお、一般に原点を通らないSDP問題の方が、原点を通るものよりも興味深い 性質を持つ。

研究目的C

Vanderbei,Yangらは、上記の手法とは異なるアイデアに基づいてあるSDP問題 を反復計算無しで解く解法を明らかにした。本研究では前述の解法と彼らの解法 との関連を明らかにする事を目指す。

注意事項

双対自己平行であるとは、正定対称行列Pにおいては、Pおよび Pの逆行列のそれぞれの要素間に線形制約がある事、JSとは、JSを あるベクトル空間とした時、A、Bがそのベクトル空間に入っている なら、A*B=(1/2)(AB+BA)という演算に関してもその空間に入っている ことを意味する事に注意。 JSの例として、二重対称行列や固有ベクトルが固定された行列などがある。

研究目的Aの結果

可能領域が双対自己平行になっているSDP問題の解を陽に表す式を得た。

研究目的Bの結果

双対自己平行な正定対称行列集合な具体例をいくつか求める事ができた。

研究目的Cの結果

VanderbeiとYangらの解いた問題との関連において、彼等の解いた問題の双対問 題の可能領域が双対自己平行になっている事を明らかにした。

研究の結論

原点を通らない双対自己平行な正定対称行列集合が十分広いクラスである事がわ かった。その他の研究目的に関しても、その目的を達成する事ができた。 研究の残った点としては、VanderbeiとYangらのアルゴリズムとの関係がある。

参考文献

A.Ohara,Information Geometric Analysys of an Interior Point Method for Semidefinite Programming,the proceeding volume of "the conference on Geometry in Present Day Science " ,World Scientific (1998) to appear
R.J.Vanderbei and B.Yang,The simplest semidefinite programs are trival ,Mathematics of Operations Research,vol 20,No.3 (1995).