- 講師：津田宏治
- 資料：生物データマイニング論(2019)
条件なし最適化
ある関数 \(f\) が与えられた時、それが最小値を取る点を見つけ出す。
したがって、微分をとって \(0\) になる点を見つければ良い。
等式制約付き最適化
ラグランジュ乗数(Lagrangian multiplier)と呼ばれるパラメータ \(\lambda\) を導入したラグランジュ関数(Lagrangian function)
の \(\mathbf{x}\) と \(\lambda\) の両方に対する停留点（鞍点）を見つければ、制約付き問題の最適解が得られる。
理由
以下２つの理由より、\(\nabla f\) と \(\nabla g\) は、向きが逆の場合も含めて平行なベクトルとなる。したがって、あるパラメータ \(\lambda\neq0\) が存在して、
が成立しなければならない。これは、\(\nabla_{\mathbf{x}}L=0\) と表されることがわかる。また、\(\partial L/\partial\lambda = 0\) より、制約式 \(g(\mathbf{x})=0\) も導かれる。
1) \(\nabla g(\mathbf{x})\) が制約面 \(g(\mathbf{x})=0\) に対して常に垂直
制約面 \(g(\mathbf{x})\) 上の点 \(\mathbf{x}\) と \(\mathbf{x}+\boldsymbol{\varepsilon}\) を考える。
すると、\(\mathbf{x}\) の周りでの \(g(\mathbf{x})\) のテイラー展開より、
いま、\(\mathbf{x}\) と \(\mathbf{x}+\boldsymbol{\varepsilon}\) は共に制約面上に存在するので
が成り立つ。ゆえに、
- \(\|\boldsymbol{\varepsilon}\|\rightarrow0\) の極限では \(\boldsymbol{\varepsilon}^T\nabla g(\mathbf{x})\sim0\) が成り立つ。
- \(\boldsymbol{\varepsilon}^T\) は制約面上の接線である。
より、ベクトル \(\nabla g(\mathbf{x})\) は制約面 \(g(\mathbf{x})=0\) に対して垂直である。
2) \(\nabla f(\mathbf{x}^{\ast})\) も制約面に対して垂直
もし \(\nabla f(\mathbf{x}^{\ast})\) が制約面に対して垂直でないとすると、制約面にそって \(f(\mathbf{x})\) の値がさらに大きくなるように点を動かすことができるはずである。
したがって、制約面上の点で \(f(\mathbf{x})\) を最大化する点 \(\mathbf{x}^{\ast}\) においては、ベクトル \(\nabla f(\mathbf{x})\) も制約面に対して垂直でなければならない。
不等式制約付き最適化
ここで、解 \(\mathbf{x}^{\ast}\in\Omega\) には、
- 無効制約(inactive constraint) \(\overset{\text{def}}{\Longleftrightarrow}g(\mathbf{x}^{\ast}) < 0\)
- 有効制約(active constraint) \(\overset{\text{def}}{\Longleftrightarrow}g(\mathbf{x}^{\ast}) = 0\)
の2つの可能性がある。
無効制約の場合
無効制約 \(\left(g(\mathbf{x})<0\right)\) の場合、関数 \(g(\mathbf{x})\) は何も制約を課していないのと同様なので、停留条件は単に \(\nabla f(\mathbf{x}) = 0\) となる。
なお、これは上記の等式制約におけるラグランジュ関数 \((E.4)\) において \(\lambda=0\) とした場合の停留条件に等しい。
有効制約の場合
有効制約 \(\left(g(\mathbf{x})=0\right)\) の場合、等式制約におけるラグランジュ関数 \((E.4)\) において \(\lambda\neq0\) とした場合の停留条件に等しい。
ただし、\(-\nabla f(\mathbf{x}^{\ast})\) は \(g(\mathbf{x})<0\) の外側へと向かうはずだから、あるパラメータ \(\lambda>0\) が存在して、
が成立しなければならない。
| 勾配 | 意味 | 最適化問題における問題における意味 |
|---|---|---|
| \(\nabla f(\mathbf{x})\) | \(f\) が大きくなる方向 | 目的とは別の方向 |
| \(\nabla g(\mathbf{x})\) | \(g\) が大きくなる方向 | \(g(\mathbf{x})<0\) の外側へと向かう方向 |
KKT条件
上記の無効制約・有効制約のどちらの場合にせよ、\(\lambda g(\mathbf{x})=0\) が成立することがわかる。
したがって、\(g(\mathbf{x})\leq0\) という制約の下で \(f(\mathbf{x})\) を最小化するには、以下のKarush-Kuhn-Tucker(KKT)条件のもとで、\(\mathbf{x},\lambda\) に関してラグランジュ関数 \((E.4)\) の停留点を求めれば良い。
なお、当然ではあるが、「制約条件の符号の向き」と「目的関数の最大化・最小化」には以下の関係がある。（\(\lambda\geq0\)）
| 目的関数 \(f(\mathbf{x})\) | 制約条件 \(g(\mathbf{x})\) | ラグランジュ関数 \(L(\mathbf{x},\lambda)\) |
|---|---|---|
| \(\min f(\mathbf{x})\) | \(g(\mathbf{x})\leq0\) | \(L(\mathbf{x},\lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x})\) |
| \(\min f(\mathbf{x})\) | \(g(\mathbf{x})\geq0\) | \(L(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x})\) |
| \(\max f(\mathbf{x})\) | \(g(\mathbf{x})\leq0\) | \(L(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x})\) |
| \(\max f(\mathbf{x})\) | \(g(\mathbf{x})\geq0\) | \(L(\mathbf{x},\lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x})\) |
一般化
以下のラグランジュ関数を最適化する。
ここで、KKT条件は、以下となる。