最適化問題とは

数学における最適化問題は、可能な代替案の中からもっとも優れた解を見つけることに関心があります。「もっとも優れた」とは、特定の関数（目的関数とも呼ばれることが多い）を最大化または最小化する解を指します。最適化問題は、オペレーションズリサーチ、コンピュータサイエンス、機械学習、経済学、エンジニアリングなど、さまざまな分野で広く用いられています。

目的関数

最適化問題のコアには、目的関数があります。この関数は、最小化または最大化する必要がある量を表します。一般的な形式では、最適化問題は次のように定義できます。

関数を最大化しようとする場合、問題は以下のように定義されます。

\max f(x)

関数を最小化しようとする場合、問題は以下のように定義されます。

\min f(x)

これらの場合、f(x)は目的関数を表し、xは制御または変更できる決定変数です。

制約条件

制約条件は、解が満たす必要がある制限や条件です。これらは、決定変数を含む等式または不等式で表されることがあります。これらの制約を満たす全ての点xの集合を可行領域と呼びます。可行領域はSで表されます。したがって、最適化問題の一般的な形式は次のようになります。

関数を最大化しようとする場合：

\max f(x) \text{ subject to } x \in S

関数を最小化しようとする場合：

\min f(x) \text{ subject to } x \in S

これらの式では、制約条件が集合Sを定義します。制約条件は以下のような等式と不等式の形式で表されることがあります。

\begin{align*} g_i(x) & \leq 0, i = 1,...,m \\ h_j(x) & = 0, j = 1,...,p \end{align*}

ここで、g_i(x)は不等式制約を表し、h_j(x)は等式制約を表します。mとpはそれぞれ不等式制約と等式制約の数を表します。

最適値と最適解

最適化問題の最適値は、制約条件の下での目的関数のもっとも優れた値を指します。問題が最小化問題である場合、最適値は可行領域上での目的関数の最小値です。最大化問題の場合、最適値は最大値です。

最適解は通常、x^*と表され、目的関数の最適値を与える特定の決定変数xの値（または値の組み合わせ）を指します。数学的には次のように表されます。

関数を最大化しようとする場合、最適解は以下のように定義されます。

x^* = \arg\max_{x \in S} f(x)

関数を最小化しようとする場合、最適解は以下のように定義されます。

x^* = \arg\min_{x \in S} f(x)

これらの式では、x^*は目的関数の最適値を与える決定変数を表します。注意すべきは、最適化問題には複数の最適解が存在する場合があることです。つまり、複数のx^*がf(x)の最適値を与える可能性があることです。

一般的な最適化問題

実際の最適化問題は、目的関数と制約条件の性質、および決定変数が取り得る値の種類に応じて、さまざまな形式を取ります。

連続最適化

連続最適化問題は、決定変数が特定の連続範囲内の任意の値を取ることができる問題です。これらの問題は機械学習、スケジューリング、リソース割り当てなどのさまざまな領域で一般的です。

目的関数と制約条件の性質によって、いくつかのタイプの連続最適化問題があります。例えば、目的関数と制約条件がともに線形である場合、問題は線形計画問題となります。しかし、それらが非線形である場合は非線形計画問題となります。

線形計画問題 (Linear Programming)

線形計画問題（LP）は、目的関数と制約条件がともに線形である基本的な連続最適化問題です。線形計画問題では、目的関数と制約条件の各変数は1次の次数で現れ、他の変数と乗算されません。LP問題は、オペレーションズリサーチ、物流、サプライチェーン管理などの分野で広く用いられています。それらは比較的単純で効率的な解法が存在するためです。

非線形計画問題 (Nonlinear Programming)

非線形計画問題（NLP）は、目的関数、制約条件、またはその両方が非線形である最適化問題です。非線形計画問題は、線形計画問題に比べてより広範な現実世界の問題をモデル化することができますが、非線形性は問題に追加の複雑さをもたらします。

二次計画問題 (Quadratic Programming)

二次計画問題は、目的関数が二次であり、制約条件が線形である特定の非線形計画問題です。二次計画問題は、サポートベクターマシンやポートフォリオ最適化などの問題において機械学習や統計学でよく使用されます。

二次制約最適化問題 (Quadratically Constrained Programming)

二次制約最適化問題（QCP）は、制約条件も二次式であるより複雑な形式の二次計画問題です。QCP問題は、単純な二次計画問題よりも幅広いシナリオをモデル化できますが、解決がより難しいです。

二次錐最適化問題 (Second-Order Cone Programming)

二次錐最適化問題（SOCP）は、線形計画問題と二次計画問題を一般化した凸最適化問題の一種です。SOCPはLPやQPよりも幅広い範囲の問題を扱うことができながら、最適化の効率性と解の追求可能性を維持します。

半正定計画問題 (Semi-Definite Programming)

半正定計画問題（SDP）は、決定変数が行列であり、制約条件はこれらの行列が半正定である必要がある凸最適化の一種です。SDPは制御理論、信号処理、量子情報理論などの分野で応用されます。

凸最適化 (Convex Programming)

凸最適化は、目的関数が凸であり、制約条件が凸集合を形成する非線形最適化のサブクラスです。凸最適化問題は、局所最小値が同時に大域最小値でもあるという特性を持つため、非線形最適化問題の中でも特に扱いやすいです。

離散最適化

離散最適化は、決定変数が離散的な値しか取ることができない問題です。このような問題は、コンピュータサイエンス、物流、オペレーションズリサーチ、交通などの分野でよく発生します。意思決定は有限または可算無限の代替案の中から選択する必要があります。

整数計画問題 (Integer Programming)

整数計画問題（IP）は、決定変数が整数値のみを取る場合の問題です。このような問題は、生産量の決定や配送に必要なトラックの数の決定など、分数の値が意味を持たないシナリオで発生します。

混合整数計画問題 (Mixed-Integer Programming)

混合整数計画問題（MIP）では、一部の決定変数が整数値を取る必要があり、他の変数は連続値を取ることができます。このような問題は、生産計画や物流などの分野でよく見られます。意思決定は離散的な選択と連続的な量との組み合わせに関与する場合があります。

組合せ最適化 (Combinatorial Optimization)

組合せ最適化問題では、有限なオブジェクトの中から最適なオブジェクトを見つける問題です。これらの問題では、決定変数は特定のオブジェクトを解に含めるかどうかを表し、潜在的な解の数は組み合わせ的に増大します。巡回セールスマン問題やナップサック問題などが例です。

大域的最適化 (Global Optimization)

大域的最適化問題では、近隣の解だけを考慮しても改善できない、全ての可能な解の中で絶対的に最適な解を見つけることが求められます。これらの問題は特に探索空間が大きい場合や目的関数に多くの局所最適解が存在する場合に、解決が困難なことがあります。大域的最適化の手法では、局所最適解を回避して大域的最適解を求めるための戦略を採用することがよくあります。

確率最適化 (Stochastic Programming)

確率最適化は、不確実性を伴う最適化問題をモデル化するためのフレームワークです。従来の最適化では、特定の入力や制約条件の下で最適な意思決定を見つけることに取り組みますが、確率最適化では不確かさを表すためにランダム変数をモデルに導入します。結果として得られる最適化問題は、不確かなパラメータの確率分布を考慮して最適な意思決定を見つけることを目指します。

参考

https://scmopt.github.io/opt100/02optimization.html