グローバル最適化

グローバル最適化は、与えられた集合上の関数または関数集合のグローバル最小値または最大値を見つけようとする応用数学および数値解析の分野です。実数値関数の最大化は関数の最小化と同等であるため、通常は最小化問題として説明されます。 ${\displaystyle g(x)}$${\displaystyle f(x):=(-1)\cdot g(x)}$

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

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

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

グローバル最適化は、ローカルな最小値や最大値を見つけるのではなく、指定されたセットの最小値や最大値を見つけることに重点を置く点で、ローカルな最適化と区別されます。任意のローカルな最小値を見つけることは、従来のローカル最適化方法を使用すると比較的簡単です。関数のグローバルな最小値を見つけることははるかに困難です。解析的方法は適用できないことが多く、数値解法戦略を使用すると非常に困難な課題につながることがよくあります。

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

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

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

これら両方の戦略では、関数が最適化されるセットは多面体によって近似されます。内部近似では、多面体がセットに含まれ、外部近似では、多面体がセットに含まれます。

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

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

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

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

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

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

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

確率的トンネリング(STUN) は、モンテ カルロ法に基づくグローバル最適化のアプローチです。モンテ カルロ法では、関数を非線形に変換して、関数の最小値を含む領域間でのトンネリングを容易にし、客観的に最小化される関数をサンプリングします。トンネリングが容易になると、サンプル空間の探索が高速化され、適切なソリューションへの収束が高速化されます。

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

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

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

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

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

• 決定論的グローバル最適化
• 多分野にわたる設計最適化
• 多目的最適化
• 最適化（数学）

• A. Neumaier のグローバル最適化に関するページ
• L. Liberti によるグローバル最適化入門
• トーマス・ワイズによる無料電子書籍