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

決定論的グローバル最適化は、数学的最適化の 1 分野であり、最適化問題のグローバル ソリューションを見つけることに焦点を当てながら、報告されたソリューションが定義済みの許容範囲内で実際にグローバル ソリューションであるという理論的な保証を提供します。「決定論的グローバル最適化」という用語は、通常、完全または厳密な(以下を参照) 最適化方法を指します。厳密な方法は、有限時間内にグローバル最適値に収束します。決定論的グローバル最適化方法は、通常、グローバル ソリューションを見つけることが必要な場合 (つまり、数学モデルによって記述される唯一の自然発生状態が最適化問題のグローバル最小値である場合)、実行可能なソリューションを見つけることが非常に難しい場合、または単にユーザーが問題に対する最善のソリューションを見つけたい場合に使用されます。

ノイマイヤー^[1]は、最適解に近づく厳密さの度合いに応じて、グローバル最適化手法を次の4つのカテゴリーに分類しました。

• 不完全な方法では、検索に巧妙な直感的なヒューリスティックを使用しますが、検索が局所的最小値で行き詰まった場合の安全策はありません。
• 漸近的に完全な方法は、確実に大域的最小値に到達します。または、無限に実行された場合は少なくとも確率 1 で大域的最小値に到達しますが、大域的最小値が見つかったかどうかを知る手段はありません。
• 完全な方法では、正確な計算と無限に長い実行時間を前提として、確実にグローバル最小値に到達し、有限時間後に近似グローバル最小値が見つかったことが分かります (規定の許容範囲内で)。
• 厳密な方法では、許容範囲を超える可能性がある近似退化の場合を除き、丸め誤差が存在する場合でも、確実に、指定された許容範囲内でグローバル最小値に到達します。

決定論的グローバル最適化手法は、通常、最後の 2 つのカテゴリに属します。プロセスではすべての依存関係も厳密にコーディングする必要があるため、厳密なソフトウェアを構築するのは非常に難しいことに注意してください。

決定論的大域最適化法では、関数の値を空間の領域にわたって厳密に制限する方法が必要です。この文脈における決定論的方法と非決定論的方法の主な違いは、前者が解空間の領域にわたって計算を実行するのに対し、後者は単一のポイントで計算を実行することであると言えます。これは、特定の関数形式 (例: McCormick 緩和^[2] ) を利用するか、より一般的な関数形式で作業するために区間解析を使用することによって行われます。いずれの場合も制限が必要であるため、決定論的大域最適化法では、ブラック ボックスコードで作業する場合、そのコードが関数の制限も返すように明示的に記述されていない限り、厳密な結果を得ることができません。このため、決定論的大域最適化の問題は計算グラフを使用して表現されるのが一般的です。これは、結果の関数値または導関数が区間 (スカラーではなく) の結果を生成するようにすべての演算子をオーバーロードするのが簡単であるためです。

線形計画問題は、あらゆる実用的な問題にとって非常に望ましい定式化です。その理由は、内点アルゴリズムの登場により、非常に大規模な問題 (数十万、あるいは数百万の変数を含む) を効率的にグローバル最適に解決できるようになったためです。線形計画最適化問題は、厳密には決定論的グローバル最適化のカテゴリに分類されます。

線形計画問題と同様に、MILP は意思決定モデルを解くときに非常に重要です。このタイプの複雑な問題を解決するための効率的なアルゴリズムは知られており、CPLEXなどのソルバーの形で利用できます。

非線形計画問題は、決定論的グローバル最適化において極めて困難です。現代のソルバーが妥当な時間内に処理できると期待できる非線形変数の数は、およそ 100 から数百です。この記事の執筆時点では、NLP の決定論的ソリューションに対する並列ソルバーは存在せず、これが決定論的 LP と NLP プログラミング間の複雑さのギャップの原因となっています。

NLP の問題よりもさらに難しいのは、MINLP の問題を決定論的に解決することです。整数カットや、整数変数で問題を分岐させる (これにより、決定論的に解決できる NLP サブ問題が作成される) などの手法がよく使用されます。

ゼロ次法は、ゼロ次区間演算を利用する方法である。^[3]代表的な例としては区間二分法がある。

一次方法は、区間勾配や区間傾きなどの一次情報を利用する方法で構成されます。

2 次法では、2 次情報、通常は区間ヘッセ行列から導出される固有値境界を利用します。一般的なタイプの問題を処理する最も一般的な 2 次方法論の 1 つは、 αΒΒアルゴリズムです。

• ANTIGONE：非線形方程式の連続/整数グローバル最適化アルゴリズム）。^[4]これは独自のソフトウェアであり、GAMSモデリングプラットフォームANTIGONEを通じて入手可能です。^[5]
• BARON : BARONはAIMMS、AMPL、GAMS モデリング言語およびNEOSサーバーで利用可能です。 ^[6]これは独自のソフトウェアです^[7]
• Couenne : 非線形推定のための凸包オーバー・アンダーエンベロープ（Couenne）はオープンソースライブラリである^[8]
• EAGO: Easy-Advanced Global Optimization (EAGO) ^{[9] は、}Julia (プログラミング言語)で書かれたオープンソースのソルバーです。コネチカット大学で開発されました。^[10]
• LINDO（線形、対話型、離散最適化装置）にはグローバル最適化機能が含まれています。^[11]
• MAiNGO: McCormickベースの混合整数非線形大域最適化アルゴリズム(MAiNGO) ^[12]は、MPIとOpenMPの並列化を備えたC++パッケージであり、Eclipse Public License - v 2.0の下でオープンソース ^[13]として提供されています。
• Octeractエンジンは並列化機能を備えた独自のソルバーです。Octeract ^{[14]によって開発され、ライセンスされています。}
• SCIP : SCIPは、混合整数非線形計画法（MINLP） ^[15]などを解くオープンソースの最適化ソルバースイートです。