前回の記事で非線形計画問題について概説した。
[mathjax] ある目的関数を最大化または最小化する問題を最適化問題といい、変数が取りうる値に制約がある場合、それを制約条件という。 制約条件と目的関数がともに線形である場合を線形計画問題といい、シンプレックス法という手法を[…]
勾配とヘッセ行列を用いて、目的関数が最適解をもつための必要条件を示した。簡単に復習しておこう。
無制約の最適化問題
$$f(\boldsymbol{x})\to\min$$
において、\(\boldsymbol{x}^*\)が局所的最適解であるための必要条件は
\begin{cases}
勾配ベクトル\nabla f(\boldsymbol{x}^*)=0 & (一次の条件) \\
ヘッセ行列\nabla^2 f(\boldsymbol{x}^*)が半正定値 & (二次の条件)
\end{cases}
である。
大域的最適解であるための条件は、\(f(\boldsymbol{x})\)が凸関数、すなわち任意の\(\boldsymbol{x}\)に対してヘッセ行列が半正定値であることである。
以上が無制約の問題に対する解法である。
それでは、制約条件がある最適化問題の解法を紹介していこう。
制約条件の形によって場合分けをする。
等式制約のみの場合
まず、以下の最適化問題を考える。
\begin{align*}
目的関数 & f(\boldsymbol{x})\to \min \\
制約条件 & h_i(\boldsymbol{x})=0 (i=1,\ldots,m)
\end{align*}
この場合はラグランジュの未定乗数法を利用する。
目的関数\(f(\boldsymbol{x})=(一定)\)である等高線と実行可能領域とが接する点として局所的最適解が得られる。
この点では、目的関数の勾配ベクトル\(\nabla f\)と制約条件の法線ベクトル\(\nabla h_i\)が平行になることから、定数\(\lambda_i\)を用いて
$$\nabla f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ih_i(\boldsymbol{x})=0$$
が成り立つ。
これと制約条件式を連立することで極値を求めることができる。これがラグランジュの未定乗数法である。
また次式で定義するラグランジュ関数\(L\)を用いると、すっきりとした形で表示することができる。
$$L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ih_i(\boldsymbol{x})$$
等式制約条件の最小化問題の解法をまとめる。
定数\(\lambda_1,\ldots,\lambda_m\)を用いて、ラグランジュ関数
$$L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ih_i(\boldsymbol{x})$$
を立てる。\(\boldsymbol{x}=\boldsymbol{x}^*\)が最適解であるとすると
\begin{cases}
\displaystyle\frac{\partial L(\boldsymbol{x}^*,\lambda)}{\partial x_j}=\frac{\partial f(\boldsymbol{x}^*)}{\partial x_j}+\sum_{i=1}^{m}\lambda_i\frac{\partial h_i(\boldsymbol{x}^*)}{\partial x_j}=0 \\
\displaystyle\frac{\partial L(\boldsymbol{x}^*,\lambda)}{\partial \lambda_i}=h_i(\boldsymbol{x}^*)=0
\end{cases}
が成立する。
不等式制約のみの場合
つぎに、不等式制約条件を持つ最適化問題を考える。
\begin{align*}
目的関数 & f(\boldsymbol{x})\to \min \\
制約条件 & g_i(\boldsymbol{x})\le0 (i=1,\ldots,m)
\end{align*}
この場合はカルーシュ・キューン・タッカー条件(Karush-Kuhn-Tucker条件：KKT条件)を適用する。
\(\boldsymbol{x}=\boldsymbol{x}^*\)が最適解であるとすると、ある定数\(\lambda_1,\ldots,\lambda_m\)が存在して
\begin{cases}
\displaystyle\frac{\partial L(\boldsymbol{x}^*,\lambda)}{\partial x_j}=\nabla f(\boldsymbol{x}^*)+\sum_{i=1}^{m}\lambda_i\nabla g_i(\boldsymbol{x}^*)=0 \\
\displaystyle\lambda_i\frac{\partial L(\boldsymbol{x}^*,\lambda)}{\partial \lambda_i}=\lambda_i g_i(\boldsymbol{x}^*)=0 \\
\displaystyle\frac{\partial L(\boldsymbol{x}^*,\lambda)}{\partial \lambda_i}=g_i(\boldsymbol{x}^*)\le0 \\
\lambda_i\ge0
\end{cases}
が成立する。
キューン・タッカー条件は、局所的最適解であるための必要条件であることに注意する。
すなわち、キューン・タッカー条件を満たす解であっても、局所的最適解にならない場合が存在する。
目的関数および制約条件がともに凸関数である場合、キューン・タッカー条件を満たす解は大域的最適解となる。
その他の制約条件
他のパターンの非線形計画問題の解法を紹介する。
等式制約と不等式制約の組み合わせ
\begin{align*}
目的関数 & f(\boldsymbol{x})\to \min \\
制約条件 & g_i(\boldsymbol{x})\le0 (i=1,\ldots,m) \\
& h_k(\boldsymbol{x})=0 (k=1,\ldots,l)
\end{align*}
このとき、ラグランジュ関数およびキューン・タッカー条件は次式で与えられる。
$$L(\boldsymbol{x},\lambda,\mu)=f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ig_i(\boldsymbol{x})+\sum_{k=1}^{l}\mu_kh_k(\boldsymbol{x})$$
\displaystyle\frac{\partial L(\boldsymbol{x},\lambda,\mu)}{\partial x_j}=0 \\
\displaystyle\lambda_i\frac{\partial L(\boldsymbol{x},\lambda,\mu)}{\partial \lambda_i}=0，\frac{\partial L(\boldsymbol{x},\lambda,\mu)}{\partial \lambda_i}\le0， \lambda_i\ge0 \\
\displaystyle\frac{\partial L(\boldsymbol{x},\lambda,\mu)}{\partial \mu_k}=0
\end{cases}
非負制約
不等式制約に加えて、非負制約条件がある場合を考える。
\begin{align*}
目的関数 & f(\boldsymbol{x})\to \min \\
制約条件 & g_i(\boldsymbol{x})\le0 \\
& \boldsymbol{x}\ge0
\end{align*}
このとき、ラグランジュ関数はこれまでと同様だが、キューン・タッカー条件が以下のようになる。
$$L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ig_i(\boldsymbol{x})$$
\begin{cases}
\displaystyle x_j\frac{\partial L(\boldsymbol{x},\lambda)}{\partial x_j}=0，\frac{\partial L(\boldsymbol{x},\lambda)}{\partial x_j}\ge0，x_j\ge0 \\
\displaystyle\lambda_i\frac{\partial L(\boldsymbol{x},\lambda)}{\partial \lambda_i}=0，\frac{\partial L(\boldsymbol{x},\lambda)}{\partial \lambda_i}\le0，\lambda_i\ge0
\end{cases}
非負である\(x_j\)を掛けた項が条件として現れる。
具体的な非線形計画問題の解法については別の記事で紹介する。
線形代数学 内積の定義と正値性・対称性・線形性について 特別な行列の名前と定義・性質の一覧 対称行列と反対称行列の性質・分解公式 行列のn乗の計算方法ー４つのパターン サラスの公式による行列式の計算方法 余因[…]
