最適化問題で連続と離散をつなぐ新パラダイムを提唱
数理情報学専攻 室田一雄 教授

「凸性」があるかないかを基準に、新論理体系を展開
電気回路や経済学など異分野を 『離散凸』 で横断

室田一雄 教授 知らない街の人気スポットに行きたい、でも行く道がわからない。こんなとき、頼りになるカーナビ。その地点までの最短(に近い)ルートを教えてくれる。最適化問題のわかりやすい例だが、『トラベリング・セールスマンの問題』となると、解を得るのが非常にむずかしい超難問に早変わり。その理由はのちに触れるとして、最適化問題に“数理の目”で切り込み、新しい理論『離散凸解析』を提唱したのが室田教授。数理の世界の“アナログ”と“デジタル”を同じ土俵に乗せて統一的に捉えることによって、いままで見えてなかった離散世界の構造がよくわかるようになるというのだ。数理の魅力を引き出そうとする室田教授の試みとは―。

巡回セールスマン問題は“なぜ解けない”か

離散凸関数は、いろいろな分野に登場する
離散凸関数は、いろいろな分野に登場する
※画面をクリックして拡大画像をご覧下さい

 最適化とは何か。「わかりやすく言うと、利益なら最大を求めるし、コストなら最小にしたい。また、効率的に何かを探索したり、目的地に最短で到達する方策などを考えることです」。建物や車などの最適設計、金融資産の最適運用、コンビニの最適在庫管理など、最適化はとても身近なもの。その理論は、現実の問題から数学モデルをつくり、数学的に解析して役立てる手法を見いだすことを目的とする。アプローチの仕方として、連続的に分布している値をもとにする「連続最適化」と、それとは反対に、とびとび(バラバラ)に分布している(離散的)ものを扱う「離散最適化」がある。

 冒頭の経路問題に戻ろう。経路は連続した量ではなく、経路という離散構造の中からいくつかの解を選択する問題である。カーナビのようにA点とB点の2点間の最短経路を求める場合は、計算量が少ないので割り出しやすい。ところが、セールスマンがすべての都市を一度ずつ訪問し、出発した都市に戻ってくるときの最短の巡回経路を求めよという設定になると、一挙に難度は増す。訪問する都市が増えるほど解は見えなくなる。

凸関数と凸でない関数 離散化と連続化の操作
凸関数と凸でない関数 離散化と連続化の操作
※画面をクリックして拡大画像をご覧下さい

 連続最適化の世界では、中心に『凸解析』という理論が位置づけられている。「凸関数は簡単で、凸でない関数はむずかしい」、そして「物事は表と裏から見るとよく見える(双対性)」というもので、これが連続最適化の常識になっている。1970年代に理論として確立した。室田教授は、最適化問題というものを深く理解するには、連続は連続、離散は離散とそれぞれ別々に見るのではなく、連続と離散を統一的な場で議論すべきではないかと考えた。それは、連続と離散はもともと区別のないものであるからだ。たとえば、空気は連続量だが、細かく分解していくと、最終的には酸素や窒素の分子や原子になり、離散の世界に入る。「アナログ=連続」は「デジタル=離散」と密接にかかわっている。見方によって連続であったり離散であったりする。だから、離散の世界に凸解析という視点を持ってくると、離散の世界でわからないことも説明できるようになるのではないかと着目した。そのきっかけは、1982年ごろ。離散最適化で重要な劣モジュラ関数というものが、実は離散世界の凸関数にあたるという話であった。27歳の教授には「理屈はよくわからなかったが、何かが心に響いた」。この話題は、専門家の間では基本事実として知られるようになったが、その後、特段の進展を見せないまま長い時間が過ぎた。

新理論の伝道師として他分野にアピール

 1994年12月3日。行列の構造を調べていた教授に突然ひらめきが走った。「これこそ、離散凸の芽だ。核が見えた。広範に広がる」と思ったのだ。その芽とは、行列の構造がもつ新種の双対性である。「物事は表と裏から見るとよく見える」という双対性を軸にして連続最適化と離散最適化が統一的に説明できるという、27歳のときの感動がフラッシュバックした。『離散凸解析』と名付けた新しい理論体系はこうして産声を上げた。この理論に当てはめると、カーナビによる最短経路問題には凸性があるので解ける、トラベリング・セールスマン問題は凸性がないから解けないということになる。

室田一雄 教授 「離散凸解析が広範な分野に広がる」という直観は確かだった。電気回路、オペレーションズ・リサーチ、ゲーム理論、数理経済学、生物系統学などが共通の論理に則っていることを示すことができたからだ。電気回路理論と数理経済学はまったく違う対象(モノ)を扱うが、モノを支えている論理を数式に置き換えると、共通していることがわかる。数学のおもしろいところだ。「論理を通じて別の世界に技術移転が可能な理論を提供できれば、数理工学研究者としては夢が叶うことなんです」

 現在は、より明確な理論の構築と、多くの研究者にその良さを伝える仕事に力を注いでいる。連続最適化の世界は凸解析という軸で固まっているが、離散凸はすそ野すらまだできていない。電気回路やオペレーションズ・リサーチにしても、解けるのは離散凸に近い構造だけで、その外側にある解けない問題がたくさんある。解けない問題に対しても、何らかの貢献をしたいというのが教授の本音だ。そのために、昨年末に『離散凸解析の考えかた』という書を上梓したばかり。「やさしくまとめたつもりですが、“ああ、そうか”と理解を示してくれる人、“ややこしいだけじゃないか”という人もいて」と笑う。離散凸理論の伝道師としての活動がカギを握るのは、間違いない。

 室田教授は、おもしろいと思うことには熱中するタイプ。でも、ゲームをするよりも、ゲームをつくるほうが性に合っていると言う。「未解決問題を解くのは好きじゃない。誰かがつくったゲームに参加するのは嫌なんです。人が決めたレールの上を走れといわれているようで」。工学と理学の2つの顔(博士号)を持っているのも、こうした気質からなのかもしれない。いまは、最適化―離散凸解析を中心に、数値解析法や群論的分岐理論の工学的応用などの研究も展開している。次の研究テーマはと問うと、まったく違った分野を標的にする可能性もあると即答。理論の世界で画期的といわれるテーマは狙い撃ちで出てくるものではない。視野を広げて違う分野で何が起きているかを常にウオッチしておくことが不可欠と説く。どうやら、次の柱も数理の魅力をアピールするものになりそうな予感―である。

ISTyくん