前回の記事で、制約条件付き非線形計画問題の解法を紹介した。
[mathjax] 前回の記事で非線形計画問題について概説した。 [sitecard subtitle=関連記事 url=https://ramenhuhu.com/math-nlp] 勾配とヘッセ行列を用いて、目的関数が[…]
ここでは具体的な非線形問題を解きながら理解を深めていきたい。
演習問題①
次の非線形計画問題を解け。
\[\begin{align*}
\mathrm{Minimize} & (x_1-1)^2+(x_2-2)^2 \\
\mathrm{subject~to} & x_1^2+x_2^2-2\le0 \\
& x_1-x_2\ge0 \\
& x_2\ge0
\end{align*}\]
不等式制約と非負制約の組み合わせになっている。
不等式の向きに注意してラグランジュ関数、キューン・タッカー条件を考える。
(解)
$$f(\boldsymbol{x})=(x_1-1)^2+(x_2-2)^2$$
とおく。この目的関数の凸性を調べるため、ヘッセ行列を求める。
\[
H(\boldsymbol{x}) = \nabla^2f(\boldsymbol{x}) = \left(
\begin{array}{cc}
\frac{\partial^2 f(\boldsymbol{x})}{\partial x_1^2} & \frac{\partial^2 f(\boldsymbol{x})}{\partial x_1\partial x_2} \\
\frac{\partial^2 f(\boldsymbol{x})}{\partial x_2\partial x_1} & \frac{\partial^2 f(\boldsymbol{x})}{\partial x_2^2}
\end{array}
\right)=\left(
\begin{array}{cc}
2 & 0 \\
0 & 2
\end{array}
\right)
\]
これは明らかに正定値であるので、\(f\)は凸関数である。
また、制約条件の一つ目は円を表すため明らかに狭義凸であり、残りは線形である。
したがって、この問題は凸計画問題である。
ラグランジュ関数を次式で与える。
$$L(\boldsymbol{x},\lambda)=(x_1-1)^2+(x_2-2)^2+\lambda_1(x_1^2+x_2^2-2)+\lambda_2(-x_1+x_2)$$
この問題のキューン・タッカー条件は、次のようになる。
\begin{cases}
\displaystyle\frac{\partial L}{\partial x_1}=2(x_1-1)+2\lambda_1x_1-\lambda_2=0 \\
\displaystyle x_2\frac{\partial L}{\partial x_2}=x_2\{2(x_2-2)+2\lambda_1x_2+\lambda_2\}=0，\frac{\partial L}{\partial x_2}\ge0，x_2\ge0 \\
\displaystyle\lambda_1\frac{\partial L}{\partial \lambda_1}=\lambda_1(x_1^2+x_2^2-2)=0，\frac{\partial L}{\partial \lambda_1}\le0，\lambda_1\ge0 \\
\displaystyle\lambda_2\frac{\partial L}{\partial \lambda_2}=\lambda_2(-x_1+x_2)=0，\frac{\partial L}{\partial \lambda_2}\le0，\lambda_2\ge0
\end{cases}
これより
$$(x_1，x_2，\lambda_1，\lambda_2)=\left(1，1，\frac{1}{2}，1\right)$$
において最小値\(1\)をとる。
(補足)
キューン・タッカー条件から得られる方程式の数が多く、不等式条件も含まれるため、計算は面倒である。
この問題は凸計画問題であるので、キューン・タッカー条件を満たす解はただ一つであり、それが最適解である。
よって、すべての場合を丁寧に計算するよりも、計算しやすい条件から順にみていく方が効率的に解にたどり着ける場合もある。
\(\lambda_1,\lambda_2\not=0\)を仮定すると、下の二式から
\begin{cases}
x_1^2+x_2^2-2=0 \\
-x_1+x_2=0
\end{cases}
および\(x_2\ge0\)より、\(x_1=x_2=1\)を得る。これを上の二式に代入して計算すると、\(\lambda_1=\frac{1}{2},\lambda_2=1\)となる。
これらはすべてのキューン・タッカー条件を満たすため、求めるべき解であることがわかる。
もう一問解いてみよう。
演習問題②
\[\begin{align*}
\mathrm{Minimize} & 2x_1^2-tx_1x_2+3x_2^2+3tx_2 \\
\mathrm{subject~to} & x_1^2+x_2^2\le5
\end{align*}\]
ただし、\(t\)はパラメータである。このとき
（１）この問題が凸計画問題となる\(t\)の範囲を求めよ。
（２）パラメータ\(t\)が（１）の範囲にあるときのキューン・タッカー条件を示せ。また、\(t=1\)のときの解を求めよ。
制約条件は円なので、目的関数が凸関数であればこの問題は凸計画問題である。
ヘッセ行列が半正定値となる範囲を求めればよい。
(解)
（１）
制約条件は円の内部なので凸集合である。よって、目的関数
$$f(x_1,x_2)=2x_1^2-tx_1x_2+3x_2^2+3tx_2$$
が凸関数であれば凸計画問題である。
勾配ベクトルは
\[
\nabla f(x_1,x_2) = \left(
\begin{array}{cc}
4x_1-tx_2 \\
-tx_1+6x_2+3t
\end{array}
\right)
\]
であり、ヘッセ行列は
\[
\nabla^2 f(x_1,x_2) = \left(
\begin{array}{cc}
4 & -t \\
-t & 6
\end{array}
\right)
\]
となる。
ここで、\(\boldsymbol{y}=(y_1,y_2)^T\)とすると
$$\boldsymbol{y}^T\nabla^2 f(x_1,x_2)\boldsymbol{y}=4\left(y_1-\frac{t}{4}y_2\right)^2+\left(\frac{24-t^2}{4}\right)y_2^2$$
が\(0\)以上であることが目的関数が凸関数であるための必要十分条件なので
$$24-t^2\ge0$$
の範囲であれば凸関数である。これより、求める\(t\)の範囲は
$$-2\sqrt{6}\le t\le2\sqrt{6}$$
である。
（２）
ラグランジュ関数を次式でおく。
$$L(x_1,x_2,\lambda)=2x_1^2-tx_1x_2+3x_2^2+3tx_2+\lambda(x_1^2+x_2^2-5)$$
この問題が満たすべきキューン・タッカー条件は、以下のように書くことができる。
\begin{align*}
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial x_1}&=4x_1-tx_2+2\lambda x_1=0 \\
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial x_2}&=6x_2+2\lambda x_2-tx_1+3t=0 \\
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial \lambda}&=x_1^2+x_2^2-5\begin{cases}=0 & (\lambda\gt0) \\ \le0 & (\lambda=0) \end{cases}
\end{align*}
\(t=1\)のとき、目的関数は次のように式変形できる。
\begin{align*}
f(x_1,x_2)&=2x_1^2-x_1x_2+3x_2^2+3x_2 \\
&=2\left(x_1-\frac{1}{4}x_2\right)^2+\frac{23}{8}\left(x_2+\frac{12}{23}\right)^2-\frac{18}{23}
\end{align*}
よって、\(f(x_1,x_2)\)は\(x_1=\displaystyle-\frac{3}{23},x_2=\displaystyle-\frac{12}{23}\)のときに最小値\(\displaystyle-\frac{18}{23}\)をとる。
この解は制約条件を満たすので、これが最適解である。
このときのキューン・タッカー条件を確認する(計算の詳細は省略する)。
\begin{align*}
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial x_1}&=-\frac{6}{23}\lambda \\
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial x_2}&=-\frac{24}{23}\lambda \\
\displaystyle\frac{\partial L(x_1,x_2,\lambda)}{\partial \lambda}&=-\frac{2492}{529}
\end{align*}
\(\lambda=0\)のとき、第一式および第二式はともにゼロになり、第三式\(\le0\)を満たしている。
この最適解がキューン・タッカー条件を満たすことを確認できた。
線形代数学 内積の定義と正値性・対称性・線形性について 特別な行列の名前と定義・性質の一覧 対称行列と反対称行列の性質・分解公式 行列のn乗の計算方法ー４つのパターン サラスの公式による行列式の計算方法 余因[…]
