京都大学 大学院情報学研究科 数理工学専攻 最適化数理分野

研究概要

最適化は工学の諸分野における基本的なテーマであるだけでなく,自然科学や社会科学の領域においても現れる重要な概念です.私たちの研究室では,「最適化は問題解決のキーワード」を合言葉に,最適化に関連する諸問題に対するモデリング手法ならびにそれらの問題の理論的性質の解明や解法(アルゴリズム)の開発に関する研究を行っています.また,工学の計画・設計問題だけでなく,経営,ファイナンスなど様々な社会科学の分野においても,実用的な問題解決の手法を提供することを目指しています.

数理最適化とは

数理最適化の手続きは一般に以下の3つのステップから成ります.

1. 問題のポイントを整理して数学モデルを作成する.
2. モデルの特性を考慮した適切な方法(アルゴリズム)を用いて解を求める.
3. 得られた解をもとに現実の問題の解決策を実施する.

これらのステップは互いに密接に関係しており,切り離して単独に扱うことはできません.たとえば,ある問題に対する数学モデルは一般に一通りではありません.モデルの数学的性質が違っていれば,その解法も異なるため,モデルを作成する際には,どのような解法を適用することができるかということを考える必要があります.また,数学モデルは現実の複雑な状況を単純化・抽象化しているため,モデルから得られた解がそのまま現実の問題に適用できるとは限りません.モデルを単純化しすぎると現実とのギャップが大きくなり得られた解が役立たず,逆にモデルを現実に近付けようとして複雑化しすぎると適用できる手法がないという困ったことになってしまいます.そのため,問題解決にあたっては,モデリングやアルゴリズムの基礎を踏まえた上で,問題全体を見渡せる広い視野をもつことが求められます.

理論と応用

数理最適化の研究には大きく分けて

1. モデリングやアルゴリズムの基礎を与える理論研究
2. 現実の具体的な問題を解決する応用研究

があります.理論は,学問的な見地からだけでなく,実際の問題を取り扱う際にも非常に重要です.確かに現実は理論どおりには行かないのが普通ですが,そのことを十分認識した上で理論を用いれば問題に対する本質的な見通しを得ることができるはずです.つまり,確固とした理論に基づいて問題を取り扱うことにより,より確かな成果を得ることができるのです.また,応用に関しては,数理最適化は典型的なシステム的方法論なので,個別の分野に限定されず,さまざまな分野の問題に対して幅広く適用することが可能です.

ORと数理計画

オペレーションズ・リサーチ(OR)は第2次大戦中に英国で行われた作戦研究に端を発し,その後,経営のための科学的方法論を研究する学問分野として発展してきました.ORの中心的なテーマは数理最適化であり,そこで取り扱う問題は一般に数理計画問題とも呼ばれています.現在では数理計画問題は工学,情報学,経営学,経済学など非常に広範な応用分野における数理モデルとして用いられていますが,数理計画をシステム的方法論として研究する立場からは,具体的な応用分野によって問題を分類するのではなく,その数学的な性質に基づいて問題を分類し,その各々に対して体系的な研究を行うというアプローチをとります.

さまざまな数理計画問題

数理計画問題は一般に,制約条件を満たす解(実行可能解)のなかで目的関数の値が最小あるいは最大になるもの(最適解)を求める問題ということができます.問題の数学的な性質に基づいて数理計画問題を大きく分類すると以下の3つになります.

1. 線形計画問題
2. 非線形計画問題
3. 組合せ計画問題

さらに,線形計画問題のなかにはネットワーク・フロー問題などの重要な問題が特別な場合として含まれています.また,非線形計画問題は2次計画問題,凸計画問題,半正定値計画問題等々に細分化され,組合せ計画問題も整数計画問題やグラフ・ネットワークに関連した様々な最適化問題を含んでいます.また,不確実性のもとでの意思決定を取り扱う確率計画問題,時間的な変化を伴う意思決定を取り扱う多段階計画問題,階層構造をもつ意思決定を取り扱う2レベル計画問題など,重要で興味深い問題が数多く存在します.また,最適化問題そのものではありませんが,最適化問題と非常に密接な関係をもつ変分不等式問題や線形・非線形相補性問題などの均衡問題や,それらを制約条件に含む最適化問題である均衡制約数理計画問題なども,数理計画の重要なテーマとして研究が行われています.これらの問題については後で改めて言及します(「数理計画の新しい展開」の項を参照).

数理計画問題の最適解

線形計画問題や凸計画問題など一部の非線形計画問題においては最適解は上述した通りの解となります.しかし,一般の非線形計画問題においては必ずしもそうではありません.非線形計画問題では,ふつうの意味での最適解を大域的最適解と呼び,実行可能解の集合(実行可能領域)のある限られた範囲内で最も良い目的関数値をもつものを局所的最適解と呼んでいます.それらの問題においては,大域的最適解を求めること(正確に言うと,大域的最適解を必ず求めることができると理論的に保証すること)は非常に難しいため,ふつうは局所的最適解を求めることが目標となります.大域的最適解を求めることを強調する場合は特に大域的最適化と言います.一方,組合せ計画問題では実行可能解の数はふつう有限なので,その中から最適解を見つけることは数学的には自明な問題です.しかし,現実の問題では有限個といっても実行可能解の数が天文学的になってしまうことが多いため,その中から最良のものを現実的な時間内に見つけ出すことが重要な課題となります.

数理計画のアルゴリズム

言うまでもなく,現実の問題を正確かつ迅速に解くことができるアルゴリズムが望ましいのですが,それでは正確かつ迅速に問題を解くというのはどういうことでしょうか?それを議論するには,どのような条件が満たされたら最適解が得られたと判定できるのか,また最適解を得るために必要な計算量はどのように評価できるのか,といった事柄を明確にする必要があります.そこで本質的に重要な役割を果たすのが,最適性や双対性,収束率や計算の複雑さなどの理論です.理論的な裏付けのあるアルゴリズムは,有効性と信頼性に優れた性質をもつ実用性の高い方法ということができます.

実際,線形計画問題や2次計画問題,半正定値計画問題などの凸計画問題に対しては,理論的に優れた性質を持ち,大規模な問題を正確・迅速に解くことができるアルゴリズムが開発され,広く実用に供されています.一般の非線形計画問題の場合,大域的最適解を確実に計算できるアルゴリズムには取り扱える問題のタイプや大きさに限界があります.しかし,局所的最適解を効率的に計算できる高性能アルゴリズムは様々なものが開発されています.また,必ずしも理論的な保証はないが現実に有効と期待される考え方を用いて大域的最適解を計算しようとする発見的手法(ヒューリスティクス)とよばれる方法も開発されています.組合せ計画問題の場合も状況は似ており,ある種のグラフ・ネットワーク問題に対しては非常に効率的なアルゴリズムが存在しますが,一般的な組合せ問題に対しては最適解を厳密に求めるのは困難な場合が多く,そのような問題に対しては様々な近似解法や発見的解法が開発されています.数理計画問題の解を求めるときは,言うまでもなくコンピュータを使って計算しますが,問題の性質をうまく利用することにより,並列計算が可能になる場合もあります.そのようなときには複数のコンピュータ(プロセッサ)を同時に用いて計算効率を向上させることにより,非常に大規模な問題を解くことができます.

数理計画の新しい展開

1. 確率的最適化とロバスト最適化:現実の問題には様々な不確実性が存在します.たとえば,将来の生産計画を立てる問題をモデル化する場合,将来の需要やコストなどはしばしば過去のデータを用いた予測値を用いますが,それらの値には予測誤差を含んでいます.そのような不確実性を取り扱う基本的な方法に感度分析と呼ばれる手法がありますが,より直接的に不確実性を取り扱うには確率計画法によるアプローチとロバスト最適化によるアプローチが有力です.前者は不確実性を確率的な事象と捉え,目的関数値の期待値や分散あるいは制約条件を満たす確率などを評価して最適化を行う方法であり,後者は不確実性の範囲をあらかじめ設定した上で,その中で最悪の事態が発生したときを想定して最適化を行う方法です.

2. 均衡問題:2人のプレイヤーによるゲームにおいて,どちらのプレイヤーも自分だけが戦略を変更しても得るものがないとき,均衡状態にあると考えられます.このように,最適化を行おうとする主体(このゲームではプレイヤー)が複数存在し,それらの各々が何らかの意味で最適化を図ったときに達成される均衡状態を求める問題を均衡問題と呼びます.均衡問題はゲーム以外にも,経済学,構造力学,交通工学,金融工学など様々な分野においてしばしば現れます.また最適化問題の最適性条件も均衡問題の形に表せるので,ある意味で,均衡問題は最適化問題を含む一般的な問題とみなすこともできます.均衡問題を数学的に定式化したものが変分不等式問題や線形・非線形相補性問題です.これらの問題は最適化問題と共通する部分も多く,数理計画の枠組みのなかで広く研究されています.

3. 2レベル最適化問題とMPEC:2人のプレイヤーが先手と後手に分かれて行うゲームを考えましょう.その場合,後手が合理的な行動をすると期待できるなら,先手は自分の打つ手に対する後手の反応を予測して,自分の利得を最適化しようとするでしょう.そのとき,先手と後手は対等ではなく,このゲームは先手のプレイヤーがイニシアティブをもった(先手にとっての)最適化問題とみなせます.ただし,その問題には先手プレイヤーの打つ手に対する後手プレイヤーの最適化行動が内部に含まれており,問題の構造としては上位レベル(先手プレイヤーの問題)と下位レベル(後手プレイヤーの問題)の2つの階層をもつ2レベル最適化問題と見ることができます.さらに,下位レベルの最適化問題をその最適性条件(均衡条件)で置き換えることによって得られる問題は均衡制約数理計画問題(Mathematical Program with Equilibrium Constraints: MPEC)と呼ばれます.MPECはゲームだけでなく,非常に多様な応用をもつ問題であり,近年活発に研究が行われています.

数理計画の応用

上にも述べたように数理最適化の応用分野は枚挙にいとまがありません.ここでは私たちの研究室でこれまでに取り扱った問題のいくつかを例として取り上げましょう.

1. ファイナンス工学:リスクの最小化とリターン(収益)の最大化を目的とするポートフォリオ最適化問題はファイナンス(金融)工学の最も基本的な問題ですが,この問題は平均・分散モデルと呼ばれる2次計画問題として定式化できます.また,別のリスク規範を用いれば線形計画問題として定式化することも可能です.ポートフォリオ最適化問題においては不確実性をどのようにして取り扱うかが重要なポイントですが,シナリオ・ツリーやシミュレーションに基づく多期間確率計画モデルやロバスト最適化の考え方に基づく2次錐計画モデルなど様々な数理計画モデルが提案されています.

2. 交通流均衡問題:道路ネットワークを利用する多数の車(ユーザ)がそれぞれ出発地から目的地までどのように経路を選択して移動するかを予測する問題を交通量配分問題といい,そのような問題を解いて得られる結果は道路網の設計や道路交通情報の提供などに用いられます.ユーザの経路選択規範が等時間原則(Wardropの第1原則)に従うとき,この問題は利用者均衡問題と呼ばれ,変分不等式あるいは相補性問題として定式化できます.また,道路交通網の設計問題や有料道路の課金により交通量を調整するロード・プライシング問題などは均衡制約数理計画問題(MPEC)として定式化することにより,最適化問題として取り扱うことが可能となります.

3. データマイニング:大量のデータから役立つ情報を引き出すデータマイニングの有力な手法にサポートベクターマシン(SVM)と呼ばれるものがあります.SVMには様々なバージョンがありますが,計算という立場から見れば,それらの多くは2次計画問題を解くことに帰着されます.また,データマイニングではニューラルネットワークも有力な手段としてよく用いられます.代表的なニューラルネットワークである誤差逆伝播ネットワークやホップフィールドネットワークはそれぞれ非線形最適化や組合せ最適化の枠組みで取り扱うことができます.

4. 通信工学:現在の高度な通信にはハードウェアとソフトウェアの最適な設計が不可欠です.通信ネットワーク設計,信号処理,プロトコル設計,電力配分など様々な問題が数理計画問題として定式化できます.災害に強く,コストの低い通信ネットワークの設計はネットワーク計画問題になります.雑音に強い信号処理や指向性アンテナの設計問題は半正定値計画問題に帰着することができます.複数ユーザの干渉が問題となる通信経路(ADSLなど)の電力配分問題は非協力ゲームと考えることができ,そのユーザ均衡は非線形相補性問題を解くことによって求めることができます.