組合せ数学セミナー
発表内容の概要
ベクトルのL0ノルムや行列のランクを目的関数，もしくは制約式に
含むスパース最適化問題は，信号処理，機械学習，数理最適化など
の様々な分野で盛んに研究されている．L0ノルムやランクは非凸関
数であり，スパース最適化問題は一般にはNP困難であることが知ら
れている．そこで，それらの非凸関数を凸緩和した問題を代わりに
解くことが常套手段となっている．
本講演では，スパース最適化問題を等価で扱いやすい非凸最適化
問題に変形し，その局所最適解を求める方法を提案する．具体的に
は，L0ノルムやランクを２つの凸関数の差（DC分解）で表現し，凸
最適化を繰り返すDCアルゴリズムを適用する．DC分解を工夫するこ
とで反復毎に解析解が求まり，“毎反復で最適化問題を解く必要が
あるために計算時間がかかる”というDCアルゴリズムの欠点が解消
される．また，凸緩和問題に対する近接勾配法と提案手法の関係に
ついても触れたい．
有向木詰め込みに関するEdmondsの定理は，互いに辺を共有しない有向木の最大個数が
ある種の最小カット値と等しいことを示すものであり，この最大最小定理に基づいて
有向木詰め込みに関する様々な最適化問題のアルゴリズムが与えられている．近年，
Edmondsの定理やアルゴリズムの様々な方向への一般化，抽象化が研究されている．
本講演では，有向木詰め込みに関する既存研究について紹介した後，さらなる拡張に
関する成果について紹介する．
なお，講演内容の一部はKristof Berczi氏，Tamas Kiraly氏との共同研究に基づくも
のである．
（Nonpureな）単体的複体のshellabilityと関連する性質として、sequential
Cohen-Macaulaynessと分割可能性がある。どちらもshellabilityから含意され
る性質であるが、この両者の間には含意関係はないことが知られている。
Pureな複体については、sequential Cohen-Macaulaynessと分割可能性の両者
から含意される共通の性質として、h-vectorの非負性があるが、nonpureな場合
には少し状況が異なる。Sequential Cohen-Macaulaynessからはアナロジーとし
てh-triangleの非負性が含意されることが知られているが、分割可能性からは
含意されない。この辺の事情を紹介し、分割可能性に対してh-triangleの非負
性を弱めて議論する方法を提案する。また、これをhereditary propertyについ
ての議論に用いることの可能性についても議論する。
次数2の頂点を持たないtreeをhomeomorphically irreducible tree (HIT)とよぶ．
特にグラフGのspanning treeであるHITをGのhomeomorphically irreducible spanning
tree (HIST)とよぶ．
これまでの研究で，連結$P_5$-free graph（5頂点の誘導pathを持たないグラフ）は，
頂点数が8以上，最小次数が3以上であればHISTを持つことが知られていた．
一方，最近の研究により，連結$P_6$-free graphの場合，
どれだけ頂点数と最小次数を大きくしてもHISTを持たない無限系列が存在することが
わかった．
本講演では，連結$P_6$-free graphに対してどのくらい大きいHITの存在性が保証でき
るかを議論する．
進化系統樹という一例にも見られるように生物学的現象と離散数学的概念の間には元々
密接な関係があるが，代数学や幾何学とのつながりが注目され，数理生物学は近年急速
に応用数学の一大領域として認知されつつある[cf. AMS Notices, Nov.2015]．そこで，
本講演は軸足を離散数学に置きつつも数理生物学の多様な問題に触れることを狙った二
部構成で行う．第１部では tree-based networks（いわば進化系統樹の拡張版のような
有向非巡回グラフ）に関する幾つかの問題を紹介し，そのうち一つの解決について述べる．
第２部では距離空間のグラフ表現を考察する．Four-point condition (4PC)は系統樹で
表現可能な距離の特徴づけとしてよく知られているが，ここでは4PCとその周辺を概説し
た上で，あえて系統樹ではなく最小全域木に関連づけて「距離空間がtree-likeであるの
はどのようなときか」を論じる．最後に，第１部の内容にも関わる興味深い問題として，
木を含むがさらに広いグラフに由来する距離空間の特徴づけについても言及する．
与えられた正則整数行列の整数結合全体でつくられる格子の、原点に一番近い原点以外の格子点
を求める問題を、格子の最短ベクトル問題(Shortest Vector Problem, SVP)と呼ぶ。
SVPの近似解を求める確率的アルゴリズムを考える。この問題の主要なアプローチは、基底簡約
問題に帰着させるものである。基底簡約とは、生成する格子が変化しないように、簡約された行
列に基底変換していくものである。ここで簡約されたとは、Gram Schmidt 直交化ベクトルの長
さ列の辞書式順序で考えている。基底簡約アプローチの重要なスタート地点は、LLLアルゴリズ
ム(Lenstra, Lenstra, and Lovasz 1982年)である。われわれのアルゴリズムは、基底簡約アル
ゴリズムである(LLLを発展させた)RSRアルゴリズムが元になっている。RSRアルゴリズムを発展
させた柏原深瀬のアルゴリズム(2015年)では、基底ベクトルの整数結合の範囲をどこまで考える
と良いかを生成するベクトルの長さの期待値的に評価して、ベクトルの生成を行った。また、そ
のときの期待値は、直交化ベクトルの長さの2乗の和に比例することも示した。柏原深瀬のアル
ゴリズムでは、基底を更新するベクトルは、Stock Vectorという形で、すぐには基底に適用せず
に、保存する仕組みも導入した。Stock Vectorは、基底を更新するものだけでなく、惜しくも更
新できなかったものも保存している。
従来は、1本ずつ更新ベクトルを基底行列に挿入して、直交化ベクトルの長さを短くすることを
行なっていた。産総研の照屋さんと共同で作っている今回のアルゴリズムでは、index iとindex
i+1の直交ベクトルの自乗長さの和を減らすために、以下のような2本のベクトルがStock Vecto
rの中から見つかったときに、2本同時に基底行列に挿入を行っている。
(1)index iの直交化ベクトルを短くする。
(2)index iとindex i+1の直交化ベクトルの自乗長さの和は4%以上小さくなる。
帰納的ゲーム理論では、主体の認識するゲームの構造が変化する状況を分析する。
本研究では、信念改訂理論を応用することで、主体が得られた情報をもとに
認識をどのように変化させ、どのような意思決定に至るのかを分析する。
この分析を通じて、帰納的ゲーム理論が応用される、社会での差別・偏見の形成
改訂を考察する。
トップに戻る