研究紹介



離散最適化 (岩田教授)

離散 (組合せ) 最適化問題とは, 最適化問題の中でも特に「解が離散 (組合せ) 的な構造を持つもの」を指します. たとえば,

  • 現在地から目的地までの最短経路を求める問題
  • セールスマンが顧客先を回るための経路を設計する問題
  • 双方に好みがある状況において学生の大学への割当を決める問題 などが挙げられます.

離散最適化問題の中には, その構造を利用して効率的に解くことのできる問題と, 効率的な厳密解法の開発は本質的に無理であろうと考えられている問題とがあります. 実用上有用な多くの離散最適化問題が, NP困難と呼ばれる後者の部類に属するとはいえ, 効率的に解くことのできる問題の構造を知ることは, 計算困難な問題に対する現実的な対処法を探る際の道具としても重要です. このような背景から, 離散最適化問題に対し, 問題の持つ構造の解析や, 問題に対する効率的なアルゴリズムの開発, および, 問題を統一的に扱えるような枠組みや理論の構築を目指しています.  

固有値計算による大域最適化(岩田教授)

連続変数に関する最適化問題では,実行可能領域と目的関数の両方が凸である凸最適化問題を解く効率的なアルゴリズムが知られているのに対して,そうではない非凸最適化問題は,一般に難しいと言われています.しかし,幾何的な背景を有する特殊な非凸最適化問題に対しては,その構造を利用して効率的な厳密解法が設計できる可能性が残されています.下図では,一般化固有値問題を解いて,非凸最適化問題のKKT点を列挙することによって,楕円体間の符号付き距離を計算しています.一般化固有値計算による大域最適化は,数理7研が世界に先駆けて開発した新たな計算手法です.

離散幾何・計算幾何 (谷川准教授)

科学・工学の諸問題に現れる幾何的対象を計算機上で効率的に解析するための研究を行なっています.特にグラフの埋込問題や剛性問題を研究しています.例えば,指定された辺長を実現するようなグラフの平面描画は存在するか?存在するなら,可能な描画は唯一に定まるか?といった問題を考えています.また同様な問題を球面空間で考え,低階数行列補完問題などの研究も行っています. センサー間の距離情報から全体の配置を同定する問題や,タンパク質の挙動を推定する問題など,様々な応用を踏まえた理論展開を目指しています.  

機械学習・通信と最適化手法 (相馬助教)

機械学習や通信などの分野において,最適化手法は非常に重要な役割を果たしています.数理7研では,最適化の理論研究はもちろん,他分野へ最適化手法を応用する研究も行っています. ベクトル・行列における「疎・低ランク」な表現はデータ圧縮や機械学習で有用な技術です.我々は,行列の線形空間に対して低ランク行列からなる基底を求めるアルゴリズムを提案し,本アルゴリズムの画像分離への応用を示しました.以下の図は,4枚の画像を低ランク行列で近似し混合してから,本アルゴリズムを用いて分離したものです.混ざった画像が正しく分離されていることが確認できます.

また,機械学習や通信に現れる非凸な(難しい)最適化問題の解法の研究も行っています.たとえば,圧縮センシングではLp最小化(0<p<1)と呼ばれる非凸最適化による手法が知られていますが,これを多項式時間アルゴリズムにできるかどうかは未解決問題でした.これに対して,多項式最適化の手法である二乗和多項式緩和(Sum of Squares Relaxation)を応用することで,Lp最小化を多項式時間で解くアルゴリズムを与えました.