線型不等式と線型等式制約条件のもとでの最小化問題
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)に加えて有限\(I+J\)個ずつの非ゼロベクトル\(a_{1},\cdots ,a_{I},b_{1},\cdots ,b_{J}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{1},\cdots ,c_{I},d_{1},\cdots ,d_{J}\in \mathbb{R} \)が与えられているものとします。ベクトルとスカラーの組\(\left(a_{i},c_{i}\right) \ \left( i=1,\cdots ,I\right) \)から以下の集合\begin{eqnarray*}G_{i} &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a_{i}\cdot x\leq c_{i}\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{i1}x_{1}+\cdots +a_{in}x_{n}\leq c_{i}\right\}
\end{eqnarray*}を定義し、これを\(i\)番目の制約集合（\(i\) th constraint set）と呼びます。制約集合\(G_{1},\cdots ,G_{I}\)の共通部分を、\begin{equation*}G=\bigcap_{i=1}^{I}G_{i}
\end{equation*}で表記します。また、ベクトルとスカラーの組\(\left( b_{j},d_{j}\right) \ \left( j=1,\cdots,J\right) \)から以下の集合\begin{eqnarray*}H_{j} &=&\left\{ x\in \mathbb{R} ^{n}\ |\ b_{j}\cdot x=d_{j}\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ b_{j1}x_{1}+\cdots +b_{jn}x_{n}=b_{j}\right\}
\end{eqnarray*}を定義し、これを\(j\)番目の制約集合（\(j\) th constraint set）と呼びます。制約集合\(H_{1},\cdots ,H_{J}\)の共通部分を、\begin{equation*}H=\bigcap_{j=1}^{J}H_{j}
\end{equation*}で表記します。以上を踏まえた上で、すべての制約集合の共通部分\begin{equation*}
G\cap H
\end{equation*}を制約集合（constraint set）と呼びます。関数\(f\)の変数\(x\)がとり得る値の範囲を以下の集合\begin{equation*}X\cap G\cap H
\end{equation*}に制限した場合の\(f\)の最小点を特定する問題を線型不等式と線型等式制約条件のもとでの最小化問題（minimization problem with linear inequality and equality constraints）と呼び、これを、
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
で表記します。集合\(X\cap G\cap H\)を最小化問題の定義域（domain of the minimization problem）と呼びます。\(X=\mathbb{R} ^{n}\)の場合には\(X\cap G\cap H=G\cap H\)です。最小化問題において最小化する対象となる関数\(f\)を目的関数（objective mathrmtion）と呼び、制約集合\(G\cap H\)を規定する条件\(a_{i}\cdot x\leq c_{i}\)を不等式制約条件（inequality constraint）と呼び、\(b_{j}\cdot x=d_{j}\)を等式制約条件（equality constraint）と呼びます。
非ゼロベクトル\(a_{i}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{i}\in \mathbb{R} \)が与えられたとき、それぞれの\(x\in \mathbb{R} ^{n}\)に対して、\begin{equation*}g_{i}\left( x\right) =a_{i}\cdot x-c_{i}
\end{equation*}を定める多変数関数\(g_{i}:\mathbb{R} ^{n}\rightarrow \mathbb{R} \)を定義すれば、\(i\)番目の制約集合を、\begin{equation*}G_{i}=\left\{ x\in \mathbb{R} ^{n}\ |\ g_{i}\left( x\right) \leq 0\right\}
\end{equation*}と表現できます。また、非ゼロベクトル\(b_{j}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(d_{j}\in \mathbb{R} \)が与えられたとき、それぞれの\(x\in \mathbb{R} ^{n}\)に対して、\begin{equation*}h_{j}\left( x\right) =b_{j}\cdot x-d_{j}
\end{equation*}を定める多変数関数\(h_{j}:\mathbb{R} ^{n}\rightarrow \mathbb{R} \)を定義すれば、\(j\)番目の制約集合を、\begin{equation*}H_{j}=\left\{ x\in \mathbb{R} ^{n}\ |\ h_{j}\left( x\right) \leq 0\right\}
\end{equation*}と表現できます。以上の関数を用いれば、先の最小化問題を、
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & g_{i}\left( x\right) \leq 0\quad \left( i=1,\cdots ,I\right) \\
& h_{j}\left( x\right) =0\quad \left( j=1,\cdots ,J\right)
\end{array}$$
と表現することもできます。
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & ax\leq c \\
& bx=d
\end{array}$$
と定式化されます。
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in X} & f\left( x_{1},x_{2}\right) \\
s.t. & a_{11}x_{1}+a_{12}x_{2}\leq c_{1} \\
& a_{21}x_{1}+a_{22}x_{2}\leq c_{2} \\
& b_{11}x_{1}+b_{12}x_{2}\leq d_{1} \\
& b_{21}x_{1}+b_{22}x_{2}\leq d_{2}
\end{array}$$
と定式化されます。
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\geq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
を構成します。先に定式化最小化問題とは異なり、不等式制約条件\(a_{i}\cdot x\geq c_{i}\)の不等号の向きが逆になっています。ただし、これを以下の問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & -a_{i}\cdot x\leq -c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
に読み替えることにより、通常の最小化問題として扱うことができます。
線型不等式制約のもとでの最小化問題との関係
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a_{i},b_{j}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{i},d_{j}\in \mathbb{R} \ \left( i=1,\cdots ,I;\ j=1,\cdots ,J\right) \)から線型不等式と線型等式制約条件のもとでの最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
を定義します。以下の関係\begin{eqnarray*}
b_{j}\cdot x=d_{j} &\Leftrightarrow &b_{j}\cdot x\leq d_{j}\wedge b_{j}\cdot
x\geq d_{j} \\
&\Leftrightarrow &b_{j}\cdot x\leq d_{j}\wedge -b_{j}\cdot x\leq -d_{j}
\end{eqnarray*}が成り立つことを踏まえると、1本の線型等式制約条件は2本の線型不等式制約条件に入れ替え可能であるため、先の問題を以下のような線型不等式制約付き最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x\leq d_{j}\quad \left( j=1,\cdots ,J\right) \\
& -b_{j}\cdot x\leq -d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
と同一視できます。したがって、線型不等式制約条件付き最小化問題について成り立つ性質がそのまま線型不等式と線型等式制約条件のもとでの最小化問題についても成立します。以下ではこの事実を利用して諸々の命題を証明します。
最小点であるための必要条件（クーン・タッカー条件）
線型不等式と線型等式制約条件のもとでの最小化問題に解が存在する場合、それはどのような条件を満たすのでしょうか。線型不等式と線型等式制約条件のもとでの最小化問題を線型不等式制約付き最小化問題に読み替えることにより以下の命題が導かれます。
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap H\)が最小点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能であるならば、以下の条件\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x^{\ast }\right) +\sum_{i=1}^{I}\lambda
_{i}a_{i}+\sum_{j=1}^{J}\mu _{j}b_{j}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\left( a_{i}\cdot x^{\ast }-c_{i}\right) =0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :a_{i}\cdot
x^{\ast }\leq c_{i} \\
&&\left( d\right) \ \forall j\in \left\{ 1,\cdots ,J\right\} :b_{j}\cdot
x^{\ast }=d_{j} \\
&&\left( e\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす実数\(\lambda _{1},\cdots,\lambda _{I},\mu _{1},\cdots ,\mu _{J}\in \mathbb{R} \)が存在する。
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0
\end{array}$$
について考えます。これは以下の問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0
\end{array}$$
へ読み替え可能です。最小化問題の定義域は、\begin{equation*}
\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}=10\wedge -x_{1}\leq 0\wedge -x_{2}\leq 0\right\}
\end{equation*}ですが、これらは\(\mathbb{R} ^{2}\)上のコンパクト集合です。\(f\)はコンパクト集合上に定義された連続関数であるため、最大値・最小値の定理より最小値が存在します。\(f\)は全微分可能であり、勾配ベクトルは、\begin{equation*}\nabla f\left( x_{1},x_{2}\right) =\left( 2x_{1},2x_{2}\right)
\end{equation*}となります。\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最小点であるならば、最小点であるための必要条件より、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
+\lambda _{1}\left( -1,0\right) +\lambda _{2}\left( 0,-1\right) +\mu
_{1}\left( 1,2\right) =\left( 0,0\right) \\
&&\left( b_{1}\right) \ \lambda _{1}\left( -x_{1}^{\ast }\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\left( -x_{2}^{\ast }\right) =0 \\
&&\left( c_{1}\right) \ -x_{1}^{\ast }\leq 0 \\
&&\left( c_{2}\right) \ -x_{2}^{\ast }\leq 0 \\
&&\left( d\right) \ x_{1}^{\ast }+2x_{2}^{\ast }=10 \\
&&\left( e\right) \ \forall i\in \left\{ 1,2\right\} :\lambda _{i}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\lambda _{2},\mu _{1}\in \mathbb{R} \)が存在します。具体的には、\begin{eqnarray*}&&\left( a_{1}\right) \ 2x_{1}-\lambda _{1}+\mu _{1}=0 \\
&&\left( a_{2}\right) \ 2x_{2}-\lambda _{2}+2\mu _{1}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\left( -x_{1}\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\left( -x_{2}\right) =0 \\
&&\left( c_{1}\right) \ -x_{1}\leq 0 \\
&&\left( c_{2}\right) \ -x_{2}\leq 0 \\
&&\left( d\right) \ x_{1}+2x_{2}=10 \\
&&\left( e\right) \ \forall i\in \left\{ 1,2\right\} :\lambda _{i}\geq 0
\end{eqnarray*}を満たす\(x_{1},x_{2},\lambda _{1},\lambda _{2},\mu_{1}\)を特定することになります。以上の条件を満たすのは、\begin{equation*}\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) =\left(
2,4,0,0,-4\right)
\end{equation*}だけです（演習問題）。したがって最小点は\(\left( 2,4\right) \)であり、最小値が\(f\left( 2,4\right) =20\)であることが明らかになりました。
ラグランジュの未定乗数法
目的関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が線型不等式制約のもとでの最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x\leq d_{j}\quad \left( j=1,\cdots ,J\right) \\
& -b_{j}\cdot x\leq -d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
の解であるとともに、\(f\)が点\(x^{\ast }\)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x^{\ast }\right) +\sum_{i=1}^{I}\lambda
_{i}a_{i}+\sum_{j=1}^{J}\mu _{j}b_{j}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\left( a_{i}\cdot x^{\ast }-c_{i}\right) =0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :a_{i}\cdot
x^{\ast }\leq c_{i} \\
&&\left( d\right) \ \forall j\in \left\{ 1,\cdots ,J\right\} :b_{j}\cdot
x^{\ast }=d_{j} \\
&&\left( e\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす\(I+J\)個の実数\(\lambda _{1},\cdots ,\lambda _{I},\mu _{1},\cdots ,\mu _{J}\)が存在することが明らかになりました。ただ、関数\(f\)が全微分可能なそれぞれの内点に対して、以上の条件を満たす実数\(\lambda _{1},\cdots,\lambda _{I},\mu _{1},\cdots ,\mu _{J}\)が存在するか判定する作業は煩雑になりがちです。ただ、この問題は以下のような形で解決可能です。
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a_{i},b_{j}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{i},d_{j}\in \mathbb{R} \ \left( i=1,\cdots ,I;\ j=1,\cdots ,J\right) \)のもとでの最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
が与えられたとき、それぞれの\(\left( x,\lambda ,\mu \right) \in X\times \mathbb{R} ^{I}\times \mathbb{R} ^{J}\)に対して、\begin{equation*}L\left( x,\lambda ,\mu \right) =f\left( x\right) +\sum_{i=1}^{I}\lambda
_{i}\left( a_{i}\cdot x-c_{i}\right) +\sum_{j=1}^{J}\mu _{j}\left(
b_{j}\cdot x-d_{j}\right)
\end{equation*}を定める関数\(L:X\times \mathbb{R} ^{I}\times \mathbb{R} ^{J}\rightarrow \mathbb{R} \)を定義し、これをラグランジュ関数（Lagrangian）と呼びます。
関数\(f\)が定義域の内点\(x\in X^{i}\)において全微分可能である場合、ラグランジュ関数\(L\)は明らかに点\(\left( x,\lambda ,\mu \right) \)において全微分可能です。そこで、\(L\)をそれぞれの変数\(x_{k}\ \left( k=1,\cdots ,n\right) \)に関して偏微分して\(0\)とおくと、\begin{eqnarray*}\forall k\in \left\{ 1,\cdots ,n\right\} :\frac{\partial L\left( x,\lambda
,\mu \right) }{\partial x_{k}}=0 &\Leftrightarrow &\forall k\in \left\{
1,\cdots ,n\right\} :\frac{\partial f\left( x\right) }{\partial x_{k}}+\sum_{i=1}^{I}\lambda _{i}a_{ik}+\sum_{j=1}^{J}\mu _{j}b_{jk}=0 \\
&\Leftrightarrow &\nabla f\left( x\right) +\sum_{i=1}^{I}\lambda
_{i}a_{i}+\sum_{j=1}^{J}\mu _{j}b_{j}=0
\end{eqnarray*}を得ます。さらに、\(L\)をそれぞれの変数\(\lambda_{i}\ \left( i=1,\cdots ,I\right) \)に関して偏微分し、得られた結果と\(\lambda _{i}\)の積を\(0\)とおくと、\begin{equation*}\forall i\in \left\{ 1,\cdots ,I\right\} :\lambda _{i}\frac{\partial L\left(
x,\lambda ,\mu \right) }{\partial \lambda _{i}}=0\Leftrightarrow \forall
i\in \left\{ 1,\cdots ,I\right\} :\lambda _{i}\left( a_{i}\cdot
x-c_{i}\right) =0
\end{equation*}を得ます。また、\begin{eqnarray*}
\forall i\in \left\{ 1,\cdots ,I\right\} :\frac{\partial L\left( x,\lambda
,\mu \right) }{\partial \lambda _{i}}\leq 0 &\Leftrightarrow &\forall i\in
\left\{ 1,\cdots ,I\right\} :a_{i}\cdot x-c_{i}\leq 0 \\
&\Leftrightarrow &\forall i\in \left\{ 1,\cdots ,I\right\} :a_{i}\cdot x\leq
c_{i}
\end{eqnarray*}を得て、\begin{eqnarray*}
\forall j\in \left\{ 1,\cdots ,J\right\} :\frac{\partial L\left( x,\lambda
,\mu \right) }{\partial \mu _{j}}=0 &\Leftrightarrow &\forall j\in \left\{
1,\cdots ,J\right\} :b_{j}\cdot x-d_{j}=0 \\
&\Leftrightarrow &\forall j\in \left\{ 1,\cdots ,J\right\} :b_{j}\cdot
x=d_{j}
\end{eqnarray*}を得るため、クーン・タッカー条件を、\begin{eqnarray*}
&&\left( a\right) \ \forall k\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial x_{k}}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda _{i}\frac{\partial L\left( x^{\ast },\lambda ,\mu \right) }{\partial \lambda _{i}}=0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial \lambda _{i}}\leq 0 \\
&&\left( d\right) \ \forall j\in \left\{ 1,\cdots ,J\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial \mu _{j}}=0 \\
&&\left( e\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}と言い換えることができます。つまり、最小化問題の解が存在する場合、ラグランジュ関数を構成した上で以上の条件を満たす点\(x^{\ast }\)を特定すれば、その点は最小化のための必要条件を満たすことが保証されるということです。これをラグランジュの未定乗数法（method of Lagrange multipler）と呼びます。
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
を定義する。それぞれの\(\left( x,\lambda ,\mu \right) \in X\times \mathbb{R} ^{I}\times \mathbb{R} ^{J}\)に対して、\begin{equation*}L\left( x,\lambda ,\mu \right) =f\left( x\right) +\sum_{i=1}^{I}\lambda
_{i}\left( a_{i}\cdot x-c_{i}\right) +\sum_{j=1}^{J}\mu _{j}\left(
b_{j}\cdot x-d_{j}\right)
\end{equation*}を定める関数\(L:X\times \mathbb{R} ^{I}\times \mathbb{R} ^{J}\rightarrow \mathbb{R} \)を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\cap H\)が最小点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \forall k\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial x_{k}}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda _{i}\frac{\partial L\left( x^{\ast },\lambda ,\mu \right) }{\partial \lambda _{i}}=0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial \lambda _{i}}\leq 0 \\
&&\left( d\right) \ \forall j\in \left\{ 1,\cdots ,J\right\} :\frac{\partial
L\left( x^{\ast },\lambda ,\mu \right) }{\partial \mu _{j}}=0 \\
&&\left( e\right) \ \forall i\in \left\{ 1,\cdots ,I\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす実数\(\lambda _{1},\cdots,\lambda _{I},\mu _{1},\cdots ,\mu _{J}\in \mathbb{R} \)が存在する。
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0
\end{array}$$
を構成します。これは以下の問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0
\end{array}$$
へ読み替え可能です。最小化問題の定義域は、\begin{equation*}
\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}=10\wedge -x_{1}\leq 0\wedge -x_{2}\leq 0\right\}
\end{equation*}ですが、これらは\(\mathbb{R} ^{2}\)上のコンパクト集合です。\(f\)はコンパクト集合上に定義された連続関数であるため、最大値・最小値の定理より最小値が存在します。ラグランジュ関数を、\begin{equation*}L\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right)
=x_{1}^{2}+x_{2}^{2}+\lambda _{1}\left( -x_{1}\right) +\lambda _{2}\left(
-x_{2}\right) +\mu _{1}\left( x_{1}+2x_{2}-10\right)
\end{equation*}と定義します。\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最小点であるならば、以下の条件\begin{eqnarray*}&&\left( a_{1}\right) \ \frac{\partial L\left( x_{1}^{\ast },x_{2}^{\ast
},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial x_{1}}=0 \\
&&\left( a_{2}\right) \ \frac{\partial L\left( x_{1}^{\ast },x_{2}^{\ast
},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial x_{2}}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\frac{\partial L\left( x_{1}^{\ast
},x_{2}^{\ast },\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda
_{1}}=0 \\
&&\left( b_{2}\right) \ \lambda _{2}\frac{\partial L\left( x_{1}^{\ast
},x_{2}^{\ast },\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda
_{2}}=0 \\
&&\left( c_{1}\right) \ \frac{\partial L\left( x_{1}^{\ast },x_{2}^{\ast
},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{1}}\leq 0 \\
&&\left( c_{2}\right) \ \frac{\partial L\left( x_{1}^{\ast },x_{2}^{\ast
},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{2}}\leq 0 \\
&&\left( d\right) \ \frac{\partial L\left( x_{1}^{\ast },x_{2}^{\ast
},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \mu _{1}}=0 \\
&&\left( e\right) \ \forall i\in \left\{ 1,2\right\} :\lambda _{i}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\lambda _{2},\mu _{1}\in \mathbb{R} \)が存在します。具体的には、\begin{eqnarray*}&&\left( a_{1}\right) \ 2x_{1}-\lambda _{1}+\mu _{1}=0 \\
&&\left( a_{2}\right) \ 2x_{2}-\lambda _{2}+2\mu _{1}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\left( -x_{1}\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\left( -x_{2}\right) =0 \\
&&\left( c_{1}\right) \ -x_{1}\leq 0 \\
&&\left( c_{2}\right) \ -x_{2}\leq 0 \\
&&\left( d\right) \ x_{1}+2x_{2}=10 \\
&&\left( e\right) \ \forall i\in \left\{ 1,2\right\} :\lambda _{i}\geq 0
\end{eqnarray*}を満たす\(x_{1},x_{2},\lambda _{1},\lambda _{2},\mu_{1}\)を特定することになります。先に、同じ問題に対してラグランジュの未定乗数法を利用せずにクーン・タッカー条件を特定しましたが、ここで特定した条件はそれと合致しています。ちなみに、以上の条件を満たすのは、\begin{equation*}\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) =\left(
2,4,0,0,-4\right)
\end{equation*}だけです。したがって最小点は\(\left( 2,4\right) \)であり、最小値が\(f\left( 2,4\right) =20\)であることが明らかになりました。
線型不等式と線型等式制約条件のもとでの最小化問題の解法
目的関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が線型不等式と線型等式制約のもとでの最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{i}\cdot x\leq c_{i}\quad \left( i=1,\cdots ,I\right) \\
& b_{j}\cdot x=d_{j}\quad \left( j=1,\cdots ,J\right)
\end{array}$$
の解であるとともに、\(f\)が点\(x^{\ast }\)において全微分可能である場合、その点が満たす条件が明らかになりました。加えて、条件を満たす点の特定を容易にするラグランジュの未定乗数法について解説しました。
ただ、最小化のための必要条件は目的関数が全微分可能な内点を対象とした条件であり、目的関数が全微分可能ではない内点について何も言っていません。目的関数が全微分可能ではない内点もまた最小点になり得るため、そのようなすべての点も最小点の候補に加える必要があります。
加えて、これまでは目的関数\(f\)の定義域\(X\)の内点のみを対象に議論を行ってきましたが、定義域\(X\)の境界点もまた最小点になり得るため、\(X\)が境界点を要素として持つ場合、そのようなすべての点も最小点の候補に加える必要があります。
以上を踏まえると、線型不等式と線型等式制約のもとでの最小化問題の解を求めるためには以下の手順にしたがう必要があります。
- 最小点が存在することを確認する。その際、最大値・最小値の定理などが役に立つ。
- 目的関数\(f\)の定義域\(X\)の内点の中でも、最小化のための必要条件を満たす点をすべて特定する。その際、ラグランジュの未定乗数法を使えば作業が円滑に進む。
- 目的関数\(f\)の定義域\(X\)の内点の中でも、制約条件を満たすとともに、関数が全微分可能ではない点をすべて特定する。
- 目的関数\(f\)の定義域\(X\)に含まれる境界点の中でも、制約条件を満たす点をすべて特定する。
- 以上の点の中でも\(f\left( x\right) \)の値を最小化する点が最小点である。
特に、目的関数\(f\)の定義域\(X\)が\(\mathbb{R} ^{n}\)上の開集合であるとともに、\(f\)が\(X\)上の任意の点において全微分可能である場合には、関数\(f\)が全微分可能ではない点や、関数\(f\)の定義域\(X\)に含まれる境界点は存在しないことが保証されるため、最小点を特定するためには以下の手順にしたがえばよいということになります。
- 最小点が存在することを確認する。その際、最大値・最小値の定理などが役に立つ。
- 目的関数\(f\)の定義域\(X\)の内点の中でも、最小化のための必要条件を満たす点をすべて特定する。その際、ラグランジュの未定乗数法を使えば作業が円滑に進む。
- 以上の点の中でも\(f\left( x\right) \)の値を最小化する点が最小点である。
x_{2}\right\vert
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}=0 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0
\end{array}$$
について考えます。\(f\)はコンパクト集合\(G\cap H\)上に定義された連続関数であるため、最大値・最小値の定理より最小点が存在します。ただ、\(f\)が全微分可能なのは\(x_{1}\not=0\)かつ\(x_{2}\not=0\)を満たす点\(\left(x_{1},x_{2}\right) \in \mathbb{R} ^{2}\)に限定されます。ラグランジュ関数を、\begin{equation*}L\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) =\left\vert
x_{1}\right\vert +\left\vert x_{2}\right\vert +\lambda _{1}\left(
-x_{1}\right) +\lambda _{2}\left( -x_{2}\right) +\mu _{1}\left(
x_{1}+x_{2}\right)
\end{equation*}と定義します。\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最小点であるならば、以下の条件\begin{eqnarray*}&&\left( a_{1}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\mu _{1}\right) }{\partial x_{1}}=\frac{x_{1}}{\left\vert
x_{1}\right\vert }-\lambda _{1}+\mu _{1}=0 \\
&&\left( a_{2}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\mu _{1}\right) }{\partial x_{2}}=\frac{x_{2}}{\left\vert
x_{2}\right\vert }-\lambda _{2}+\mu _{1}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\frac{\partial L\left(
x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{1}}=\lambda _{1}\left( -x_{1}\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\frac{\partial L\left(
x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{2}}=\lambda _{2}\left( -x_{2}\right) =0 \\
&&\left( c_{1}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{1}}=-x_{1}\leq 0 \\
&&\left( c_{2}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\mu _{1}\right) }{\partial \lambda _{2}}=-x_{2}\leq 0 \\
&&\left( d\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda _{1},\lambda
_{2},\mu _{1}\right) }{\partial \mu _{1}}=x_{1}+x_{2}=0 \\
&&\left( e\right) \ \lambda _{1},\lambda _{2}\geq 0
\end{eqnarray*}を満たす\(\left( x_{1},x_{2},\lambda _{1},\lambda_{2},\mu _{1}\right) \)を特定することになります。ただし、\(x_{1}\not=0\)かつ\(x_{2}\not=0\)のもとでは条件を満たす\(\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\mu _{1}\right) \)は存在しません（演習問題）。残された最小点の候補は\(f\)が全微分可能ではない\(G\cap H\)上の点、すなわち\(x_{1}=0\)または\(x_{2}=0\)の少なくとも一方を満たす\(G\cap H\)上の点です。それらの点の中で\(f\)を最小化するのは点\(\left( 0,0\right) \)です。したがって\(\left( 0,0\right) \)が最小点であり、最小値は\(f\left( 0,0\right) =0\)です。
演習問題
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0
\end{array}$$
を解いてください。
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}=10 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0
\end{array}$$
を解いてください。
\end{equation*}を定めるものとします。以下の最小化問題
$$\begin{array}{cl}\min\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} ^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}=20 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0
\end{array}$$
を解いてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】