複数の線型不等式制約条件のもとでの多変数関数の最大化問題
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられているものとします。加えて、有限\(m\)個ずつの非ゼロベクトル\(a_{1},\cdots ,a_{m}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{1},\cdots ,c_{m}\in \mathbb{R} \)が与えられているものとします。ベクトルとスカラーの組\(\left(a_{i},c_{i}\right) \ \left( i=1,\cdots ,m\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_{m}\)の共通部分を、\begin{equation*}G=\bigcap_{i=1}^{m}G_{i}
\end{equation*}で表記し、これを制約集合（constraint set）と呼びます。関数\(f\)の変数\(x\)がとり得る値の範囲を以下の集合\begin{equation*}X\cap G
\end{equation*}に制限した場合の\(f\)の最大点を特定する問題を線型不等式制約付き最大化問題（maximization problem with linear constraints）と呼び、これを、
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}$$
で表記します。集合\(X\cap G\)を最大化問題の定義域（domain of the maximization problem）と呼びます。\(X=\mathbb{R} ^{n}\)の場合には\(X\cap G=G\)です。最大化問題において最大化する対象となる関数\(f\)を目的関数（objective mathrmtion）と呼び、制約集合\(G\)を規定するそれぞれの条件\(a_{i}\cdot x\leq c_{i}\)を\(i\)番目の不等式制約条件（inequality constraint）と呼びます。
点\(x\in X\)が制約集合\(G\)の要素である場合、すなわち、\begin{equation*}\forall i\in \left\{ 1,\cdots ,m\right\} :a_{i}\cdot x\leq c_{i}
\end{equation*}が成り立つ場合、点\(x\)は実行可能（feasible）であると言います。点\(x\in X\)が\(i\)番目の制約集合\(G_{i}\)の内点である場合、すなわち、\begin{equation*}a_{i}\cdot x<c_{i}
\end{equation*}が成り立つ場合には、点\(x\)のもとで\(i\)番目の制約条件はバインドしない（not binded）とか有効ではない（inactive）などと言います。点\(x\in X\)が\(i\)番目の制約集合\(G_{i}\)の境界点である場合、すなわち、\begin{equation*}a_{i}\cdot x=c_{i}
\end{equation*}が成り立つ場合には、点\(x\)のもとで\(i\)番目の制約条件はバインドする（binded）とか有効である（active）などと言います。
非ゼロベクトル\(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) =c_{i}-a_{i}\cdot x
\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) \geq 0\right\}
\end{equation*}と表現できるため、先の最大化問題を、
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & g_{1}\left( x\right) \geq 0 \\
& \vdots \\
& g_{m}\left( x\right) \geq 0\end{array}$$
と表現することもできます。
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}x\leq c_{1} \\
& a_{2}x\leq c_{2}\end{array}$$
と定式化されます。
$$\begin{array}{cl}
\max\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}\end{array}$$
と定式化されます。
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\geq c_{1} \\
& \vdots \\
& a_{m}\cdot x\geq c_{m}\end{array}$$
を構成します。先に定式化した最大化問題とは異なり、制約条件\(a_{i}\cdot x\geq c_{i}\)の不等号の向きが逆になっています。ただし、これを以下の問題
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & -a_{1}\cdot x\leq -c_{1} \\
& \vdots \\
& -a_{m}\cdot x\leq -c_{m}\end{array}$$
に読み替えることにより、通常の最大化問題として扱うことができます。
最大点であるための必要条件（クーン・タッカー条件）
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a_{1},\cdots ,a_{m}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{1},\cdots ,c_{m}\in \mathbb{R} \ \left( i=1,\cdots ,m\right) \)のもとでの最大化問題\begin{equation}\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}
\quad \cdots (1)
\end{equation}が与えられているものとします。この問題に解が存在する場合、それはどのような条件を満たすのでしょうか。
それぞれの\(x\in X\)に対して、\begin{equation*}\left( -f\right) \left( x\right) =-f\left( x\right)
\end{equation*}を定める関数\begin{equation*}
-f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \end{equation*}を定義した上で、以下の最小化問題\begin{equation}
\begin{array}{cl}
\min\limits_{x\in X} & \left( -f\right) \left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}
\quad \cdots (2)
\end{equation}を定義します。
最大化問題\(\left( 1\right) \)と最小化問題\(\left( 2\right) \)は制約集合\begin{equation*}G=\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\}
\end{equation*}を共有しています。また、点\(x^{\ast }\in \mathbb{R} ^{n}\)を任意に選んだとき、\begin{eqnarray*}\forall x\in X\cap G:f\left( x^{\ast }\right) \geq f\left( x\right)
&\Leftrightarrow &\forall x\in X\cap G:-f\left( x^{\ast }\right) \leq
-f\left( x\right) \\
&\Leftrightarrow &\forall x\in X\cap G:\left( -f\right) \left( x^{\ast
}\right) \leq \left( -f\right) \left( x\right)
\end{eqnarray*}という関係が成り立つため、点\(x^{\ast }\)が最大化問題\(\left( 1\right) \)の解であることと、この点\(x^{\ast }\)が最小化問題\(\left( 2\right) \)の解であることは必要十分です。以上より、\(\left( 1\right) \)と\(\left( 2\right) \)は問題として等しいことが明らかになりました。したがって、最小化問題\(\left( 2\right) \)の解に関して成り立つ性質は、そのまま最大化問題\(\left( 1\right) \)の解に関する性質として引き継がれます。したがって、最大化問題\(\left( 1\right) \)の解が満たす条件を特定する代わりに、最小化問題\(\left( 2\right) \)の解が満たす条件を特定しても一般性は失われません。
関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最大化問題\(\left( 1\right) \)の最大点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能であるものとします。このとき、関数\(-f\)は最小化問題\(\left( 2\right) \)の最小点であり、なおかつ\(-f\)もまた点\(x^{\ast }\)において全微分可能であるため、最小化問題に関するクーン・タッカー条件より、\begin{eqnarray*}&&\left( a\right) \ \nabla \left( -f\right) \left( x^{\ast }\right)
+\sum_{i=1}^{m}\lambda _{i}a_{i}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\left( a_{i}\cdot x^{\ast }-c_{i}\right) =0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :a_{i}\cdot
x^{\ast }\leq c_{i} \\
&&\left( d\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\cdots ,\lambda _{m}\in \mathbb{R} \)が存在しますが、先の考察より、これは最大化問題\(\left( 1\right) \)に関するクーン・タッカー条件でもあります。以上の条件は、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x^{\ast }\right) -\sum_{i=1}^{m}\lambda
_{i}a_{i}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\left( a_{i}\cdot x^{\ast }-c_{i}\right) =0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :a_{i}\cdot
x^{\ast }\leq c_{i} \\
&&\left( d\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\cdots ,\lambda _{m}\in \mathbb{R} \)が存在することと必要十分です。
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}$$
を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最小点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能であるならば、以下の条件\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x^{\ast }\right) -\sum_{i=1}^{m}\lambda
_{i}a_{i}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\left( a_{i}\cdot x^{\ast }-c_{i}\right) =0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :a_{i}\cdot
x^{\ast }\leq c_{i} \\
&&\left( d\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす実数\(\lambda _{1},\cdots,\lambda _{m}\in \mathbb{R} \)が存在する。
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}\leq 4 \\
& x_{1}\geq 0 \\
& x_{2}\geq 1\end{array}$$
について考えます。これは以下の問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}\leq 4 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq -1\end{array}$$
へ読み替え可能です。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 4\wedge -x_{1}\leq 0\wedge -x_{2}\leq -1\right\}
\end{equation*}です。\(f\)はコンパクト集合\(G\)上に定義された連続関数であるため、最大値・最小値の定理より先の最大化問題には解が存在します。\(f\)は全微分可能であり、勾配ベクトルは、\begin{equation*}\nabla f\left( x_{1},x_{2}\right) =\left( -2x_{1},-2x_{2}\right)
\end{equation*}となります。点\(\left(x_{1},x_{2}\right) \in G\)が最小点であるならば、クーン・タッカー条件\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x_{1},x_{2}\right) -\lambda _{1}\left(
1,1\right) -\lambda _{2}\left( -1,0\right) -\lambda _{3}\left( 0,-1\right)
=\left( 0,0\right) \\
&&\left( b_{1}\right) \ \lambda _{1}\left( x_{1}+x_{2}-4\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\left( -x_{1}\right) =0 \\
&&\left( b_{3}\right) \ \lambda _{3}\left( -x_{2}+1\right) =0 \\
&&\left( c_{1}\right) \ x_{1}+x_{2}\leq 4 \\
&&\left( c_{2}\right) \ -x_{1}\leq 0 \\
&&\left( c_{3}\right) \ -x_{2}\leq -1 \\
&&\left( d\right) \ \forall i\in \left\{ 1,2,3\right\} :\lambda _{i}\geq 0
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a_{1}\right) \ -2x_{1}-\lambda _{1}+\lambda _{2}=0 \\
&&\left( a_{2}\right) \ -2x_{2}-\lambda _{1}+\lambda _{3}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\left( x_{1}+x_{2}-4\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}\left( -x_{1}\right) =0 \\
&&\left( b_{3}\right) \ \lambda _{3}\left( -x_{2}+1\right) =0 \\
&&\left( c_{1}\right) \ x_{1}+x_{2}\leq 4 \\
&&\left( c_{2}\right) \ -x_{1}\leq 0 \\
&&\left( c_{3}\right) \ -x_{2}\leq -1 \\
&&\left( d_{1}\right) \ \lambda _{1}\geq 0 \\
&&\left( d_{2}\right) \ \lambda _{2}\geq 0 \\
&&\left( d_{3}\right) \ \lambda _{3}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\lambda _{2},\lambda _{3}\in \mathbb{R} \)が存在します。\(x_{1}>0\)と仮定すると\(\left( b_{2}\right) \)より\(\lambda _{2}=0\)を得ます。すると\(\left( a_{1}\right) \)より\(\lambda _{1}<0\)となり、これは\(\left( d\right) \)と矛盾です。したがって、\(x_{1}>0\)は成り立たず、これと\(\left( c_{2}\right) \)より、\begin{equation*}x_{1}=0
\end{equation*}であることが明らかになりました。すると\(\left( a_{1}\right) \)より、\begin{equation*}\lambda _{1}=\lambda _{2}
\end{equation*}を得て、\(\left( b_{1}\right) \)より、\begin{equation*}\lambda _{1}\left( x_{2}-4\right) =0
\end{equation*}を得ます。したがって\(\lambda _{1}=0\)または\(x_{2}=4\)です。まずは\(\lambda _{1}=0\)の場合について考えます。これと\(\left( a_{2}\right) \)より\(2x_{2}-\lambda _{3}=0\)を得ます。一方、\(\left( c_{3}\right) \)より\(x_{2}>0\)であるため\(\lambda _{3}>0\)です。すると\(\left( b_{3}\right) \)より\(x_{2}=1\)を得て、\(\left( a_{2}\right) \)より\(\lambda _{3}=2\)を得ます。以上より、\begin{equation}\left( x_{1}^{\ast },x_{2}^{\ast },\lambda _{1},\lambda _{2},\lambda
_{3}\right) =\left( 0,1,0,0,2\right) \quad \cdots (1)
\end{equation}はクーン・タッカー条件を満たすことが明らかになりました。続いて、\(x_{2}=4\)の場合について考えます。これと\(\left( a_{2}\right) \)より\(8+\lambda_{1}-\lambda _{3}=0\)を得る一方で\(\left(b_{3}\right) \)より\(\lambda _{3}=0\)を得るため\(\lambda _{1}=-8\)となりますが、これは\(\left( d_{1}\right) \)と矛盾です。したがって、最大化問題に関するクーン・タッカー条件を満たす点は\(\left( 1\right) \)だけであることが明らかになりました。
先の命題は目的関数が全微分可能な点が最大化問題の解であるための必要条件を与えるものであり、十分条件ではありません。つまり、目的関数が全微分可能な点が最大化問題の解である場合、その点は必ずクーン・タッカー条件を満たす一方で、クーン・タッカー条件を満たす点は最大化問題の解であるとは限らないということです。以下の例より明らかです。
\end{equation*}を定めるものとします。\(f\)は微分可能です。以下の制約付き最大化問題
$$\begin{array}{cl}
\max\limits_{x\in \mathbb{R}} & f\left( x\right) \\
s.t. & x\leq 1 \\
& -x\leq 1\end{array}$$
について考えます。制約集合は、\begin{eqnarray*}
G &=&\left\{ x\in \mathbb{R} \ |\ x\leq 1\wedge -x\leq 1\right\} \\
&=&\left[ -1,1\right]
\end{eqnarray*}です。\(f\)はコンパクト集合\(G\)上に定義された連続関数であるため、最大値・最小値の定理より先の最大化問題には解が存在します。\(f\)は微分可能です。点\(0\in G\)において、\begin{equation*}f^{\prime }\left( 0\right) =0\quad \because f^{\prime }\left( x\right)
=3x^{2}
\end{equation*}であるため、\(\left( \lambda _{1},\lambda_{2}\right) =\left( 0,0\right) \)に注目したとき、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( 0\right) -\lambda _{1}\left( -1\right)
-\lambda _{2}1=0 \\
&&\left( b_{1}\right) \ \lambda _{2}\left( x-1\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{1}\left( -x-1\right) =0 \\
&&\left( c_{1}\right) \ x\leq 1 \\
&&\left( c_{2}\right) \ -x\leq 1 \\
&&\left( d_{1}\right) \ \lambda _{1}\geq 0 \\
&&\left( d_{2}\right) \ \lambda _{2}\geq 0
\end{eqnarray*}がいずれも成り立ちます。したがって点\(0\)はクーン・タッカー条件を満たします。一方、\(f\)は狭義単調増加関数であるため最大点は\(1\)であり、点\(0\)は最小点ではありません。
ラグランジュの未定乗数法
目的関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a_{i}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{i}\in \mathbb{R} \ \left( i=1,\cdots ,m\right) \)のもとでの最大化問題
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}$$
が与えられたとき、それぞれの\(\left( x,\lambda _{1},\cdots,\lambda _{m}\right) \in X\times \mathbb{R} ^{m}\)に対して、\begin{eqnarray*}L\left( x,\lambda _{1},\cdots ,\lambda _{m}\right) &=&f\left( x\right)
+\lambda _{1}\left( c_{1}-a_{1}\cdot x\right) +\cdots +\lambda _{m}\left(
c_{m}-a_{m}\cdot x\right) \\
&=&f\left( x\right) +\sum_{i=1}^{m}\lambda _{i}\left( c_{i}-a_{i}\cdot
x\right)
\end{eqnarray*}を値として定める関数\begin{equation*}
L:X\times \mathbb{R} ^{m}\rightarrow \mathbb{R} \end{equation*}を定義し、これをラグランジュ関数（Lagrangian）と呼びます。
目的関数\(f\)が定義域の内点\(x\in X^{i}\)において全微分可能である場合、ラグランジュ関数\(L\)は明らかに点\(\left( x,\lambda _{1},\cdots,\lambda _{m}\right) \)において全微分可能です。そこで、\(L\)をそれぞれの変数\(x_{j}\ \left( j=1,\cdots ,n\right) \)に関して偏微分して\(0\)とおくと、\begin{eqnarray*}\forall j\in \left\{ 1,\cdots ,n\right\} :\frac{\partial L\left( x,\lambda
_{1},\cdots ,\lambda _{m}\right) }{\partial x_{j}}=0 &\Leftrightarrow
&\forall j\in \left\{ 1,\cdots ,n\right\} :\frac{\partial f\left( x\right) }{\partial x_{j}}-\sum_{i=1}^{m}\lambda _{i}a_{ij}=0 \\
&\Leftrightarrow &\nabla f\left( x\right) -\sum_{i=1}^{m}\lambda _{i}a_{i}=0
\end{eqnarray*}を得ます。さらに、\(L\)をそれぞれの変数\(\lambda_{i}\ \left( i=1,\cdots ,m\right) \)に関して偏微分し、得られた結果と\(\lambda _{i}\)の積を\(0\)とおくと、\begin{equation*}\forall i\in \left\{ 1,\cdots ,m\right\} :\lambda _{i}\frac{\partial L\left(
x,\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial \lambda _{i}}=0\Leftrightarrow \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\left( a_{i}\cdot x-c_{i}\right) =0
\end{equation*}が成り立ち、また、\begin{eqnarray*}
\forall i\in \left\{ 1,\cdots ,m\right\} :\frac{\partial L\left( x,\lambda
_{1},\cdots ,\lambda _{m}\right) }{\partial \lambda _{i}}\geq 0
&\Leftrightarrow &\forall i\in \left\{ 1,\cdots ,m\right\} :c_{i}-a_{i}\cdot
x\geq 0 \\
&\Leftrightarrow &\forall i\in \left\{ 1,\cdots ,m\right\} :a_{i}\cdot x\leq
c_{i}
\end{eqnarray*}が成り立ちます。したがって、最大化のためのクーン・タッカー条件は、ラグランジュ関数\(L\)に関する以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall j\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial x_{j}}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda _{i}\frac{\partial L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial \lambda _{i}}=0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\frac{\partial
L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial
\lambda _{i}}\geq 0 \\
&&\left( d\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}と必要十分であることが明らかになりました。
つまり、最大化問題が与えられたとき、ラグランジュ関数を定義した上で以上の条件を満たす点\(x^{\ast }\)を特定すれば、その点はクーン・タッカー条件を満たすことが保証されるということです。これをラグランジュの未定乗数法（method of Lagrange multipler）と呼びます。
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}$$
を定義する。それぞれの\(\left( x,\lambda _{1},\cdots ,\lambda _{m}\right) \in X\times \mathbb{R} ^{m}\)に対して、\begin{equation*}L\left( x,\lambda _{1},\cdots ,\lambda _{m}\right) =f\left( x\right)
+\sum_{i=1}^{m}\lambda _{i}\left( c_{i}-a_{i}\cdot x\right)
\end{equation*}を定める関数\(L:X\times \mathbb{R} ^{m}\rightarrow \mathbb{R} \)を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最大点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \forall j\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial x_{j}}=0 \\
&&\left( b\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda _{i}\frac{\partial L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial \lambda _{i}}=0 \\
&&\left( c\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\frac{\partial
L\left( x^{\ast },\lambda _{1},\cdots ,\lambda _{m}\right) }{\partial
\lambda _{i}}\geq 0 \\
&&\left( d\right) \ \forall i\in \left\{ 1,\cdots ,m\right\} :\lambda
_{i}\geq 0
\end{eqnarray*}を満たす実数\(\lambda _{1},\cdots,\lambda _{m}\in \mathbb{R} \)が存在する。
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}\leq 4 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq -1\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 4\wedge -x_{1}\leq 0\wedge -x_{2}\leq -1\right\}
\end{equation*}です。先に、以下の点\begin{equation*}
\left( x_{1}^{\ast },x_{2}^{\ast },\lambda _{1},\lambda _{2},\lambda
_{3}\right) =\left( 0,1,0,0,2\right)
\end{equation*}がクーン・タッカー条件を満たすことを示しましたが、同じことをラグランジュの未定乗数法を用いて導きます。ラグランジュ関数を、\begin{equation*}
L\left( x_{1},x_{2},\lambda _{1},\lambda _{2},\lambda _{3}\right)
=-x_{1}^{2}-x_{2}^{2}+\lambda _{1}\left( 4-x_{1}-x_{2}\right) +\lambda
_{2}x_{1}+\lambda _{3}\left( -1+x_{2}\right)
\end{equation*}と定義します。点\(\left(x_{1},x_{2}\right) \in G\)が最大点であるならば、以下の条件\begin{eqnarray*}&&\left( a_{1}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\lambda _{3}\right) }{\partial x_{1}}=0 \\
&&\left( a_{2}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\lambda _{3}\right) }{\partial x_{2}}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\frac{\partial L\left(
x_{1},x_{2},\lambda _{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda
_{1}}=0 \\
&&\left( b_{2}\right) \ \lambda _{2}\frac{\partial L\left(
x_{1},x_{2},\lambda _{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda
_{2}}=0 \\
&&\left( b_{3}\right) \ \lambda _{3}\frac{\partial L\left(
x_{1},x_{2},\lambda _{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda
_{3}}=0 \\
&&\left( c_{1}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda _{1}}\geq 0 \\
&&\left( c_{2}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda _{2}}\geq 0 \\
&&\left( c_{3}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda
_{1},\lambda _{2},\lambda _{3}\right) }{\partial \lambda _{3}}\geq 0 \\
&&\left( d_{1}\right) \ \lambda _{1}\geq 0 \\
&&\left( d_{2}\right) \ \lambda _{2}\geq 0 \\
&&\left( d_{3}\right) \ \lambda _{3}\geq 0
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a_{1}\right) \ -2x_{1}-\lambda _{1}+\lambda _{2}=0 \\
&&\left( a_{2}\right) \ -2x_{2}-\lambda _{1}+\lambda _{3}=0 \\
&&\left( b_{1}\right) \ \lambda _{1}\left( 4-x_{1}-x_{2}\right) =0 \\
&&\left( b_{2}\right) \ \lambda _{2}x_{1}=0 \\
&&\left( b_{3}\right) \ \lambda _{3}\left( -1+x_{2}\right) =0 \\
&&\left( c_{1}\right) \ 4-x_{1}-x_{2}\geq 0 \\
&&\left( c_{2}\right) \ x_{1}\geq 0 \\
&&\left( c_{3}\right) \ -1+x_{2}\geq 0 \\
&&\left( d_{1}\right) \ \lambda _{1}\geq 0 \\
&&\left( d_{2}\right) \ \lambda _{2}\geq 0 \\
&&\left( d_{3}\right) \ \lambda _{3}\geq 0
\end{eqnarray*}を満たす\(\lambda _{1},\lambda _{2},\lambda _{3}\in \mathbb{R} \)が存在します。以上の条件、すなわち最小化問題に関するクーン・タッカー条件を満たす点は、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast },\lambda _{1},\lambda _{2},\lambda
_{3}\right) =\left( 0,1,0,0,2\right)
\end{equation*}だけです（確認してください）。これは先の結果と整合的です。
複数の線型不等式制約条件のもとでの最大化問題の解法
関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a_{i}\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c_{i}\in \mathbb{R} \ \left( i=1,\cdots ,m\right) \)から最大化問題
$$\begin{array}{cl}
\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}\cdot x\leq c_{1} \\
& \vdots \\
& a_{m}\cdot x\leq c_{m}\end{array}$$
を定義したとき、\(f\)が全微分可能な\(X\)の内点\(x^{\ast }\in X^{i}\cap G\)が最大点である場合には、この点\(x^{\ast }\)はクーン・タッカー条件を満たすことが明らかになりました。加えて、クーン・タッカー条件を満たす点の特定を容易にするラグランジュの未定乗数法について解説しました。
ただ、クーン・タッカー条件は目的関数\(f\)が全微分可能な\(X\)の内点を対象とした条件であり、\(f\)が全微分可能ではない\(X\)の内点について何も言っていません。目的関数\(f\)が全微分可能ではない\(X\)の内点もまた最大点になり得るため、そのような点が制約集合\(G\)の要素である場合、それらの点も最大点の候補に加える必要があります。
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}+2x_{2}\leq 3 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}\leq 3\wedge -x_{1}\leq 0\wedge -x_{2}\leq 0\right\}
\end{equation*}です。\(f\)は\(x_{1}=0\)または\(x_{2}=0\)の少なくとも一方を満たす任意の点\(\left(x_{1},x_{2}\right) \in \mathbb{R} ^{2}\)において全微分可能ではないため、それらの点がクーン・タッカー条件を満たすか検討対象になり得ません。したがって、そのような点が\(G\)の要素である場合、それらの点を最大点の候補に加える必要があります。ちなみに、\(f\)の最大点は\(f\)が全微分可能ではない以下の点\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}です（演習問題）。
加えて、これまでは目的関数\(f\)の定義域\(X\)の内点のみを対象に議論を行ってきましたが、定義域\(X\)の境界点もまた最大点になり得るため、\(X\)の境界点が制約集合\(G\)の要素である場合、それらの点も最大点の候補に加える必要があります。
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}_{+}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}\leq 3\end{array}$$
すなわち、
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}_{+}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}\leq 3 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}\leq 3\wedge -x_{1}\leq 0\wedge -x_{1}\leq 0\right\}
\end{equation*}です。\(x_{1}=0\)または\(x_{2}=0\)の少なくとも一方を満たす任意の点\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)は\(f\)の定義域\(\mathbb{R} _{+}^{2}\)の境界点であるため、それらの点がクーン・タッカー条件を満たすか検討対象になり得ません。したがって、そのような点が\(G\)の要素である場合、それらの点を最大点の候補に加える必要があります。ちなみに、\(f\)の最大点は\(X\)の境界点である以下の点\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}です（演習問題）。
以上の論点を踏まえると、複数の線型不等式制約のもとでの最大化問題の解を求めるためには以下の手順にしたがう必要があります。
- 最大点が存在することを確認する。その際、最大値・最小値の定理などが役に立つ。
- 目的関数\(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) \)の値を最大化する点が最小点である。
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}\leq 4 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq -1\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 4\wedge -x_{1}\leq 0\wedge -x_{2}\leq -1\right\}
\end{equation*}です。\(f\)はコンパクト集合\(G\)上に定義された連続関数であるため、最大値・最小値の定理より先の最大化問題には解が存在します。加えて、\(f\)の定義域\(\mathbb{R} ^{2}\)は\(\mathbb{R} ^{2}\)上の開集合であり、\(f\)は\(\mathbb{R} ^{2}\)上の任意の点において全微分可能であるため、クーン・タッカー条件を満たす点だけが最大化問題の解の候補です。先に求めたように、以下の点\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast },\lambda _{1},\lambda _{2},\lambda
_{3}\right) =\left( 0,1,0,0,2\right)
\end{equation*}だけがクーン・タッカー条件を満たすため、最大点は、\begin{equation*}
\left( 0,1\right)
\end{equation*}であり、\(f\)の最大値は、\begin{equation*}f\left( 0,1\right) =-0^{2}-1^{2}=-1
\end{equation*}であることが明らかになりました。
演習問題
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+x_{2}\leq -1 \\
& -x_{1}\leq 3 \\
& -x_{2}\leq 3\end{array}$$
を解いてください。
x_{2}\right\vert
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}\leq 3 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0\end{array}$$
を解いてください。
\end{equation*}を定めるものとします。以下の最大化問題
$$\begin{array}{cl}
\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & x_{1}+2x_{2}\leq 3 \\
& -x_{1}\leq 0 \\
& -x_{2}\leq 0\end{array}$$
を解いてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】