グローバル最適化

大域的最適化は、オペレーションズ・リサーチ、応用数学、数値解析の一分野であり、与えられた集合における関数または関数集合の大域的最小値または最大値を求めることを試みます。実数値関数の最大化は関数の最小化と等価であるため、通常、最小化問題と呼ばれます。 $g(x)$ $f(x):=(-1)\cdot g(x)$

大域的最小値と、におけるすべての大域的最小化関数の集合を持つ、おそらく非線形かつ非凸な連続関数が与えられれば、標準的な最小化問題は次のように与えられる。 $f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R}$ $f^{*}$ $X^{*}$ $\オメガ$

\min _{x\in \Omega }f(x),

つまり、における大域的最小値とを見つけることです。ここで、は不等式によって定義される（必ずしも凸ではない）コンパクトセットです。 $f^{*}$ $X^{*}$ $\オメガ$ $g_{i}(x)\geqslant 0,i=1,\ldots ,r$

大域最適化は、局所最適化とは異なり、与えられた集合における最小値または最大値を見つけることに焦点を当てており、局所的最小値や最大値を見つけることとは対照的です。任意の局所最小値を見つけることは、古典的な局所最適化手法を用いれば比較的簡単です。関数の大域的最小値を見つけることははるかに困難です。解析的手法は適用できないことが多く、数値解法を用いると非常に困難な課題につながることがよくあります。

アプリケーション

グローバル最適化アプリケーションの典型的な例は次のとおりです。

タンパク質構造予測（エネルギー/自由エネルギー関数の最小化）
計算系統学（例：樹形図における形質変換の数を最小化する）
巡回セールスマン問題と電気回路設計（経路長の最小化）
化学工学（例：ギブスエネルギーの分析）
安全性検証、安全工学（例：機械構造物、建物）
最悪のケース分析
数学の問題（例：ケプラー予想）
オブジェクトパッキング（構成設計）の問題
いくつかの分子動力学シミュレーションの開始点は、シミュレートするシステムのエネルギーの初期最適化です。
スピングラス
電波伝搬モデルや科学・工学分野における他の多くのモデルの較正
非線形最小二乗分析やその他の一般化のような曲線フィッティングは、化学、物理学、生物学、経済学、金融、医学、天文学、工学の分野で、モデルパラメータを実験データに適合させる際に使用されます。
IMRT放射線治療計画

決定論的手法

最も成功する一般的な正確な戦略は次のとおりです。

内側と外側の近似

どちらの戦略においても、関数の最適化対象となる集合は多面体で近似されます。内近似では多面体が集合に含まれますが、外近似では多面体が集合に含まれます。

切断面法

切断面法とは、実行可能集合または目的関数を、カットと呼ばれる線形不等式を用いて反復的に改良する最適化手法の総称です。このような手法は、混合整数線形計画問題（MILP）の整数解を求める際に広く用いられているほか、必ずしも微分可能ではない一般的な凸最適化問題を解く際にも用いられます。MILPを解くための切断面法は、 Ralph E. GomoryとVáclav Chvátalによって導入されました。

分岐限定法

分岐限定法（BBまたはB&B）は、離散最適化問題および組み合わせ最適化問題のためのアルゴリズム設計パラダイムです。分岐限定法アルゴリズムは、状態空間探索による候補解の体系的な列挙から構成されます。候補解の集合は、集合全体をルートとするルート付きツリーを形成するものと考えられています。アルゴリズムは、解集合のサブセットを表すこのツリーの分岐を探索します。分岐の候補解を列挙する前に、その分岐は最適解の推定上限と下限に対してチェックされ、アルゴリズムによってこれまでに見つかった最良の解よりも優れた解を生成できない場合は破棄されます。

間隔法

区間演算、区間数学、区間解析、または区間計算は、1950年代から1960年代にかけて数学者によって開発された手法であり、数学的計算における丸め誤差や測定誤差に上限を設け、信頼性の高い結果をもたらす数値解析手法を開発するためのアプローチです。区間演算は、方程式や最適化問題に対する信頼性が高く保証された解を見つけるのに役立ちます。

実代数幾何学に基づく方法

実代数学は、代数学のうち実代数幾何学（および半代数幾何学）に関連する分野です。主に、順序体および順序環（特に実閉体）の研究と、それらの正多項式および多項式の平方和の研究への応用を扱います。凸最適化にも応用できます。

確率的手法

正確または不正確なモンテカルロベースのアルゴリズムはいくつか存在します。

直接モンテカルロサンプリング

この方法では、ランダムシミュレーションを使用して近似解を見つけます。

例:巡回セールスマン問題は、いわゆる従来の最適化問題です。つまり、最適な経路を決定するために必要なすべての事実 (各目的地間の距離) は確実にわかっており、目標は可能な移動手段をすべて試して、総距離が最短となるものを見つけることです。ただし、各目的地までの総移動距離を最小化するのではなく、各目的地に到着するまでの総所要時間を最小化したいとします。これは、移動時間が本質的に不確実であるため (交通渋滞、時間帯など)、従来の最適化の範囲を超えています。結果として、最適な経路を決定するには、シミュレーション、つまり最適化を使用して、まず、ある地点から別の地点までの移動にかかる可能性のある時間の範囲 (この場合は特定の距離ではなく確率分布で表される) を把握し、次に移動の決定を最適化して、その不確実性を考慮した最適な経路を特定する必要があります。

確率的トンネリング

確率的トンネリング（STUN）は、モンテカルロ法に基づく大域最適化手法です。STUNは、客観的に最小化される関数をサンプリングし、関数を非線形変換することで、関数の最小値を含む領域間のトンネリングを容易にします。トンネリングが容易になることで、サンプル空間の探索が高速化し、良好な解への収束が速くなります。

平行焼戻し

パラレルテンパリング（レプリカ交換MCMCサンプリング）は、物理システムのモンテカルロ法シミュレーション、そしてより一般的にはマルコフ連鎖モンテカルロ（MCMC）サンプリング法の動的特性を改善することを目的としたシミュレーション手法です。レプリカ交換法は、もともとSwendsen ^[1]によって考案され、その後Geyer ^{[2]によって拡張され、その後}Giorgio Parisi ^[3]などによって発展させられました。^[4] 杉田と岡本はパラレルテンパリングの分子動力学バージョンを定式化しました。^[5]これは通常、レプリカ交換分子動力学、またはREMDとして知られています。

基本的には、ランダムに初期化されたシステムのN個のコピーを異なる温度で実行します。次に、メトロポリス基準に基づいて、異なる温度における構成を交換します。この手法の考え方は、高温での構成を低温でのシミュレーションに利用できるようにすることです。また、その逆も可能です。これにより、低エネルギー構成と高エネルギー構成の両方をサンプリングできる非常に堅牢なアンサンブルが得られます。このようにして、一般にカノニカルアンサンブルでは十分に計算されない比熱などの熱力学的特性を、非常に高い精度で計算できます。

ヒューリスティックスとメタヒューリスティックス

その他のアプローチには、次のような、多かれ少なかれインテリジェントな方法で検索スペースを検索するヒューリスティック戦略が含まれます。

アリコロニー最適化（ACO）
シミュレーテッドアニーリング、一般的な確率的メタヒューリスティック
タブー探索、局所最小値から脱出可能な局所探索の拡張
進化アルゴリズム（例：遺伝的アルゴリズムや進化戦略）
微分進化法は、与えられた品質尺度に関して候補となる解決策を繰り返し改善することで問題を最適化する手法である。
群集ベースの最適化アルゴリズム（例：粒子群集最適化、社会的認知最適化、マルチ群集最適化、アリコロニー最適化）
グローバル検索戦略とローカル検索戦略を組み合わせたミームアルゴリズム
反応型検索最適化（すなわち、サブシンボリック機械学習技術を検索ヒューリスティックスに統合すること）
段階的最適化は、最初に非常に単純化された問題を解き、その問題を（最適化しながら）徐々に変形していき、困難な最適化問題と等価になるまで、困難な最適化問題を解決しようとする手法である。^[6]^[7]^[8]

応答曲面法に基づくアプローチ

自己組織化に基づくIOSO間接最適化
ベイズ最適化、ベイズ統計を用いたブラックボックス関数の大域的最適化のための逐次設計戦略^[9]

参照

脚注

^ Swendsen RHとWang JS (1986) スピングラスのレプリカモンテカルロシミュレーション Physical Review Letters 57: 2607–2609
^ CJ Geyer、(1991)「コンピューティング科学と統計」、第23回インターフェイスシンポジウム議事録、アメリカ統計協会、ニューヨーク、p. 156。
^ Marco FalcioniとMichael W. Deem (1999). 「ゼオライト構造解析のためのバイアス付きモンテカルロ法」. J. Chem. Phys . 110 (3): 1754– 1766. arXiv : cond-mat/9809085 . Bibcode :1999JChPh.110.1754F. doi :10.1063/1.477812. S2CID 13963102.
^ David J. EarlとMichael W. Deem (2005)「平行テンパリング：理論、応用、そして新たな展望」、 Phys. Chem. Chem. Phys.、7、3910
^ Y. Sugita and Y. Okamoto (1999). 「レプリカ交換分子動力学法によるタンパク質フォールディング」. Chemical Physics Letters . 314 ( 1– 2): 141– 151. Bibcode :1999CPL...314..141S. doi :10.1016/S0009-2614(99)01123-9.
^ Thacker, Neil; Cootes, Tim (1996). 「段階的非凸性と多重解像度最適化法」. Vision Through Optimization .
^ ブレイク、アンドリュー; ジッサーマン、アンドリュー (1987). Visual Reconstruction. MIT Press. ISBN 0-262-02271-0。^{[ページが必要]}
^ Hossein Mobahi、John W. Fisher III. ガウスホモトピー継続と凸包の関連性について、Lecture Notes in Computer Science (EMMCVPR 2015)、Springer、2015年。
^ Jonas Mockus (2013). ベイズ的アプローチによるグローバル最適化：理論と応用. Kluwer Academic.

参考文献

決定論的グローバル最適化:

R. Horst、H. Tuy、「グローバル最適化：決定論的アプローチ」、Springer、1996 年。
R. Horst、PM Pardalos、NV Thoai著、『グローバル最適化入門、第2版』Kluwer Academic Publishers、2000年。
A.Neumaier、「連続グローバル最適化と制約充足における完全な探索」、Acta Numerica 2004 (A. Iserles 編)、Cambridge University Press 2004 の 271 ～ 369 ページ。
M. Mongeau, H. Karsenty, V. Rouzé, J.-B. Hiriart-Urruty, ブラックボックスグローバル最適化のためのパブリックドメインソフトウェアの比較. Optimization Methods & Software 13(3), pp. 203–226, 2000.
JD Pintér著『Global Optimization in Action - Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications』Kluwer Academic Publishers, Dordrecht, 1996. 現在、Springer Science and Business Media, New Yorkより刊行。本書では、確率的グローバル最適化手法についても解説している。
L. ジョリン、M. キーファー、O. ディドリット、E. ウォルター (2001)。適用された間隔分析。ベルリン：シュプリンガー。
ER Hansen (1992)、Interval Analysis を使用した Global Optimization、Marcel Dekker、ニューヨーク。

シミュレーテッドアニーリングの場合:

Kirkpatrick, S.; Gelatt, CD; Vecchi, MP (1983-05-13). 「シミュレーテッドアニーリングによる最適化」. Science . 220 (4598). アメリカ科学振興協会 (AAAS): 671– 680. Bibcode : 1983Sci...220..671K. doi : 10.1126/science.220.4598.671. ISSN 0036-8075. PMID 17813860. S2CID 205939.

反応型検索最適化の場合:

Roberto Battiti、M. Brunato、F. Mascia、「Reactive Search and Intelligent Optimization」、Operations Research/Computer Science Interfaces Series、第45巻、Springer、2008年11月。ISBN 978-0-387-09623-0

確率的手法の場合:

A. Zhigljavsky著『大域ランダム探索理論』数学とその応用、Kluwer Academic Publishers、1991年。
Hamacher, K (2006). 「複雑なポテンシャルエネルギーランドスケープの確率的トンネル効果による大域最適化における適応」. Europhysics Letters 74 (6). IOP Publishing: 944– 950. Bibcode : 2006EL.....74..944H. doi : 10.1209/epl/i2006-10058-0. ISSN 0295-5075. S2CID 250761754.
Hamacher, K.; Wenzel, W. (1999-01-01). 「完全ファネルランドスケープにおける確率的最小化アルゴリズムのスケーリング挙動」. Physical Review E. 59 ( 1): 938– 941. arXiv : physics/9810035 . Bibcode :1999PhRvE..59..938H. doi :10.1103/physreve.59.938. ISSN 1063-651X. S2CID 119096368.
Wenzel, W.; Hamacher, K. (1999-04-12). 「複雑なポテンシャルエネルギーランドスケープの大域的最小化のための確率的トンネリングアプローチ」. Physical Review Letters . 82 (15). American Physical Society (APS): 3003– 3007. arXiv : physics/9903008 . Bibcode :1999PhRvL..82.3003W. doi :10.1103/physrevlett.82.3003. ISSN 0031-9007. S2CID 5113626.

平行焼戻しの場合：

Hansmann, Ulrich HE (1997). 「生体分子のコンフォメーション研究のための並列テンパリングアルゴリズム」. Chemical Physics Letters . 281 ( 1–3 ). Elsevier BV: 140–150 . arXiv : physics/9710041 . Bibcode :1997CPL...281..140H. doi :10.1016/s0009-2614(97)01198-6. ISSN 0009-2614. S2CID 14137470.

継続メソッドの場合:

Zhijun Wu. 大域最適化への特殊接続アプローチとしての有効エネルギー変換スキームと分子コンフォメーションへの応用. 技術報告書, アルゴンヌ国立研究所, イリノイ州 (米国), 1996年11月.

目的関数の定義領域の次元に関する一般的な考慮事項:

Hamacher, Kay (2005). 「1次元関数の確率的大域最適化について」. Physica A: 統計力学とその応用. 354. Elsevier BV: 547–557 . Bibcode :2005PhyA..354..547H. doi :10.1016/j.physa.2005.02.028. ISSN 0378-4371.

決定論的および確率論的グローバル最適化手法を比較できる戦略については

外部リンク

A. Neumaierのグローバル最適化に関するページ
L. リベルティ著「グローバル最適化入門」
トーマス・ワイズによる無料電子書籍