第46巻第2号283-296(1998)  特集「計算と最適化」 [原著論文]

半正定値計画問題に対する主双対内点法の
自己双対な探索方向族について

統計数理研究所 土谷隆

要旨

本論文では半正定値計画問題に対する自己双対な探索方向族について述べる.半正定値計画問題は,半正定値対称行列の錐とアフィン空間の交わりの上で線形関数を最小化する最適化問題である.制御や組合せ的最適化問題等多数の応用を持ち,現在活発に研究が進められている.半正定値計画問題に対する主双対内点法は線形計画問題に対するものの拡張であるが,拡張の仕方は一意的ではなく,さまざまな立場から多数の探索方向が提案されている.本論文ではこれらの探索方向を簡単にサーベイすると共に,スケーリング不変性および主問題と双対問題に対する対称性という立場から考察し,これまで知られているスケーリング不変な主双対内点法の探索方向すべてを含む,自己双対なMonteiro-Tsuchiya族の部分族を提案する.

キーワード:半正定値計画法,主双対内点法,Monteiro-Tsuchiya族,探索方向の自己双対性,Nesterov-Todd探索方向,HRVW/KSH/M探索方向.


第46巻第2号297-316(1998)  特集「計算と最適化」 [原著論文]

半正定値計画問題に対する主双対内点法における
共役勾配法の実装

東京工業大学 中田和秀
京都大学大学院 藤沢克樹
東京工業大学 小島政和

要旨

半正定値計画問題(Semideinite Programming,SDPと略)を主双対内点法により解くソフトウェアは,本研究が基づいたSDPAを含め幾つか公開されている.これらのソフトウェアでは,主双対内点法の各反復で解く線形方程式系に,コレスキー分解やLU分解等の直接法を利用している.しかし,直接法では,計算時間やメモリの制約から,組合せ最適化問題への応用等に現れる大規模な問題を解くことが困難である.本研究では,この困難を克服するためにSDPAの各反復で解く線形方程式系に反復解法である共役勾配法を用い,さらに,計算効率を高める種々の工夫を組み入れたソフトウェアSDPA-CGの開発を行った.記憶容量の面でも,SDPA-CGでは線形方程式系の係数行列を保持せずに共役勾配法の計算を行うことにより,SDPAに比ベメモリ使用量を大幅に減らすことができ,より大規模な問題を扱うことが可能となった.論文の後半では,最大クリーク問題のSDP緩和,グラフ分割問題のSDP緩和,ノルム最小化問題に対するSDPA-CGの数値実験結果を報告する.この実験を通して,組合せ最適化問題のSDP緩和のように,要求される精度が小数点1〜2桁程度の低い場合にはSDPA-CGは有効に働くことを検証した.特に,超大規模な最大クリーク問題のSDP緩和(行列変数サイズ=500,制約条件数=112,253)を効率良く解くことができた.

キーワード:内点法,半正定値計画,共役勾配法.


第46巻第2号317-334(1998)  特集「計算と最適化」 [原著論文]

半正定値計画問題に関する情報幾何を用いた考察

大阪大学大学院 小原敦美

要旨

本稿では半正定値計画(以下SDP)問題の性質を情報幾何の立場から論じる.SDP問題の許容領域を正定対称行列の部分多様体とみなし,情報幾何構造から導かれる第二基本形式と呼ばれるこの部分多様体の埋め込み曲率を考えると,この第二基本形式が小さいほどSDP問題をある種の内点法で解くのに必要な計算コストが少なくなることを示す.

特に第二基本形式がその許容領域上でOになるとき(この部分多様体を二重自己平行であるとよぶことにする),対応するSDP問題は任意の許容解がひとつわかればNewton反復なしで最適解を求めることができ,解の陽な公式も得ることができる.

またこのような性質を持つ正定対称行列の二重自己平行な許容領域は,対称行列のJordan部分代数と関係があることを示し,このことを用いて二重自己平行となるような許容領域の具体的な例のいくつかを構成する.

キーワード:半正定値計画問題,情報幾何,二重自己平行,Jordan代数,陽な解表示.


第46巻第2号335-343(1998)  特集「計算と最適化」 [研究ノート]

ホモトピー法と内点法

統計数理研究所 水野眞治

要旨

線形計画問題を解く内点法は,基本的にセンターパスを追跡する方法とみなすことができる.一方,ホモトピー法は,与えられた方程式系を補助方程式系に連続的に変形する方程式系を定義し,その解集合に含まれるパスを追跡することにより,もとの方程式系を解く方法である.そこで,線形計画問題から方程式系を導き出し,補助方程式系との間のホモトピーを定義する.そして,導かれたホモトピー方程式系の解集合に含まれるパスが内点法のセンターパスであり,そのパスを追跡する方法がインフィージブル内点法とみることができることを示す.

キーワード:内点法,線形計画問題,ホモトピー法,方程式系.


第46巻第2号345-358(1998)  特集「計算と最適化」 [原著論文]

半無限計画の最適性と双対性

統計数理研究所 伊藤聡

要旨

半無限計画は有限次元空間における無限個の制約条件つき最適化であり,このような問題は一般の近似問題,分権システムにおける資源配分,競争状況下での意志決定,多目的最適化,信号処理など工学のあらゆる分野に現われる.また,無限制約式は適当な条件のもとで最適値関数を含む式に等価的に変換され,この意味で半無限計画の理論は階層的最適化に対する基礎を与えるといえる.

本論文では,特に関数解析的な手法を用いて半無限計画問題の最適性条件と双対性について考察する.まず,適当な仮定のもとで制約関数をBanach空間上に値をとる作用素とみなすことにより,その最適性条件を誘導する.Lagrange乗数は制約式のインデックス集合上の測度として定義されるが,最適性条件を満たす乗数の集合は,空集合でない限り,必ず有限個の点からなる台を持つ離散測度を含むことを示す.一方,凸計画問題に対してはSlaterの制約想定のもとで強双対性が成立することがよく知られている.半無限計画における双対問題はやはりインデックス集合上の測度空間で定式化されるが,Slaterの条件のもとではその解集合が最適性条件を満たす乗数の集合と一致することを示し,これにより双対問題の解集合を特徴づける.最後に逆双対性についても考察する.

キーワード:半無限計画,凸計画,最適性条件,Lagrange乗数,双対性,逆双対性.


第46巻第2号359-381(1998)  特集「計算と最適化」 [原著論文]

球面上の最適配置の問題

統計数理研究所 種村正美

要旨

本論では,球面上に均等に分布する点配置の問題について議論する.球面上のミニマクス最適問題と最小エネルギー問題について論じた後,これらと原理的に全く異なる,最適配置を得るための新しい方法を提案する.

新しい方法を「球面調節法」とよぶ.まず,球面調節法は点の個数が少ない場合,ポアソン初期配置から大局的最適配置を生成できることを示す.また,球面調節法は,広範囲の点の個数に対して局所的最適配置を生成するためにも有用であることが示される.

最後に,われわれの新しい方法は,注意深く選ばれた良い配置を初期条件に用いると,その配置を改良したより良い配置が得られることが示される.その一例として,反発相互作用の下でマルコフ連鎖モンテカルロ法によって作られた平衡配置が,球面調節法で改善されることが示される.

キーワード:球面調節法,最小エネルギー解,マルコフ連鎖モンテカルロ法,ミニマクス解,Voronoi分割.


第46巻第2号383-399(1998)  特集「計算と最適化」  [原著論文]

目的論的モデル

統計数理研究所 石黒真木夫

要旨

変動する環境にあるシステムのふるまいを説明する対立的(補完的)な2つの方法がある.一つはそのふるまいを刺激に対する反応として説明するものであり,他方はそのふるまいを何らかの目的のためとして説明するやり方である.このような2通りの説明法をそれぞれ因果論的説明,目的論的説明と名付けよう.この論文では線形システムのふるまいの目的論的説明を与えるモデルを提案する.このモデルは本来因果論的説明を与える多次元ARモデルの係数行列を目的論的解釈を持つパラメータによってリパラメトライズしたものである.数値例としてセメントのロータリーキルンシステムの解析を示す.

キーワード:多次元ARモデル,因果解析,目的解析,セメントロータリーキルン.


第46巻第2号401-409(1998)  特集「計算と最適化」  [研究詳解]

最尤系統樹の探索法

統計数理研究所 曹纓・長谷川政美

要旨

最尤法による分子系統樹推定法の問題点を議論した.ここでは特に,種の数が増えた場合に可能な系統樹の数が爆発的に増えるという問題を解決するために提案されている,局所再配置法とQuartet-Puzzling法という2つの方法について,実際のデータヘの応用を通じて,それぞれの問題点を議論した.

キーワード:分子系統樹,最尤法,系統樹探索,局所再配置法,Quartet-Puzzling法.


第46巻第2号411-431(1998)  特集「計算と最適化」  [原著論文]

汎用並列分枝限定法ツールPUBBによる
組合せ最適化問題の厳密解法

東京理科大学 品野勇治
神戸商科大学 藤江哲也

要旨

分枝限定法は,組合せ最適化問題に対する代表的な厳密解法である.近年では,並列計算機の発達にともなって並列分枝限定法の研究が盛んである.特に,分枝限定法が持つアルゴリズムの汎用性に着目した汎用ツールが開発されている.本稿では,品野らによって開発された汎用並列分枝限定法ツールPUBB(Parallelization Uti1ity for Branch-and-Bound algorithms)の概要と適用例を示す.PUBBは,現在公開準備中であり,付録として,C言語によるユーザ・インターフェースの概略を与える.

キーワード:分枝限定法,並列処理,組合せ最適化,巡回セールスマン問題,最大クリーク問題.


第46巻第2号433-444(1998)  特集「計算と最適化」  [研究ノート]

計算科学のための専用計算機

統計数理研究所 泰地真弘人

要旨

科学計算用の専用計算機,特に古典粒子系の動力学計算専用計算機とその周辺について述べる.GRAPE(GRAvityPipE)は特に重力多体問題のシミュレーションのために設計された計算機で,重力・クーロン力を高速に計算するためのアクセラレータである.その中でもGRAPE-4システムはテラフロップスを世界で初めて越えた計算機として特記される.こうした高い性能を達成するための鍵となるのは,長いパイプラインの利用とブロードキャスト・メモリ・アーキテクチュアである.特に後者によってメモリ・ボトルネックの問題を解決することができる.ブロードキャスト・メモリ・アーキテクチュアが有効な問題は粒子シミュレーションに限らず,例えば密行列計算などもこの方法で加速できる.こうしたアーキテクチュアを持つ準汎用計算機の製作についても論ずる.

キーワード:専用計算機,重力多体問題,密行列計算,古典粒子シミュレーション.


第46巻第2号445-460(1998)  「原著論文」

統計データ解析における並列計算機システムの
性能評価

筑波大学 下平文彦
筑波大学 白川友紀
統計数理研究所 田村義保

要旨

近年,情報処理機器の発展に伴い社会のあらゆる場所で大量のデータが蓄積されるようになってきており,その解析が重要になってきている.しかし,大量のデータに対して精密な解析を行なおうとすると,膨大な時間がかかってしまう

本研究では,並列計算機上で統計データ解析の高速な処理を行なうことを目的とする.パソコン・クラスタ,並列計算機CP-PACS及びIBM RS/6000SP上で実行し,その処理時間,並列処理効率,及び速度向上の様子などを測定し,各計算機のデータ解析分野への適応性などを評価した.尚,本研究では基本統計量,重回帰分析,主成分分析について測定した.

その結果,100変量,10万サンプルのデータを16台のPUを使用して処理する場合には,基本統計量,重回帰分析,主成分分析の処理効率はCP-PACSではそれぞれ,100%以上(463.6%),30.4%,78.7%となった.同様の条件の時,RS/6000SPでは,98.4%,23.4%,100%以上(137.3%)となった.また,8PUのパソコン・クラスタでは100変量,1万サンプルのデータの時,それぞれ87.1%,3.4%,54.8%となった.

実処理時間を比較すると基本統計量ではCP-PACSが,通信の頻繁に行なわれる重回帰分析ではRS/6000SPが,主成分分析ではRS/6000SPが最も適しているという結果が得られた.また,主成分分析では計算途中に通信が行なわれないこともあり,パソコン・クラスタでも実用に耐え得る速度が得られた.

キーワード:並列計算機,CP-PACS,RS/6000SP,パソコン・クラスタ,並列処理効率.


第46巻第2号461-476(1998)  「原著論文」

近似主領域での修正情報量に基づく確率分布間の
一様近似と多変量一般指数型分布族の
揺動の定量的評価への応用

総合研究大学院大学 山田智哉
統計数理研究所 松縄規

要旨

互いに絶対連続な二つの確率分布間のいくつかの代表的隔たりの尺度を,近似主領域と呼ばれる殆どの確率がそこに分布する領域で定義する.またそれらを利用して分布間の近似を定量的に評価するための基礎理論を展開する.特に,修正Kullback-Leibler情報量を隔たりの尺度とする時の近似の評価理論を,いくつかの有用な両側不等式を与えることにより論じる.応用として,多変量一般指数型分布族の正準パラメータまたは分布の平均値が揺らぐ時に,それに伴う密度関数の揺動の大きさを,近似主領域で定義された修正情報量を用いて定量的に評価する.その場合,近似される分布と近似する分布,あるいは統計基礎モデルと発展モデルと言った近似の方向性が意味を持っている.一方,通常の多くの統計理論における様に,近似の方向性を考慮しない場合には,本稿で主として扱っている近似の強さは全変動距離に基づく一様近似に相当する.このことを明示するために,この距離に関連するいくつかの有用な不等式も与える.

キーワード:近似主領域,修正情報量,全変動距離,一様近似,一般指数型分布族.


第46巻第2号477-491(1998)  「研究詳解」

複雑な粘弾性物質のモデル化と逆問題:
Riemann-Liouvi11e積分表示

東北大学大学院 原啓明・李相錫
群馬工業高等専門学校 小幡常啓
統計数理研究所 田村義保

要旨

MaxwellとKe1vin-Voigt要素から成る複雑な粘弾性物質のモデルを構成し,Riemam-Liouville(RL)積分を利用してこの体系が呈する不規則現象を逆問題として定式化する.つまり,観測データから不規則現象の性質を予測できる表式が逆問題としてRL積分表示の逆変換から導出されることを示す.また,情報幾何の立場で観測データを標本(確率変数)の実現値とみて,観測値から決まる確率密度関数の汎関数を推定する.

キーワード:逆問題,Riemam-Liouville積分,分数次微積分,情報幾何.