組合せ数学セミナー
発表内容の概要
クラスタリングは，機械学習やデータマイニングで幅広く利用されて
いるデータ解析手法である．クラスタリングをモデル化した最適化問
題の一つとして，クリーク分割問題が知られている．この問題では，
枝重み（正負あり）付き完全無向グラフが与えられ，頂点集合を好き
な個数のクラスターに分けて，クラスター内の枝重みの総和を最大化
する．クリーク分割問題に対しては，Groetschel & Wakabayashi (1989)
による整数線形計画問題としての定式化が知られているが，制約式の
本数が非常に多く，数百頂点のネットワークにしか適用することがで
きない．Miyauchi & Sukegawa (2015)は，一部の制約式の冗長性を指
摘し，新たな定式化を提案したが，その効果は限定的であった．本発
表では，実インスタンスの性質に着目し，制約式の本数を大幅に減ら
した新たな定式化を提案する．提案定式化は，数千頂点のネットワー
クに対しても適用することができる．また，整数線形計画問題として
の定式化に加えて，最大充足性問題としてのエンコーディングについ
ても議論する．本発表の内容は，薗部知大氏（国立情報学研究所），
鮏川矩義氏（東京理科大学）との共同研究に基づいている．
前半はDES暗号とAES暗号の安全性に関する研究を紹介する。まず、暗号を
数学的に定義し、DES暗号とAES暗号の構造を説明する。そして、数種類の
観点からそれぞれの暗号の安全性を統計的に検証した結果を紹介する。
後半は離散対数アルゴリズムについて解説する。離散対数の定義を確認し、
単純な列挙法から比較的効率の良い数体篩法まで、多くのアルゴリズムを
取り扱い、計算量から見た暗号の安全性との関係を考察する。
表題のいう組合せ論的ゼータ函数とは、
グラフや（擬）有限力学系などの離散構造に対し、
「一定の手続き」で定義されるゼータをさす。
その代表例は有限グラフに対して定義される伊原ゼータや、
有限力学系のアルチン＝メイザー・ゼータが挙げられる。
これらのゼータは一様に、本講で述べるところの
「三種の表示」、すなわち指数表示、オイラー表示、橋本表示をもつ。
ただ、これら三種の表示の鼎立は、これまではそれぞれのゼータに対して、
個別の議論に負うところが大きく、その一般的な原理を追う動機には、
特別の意識を払われてこなかったように思える。
この講演では、これら三種の表示の鼎立の原理を明らかにすべく、
その一回目として、「有限集合族のゼータ」を定義し、
それが三種の表示を持つための条件を考察することにより、
組合せ論的ゼータがもつ三種の表示の鼎立に向けた定礎をはかる。
次の講演の機会では、組合せ論的ゼータの定義と、
それがいかに三種の表示を鼎立せしめるか、その詳細を議論する予定である。
錐最適化問題(SOCPやSDPなど）を解くために，
制約想定（たとえば，Slater条件）を仮定し，
内点法を利用することが多いである．
しかし，制約想定が成り立ったないときに，前処理をしなければ，
直接に内点法で解くことは,大変困難であることが知られている.
本発表では，最初に「面縮小法」という悪条件問題の前処理手法と
その最近の発展を紹介する．
そして，「恭順錐」という新たな概念を紹介し，「面縮小法」を
用い，恭順錐に対するエラーバウンドを示す．
最後に，時間が許せば，様々な錐の幾何学の課題
を述べる．
たとえば，Caratheodory数やp次錐(p\neq 2)の非等質性などである．
与えられた無向グラフに対して、各辺に向きを与え、各頂点の出次数
に関して定められる目的関数を最小化する形の最適化問題を考える。
特に、制約として非巡回性があるときとないときで状況が大きく変わ
ることを観察する。非巡回性のある最適化問題は単体的複体のshellability
と関連のある問題となる。
音楽コンクールなど様々な場面で、
数値化し難い印象の評価が必要になることがある。
比較対象を同時に比べることができない場合には公平な審査が難しい。
このような場合に、グラフやブロックデザインなどの
組合せ構造を用いて全体を少数ずつに分解して比較し、
それぞれの結果から全体の順位を得る方法を提案する。
少数ずつの結果を重み付き有向グラフとして表し、
重みの更新を繰り返して全体の結果を得るアルゴリズムを中心に紹介する。
トップに戻る