最適化問題の定式化
目的関数、制約条件、実行可能領域
入門（大学初年級レベル）
最適化とは何か
最適化とは、「与えられた条件の下で、ある量を最大または最小にする」ことである。私たちは日常的に最適化を行っている。
- 通勤時間を最小にするルートを選ぶ
- 予算内で最も満足度の高い買い物をする
- 決められた時間で最大の勉強効果を得る
これらを数学的に扱うために、問題を定式化（formulation）する必要がある。
目的関数
定義：目的関数
目的関数（objective function）とは、最大化または最小化したい対象を表す関数である。変数 $x$（または複数の変数 $x_1, x_2, \ldots, x_n$）を入力として、実数値を出力する。
$$f: \mathbb{R}^n \to \mathbb{R}$$例1：面積の最大化
周の長さが $20$ の長方形で、面積を最大にしたいとする。
長方形の2辺の長さを $x$, $y$ とすると：
- 周の長さの条件：$2x + 2y = 20$、つまり $y = 10 - x$
- 面積（目的関数）：$f(x) = x \cdot y = x(10 - x) = 10x - x^2$
この $f(x) = 10x - x^2$ を最大化することが目標である。
例2：コストの最小化
ある工場で製品Aを $x$ 個、製品Bを $y$ 個生産するとき、総コストが
$$C(x, y) = 100x + 150y + 2000$$で表されるとする。このコスト関数 $C(x, y)$ を最小化することが目標である。
制約条件
定義：制約条件
制約条件（constraint）とは、変数が満たすべき条件である。制約条件には主に2種類ある。
- 等式制約：$g(x) = 0$ の形
- 不等式制約：$h(x) \leq 0$ または $h(x) \geq 0$ の形
例3：生産計画の制約
工場の生産計画で、以下のような制約があるとする。
- 原材料の制限：$2x + 3y \leq 100$（不等式制約）
- 労働時間の制限：$x + 2y \leq 50$（不等式制約）
- 生産量は非負：$x \geq 0$, $y \geq 0$（非負制約）
制約なし最適化と制約付き最適化
制約条件がない場合を制約なし最適化（unconstrained optimization）、制約条件がある場合を制約付き最適化（constrained optimization）と呼ぶ。
まずは制約なしの場合から学び、後の章で制約付きの場合（ラグランジュの未定乗数法など）を扱う。
実行可能領域
定義：実行可能領域
実行可能領域（feasible region）または実行可能集合とは、すべての制約条件を満たす点の集合である。
$$\mathcal{F} = \{x \in \mathbb{R}^n : \text{すべての制約条件を満たす}\}$$実行可能領域内の点を実行可能解（feasible solution）と呼ぶ。
例4：2変数の実行可能領域
制約条件が
$$x + y \leq 4, \quad x \geq 0, \quad y \geq 0$$のとき、実行可能領域は下図の三角形の内部と境界である。
最大化と最小化
最適化問題は最大化問題と最小化問題の2種類がある。
標準形
最小化問題の標準形：
$$\begin{aligned} \min_{x} \quad & f(x) \\ \text{subject to} \quad & g_i(x) = 0, \quad i = 1, \ldots, m \\ & h_j(x) \leq 0, \quad j = 1, \ldots, p \end{aligned}$$ここで「subject to」は「〜を満たすとき」という意味で、s.t. と略記されることもある。
最大化と最小化の変換
最大化問題と最小化問題は、目的関数の符号を変えることで互いに変換できる。
$$\max_x f(x) = -\min_x (-f(x))$$したがって、最小化問題だけを考えれば十分である。ただし、問題の文脈に応じて最大化・最小化の両方を使う。
具体例
例5：箱の容積最大化
1辺 $a$ の正方形の板の四隅から、1辺 $x$ の正方形を切り取り、折り曲げて蓋のない箱を作る。容積を最大にするには $x$ をどう選べばよいだろうか？
定式化：
- 箱の底面：$(a - 2x) \times (a - 2x)$
- 箱の高さ：$x$
- 容積（目的関数）：$V(x) = x(a - 2x)^2$
制約条件：
$$0 < x < \dfrac{a}{2}$$（$x$ は正で、かつ $a - 2x > 0$ でなければならない）
この問題は次章で微分を使って解く。
例6：最短距離問題
点 $(3, 0)$ から、放物線 $y = x^2$ 上の点への最短距離を求める。
定式化：
放物線上の点を $(x, x^2)$ とすると、$(3, 0)$ からの距離の2乗は
$$D(x) = (x - 3)^2 + (x^2)^2 = (x - 3)^2 + x^4$$距離を最小にすることと、距離の2乗を最小にすることは同じなので、$D(x)$ を最小化する。
制約条件：
$x$ は任意の実数（制約なし最適化）
例7：機械学習の損失関数
機械学習では、モデルの予測と実際の値の誤差を最小化する。例えば、線形回帰では
$$L(w) = \displaystyle\sum_{i=1}^{n} (y_i - w^T x_i)^2$$という損失関数（loss function）を最小化する。ここで $w$ はモデルのパラメータ、$(x_i, y_i)$ はデータである。
局所最適と大域最適
定義：局所最小点と大域最小点
点 $x^*$ が局所最小点（local minimum）であるとは、$x^*$ のある近傍内で $f(x^*) \leq f(x)$ が成り立つことである。
点 $x^*$ が大域最小点（global minimum）であるとは、実行可能領域全体で $f(x^*) \leq f(x)$ が成り立つことである。
注意
一般の最適化問題では、局所最小点が大域最小点とは限らない。複数の局所最小点が存在することもある。
しかし、目的関数が凸関数（凸集合と凸関数で学習）の場合は、局所最小点は必ず大域最小点になる。これが凸最適化が重要な理由の一つである。
まとめ
- 目的関数：最大化または最小化したい関数
- 制約条件：変数が満たすべき条件（等式制約・不等式制約）
- 実行可能領域：すべての制約を満たす点の集合
- 最大化問題と最小化問題は符号の変換で互いに変換可能
- 局所最適と大域最適は一般には異なる
よくある質問
最適化問題とはどのようなものですか？
目的関数 $f(x)$ を制約条件 $g_i(x) \leq 0$、$h_j(x) = 0$ のもとで最小（または最大）化する問題です。生産コストの最小化、利益の最大化、ルートの最短化など、工学・経済・機械学習の多くの問題が最適化問題として定式化できます。
局所最適解と大域最適解の違いは何ですか？
局所最適解は近傍の点より良い解で、大域最適解は全体の中で最良の解です。凸最適化では局所最適解＝大域最適解ですが、非凸問題では複数の局所最適解が存在します。実問題では大域最適解の探索が困難な場合が多く、近似や発見的手法を使います。
無制約最適化と制約付き最適化の違いは何ですか？
無制約最適化 $\min f(x)$ は探索空間に制限がなく、微分条件 $\nabla f = 0$ で解の候補を求めます。制約付き最適化 $\min f(x)$ s.t. $g(x) \leq 0$ では等号制約にラグランジュ乗数法、不等号制約にKKT条件を使います。制約があると解空間が絞られ、最適性条件が複雑になります。