こちらからダウンロード

山下研究室は、2012 年 10 月にできた新しい研究室です。
研究室紹介
山下 真 研究室
研究分野
メールアドレス
研究室ホームページ
-
数理最適化 (特に連続最適化, 非線形最適化)
[email protected]
http://www.is.titech.ac.jp/˜makoto/lab/index-j.html
研究分野 -数理最適化主な研究分野は数理最適化であり、「制約条件を満たす候補の中から、最善のものを見つけ出す
数学的手法」を研究対象としています。山下研究室の研究内容をひとことで言うとすれば、
ベストを追求する数学
と言うことができます。
数理最適化を知るために、ここでは具体例をひとつ考えてみましょう。
18 歳∼29 歳の女性が一日に必要なタンパク質とビタミン C は、それぞれ 55g, 100mg とされて
います。いちご１個とおにぎり１個は以下の左表にある栄養を持っています。このとき、一日に
必要な量を確保しつつ、摂取カロリーを最小にするにはどうすればいいでしょうか？（数値デー
タは、http://www.nutritional.jp/, http://www1.mhlw.go.jp/shingi/s9906/s0628-1 11.html を
参考にしました。）答えは、右ページの一番下にあります。
カロリー
タンパク質
ビタミン C
いちご
34kcal
0.9g
62mg
おにぎり
493 kcal
27.7g
5mg
一日の必要量
55g
100mg
⇒
最小化 : 34x1 + 493x2
制約 : 0.9x1 + 27.7x2 ≥ 55
62x1 + 5x2 ≥ 100
x1 , x 2 ≥ 0
この問題でいちごとおにぎりの個数をそれぞれ変数 x1 と x2 に割り当てると、右上にあるような
最適化問題として数学的に記述することができます。
一般に数理最適化問題は、目的関数 f : Rn → R と実行可能集合 S ⊂ Rn があたえられたとき
に、以下のように記述できます。
最小化
f (x) : 制約 x ∈ S
上のいちごとおにぎりの問題では、摂取カロリーが目的関数 f に、必要量を確保できるいちごとお
にぎりの数が実行可能集合 S に対応しています。
このいちごとおにぎりの問題は「線形計画問題」という数理最適化問題でも基礎となる問題とし
て定式化されています。数理最適化問題には他にも、出発駅と到着駅の最短ルートを探したりなど
する「ネットワーク最適化問題」や、線形計画問題の対称行列空間への拡張である「半正定値計画
問題」などがあります。
数理最適化の分野は、変数が連続 (例：x ≥ 3) か離散 (例：x は 0 以上の整数) か、によって連続
最適化、離散最適化に大きく分かれています。この 2 つは密接に関係していますが、山下研究室で
は連続最適化を積極的に研究しています。
研究トピック
最近は、数理最適化の中でもセンサネットワーク位置推定問題や非線形半正定値計画問題などに
取り組んでいます。ここでは、センサネットワーク位置推定問題について紹介します。
右図はタンパク質の構造を示しています。タンパク質に含
まれる各原子の 3 次元座標がわかるとき、原子と原子の間の
距離を計算することは簡単です。研究対象となっているのは、
その逆の計算であり、
「核磁気共鳴で原子間距離の情報をあた
えられたときに、どのようにして 3 次元座標を推定するか」と
いう問題です。この問題は NP 困難な問題の一つであり、正
確に解を求めるには莫大な計算量が必要とされています。
このようなタンパク質構造推定はセンサネットワーク位置
推定問題の重要な応用と考えられており、各原子をセンサと
みなすことによって数学的にはセンサネットワーク位置推定
問題として記述することができます。
最近は、この問題を半正定値計画問題に緩和することで高
精度な解を求めたり、大規模な問題を解けるように最短路手
法などを組み合わせたり、というような研究を進めています。
数理最適化の面白さ
数理最適化の研究の方向性は、
より大きな問題をより速く、より正確に解く
ということにあります。例えば、線形計画問題でもシンプレックス法や内点法といったの解法があ
り、計算途中に現れる辞書の更新を高速に行う改訂シンプレックス法や内点法のボトルネックにな
る Schur 補完行列を部分分解して大規模問題を扱う手法など、より効率的に線形計画問題を解くた
めの研究がそれぞれの解法で行われています。さらに、大枠としては同じ発想による解法であって
も、各アルゴリズムの選択やそれらのソフトウェアの実装によっては何十倍も計算時間が変わるこ
とが多く、コンピュータの性質をどれだけ活用して高速に計算をするか、という視点も重要になり
つつあります。
つまり、数学の理論的発展と、それに基づくソフトウェア実装の両方を楽しめる一粒で２度美味
しい研究なのです。
山下研究室を志望する学生へ
研究室を選ぶときには、自分の好きなこと、あ
るいは得意とすることで選んでください。これが
できない、あれができない、だからこの研究室は
無理、というような消極的な選択法ではなく、積
極的な選択をしてください。
山下研究室なら、数学もソフトウェア実装も
楽しめる、という人があっていると考えています。
ゼミ（週に３、４個）では線形代数や凸解析など
の基礎知識をベースにして数理最適化の比較的新
しい本を輪読したり、卒業論文や修士論文では最
適化アルゴリズムの性能を確認するために C 言語
や C++, MATLAB などソフトウェア実装で実際
にアルゴリズムを実行することなどがあります。
左ページの答え：いちご 61.1 個, おにぎり 0 個 (いちごとおにぎりだけでバランスのよい食事にする
のは困難なので、いろんな食材を楽しみましょう。)