決定論的大域最適化は、最適化問題の大域解を求めることに重点を置いた数理最適化の一分野であり、提示された解が、事前に定義された許容範囲内で、実際に大域解であることを理論的に保証します。「決定論的大域最適化」という用語は、通常、完全または厳密な（下記参照）最適化手法を指します。厳密な手法は、有限時間内に大域最適解に収束します。決定論的大域最適化手法は、大域解を求めることが必須である場合（つまり、数学モデルによって記述される唯一の自然発生状態が最適化問題の大域最小値である場合）、実行可能な解を求めることが極めて困難な場合、あるいは単にユーザーが問題に対する最善の解を求めたい場合に使用されます。
概要
ノイマイヤー[ 1 ]は、最適解に近づく厳密さの度合いに応じて、グローバル最適化手法を次の4つのカテゴリーに分類しました。
- 不完全な方法は、探索に巧妙な直感的なヒューリスティックスを使用するが、探索が局所的最小値に陥った場合の安全策がない。
- 漸近的に完全な方法は、確実に、または少なくとも無制限に実行できる場合は確率 1 でグローバル最小値に到達しますが、グローバル最小値が見つかったかどうかを知る手段はありません。
- 完全な方法では、正確な計算と無制限に長い実行時間を前提として、確実にグローバル最小値に到達し、有限時間後に近似グローバル最小値が見つかったことが分かります (規定の許容範囲内で)。
- 厳密な方法では、許容誤差を超える可能性がある近似退化の場合を除き、丸め誤差が存在する場合でも、確実に、指定された許容誤差内でグローバル最小値に到達します。
決定論的グローバル最適化手法は、通常、最後の2つのカテゴリに属します。厳密なソフトウェアを構築するには、すべての依存関係も厳密にコーディングする必要があるため、非常に困難であることに注意してください。
決定論的大域最適化法では、空間の領域にわたって関数値を厳密に制限する方法が必要です。この文脈における決定論的手法と非決定論的手法の主な違いは、前者が解空間の領域にわたって計算を実行するのに対し、後者は単一の点について計算を実行することであると言えます。これは、特定の関数形式（例：マコーミック緩和[ 2 ]）を利用するか、より一般的な関数形式で動作するために区間解析を使用することによって行われます。いずれの場合でも制限が必要であるため、決定論的大域最適化法では、ブラックボックスコードで作業する場合、そのコードが関数の境界も返すように明示的に記述されていない限り、厳密な結果を得ることができません。このため、決定論的大域最適化の問題は計算グラフを使用して表現されるのが一般的です。これは、結果として得られる関数値または導関数が区間（スカラーではなく）の結果を生成するようにすべての演算子をオーバーロードするのが簡単であるためです。
決定論的グローバル最適化問題のクラス
線形計画問題（LP）
線形計画問題は、あらゆる実用的な問題にとって非常に望ましい定式化です。その理由は、内点法アルゴリズムの登場により、非常に大規模な問題（数十万、あるいは数百万の変数を含む）を効率的に大域的最適解へと解くことが可能になったためです。線形計画最適化問題は、厳密には決定論的大域的最適化の範疇に属します。
混合整数線形計画問題（MILP）
線形計画問題と同様に、MILPは意思決定モデルを解く際に非常に重要です。この種の複雑な問題を解くための効率的なアルゴリズムは既知であり、 CPLEXなどのソルバーとして利用可能です。
非線形計画問題（NLP）
非線形計画問題は、決定論的大域最適化において極めて困難です。現代のソルバーが妥当な時間で処理できると期待される非線形変数の数は、おおよそ100から数百個程度です。本稿執筆時点では、NLPの決定論的解法を扱う並列ソルバーは存在せず、これが決定論的LPとNLPプログラミングの計算量格差の原因となっています。
混合整数非線形計画問題（MINLP）
NLPの問題よりもさらに困難で、MINLPの問題を決定論的に解くことは非常に困難です。整数カットや、整数変数に基づいて問題を分岐させる（つまり、決定論的に解けるNLPのサブ問題を作成する）といった手法がよく用いられます。
ゼロ次メソッド
ゼロ次法は、ゼロ次区間演算を利用する手法である。[ 3 ]代表的な例としては区間二分法がある。
一次手法
一次手法は、区間勾配や区間傾きなどの一次情報を利用する手法で構成されます。
二次的方法
2次解法は、通常、区間ヘッセ行列から導出される固有値境界などの2次情報を利用します。一般的な問題を扱う最も一般的な2次解法の一つは、αΒΒアルゴリズムです。
決定論的グローバル最適化ソルバー
- 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 ]を解くことができます。
参考文献
- ^連続グローバル最適化と制約充足における完全探索、Acta Numerica 2004（A. Iserles 編）、ケンブリッジ大学出版局 2004
- ^因数分解可能な非凸計画の大域解の計算可能性：第1部 - 凸過小評価問題、数理計画、1976年、1(10)、147-175
- ^ Hansen, ER、区間分析を使用したグローバル最適化、Marcel Dekker Inc、ニューヨーク、1992
- ^ Misener, Ruth ; Floudas, Christodoulos A. (2014). 「ANTIGONE: 非線形方程式の連続／整数大域的最適化アルゴリズム」. Journal of Global Optimization . 59 ( 2–3 ): 503–526 . doi : 10.1007/s10898-014-0166-2 . hdl : 10044/1/15506 . S2CID 41823802 .
- ^ ANTIGONEのGAMS文書、2013年4月16日、 2019年7月27日閲覧。
- ^ 「NEOSサーバー上のBARON」 。 2013年6月29日時点のオリジナルよりアーカイブ。2016年1月26日閲覧。
- ^ 「最適化会社」。
- ^ P. ベロッティ、C. キルヒェス、 S. レイファー、J. リンデロート、J. リュートケ、A. マハジャン (2013)。混合整数非線形最適化。 Acta Numerica、22、1-131 ページ。土井：10.1017/S0962492913000032。 http://journals.cambridge.org/abstract_S0962492913000032
- ^ Wilhelm, ME ; Stuber, MD (2020). 「EAGO.jl: Julia での簡単かつ高度なグローバル最適化」 .最適化手法とソフトウェア. 37 (2): 425– 450. doi : 10.1080/10556788.2020.1786566 . S2CID 225503302 .
- ^「EAGO ソースコード」。GitHub 。
- ^ Linus E. Schrage, 線形計画法、整数計画法、二次計画法、Scientific Press、1986年、 ISBN 0894260901
- ^ 「混合整数非線形グローバル最適化のためのマコーミックベースのアルゴリズム（MAiNGO）」。
- ^ 「MAiNGO ソースコード」。
- ^ 「オクターアクト」。
- ^ 「SCIP最適化スイート」。
