最適化問題

ある集合の中から、目的関数を最小にする要素を選ぶ問題。

標準形はこう書く。

$$\underset{x\in {ℝ}^n}{\min }f(x)\text{subject to}{g}_i(x)\le 0,h_j(x)=0$$

• $x$ … 決定変数。動かせるもの
• $f$ … 目的関数。良し悪しを測る物差し
• $g_i,h_j$ … 制約条件。動かせる範囲を限る

最大化は $\max f(x)=-\min (-f(x))$ なので、最小化だけ考えれば足りる。 文献が最小化で統一されているのはこのため。

実行可能領域#

制約をすべて満たす $x$ の集合を実行可能領域 $ℱ$ と呼ぶ。 最適化とは $ℱ$ の中で $f$ が最小になる点を探すこと。$ℱ$ が空なら その問題は実行不能で、解は存在しない。

解が存在するとは限らない#

$f(x)=-x$ を制約なしで最小化しようとすると、いくらでも小さくできてしまう（非有界）。 解の存在は当たり前ではなく、$ℱ$ が有界閉集合で $f$ が連続なら 最小値が存在する（Weierstrass の定理）、といった条件が要る。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization, §1.1, §4.1. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/
• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, §1. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5