最適化セミナーのご案内

B.5 凸緩和法に基づく大域的最適化アルゴリズム

 一般に,非線形最適化問題は,実行可能領域(制約条件を満たす領域)の中に複数の局所的最適解を持ちます.「局所的最適解」とは,「その近くでは最も良い解だが,実行可能領域全体では最も良いとは限らない解」のことです.これに対し,「大域的最適解」とは「実行可能領域全体で最も良いことが保証された解」となります注1.次は1変数の非線形な最小化問題(制約は変数の上下限のみ)における局所的最適解が複数存在する例です.

 非線形最適化問題を解く際に適用する通常のアルゴリズムでは,「局所的最適解を一つ見つける」ことが目的とされています.これは,非線形最適化問題において大域的最適解を見つけることが一般に困難であるからに他なりません.

 しかし,大域的最適解を求めるための研究は比較的古くから行われており,そのための手法の一つとして,組み合わせ最適化問題でよく用いられる「分枝限定法」の考え方を用いた手法が構成できます.

 

 本手法は以下のようなステップを繰り返します.

  1. (大域的最適解が存在する可能性のある)実行可能領域を分割し,分割された領域で「子問題」を生成して解く
  2. 元の問題の実行可能解を何らかの方法で求める
  3. 1.2.の結果を用いて分割した各領域に大域的最適解が存在する可能性を判断し,存在しないと判断された領域を考慮から除外する

 このアルゴリズムが機能するための前提条件として,各区間において生成された「子問題」が

『子問題の目的関数は,その実行可能領域において元の問題の目的関数を下から抑える』(*)

なる性質を持たなければなりません.したがって,このアルゴリズムを実行するには,制約式や目的関数の解析的な性質を用いながら上記の性質を持つように,子問題を生成する必要があります.

 非線形関数として表された制約式や目的関数の形は非常に多様ですので,この子問題生成過程を自動化することは一般に困難です.しかし,定式の情報がモデリング言語を通じて,初等的な関数の合成(計算グラフ)として表現されていることを利用すれば,その過程を自動化,ユーザが特に意識することなく,大域的最適解の探索を行うことができます.

 本アルゴリズムを用いる際に注意すべき点は,多数の子問題を繰り返し解くことによるメモリ消費です.本アルゴリズムで子問題を生成する仕組みは,組み合わせ最適化問題でよく用いられる分枝限定法に基づくものですが,組み合わせ問題の性質によっては分枝限定法が長い時間を要するのと同じように,本問題でも長い計算時間を要する可能性があります.

注1)大域的最適解も局所的最適解の一つと言えます.


 

 

上に戻る