導入
最適化は、さまざまなシステムの最適な条件や構成を検索することからなる数学の分野です。この言葉は、最高を意味するラテン語のオプティマムから来ています。
これは数値解析と応用数学において非常に重要であり、産業および工学の基礎となります。実際、経済的、物理的、化学的現象などを数式で表すと、最大の効率や理想的な構成を得るためにシステムを最適化する必要があります。このために、数学的ツールを使用します。今日では、エンジンの動作、鉄道路線の管理、経済投資、化学反応など、すべてが最適化されています。例は数多くあるため、これらの問題を解決するツールを持つことが重要です。
意味
より正式には、最適化とは次のような形式の問題を研究することです。
- 与えられた:関数$$ {f : A \rightarrow \mathbb R} $$実数の集合の集合Aの
- 検索:次のようなAの要素x 0 $$ {f(x_0) \ge f(x)} $$A内のすべてのxに対して (「最大化」)、または$$ {f(x_0) \le f(x)} $$A内のすべてのxに対して (「最小化」)。
このような定式化は、数学的プログラムと呼ばれることもあります (この用語はコンピューター プログラミングとは直接関係ありませんが、線形計画法などに使用されます。以下の歴史を参照)。この一般的な枠組みの中で、いくつかの理論的および実際的な問題を研究できます。
fの最大化は−f の最小化と同等であるため、最適化問題を解くには最小値 (または最大値) を見つける方法で十分です。
Aがユークリッド空間の特定の部分集合であることがよくあります。
極小値x * は、 x *の近傍V が存在するような点として定義されます。
テクニック
数学的問題を解決するための手法は、制約付きセットの目的関数の性質によって異なります。次の主要なサブドメインが存在します。
- 線形計画法では、集合 A の境界と目的関数が線形である場合を研究します。これは、製油所向けのプログラムを確立するために広く使用されている方法ですが、現在の市場価格に基づいて、制約の下で塩分混合物の最も収益性の高い組成を決定するためにも使用されます。
- 整数線形計画法では、一部またはすべての変数が整数値を取るように制約される線形計画法を研究します。これらの問題は、分離と評価、割線などのさまざまな方法で解決できます。
- 二次計画法では、線形等式/不等式からの集合 A の記述を保持しながら、目的関数に二次項を含めることができます。
- 非線形計画法は、目的または制約 (またはその両方) に非線形部分が含まれる一般的なケースを研究します。
- 確率的計画法では、制約の一部が確率変数に依存する場合を研究します。
- 動的計画法は、最適解は必ず最適な部分解から構成されるという特性を利用して (注: 一般にその逆は当てはまりません)、組み合わせ爆発を回避しながら問題を分解します。目的関数が単調増加する場合にのみ使用できます。これは動的プログラミングであり、次のようなことが可能になります。
2 回微分可能な関数の場合、関数の勾配が 0 である場所 (静止点など) を見つけ、ヘッセ行列を使用して点の種類を分類することで、制約のない問題を解決できます。ヘッセ行列が正定値の場合、点は局所最小値になります。負の定値の場合は極大値、不定値の場合は「通過点」になります。
関数が一連の許容解 (制約によって定義される) 上で凸である場合、局所最小値は大域最小値でもあります。二重微分可能な凸関数を最適化するための、堅牢かつ高速な数値手法が存在します。これらの機能の外では、あまり効果的ではない技術を使用する必要があります。
制約のある問題は、ラグランジュ乗数を使用して制約のない問題に変換できることがよくあります。この方法では、制約に近づくにつれてペナルティが増加することになります。 Hugh Everettによるアルゴリズムにより、反復ごとに乗数の値を一貫して更新して、収束を保証できます。彼はまた、これらの乗数の解釈を一般化して、連続でも微分可能でもない関数に適用しました。ラムダは単なるペナルティ係数になります。
いくつかの不十分な極小値を含む非線形最適化問題で良好な極小値を見つけるための多くの手法が存在し、それらは一般にメタヒューリスティックとみなされます。
