内点法・情報幾何・最適化モデリング
要旨
本論文では,凸最適化に関するモデリング・数理・アルゴリズムに関連した3つの話題を紹介する.第一の話題は内点法と情報幾何である.内点法の情報幾何の理論の概要を説明し,十分に大きな問題に対する数値実験を通じて,線形計画問題・半正定値計画問題両方の問題において,内点法の反復回数が微分幾何学的量であることを検証する.第二の話題はデータ同化に現れる大規模ガウシアングラフィカルモデル推定への内点法の適用である.推定された分散・共分散行列で一番大きいものは$34300\times 34300$であり,このモデルは101310個のパラメータを持つ.また,推定されたモデルのうちでパラメータ数最大のものは,行列の大きさが$8585\times 8585$で,150381個のパラメータを持つ.これらを含むいくつかのモデルを最尤推定し,AIC や BIC によりモデル選択を行った.最後の話題は古代メソポタミア都市ヌジの社会構造および人口の推定である.我々は,ヌジから出土した2000枚弱の粘土板に記された人名のデータベースに基づき,凸2次計画問題を用いて文書の作成された順番および登場する人物の生誕年および死亡年を推定し,古代社会の社会構造や人口動態について検討する.
キーワード:内点法,情報幾何,グラフィカルモデル,データ同化,メソポタミア, ヌジ,人口推定.
データ同化における大規模グラフィカルモデルの推定について
要旨
多変量の変化をモデル化する際に,共分散行列が導入されることが多い.本稿では,大規模な時系列解析であるデータ同化における共分散行列の構築方法を解説する.データ同化では,初期状態,モデル化された物理過程,観測データの重みを規定する際に共分散行列が用いられる.共分散行列は,標本共分散行列に何らかの構造を課して変換することで作成される.共分散構造のモデル化は,標本共分散行列の正則化と物理的拘束条件の付加からなる.正則化は,特異な標本共分散行列を非特異なものへと変換し,遠地点間の偽の相関を除去し,行列指定に必要なパラメータ数を減少させるために必要となる.従来の研究では,正則化は物理空間,周波数空間,ウェーブレット空間でなされてきた.本稿では,ガウシアングラフィカルモデルを用いた正則化法を紹介する.これは,逆行列空間での正則化と考えられる.各変数に対して,近傍とする変数を選定し,非近傍の変数とは条件付き独立という形でモデル化する.条件付き独立性は,共分散行列の逆行列にゼロ要素を指定することで表現される.非ゼロ要素はニュートン法を用いて,数値的に最尤推定する.適切な近傍は,AIC や BIC など情報量規準に照らして選択する.さらに,共分散行列が巨大次元である場合の実装法についても紹介する.単純な $3\times 3$ 行列を用いた簡単な例,および人工衛星観測による海面高度データへの適用例を示す.
キーワード:ガウシアングラフィカルモデル,共分散選択,ニュートン法,並列計算.
制約整数計画ソルバSCIPの並列化
要旨
制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.\textsf{SCIP}(Solving Constraint Integer Programs)は,CIPを解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された\textsf{SCIP} に対する2種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する\textsf{ParaSCIP} である.もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作する\textsf{FiberSCIP}である.\textsf{ParaSCIP} は,HLRN IIスーパーコンピュータ上で,一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また,統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5上では,これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた.
キーワード:混合整数計画,制約整数計画,SCIP,並列化.
ナース・スケジューリングにおける部分問題実行可能解空間のネットワーク表現
要旨
本論文では,ナース・スケジューリングの解空間把握に取り組む.病棟ナースの勤務表作成では,各シフトに適切な人数とスキルレベルのナースを揃えると同時に,それぞれのナースの勤務負荷を考慮しなければならない.ナース・スケジューリングは,組合せ最適化問題として解くことが難しい問題として知られてきたが,これに加え,人間が潜在的に考慮している制約や評価尺度も存在することから,コンピュータや最適化アルゴリズムにとって扱いにくい問題でもある.この問題における意思決定を支援するためには,実行可能解空間を直感的に把握でき,その中の良解の分布に関する情報を提供できるような仕組みが必要である.本論文では,ナース・スケジューリングの部分問題として,1ナースの最適スケジュールを見つける問題を対象に,この問題の解空間を表現するネットワークを構築する.このネットワークのソースノードからシンクノードまでの全経路は,そのナースの実行可能スケジュールであると同時に,すべての実行可能スケジュールがこのネットワークの経路として含まれる.ある試行解(勤務表)に対し,他のナースのスケジュールを固定した下での最適スケジュールや上位複数の最良スケジュールを,ネットワーク上の最短路や$k$最短路を探索することで得られるようになる.本論文では,このネットワークの構築方法と実際に構築した結果を報告する.
キーワード:ナース・スケジューリング,解空間,解の可視化,ネットワーク表現,動的計画.
森林管理における最適化モデルの応用
—伐採計画問題—
要旨
最適化モデルは森林経営における意思決定をサポートするツールとして,古くから幅広く森林資源管理問題に応用され,その時折の社会経済的要求に対応するため,モデルの拡張・改良を繰り返してきた.近年,開発された空間パターンを評価できる0-1整数計画法を用いた最適化モデルは,森林の多面的機能の維持・供給のための最適な管理の探索,および管理の経済評価のための有効なツールとなりうる.本稿では,これまでの森林資源管理,特に伐採計画問題における最適化モデルを概観し,近年の発展の一つとして森林管理における団地化問題を取り上げ,それに対する新たなモデルを提示する.そして今後の課題について議論する.
キーワード:最適化モデル,森林資源管理,線形計画法,空間構造,整数計画法.
測度空間における凸最適化
—無限次元における離散と連続—
要旨
すべての最適化問題は測度に関する最適化問題である.とは言い過ぎであるとしても,無限次元の最適化問題は,ほとんどの場合,適当な測度の空間における最適化問題であるとみなすことができる.一般に測度はLebesgue測度に関して絶対連続な成分と離散的な成分に分解することができるが,測度空間上の最適化において,その解が離散測度になることは少なくない.本稿は,どのような状況のもとで最適解が離散測度もしくは絶対連続測度になるのかを明らかにする試みの端緒として,まずコンパクトな空間上の測度の凸最適化についてまとめてみたものであり,公益社団法人日本オペレーションズ・リサーチ学会の第24回RAMP(数理計画研究部会)シンポジウムにおける講演予稿に加筆訂正を加えたものである.
キーワード:確率測度,無限計画,最適制御,半無限計画,一般化モーメント問題,通信路容量.
最適化手法に基づく誤り訂正符号の復号アルゴリズムについて
要旨
近年,線形計画法などの連続最適化に基づく誤り訂正符号の復号法が登場し,符号理論研究者の注目を集めている.本稿では,著者の提案する内点法に基づくLDPC符号(Low-Density Parity-Check符号)の復号法の概要とその特徴を紹介する.この復号法(内点復号法)は,LDPC符号の復号問題を凸計画問題として定式化し,バリア関数に基づく主パス追跡内点法により近似的にその凸計画問題を高速に解く,という考え方に基づいて構成されている.本復号アルゴリズムは,線形ベクトル通信路の範疇に入る定常無記憶通信路,シンボル間干渉通信路,MIMO通信路,マルチプルアクセス通信路など様々な通信路に適用が可能であり,幅広い応用が期待されている.
キーワード:内点法,凸計画問題,低密度パリティ検査符号.
X線自由電子レーザーによる分子の電子密度推定
要旨
米国,欧州,日本及び韓国ではX線自由電子レーザーと呼ばれる装置が開発され,米国,日本では運用段階にある.現在,この装置によって初めて可能となったX線領域の波長を持つ高強度レーザー光を用いた,様々な実験が計画および実施されている.本稿では,そうした実験のひとつ,X線回折を用いた生体単粒子の電子密度推定について説明し,2次元回折画像から2次元電子密度を推定する位相回復問題に対する我々の研究成果について解説する.
キーワード:X線回折,XFEL,位相回復,MAP推定,疎性.
アイゲンファクターを知る
要旨
インパクトファクターは,論文誌の価値を定量化する有名な指標である.その是非については度々議論されていつつも,国内外を問わず広く使われている.2007年に,論文の引用--被引用のネットワークを用いた新しい論文誌評価指標であるアイゲンファクターが提案された.2009年からは,インパクトファクターを発表するトムソン・ロイター社の Journal Citation Reports でもアイゲンファクターの値が発表されるようになり,注目が高まっている.指標の値がひとり歩きしないためにも,これらの指標を参照する研究者や評価者は,指標の意味を正しく理解する価値がある.本稿は,アイゲンファクターの仕組みを,インパクトファクターと対比しながら説明する.アイゲンファクターは,グーグルがウェブサイトを順位づけするために検索エンジンに用いているページランクとほぼ同じである.したがって,本稿は,アイゲンファクターより有名であると思われるページランクを丁寧に解説することを通じて,インパクトファクターやアイゲンファクターについての理解を深めるという道筋をとる.インパクトファクターやアイゲンファクターについて誤解されがちな点についても議論する.
キーワード:有向グラフ,ネットワーク,ページランク,インパクトファクター,中心性,計量書誌学.
空間データベースを用いた隣接情報の作成と自殺データの集積性への応用
要旨
空間データの一つであるLatticeデータを解析に用いる場合には,その隣接情報が肝要ではあるが,不規則的なLatticeであれば,それを作成するのは困難である.そこで,本研究では空間データベースを用いて隣接情報を作成する方法を提案した.さらに,作成された隣接情報および日本における自殺データを用いて集積性の検出へと適用し,先行研究にて検出されている同データの集積性の結果と比較した.また,空間データベースを用いれば,1つのLatticeに含まれる領域の数の修正などにも容易に対応できるので,同自殺データにおいて,二次医療圏での集積性と市区町村での集積性についても考察した.
キーワード:空間データベース,隣接情報,空間集積性,自殺データ.