非線形計画問題に対するアルゴリズムの開発

非線形計画問題に対するアルゴリズムの開発

非線形計画問題は,目的関数や制約関数(制約条件を表す関数)が非線形である数理計画問題である.非線形計画問題の中でも凸計画問題は内点法の開発により,比較的大規模な問題でも効率よく解けるようになってきている.私が考えている,現在の非線形計画問題の重要な研究課題が次の4つである.
  1. 大規模な非線形計画問題の解法の開発
    [開発できたらうれしいこと]
    現在は解ける規模を考慮して線形関数でモデル化していた問題を,非線形関数を用いてより精密にモデル化できるようになる.
  2. 大域的最適解を求めるアルゴリズムの開発
    [開発できたらうれしいこと]
    複雑なモデル化が可能になる.よりよい解決手段を提供できるようになる.
  3. 微分を使わないロバストなアルゴリズムの開発
    [開発できたらうれしいこと]
    シミュレーションで計算した関数を最適化できる.
    シミュレーションベースで,最適な製品・サービスを設計できるようになる.
  4. 理論的に優れた収束性をもつアルゴリズムの開発
    [開発に成功したらうれしいこと]
    研究者が面白がってくれる.

大規模な非線形計画問題のアルゴリズムの開発

大規模な問題を解くときには,計算時間と計算容量が大きな問題として立ちはだかる.現在,非線形計画問題の解法として実用化されているものは,次の2つのアプローチのどちらかを採用している.

直線探索アプローチ:
正定値となるように生成された近似ヘッセ行列を使った部分問題の解いて得られた探索方向と直線探索によって求めたステップ幅を使って点列を生成する方法

信頼領域アプローチ:
ヘッセ行列に正定値性の条件をかさないかわりに,信頼領域とよばれる制約条件を組み込んだ非凸な部分問題を解くことによって点列を生成する手法

直線探索アプローチを用いるときには,正定値行列となるような(近似)ヘッセ行列を生成する必要がある.このような行列を生成する方法に修正BFGS公式(準ニュートン法)がある.しかしながら,修正BFGS公式で生成される行列は必ず密な行列となるため,問題の次元の2乗に比例した計算容量が必要となる.そのため,大規模な問題では直線探索アプローチを取ることが難しい.一方,信頼領域アプローチでは非凸な2次計画問題を各反復で解く必要がある.また,信頼領域と問題固有の実行可能領域の共通集合が空集合となると,単純な方法では次の反復点を計算することができなくなる.そのため,信頼領域アプローチを取るためにはかなり複雑なアルゴリズムが必要となる.

(実装が容易な)直線探索アプローチを大規模な問題でも適用できるように,ヘッセ行列の疎性を保存する近似行列を生成する方法が研究されている.その中のひとつに私が提案した正定値行列補完を用いた準ニュートン更新がある.この更新は制約なし最小化問題に対して提案したものであるが,これを拡張すれば,一般の非線形計画問題にも適用できるのではないかと考えている.また,正定値行列補完を用いるアイデアは,一般の非線形計画問題だけでなく,モデルの予測などに用いられる非線形最小2乗問題にも適用できるのではないかと考えている.


微分を使わないロバストなアルゴリズムの開発

 近代科学は,大きく実験科学と理論科学の2つにわけることができる.実験科学の発展は,統計およびその統計理論に裏打ちされた実験計画法の影響が大きい.実験計画法のおかげで,少ない実験回数で多くの事柄がわかるようになった.しかし,多大な時間やコストがかかるような実験は,たとえ数回でも実施できないことがある.一方,理論科学は,調べたい現象に対して数理モデルを構築し,その数理モデルを理論的に分析することによって,現象を理解し,その現象を実際に活用できるようにしてきた.しかし,複雑な数理モデルを構築すると,その現象を解明することは非常に難しくなる.
 情報技術の発展により,シミュレーション科学が「もうひとつの科学」として注目を集めている.これは,複雑な数理モデルを,数学的に分析するかわりに,計算機によって模倣し,そこから現象を理解しようというアプローチである.計算機パワーによって,模倣される現象は実際に実験するよりも安価で速く行うことが可能になってきている.
 シミュレーション科学における最適化とはどのようなものになるのであろうか? 実験科学における実験計画法は,ブラックボックスである目的関数をその値(実験結果)のみで最小化する最適化手法と考えることもできる.一方,数理計画問題の多くの解法は,理論科学によって,問題が(微分可能な)関数のみでモデル化されていることを前提としている.そのため,具体的な関数でモデル化できない現象を扱うことができない.一方,計算機シミュレーションを用いれば,そのような現象の”関数値”を計算できることがある.そこで,実験計画法における”実験”を”シミュレーション”におきかえれば,計算機内の仮想世界で,実験計画法を実現することが可能となる.そうすれば,実際に実験を通して設計することに比べて,安価で早く自動的に,最適な設計ができることが期待できる.
 例えば,飛行機の翼を設計することを考えよう.これまでは,実験計画法に従いいくつかの模型をつくり,実際に実験し測定することによって,”最適な翼”を設計していた.一方,情報技術の発展により,流体力学(と計算力学)を駆使すれば,翼のまわりの現象をシミュレーションできるようになってきている.そのシミュレーションによって計算されるブラックボックスの現象値に使えば,翼の設計問題を最小化問題として定式化できる.もちろん,目的関数値は具体的な関数として与えらるわけではないので,既存の最適化手法を適用することはできない.
 シミュレーションによって計算される値に基づいた数理計画問題に対して,従来の微分をベースにした最適化手法を適用することができない.また,シミュレーションによる計算精度は,たいていの場合,計算時間に比例している.つまり,計算時間をみじかくして現象値を計算しようとすると,ある程度の誤差が含まれることを想定しなければならない.このような誤差を含む関数値に基づいて,現実的な最適解を与えるアルゴリズムの開発を目指している.


Return to home page of N. Yamashima.

< Last update: April 8, 2008 >