数理最適化

次の表記法を考えてみましょう。

${\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)}$

これは、実数の集合からxを選択した場合の目的関数x ² + 1の最小値を表します。${\displaystyle \mathbb {R} }$この場合の最小値は 1 であり、x = 0のときに発生します。

同様に表記法

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

目的関数 2x の最大値を求めます。ここでx は任意の実数です。この場合、目的関数は有界ではないため、最大値は存在しません。したがって、答えは「無限大」または「未定義」です。

次の表記法を考えてみましょう。

${\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}$

または同等に

${\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{制約条件:}}\;x\in (-\infty ,-1].}$

これは、目的関数x ² + 1を最小化する区間(−∞,−1]内の引数xの値 (または複数の値) を表します(この関数の実際の最小値は、問題で求められているものではありません)。この場合、x = 0は実行不可能、つまり実行可能集合に含まれないため、答えはx = −1です。

同様に、

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,}$

または同等に

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{制約条件:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

は、目的関数x cos yの値を最大化する（または最大化する） { x , y } のペア（またはペア）を表します。ただし、 x は区間[−5,5]内にあるという制約が追加されます（繰り返しますが、式の実際の最大値は関係ありません）。この場合、解は{5, 2 k π }と{−5, (2 k + 1) π }の形式のペアです。ここで、k はすべての整数の範囲をとります。

演算子arg minとarg max は、 argminとargmaxとも表記されることがあり、それぞれ最小値の引数と最大値の引数を表します。

最適化問題に複数の目的を追加すると、複雑さが増します。例えば、構造設計を最適化する場合、軽量かつ高剛性の設計が望ましいでしょう。2つの目的が相反する場合、トレードオフが生じます。最も軽量な設計、最も高剛性な設計がそれぞれ1つずつ存在し、重量と剛性の妥協点となる設計は無数に存在する可能性があります。ある基準を改善するために別の基準を犠牲にするトレードオフ設計の集合は、パレート集合と呼ばれます。最適な設計の重量と剛性の関係を示すグラフは、パレートフロンティアと呼ばれます。

ある設計が「パレート最適」（あるいは「パレート効率的」またはパレート集合に含まれる）であると判断されるのは、他のどの設計にも劣っていない場合である。ある設計が他の設計よりもいくつかの点で劣っていて、かつどの点においても優れていない場合、その設計は他の設計に劣っており、パレート最適ではない。

「パレート最適」解の中から「最適な解」を選択する権限は、意思決定者に委ねられます。言い換えれば、問題を多目的最適化として定義するということは、何らかの情報が不足していることを示しています。望ましい目標は与えられていますが、それらの組み合わせが互いに相対的に評価されていないのです。場合によっては、意思決定者との対話を通じて、不足している情報を補うことができます。

多目的最適化問題は、さらに一般化されてベクトル最適化問題となり、そこでは（部分的な）順序はもはやパレート順序によって与えられません。

最適化問題はしばしば多峰性、つまり複数の優れた解を持つ。それらの解はすべて全体的に優れている（コスト関数の値が同じ）場合もあれば、全体的に優れた解と局所的に優れた解が混在している場合もある。多峰性最適化アルゴリズムの目標は、これらの複数の解のすべて（または少なくとも一部）を取得することである。

古典的な最適化手法は反復的なアプローチをとるため、複数の解を求める場合には満足のいく結果が得られない。なぜなら、アルゴリズムを複数回実行しても、異なる開始点を用いた場合でも、異なる解が得られるとは限らないからである。

複数の局所的極値が存在する可能性のあるグローバル最適化問題に対する一般的なアプローチには、進化アルゴリズム、ベイズ最適化、シミュレーテッドアニーリングなどがあります。

充足可能性問題（実行可能性問題とも呼ばれる）とは、目的値に関係なく、実行可能な解をとにかく見つける問題のことである。これは、目的値がすべての解で同じであり、したがってどの解も最適であるという、数学的最適化の特殊なケースとみなすことができる。

多くの最適化アルゴリズムは、実行可能な開始点から始める必要があります。そのような開始点を得る方法の一つは、スラック変数を用いて実行可能性条件を緩和することです。十分なスラックがあれば、どの開始点も実行可能になります。次に、スラックがゼロまたは負になるまで、そのスラック変数を最小化します。

カール・ワイエルシュトラスの極値定理は、コンパクト集合上の連続実数値関数は最大値と最小値をとることを述べている。より一般的には、コンパクト集合上の下半連続関数は最小値をとり、上半連続関数は最大値をとる。

フェルマーの定理の一つに、制約のない問題の最適解は、目的関数の1階微分または勾配がゼロとなる停留点（ 1階微分判定法を参照）で見つかるというものがあります。より一般的には、目的関数の1階微分または勾配がゼロまたは未定義となる臨界点、あるいは選択集合の境界で見つかる場合もあります。内部最適解において1階微分がゼロとなることを示す方程式（または方程式の集合）は、「1階条件」または「1階条件の集合」と呼ばれます。

等式制約問題の最適解は、ラグランジュ乗数法によって求めることができる。等式制約および／または不等式制約を持つ問題の最適解は、「カルーシュ・クーン・タッカー条件」を用いて求めることができる。

1次導関数テストは極値である可能性のある点を特定しますが、このテストでは最小値である点と最大値である点、あるいはどちらでもない点を区別することはできません。目的関数が2回微分可能な場合、制約のない問題では2次導関数または2次導関数の行列（ヘッセ行列と呼ばれる）をチェックすることで、制約のある問題では目的関数と制約の2次導関数の行列（境界付きヘッセ行列と呼ばれる）をチェックすることで、これらのケースを区別できます。最大値または最小値を他の停留点から区別する条件は「2次条件」と呼ばれます（「2次導関数テスト」を参照）。候補解が1次条件を満たす場合、2次条件も満たせば、少なくとも局所最適性を確立するのに十分です。

包絡線定理は、基礎となるパラメータが変化したときに最適解の値がどのように変化するかを説明する定理である。この変化を計算するプロセスは比較静学と呼ばれる。

クロード・ベルジュの最大値定理（1963年）は、最適解の連続性を基礎となるパラメータの関数として記述する。

2 度微分可能な関数の制約のない問題では、目的関数の勾配がゼロになる点(つまり、停留点) を見つけることで、いくつかの重要な点を見つけることができます。より一般的には、ゼロの劣勾配は、凸関数やその他の局所的にリプシッツな関数を用いた最小化問題で局所最小値が見つかったことを証明します。これらの関数は、ニューラル ネットワークの損失関数の最小化で出会います。正負の運動量推定により、局所最小値を回避し、目的関数のグローバル最小値に収束します。^{[ 8 ]}

さらに、臨界点はヘッセ行列の正定値性によって分類できます。臨界点においてヘッセ行列が正定値であれば、その点は局所最小値です。ヘッセ行列が負定値であれば、その点は局所最大値です。最後に、不定値であれば、その点は何らかの鞍点です。

制約付き問題は、ラグランジュ乗数を用いることで、多くの場合、制約なし問題に変換できる。また、ラグランジュ緩和法は、困難な制約付き問題に対して近似解を提供することもできる。

目的関数が凸関数である場合、局所最小値は同時に大域最小値にもなります。凸関数を最小化するための効率的な数値計算手法として、内点法などが存在します。

より一般的には、目的関数が二次関数でない場合、多くの最適化手法では、反復のサブシーケンスが最適解に収束することを保証するために他の手法を使用します。収束を保証する最初の、そして今でもよく使われる手法は、関数を一次元に沿って最適化する線探索です。収束を保証する2番目の、そしてますます人気が高まっている手法は、信頼領域を使用します。線探索と信頼領域はどちらも、微分不可能な最適化の現代的な手法で使用されています。通常、グローバル最適化は高度なローカル最適化（ BFGSなど）よりもはるかに遅いため、多くの場合、ローカル最適化を異なる開始点から開始することで、効率的なグローバル最適化を構築できます。

• 線形計画法のために設計されたジョージ・ダンツィヒのシンプレックス法
• 二次計画法および線形分数計画法用に設計されたシンプレックス法の拡張
• ネットワーク最適化に特に適したシンプレックスアルゴリズムの変種
• 組み合わせアルゴリズム
• 量子最適化アルゴリズム

非線形計画問題を解くために用いられる反復法は、ヘッセ行列、勾配、あるいは関数値のみを評価するかどうかによって異なる。ヘッセ行列（H）と勾配（G）を評価することで収束速度は向上するが、これらの量が存在し、十分に滑らかに変化する関数においては、このような評価は各反復の計算複雑度（または計算コスト）を増加させる。場合によっては、計算複雑度が過度に高くなることもある。

最適化アルゴリズムの主要な基準の一つは、必要な関数評価の回数です。これは多くの場合、すでに大きな計算負荷となり、通常は最適化アルゴリズム自体よりもはるかに多くの計算負荷がかかります。最適化アルゴリズムは主にN個の変数に対して演算を行う必要があるためです。導関数はこのような最適化アルゴリズムに詳細な情報を提供しますが、計算はさらに困難です。例えば、勾配を近似するには、少なくともN+1回の関数評価が必要です。2次導関数の近似（ヘッセ行列にまとめられる）の場合、関数評価の回数はN²のオーダーになります。ニュートン法では2次導関数が必要となるため、各反復における関数呼び出しの回数はN²のオーダーになりますが、より単純な純粋な勾配最適化アルゴリズムではN回で済みます。ただし、勾配最適化アルゴリズムは通常、ニュートン法よりも多くの反復を必要とします。関数呼び出しの回数に関してどちらが最適かは、問題自体によって異なります。

• ヘッセ行列を評価する（または有限差分法を用いてヘッセ行列を近似する） 方法：
  • ニュートン法
  • 逐次二次計画法：ニュートン法に基づく、小規模から中規模の制約付き問題のための手法。一部のバージョンは大規模問題にも対応可能。
  • 内点法：これは制約付き最適化のための手法の大きなクラスであり、勾配情報のみを使用するものもあれば、ヘッセ行列の評価を必要とするものもあります。
• 勾配を評価する、または何らかの方法で勾配（あるいは劣勾配）を近似する手法：
  • 座標降下法：各反復で単一の座標を更新するアルゴリズム
  • 共役勾配法：大規模問題に対する反復法。（理論的には、これらの方法は二次目的関数を用いて有限ステップで終了するが、有限精度コンピュータでは実際にはこの有限終了は観測されない。）
  • 勾配降下法（別名「最急降下法」または「最急上昇法」）：歴史的、理論的に興味深い（時間のかかる）手法であり、巨大な問題の近似解を見つけるための手法として再び注目を集めている。
  • 劣勾配法：一般化勾配を用いた、局所的にリプシッツ連続な大規模関数に対する反復法。ボリス・T・ポリャクによれば、劣勾配射影法は共役勾配法に類似している。
  • バンドル降下法：局所的にリプシッツ連続な関数を持つ小規模から中規模の問題、特に凸最小化問題に対する反復法（共役勾配法に類似）。
  • Ellipsoid method: An iterative method for small problems with quasiconvex objective functions and of great theoretical interest, particularly in establishing the polynomial time complexity of some combinatorial optimization problems. It has similarities with Quasi-Newton methods.
  • Conditional gradient method (Frank–Wolfe) for approximate minimization of specially structured problems with linear constraints, especially with traffic networks. For general unconstrained problems, this method reduces to the gradient method, which is regarded as obsolete (for almost all problems).
  • Quasi-Newton methods: Iterative methods for medium-large problems (e.g. N<1000).
  • Simultaneous perturbation stochastic approximation (SPSA) method for stochastic optimization; uses random (efficient) gradient approximation.
• Methods that evaluate only function values: If a problem is continuously differentiable, then gradients can be approximated using finite differences, in which case a gradient-based method can be used.
  • Interpolation methods
  • Pattern search methods, which have better convergence properties than the Nelder–Mead heuristic (with simplices), which is listed below.
  • Mirror descent

Besides (finitely terminating) algorithms and (convergent) iterative methods, there are heuristics. A heuristic is any algorithm which is not guaranteed (mathematically) to find the solution, but which is nevertheless useful in certain practical situations. List of some well-known heuristics:

Problems in rigid body dynamics (in particular articulated rigid body dynamics) often require mathematical programming techniques, since you can view rigid body dynamics as attempting to solve an ordinary differential equation on a constraint manifold;^[9] the constraints are various nonlinear geometric constraints such as "these two points must always coincide", "this surface must not penetrate any other", or "this point must always lie somewhere on this curve". Also, the problem of computing contact forces can be done by solving a linear complementarity problem, which can also be viewed as a QP (quadratic programming) problem.

多くの設計問題は最適化問題として表現することもできます。この応用は設計最適化と呼ばれます。そのサブセットの一つが工学最適化であり、この分野の近年の成長著しいサブセットの一つが多分野設計最適化です。これは多くの問題に有用ですが、特に航空宇宙工学の問題に適用されています。

このアプローチは宇宙論や天体物理学に応用できる可能性がある。^{[ 10 ]}

経済学はエージェントの最適化と密接に関連しているため、影響力のある定義では、経済学を科学として「目的と希少な手段の関係としての人間の行動の研究」と定義し、代替的な用途も示しています。^{[ 11 ]}現代の最適化理論には、従来の最適化理論が含まれますが、ゲーム理論や経済均衡の研究とも重なります。Journal of Economic Literature のコードでは、数理計画法、最適化手法、および関連トピックをJEL:C61-C63に分類しています。

ミクロ経済学では、効用最大化問題とその双対問題である支出最小化問題は、経済最適化問題である。消費者は一貫した行動をとる限り効用を最大化すると想定され、企業は通常利益を最大化すると想定される。また、エージェントはリスク回避的であるとモデル化されることが多く、リスクを避けることを好む。資産価格も最適化理論を用いてモデル化されるが、その根底にある数学は静的最適化ではなく確率過程の最適化に基づいている。国際貿易理論も、国家間の貿易パターンを説明するために最適化を用いる。ポートフォリオの最適化は、経済学における多目的最適化の一例である。

1970年代以降、経済学者は制御理論を用いて時間の経過に伴う動的な意思決定をモデル化してきた。^{[ 12 ]}例えば、動的探索モデルは労働市場の行動を研究するために用いられる。^{[ 13 ]}決定論的モデルと確率的モデルの間には重要な区別がある。^{[ 14 ]}マクロ経済学者は、労働者、消費者、投資家、政府の相互依存的な最適化決定の結果として経済全体のダイナミクスを記述する動的確率的一般均衡（DSGE）モデルを構築する。 ^{[ 15 ] [ 16 ]}

電気工学における最適化技術の一般的な応用例としては、アクティブフィルタ設計^{[ 17 ]} 、超伝導磁気エネルギー貯蔵システムにおける迷走磁界の低減、マイクロ波構造の空間マッピング設計^{[ 18 ]}、ハンドセットアンテナ^{[ 19 ] [ 20 ] [ 21 ]} 、電磁気学に基づく設計などがある。マイクロ波コンポーネントおよびアンテナの電磁気的に検証された設計最適化では、 1993年の空間マッピングの発見以来、適切な物理ベースまたは経験的代理モデルと空間マッピング手法が広く利用されている^{[ 22 ] [ 23 ]。}最適化技術は電力潮流解析にも使用されている^{[ 24 ]}。

最適化は土木工学で広く利用されています。建設管理や交通工学は、最適化に大きく依存する土木工学の主要分野です。最適化によって解決される最も一般的な土木工学の問題は、道路の切土と盛土、構造物やインフラのライフサイクル分析^{[ 25 ]} 、資源平準化^{[ 26 ] [ 27 ]、}水資源配分、交通管理^{[ 28 ]}、スケジュール最適化などです。

最適化技術を幅広く利用するもう1つの分野はオペレーションズリサーチです。^{[ 29 ]}オペレーションズリサーチでは、意思決定の改善を支援するために確率的モデリングとシミュレーションも利用しています。オペレーションズリサーチでは、イベントに適応する動的な意思決定をモデル化するために確率的プログラミングがますます利用されるようになっています。このような問題は、大規模最適化と確率的最適化手法で解決できます。

数理最適化は、現代の多くの制御器設計で用いられています。モデル予測制御（MPC）やリアルタイム最適化（RTO）といった高度な制御器は、数理最適化を採用しています。これらのアルゴリズムはオンラインで実行され、制御対象システムのモデルと制約条件を含む数理最適化問題を反復的に解くことで、プロセスプラントのチョーク開度などの決定変数の値を繰り返し決定します。

最適化手法は、地球物理学的パラメータ推定問題において頻繁に用いられます。例えば地震記録などの地球物理学的測定値が与えられた場合、その下にある岩石や流体の物理的特性や幾何学的形状を求めるのが一般的です。地球物理学における問題の大部分は非線形であり、決定論的手法と確率論的手法の両方が広く用いられています。

非線形最適化手法は、構造解析において広く用いられている。

最適化手法は、モデル構築、最適な実験計画、代謝工学、合成生物学など、計算システム生物学の多くの側面で使用されています。^{[ 30 ]}線形計画法は、発酵産物の最大収量を計算するため^{[ 30 ]}、複数のマイクロアレイデータセットから遺伝子制御ネットワークを推論するため^{[ 31 ]}、およびハイスループットデータから転写制御ネットワークを推論するために適用されています。^{[ 32 ]}非線形計画法は、エネルギー代謝を分析するために使用され^{[ 33 ]}、代謝工学や生化学経路のパラメータ推定に適用されています。^{[ 34 ]}