- 講師:佐藤一誠
- 参考書:最適化手法
- 参考書:機械学習のための連続最適化
- 制約付き最適化問題(constrained optimization problem)
\(\mathcal{X}\subset\mathbb{R}^d\) 上に定義される関数 \(f:\mathcal{X}\rightarrow\mathbb{R}\) の最小値を求める。
$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&g(\mathbf{x})=\mathbf{0}\\ &h(\mathbf{x})\leq\mathbf{0} \end{aligned} $$
- "subject to"は、「…を条件として」 という意味。
- \(g_i,h_i\) は互いに一次独立(linearly independent)であると仮定。
- 実行可能解(feasible solution):全ての制約条件を満たす \(\mathbf{x}\)
- 凸最適化問題(convex optimization problem):関数 \(f\) が凸、集合 \(\mathcal{X}\) が凸、制約条件 \(\mathbf{g},\mathbf{h}\) が凸であれば、最適値が一意に定まる。
※ 以下、凸最適化問題を考える。
等式制約付き最適化問題
- 等式制約付き最適化問題
$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&g(\mathbf{x})=\mathbf{0}\\ \end{aligned} $$
- \(\mathbf{x}_k\) に設定して、勾配法や準ニュートン法などで以下の$$\mathbf{x}_{k+1} = \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}f(\mathbf{x}) + c_k\|\mathbf{g}(x)\|^2$$