1 数理最適化入門

1.1 数理最適化の概要と応用

数理最適化は、私たちの日常生活や産業の多くの場面で役立つ強力なツールです。最適化とは、限られた資源や条件の中で最も効率的な結果を求めることを指し、その応用範囲は、ビジネスや金融、物流、サプライチェーン管理、さらには医療や環境保護にまで広がっています。たとえば、企業はコストを最小化しつつ利益を最大化したいと考えますし、データ科学者は、誤差を最小限に抑えながら予測精度を高めたいと考えます。これらはすべて「最適化問題」として数学的にモデル化できます。

このガイドでは、数理最適化の基本的な概念から問題の分類、そしてそれぞれの問題に対してどのようなアプローチや解法があるのかを紹介し、最適なソルバー（解決アルゴリズム）を選ぶための指針も提供します。

1.2 数理最適化の基本概念と数学的定式化

数理最適化（Mathematical Programming とも呼ばれる）とは、与えられた集合から入力値を見つけ出し、関数（目的関数と呼ばれる）を最小化または最大化する問題を指します。入力値は決定変数、プライマル変数、あるいは単に変数と呼ばれます。決定変数が取り得る値の範囲を表す集合は実行可能集合と呼ばれ、決定変数の関数として表現される制約が特定の値を持つ領域として定義されることがあります。実行可能集合の各点は実行可能点と呼ばれます。

このような問題の一般的な数学的定式化は次のように書くことができます。

$$\begin{align} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & x \in F, \end{align}$$

ここで、$x$は決定変数、$f(x)$は目的関数、$F$は実行可能集合を表します。nAGの数理最適化ソルバーは、$F \subset \mathbb{R}^n$を仮定します。目的関数$f(x)$の最大化は$-f(x)$の最小化と等価であるため、以降のテキストでは最小化のみを考慮します。一部のルーチンでは、最小化問題か最大化問題かを指定できるようになっており、後者の場合は必要に応じて目的関数の変換を行います。

点$x^*$が関数$f$の局所最小値であるとは、$x^*$が実行可能$(x^* \in F)$で、$x^*$の近傍のすべての$x \in F$に対して$f(x) \geq f(x^*)$が成り立つことを言います。点$x^*$が大域最小値であるとは、それが局所最小値であり、かつすべての実行可能な$x$に対して$f(x) \geq f(x^*)$が成り立つことを言います。nAGの数理最適化ソルバーは、局所最小値を探すように設計されています。しかし、多くの問題、特に凸最適化問題では、局所最小値が1つしかありません。この場合、その唯一の局所最小値が同時に大域最小値（全体の最小値）でもあります。したがって、nAGライブラリ E04章で提供されているソルバーは、こういった問題に対しては大域最小値を見つけることができます。一方、非凸関数のように複数の局所最小値がある場合は異なります。このような複雑な問題で大域最小値を探したい場合は、nAGライブラリ E05章の大域的最適化ソルバーを使用することをお勧めします。