線型不等式制約条件のもとでの多変数関数の最大化問題
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられているものとします。加えて、非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)が与えられており、それらから以下の集合\begin{eqnarray*}G &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}\leq c\right\}
\end{eqnarray*}を定義します。これを制約集合（constraint set）と呼びます。その上で、関数\(f\)の変数\(x\)がとり得る値の範囲を以下の集合\begin{equation*}X\cap G
\end{equation*}に制限した場合の\(f\)の最小点を特定する問題を線型不等式制約付き最小化問題（minimization problem with one linear inequality constraint）と呼び、これを、
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c
\end{array}$$
で表記します。集合\(X\cap G\)を最小化問題の定義域（domain of the minimization problem）と呼びます。\(X=\mathbb{R} ^{n}\)の場合には\(X\cap G=G\)です。最小化問題において最小化する対象となる関数\(f\)を目的関数（objective function）と呼び、制約集合\(G\)を規定する条件\(a\cdot x\leq c\)を不等式制約条件（inequality constraint ）と呼びます。
点\(x\in X\)が制約集合\(G\)の要素である場合、すなわち、\begin{equation*}a\cdot x\leq c
\end{equation*}が成り立つ場合、点\(x\)は実行可能（feasible）であると言います。特に、実行可能な点\(x\)が、\begin{equation*}a\cdot x<c
\end{equation*}を満たす場合、\(x\)のもとで制約条件はバインドしない（not binded）とか有効ではない（inactive）などと言います。これは、点\(x\)が制約集合\(G\)の内点であることを意味します。一方、実行可能な点\(x\)が、\begin{equation*}a\cdot x=c
\end{equation*}を満たす場合、\(x\)のもとで制約条件はバインドする（binded）とか有効である（active）などと言います。これは、点\(x\)が制約集合\(G\)の境界点であることを意味します。
非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)が与えられたとき、それぞれの\(x\in \mathbb{R} ^{n}\)に対して、\begin{equation*}g\left( x\right) =a\cdot x-c
\end{equation*}を定める多変数関数\(g:\mathbb{R} ^{n}\rightarrow \mathbb{R} \)を定義すれば、制約集合を、\begin{equation*}G=\left\{ x\in \mathbb{R} ^{n}\ |\ g\left( x\right) \leq 0\right\}
\end{equation*}と表現できるため、先の線型不等式制約付き最小化問題を、
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & g\left( x\right) \leq 0
\end{array}$$
と表現することもできます。
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & ax\leq c
\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_{1}x_{1}+a_{2}x_{2}\leq c
\end{array}$$
と定式化されます。
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\geq c
\end{array}$$
を構成します。先に定式化した最小化問題とは異なり、制約条件\(a\cdot x\geq c\)の不等号の向きが逆になっています。ただし、これを以下の問題
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & -a\cdot x\leq -c
\end{array}$$
に読み替えることにより、通常の最小化問題として扱うことができます。
最小点であるための必要条件（クーン・タッカー条件）
線型不等式制約付き最小化問題に解が存在する場合、それはどのような条件を満たすのでしょうか。2変数関数を目的関数とする最小化問題について議論した上で、後に結論を一般化します。
目的関数\(f:\mathbb{R} ^{2}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(\left(a_{1},a_{2}\right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)およびスカラー\(c\in \mathbb{R} \)から最小化問題
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x_{1},x_{2}\right) \\
s.t. & a_{1}x_{1}+a_{2}x_{2}\leq c
\end{array}$$
を定義します。最小点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X\cap G\)が存在する場合、そこではどのような条件が成り立つのでしょうか。ただし、点\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)は\(f\)の定義域\(X\)の内点であるものとします。つまり\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G\)です。加えて、関数\(f\)は点\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)において全微分可能であるものとします。この場合、勾配ベクトル\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in \mathbb{R} ^{2}
\end{equation*}が存在します。以降では\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が最小点であるための必要条件を明らかにします。
まずは、最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)のもとで制約条件がバインドしない場合、すなわち、\begin{equation*}a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }<c
\end{equation*}が成り立つ場合について考えます。これは\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が制約集合\(G\)の内点であることを意味します。つまり\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G^{i}\)です。内部の共通部分は共通部分の内部と一致するため\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \in \left( X\cap G\right) ^{i}\)でもあります。すると点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)の周辺の任意の点が\(X\cap G\)の要素であるため、\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)は最小化問題の極小点です。したがって、極小点であるための1階の必要条件より、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}が成り立ちます。
次に、最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)のもとで制約条件がバインドする場合、すなわち、\begin{equation*}a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }=c
\end{equation*}が成り立つ場合について考えます。これは\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が制約集合\(G\)の境界点であることを意味します。つまり\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G^{f}\)です。この場合には\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)は直線\(a_{1}x_{1}+a_{2}x_{2}=c\)上の点であり、この直線の法線ベクトルは\(\left( a_{1},a_{2}\right) \)です（下図）。
点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G^{f}\)が与えられたとき、十分小さい\(t>0\)について、\begin{equation}\left( x_{1}^{\ast },x_{2}^{\ast }\right) +t\left( d_{1},d_{2}\right) \in
X\cap G \quad \cdots (1)
\end{equation}を満たす方向ベクトル\(\left( d_{1},d_{2}\right) \in \mathbb{R} ^{2}\)を任意に選んで固定します。つまり、始点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)から方向\(\left( d_{1},d_{2}\right) \)にわずかに移動して得られる点が\(X\cap G\)の点であるということです。このような方向ベクトル\(\left(d_{1},d_{2}\right) \)を実行可能な方向（feasible direction）と呼びます。\(\left( 1\right) \)を変形すると、\begin{eqnarray*}\left( 1\right) &\Leftrightarrow &\left( a_{1},a_{2}\right) \cdot \left(
x_{1}^{\ast }+td_{1},x_{2}^{\ast }+td_{2}\right) \leq c\quad \because G\text{の定義} \\
&\Leftrightarrow &\left( a_{1},a_{2}\right) \cdot \left( x_{1}^{\ast
}+td_{1},x_{2}^{\ast }+td_{2}\right) \leq \left( a_{1},a_{2}\right) \cdot
\left( x_{1}^{\ast },x_{2}^{\ast }\right) \quad \because a_{1}x_{1}^{\ast
}+a_{1}x_{2}^{\ast }=c \\
&\Leftrightarrow &\left( a_{1},a_{2}\right) \cdot \left( d_{1},d_{2}\right)
\leq 0\quad \because t>0
\end{eqnarray*}という関係が成り立ちます。つまり、\(\left(d_{1},d_{2}\right) \)が\(\left( 1\right) \)を満たすこと、すなわち実行可能な方向であることと、\(\left( a_{1},a_{2}\right) \)と\(\left(d_{1},d_{2}\right) \)が作る角が直角または鈍角であることは必要十分条件です。任意の実行可能な方向\(\left( d_{1},d_{2}\right) \)について同様の議論が成立します（下図）。
再び\(\left( 1\right) \)を満たす\(\left(d_{1},d_{2}\right) \)すなわち実行可能な方向ベクトルを任意に選んで固定します。\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が最小点であることから、十分小さい任意の\(t>0\)について、\begin{equation*}f\left( \left( x_{1}^{\ast },x_{2}^{\ast }\right) +t\left(
d_{1},d_{2}\right) \right) \geq f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
\end{equation*}が成り立ちます。すると\(t>0\)より、\begin{equation*}\frac{f\left( \left( x_{1}^{\ast },x_{2}^{\ast }\right) +t\left(
d_{1},d_{2}\right) \right) -f\left( x_{1}^{\ast },x_{2}^{\ast }\right) }{t}\geq 0
\end{equation*}を得るため、このとき、\begin{equation*}
\lim_{t\rightarrow 0+}\frac{f\left( \left( x_{1}^{\ast },x_{2}^{\ast
}\right) +t\left( d_{1},d_{2}\right) \right) -f\left( x_{1}^{\ast
},x_{2}^{\ast }\right) }{t}\geq \lim_{t\rightarrow 0+}0
\end{equation*}すなわち、\begin{equation*}
\lim_{t\rightarrow 0+}\frac{f\left( \left( x_{1}^{\ast },x_{2}^{\ast
}\right) +t\left( d_{1},d_{2}\right) \right) -f\left( x_{1}^{\ast
},x_{2}^{\ast }\right) }{t}\geq 0
\end{equation*}を得ます。左辺は変数\(t\)に関するベクトル値関数\(g\left( t\right) =t\left( d_{1},d_{2}\right) \)と多変数関数\(f\left( x_{1},x_{2}\right) \)の合成関数の点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)における右側微分係数ですが、仮定より\(f\)は点\(\left( x_{1}^{\ast },x_{2}^{\ast}\right) \)において全微分可能であるため、合成関数の微分より、\begin{equation*}\lim_{t\rightarrow 0+}\frac{f\left( \left( x_{1}^{\ast },x_{2}^{\ast
}\right) +t\left( d_{1},d_{2}\right) \right) -f\left( x_{1}^{\ast
},x_{2}^{\ast }\right) }{t}=\nabla f\left( x_{1}^{\ast },x_{2}^{\ast
}\right) \cdot \left( d_{1},d_{2}\right)
\end{equation*}となります。したがって、\begin{equation*}
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \cdot \left(
d_{1},d_{2}\right) \geq 0
\end{equation*}すなわち、\begin{equation*}
-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \cdot \left(
d_{1},d_{2}\right) \leq 0
\end{equation*}を得ます。これは\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)と\(\left(d_{1},d_{2}\right) \)が作る角が直角または鈍角であることを意味します。
議論を整理しましょう。制約条件がバインドする最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)に対して、実行可能な方向、すなわち、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) +t\left( d_{1},d_{2}\right) \in
X\cap G
\end{equation*}を満たすベクトル\(\left(d_{1},d_{2}\right) \in \mathbb{R} ^{2}\)を任意に選びます。ただしこれは、\begin{equation*}\left( a_{1},a_{2}\right) \cdot \left( d_{1},d_{2}\right) \leq 0
\end{equation*}と必要十分です。このとき、\begin{equation*}
-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \cdot \left(
d_{1},d_{2}\right) \leq 0
\end{equation*}が成り立つことが保証されます。つまり、\(\left( a_{1},a_{2}\right) \)と直角または鈍角をなす\(\left( d_{1},d_{2}\right) \)を任意に選んだとき、この\(\left( d_{1},d_{2}\right) \)は\(-\nabla f\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)とも直角または鈍角をなすことが保証されるということです。このような条件を満たすためには\(\left( a_{1},a_{2}\right) \)と\(-\nabla f\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)は同方向である必要があります（下図）。なぜなら、\(\left( a_{1},a_{2}\right) \)と\(-\nabla f\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)の方向が異なる場合には\(-\nabla f\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)と直線\(a_{1}x_{1}+a_{2}x_{2}=c\)が作る角は鋭角になるため、\(\left( a_{1},a_{2}\right) \)とは鈍角をなす一方で\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)とは鋭角をなす\(\left( d_{1},d_{2}\right) \)が存在してしまうからです。
以上の議論より、\begin{equation*}
-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\lambda \left(
a_{1},a_{2}\right)
\end{equation*}すなわち、\begin{equation*}
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda \left(
a_{1},a_{2}\right)
\end{equation*}を満たす非負の実数\(\lambda \geq 0\)が存在することが明らかになりました。
得られた結果を整理します。2変数関数\(f\)の定義域の内点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)が最小点である場合には、\begin{eqnarray*}&&\left( 1\right) \ a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }<c\Rightarrow
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right) \\
&&\left( 2\right) \ a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }=c\Rightarrow
\exists \lambda \geq 0:\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
=-\lambda \left( a_{1},a_{2}\right)
\end{eqnarray*}がともに成り立つことが明らかになりました。以上の結果をよりシンプルに表現しましょう。\(\left( 2\right) \)において\(\lambda =0\)とすれば\(\left(1\right) \)を得ます。したがって、以上の条件を、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
=-\lambda \left( a_{1},a_{2}\right) \\
&&\left( b\right) \ \lambda \geq 0
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a\right) \ \nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
+\lambda \left( a_{1},a_{2}\right) =\left( 0,0\right) \\
&&\left( b\right) \ \lambda \geq 0
\end{eqnarray*}を満たす\(\lambda \in \mathbb{R} \)が存在することとして表現できます。制約条件がバインドしない場合、すなわち\(a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }<c\)である場合には\(\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =0\)であるため\(\left( a\right) \)より\(\lambda =0\)となり、したがって\(\lambda \left( a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }-c\right) =0\)が成り立ちます。制約条件がバインドする場合、すなわち\(a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }=c\)である場合にも\(\lambda \left( a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast}-c\right) =0\)が成り立ちます。したがって、\begin{equation*}\left( c\right) \ \lambda \left( a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast
}-c\right) =0
\end{equation*}が成り立ちます。さらに、最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)が制約条件を満たすことを明示するのであれば、\begin{equation*}\left( d\right) \ a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }\leq c
\end{equation*}となります。\(\left( a\right) \)を1階の条件（first order condition）と呼び、\(\left( b\right) ,\left( c\right),\left( d\right) \)をまとめて相補スラック条件（complementary slackness condition）と呼びます。また、\(\left( a\right) \)から\(\left( d\right) \)までの条件をまとめてクーン・タッカー条件（Kuhn-Turcker condition）やカルーシュ・クーン・タッカー条件（Karush-Kuhn-Tucker condition）などと呼びます。
$$\begin{array}{cl}
\min\limits_{\left( x_{1}x_{2}\right) \in X} & f\left( x_{1},x_{2}\right) \\
s.t. & a_{1}x_{1}+a_{2}x_{2}\leq c\end{array}$$
を定義する。関数\(f\)の定義域の内点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)が最小点であり、なおかつ\(f\)が点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
+\lambda \left( a_{1},a_{2}\right) =0 \\
&&\left( b\right) \ \lambda \left( a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast
}-c\right) =0 \\
&&\left( c\right) \ a_{1}x_{1}^{\ast }+a_{1}x_{2}^{\ast }\leq c \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}を満たす実数\(\lambda \in \mathbb{R} \)が存在する。
目的関数が一般の多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)である場合の最小化問題
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c\end{array}$$
についても同様の議論が成立するため以下の命題を得ます。
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c\end{array}$$
を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最小点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \nabla f\left( x^{\ast }\right) +\lambda a=0 \\
&&\left( b\right) \ \lambda \left( a\cdot x^{\ast }-c\right) =0 \\
&&\left( c\right) \ a\cdot x^{\ast }\leq c \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}を満たす実数\(\lambda \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}+x_{2}\leq 2\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 2\right\}
\end{equation*}です。\(f\)は多変数の多項式関数であるため全微分可能であり、勾配ベクトルは、\begin{equation*}\nabla f\left( x_{1},x_{2}\right) =\left( \frac{\partial f\left(
x_{1},x_{2}\right) }{\partial x_{1}},\frac{\partial f\left(
x_{1},x_{2}\right) }{\partial 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 \left(
1,1\right) =\left( 0,0\right) \\
&&\left( b\right) \ \lambda \left( \left( 1,1\right) \cdot \left(
x_{1}^{\ast },x_{2}^{\ast }\right) -2\right) =0 \\
&&\left( c\right) \ \left( 1,1\right) \cdot \left( x_{1}^{\ast },x_{2}^{\ast
}\right) \leq 2 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a\right) \ \left( 2x_{1}+\lambda ,2x_{2}+\lambda \right) =\left(
0,0\right) \\
&&\left( b\right) \ \lambda \left( x_{1}+x_{2}-2\right) =0 \\
&&\left( c\right) \ x_{1}+x_{2}\leq 2 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}を満たす\(\lambda \in \mathbb{R} \)が存在します。仮に\(\left( c\right) \)が等号で成立するならば、\begin{equation*}x_{1}+x_{2}=2
\end{equation*}となるため、これと\(\left( a\right) \)より、\begin{equation*}\lambda =-2
\end{equation*}となり\(\left( d\right) \)と矛盾です。したがって\(\left( c\right) \)は等号で成立せず、\begin{equation*}x_{1}+x_{2}<2
\end{equation*}となるため、これと\(\left( b\right) \)より\(\lambda =0\)を得ます。すると\(\left( a\right) \)より、\begin{equation*}\left( x_{1},x_{2}\right) =\left( 0,0\right)
\end{equation*}となります。したがって、以下の点\begin{equation*}
\left( x_{1}^{\ast },x_{2}^{\ast },\lambda \right) =\left( 0,0,0\right)
\end{equation*}が最小化問題に関するクーン・タッカー条件を満たすことが明らかになりました。
先の命題は目的関数が全微分可能な点が最小化問題の解であるための必要条件を与えるものであり、十分条件ではありません。つまり、目的関数が全微分可能な点が最小化問題の解である場合、その点は必ずクーン・タッカー条件を満たす一方で、クーン・タッカー条件を満たす点は最小化問題の解であるとは限らないということです。以下の例より明らかです。
\end{equation*}を定めるものとします。以下の制約付き最小化問題
$$\begin{array}{cl}
\min\limits_{x\in \mathbb{R} } & f\left( x\right) \\
s.t. & -x\leq 1\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ x\in \mathbb{R} \ |\ -x\leq 1\right\}
\end{equation*}です。\(f\)は微分可能です。点\(0\in G\)において、\begin{equation*}f^{\prime }\left( 0\right) =0\quad \because f^{\prime }\left( x\right)
=3x^{2}
\end{equation*}であるため、\(\lambda =0\)に注目したとき、\begin{eqnarray*}&&\left( a\right) \ f^{\prime }\left( 0\right) +\lambda \left( -1\right) =0
\\
&&\left( b\right) \ \lambda \left( -1\cdot 0\right) =0 \\
&&\left( c\right) \ -1\cdot 0\leq 1 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}がいずれも成り立ちます。したがって点\(0\)はクーン・タッカー条件を満たします。一方、\(f\)は狭義単調増加関数であるため最小点は\(-1\)であり、点\(0\)は最小点ではありません。
ラグランジュの未定乗数法
目的関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)のもとでの最小化問題
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c\end{array}$$
が与えられたとき、それぞれの\(\left( x,\lambda \right) \in X\times \mathbb{R} \)に対して、\begin{equation*}L\left( x,\lambda \right) =f\left( x\right) +\lambda \left( a\cdot
x-c\right)
\end{equation*}を値として定める関数\begin{equation*}
L:X\times \mathbb{R} \rightarrow \mathbb{R} \end{equation*}を定義し、これをラグランジュ関数（Lagrangian）と呼びます。
目的関数\(f\)が定義域の内点\(x\in X^{i}\)において全微分可能である場合、ラグランジュ関数\(L\)は明らかに点\(\left( x,\lambda \right) \)において全微分可能です。そこで、\(L\)をそれぞれの変数\(x_{i}\ \left( i=1,\cdots ,n\right) \)に関して偏微分して\(0\)とおくと、\begin{eqnarray*}\forall i\in \left\{ 1,\cdots ,n\right\} :\frac{\partial L\left( x,\lambda
\right) }{\partial x_{i}}=0 &\Leftrightarrow &\forall i:\frac{\partial
f\left( x\right) }{\partial x_{i}}+\lambda a_{i}=0 \\
&\Leftrightarrow &\nabla f\left( x\right) +\lambda a=0
\end{eqnarray*}を得ます。さらに、\begin{equation*}
\lambda \frac{\partial L\left( x,\lambda \right) }{\partial \lambda }=0\Leftrightarrow \lambda \left( a\cdot x-c\right) =0
\end{equation*}が成り立ち、また、\begin{eqnarray*}
\frac{\partial L\left( x,\lambda \right) }{\partial \lambda }\leq 0
&\Leftrightarrow &a\cdot x-c\leq 0 \\
&\Leftrightarrow &a\cdot x\leq c
\end{eqnarray*}が成り立ちます。したがって、最小化のためのクーン・タッカー条件は、ラグランジュ関数\(L\)に関する以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda \right) }{\partial x_{i}}=0 \\
&&\left( b\right) \ \lambda \frac{\partial L\left( x^{\ast },\lambda \right)
}{\partial \lambda }=0 \\
&&\left( c\right) \ \frac{\partial L\left( x^{\ast },\lambda \right) }{\partial \lambda }\leq 0 \\
&&\left( d\right) \ \lambda \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\cdot x\leq c\end{array}$$
を定義する。それぞれの\(\left( x,\lambda \right) \in X\times \mathbb{R} \)に対して、\begin{equation*}L\left( x,\lambda \right) =f\left( x\right) +\lambda \left( a\cdot x-c\right)
\end{equation*}を定める関数\(L:X\times \mathbb{R} \rightarrow \mathbb{R} \)を定義する。関数\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最小点であり、なおかつ\(f\)が点\(x^{\ast }\)において全微分可能である場合には、\begin{eqnarray*}&&\left( a\right) \ \forall i\in \left\{ 1,\cdots ,n\right\} :\frac{\partial
L\left( x^{\ast },\lambda \right) }{\partial x_{i}}=0 \\
&&\left( b\right) \ \lambda \frac{\partial L\left( x^{\ast },\lambda \right)
}{\partial \lambda }=0 \\
&&\left( c\right) \ \frac{\partial L\left( x^{\ast },\lambda \right) }{\partial \lambda }\leq 0 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}を満たす実数\(\lambda \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}+x_{2}\leq 2\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 2\right\}
\end{equation*}です。先に、以下の点\begin{equation*}
\left( x_{1}^{\ast },x_{2}^{\ast },\lambda \right) =\left( 0,0,0\right)
\end{equation*}がクーン・タッカー条件を満たすことを示しましたが、同じことをラグランジュの未定乗数を用いて導きます。ラグランジュ関数を、\begin{equation*}
L\left( x_{1},x_{2},\lambda \right) =x_{1}^{2}+x_{2}^{2}+\lambda \left(
x_{1}+x_{2}-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 \right) }{\partial x_{1}}=0 \\
&&\left( a_{2}\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda \right) }{\partial x_{2}}=0 \\
&&\left( b\right) \ \lambda \frac{\partial L\left( x_{1},x_{2},\lambda
\right) }{\partial \lambda }=0 \\
&&\left( c\right) \ \frac{\partial L\left( x_{1},x_{2},\lambda \right) }{\partial \lambda }\leq 0 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a_{1}\right) \ 2x_{1}+\lambda =0 \\
&&\left( a_{2}\right) \ 2x_{2}+\lambda =0 \\
&&\left( b\right) \ \lambda \left( x_{1}+x_{2}-2\right) =0 \\
&&\left( c\right) \ x_{1}+x_{2}-2\leq 0 \\
&&\left( d\right) \ \lambda \geq 0
\end{eqnarray*}を満たす\(\lambda \in \mathbb{R} \)が存在します。\(\lambda >0\)と仮定すると\(\left( b\right) \)より\(x_{1}+x_{2}-2=0\)を得ます。これと\(\left( a\right) ,\left( b\right) \)より\(4+2\lambda =0\)すなわち\(\lambda =-2\)となりますが、これは\(\lambda >0\)と矛盾です。したがって背理法より\(\lambda >0\)ではなく、ゆえに\(\left( d\right) \)より\(\lambda =0\)となります。すると\(\left( a\right) ,\left( b\right) \)より\(x_{1}=x_{2}=0\)を得るため、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast },\lambda \right) =\left( 0,0,0\right)
\end{equation*}がクーン・タッカー条件を満たすことが明らかになりました。これは先の結果と整合的です。
線型不等式制約のもとでの最小化問題の解法
関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)から最小化問題
$$\begin{array}{cl}
\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c\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\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}\leq 3\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}
\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\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+2x_{2}\leq 3\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\)の内点の中でも、制約条件\(a\cdot x\leq c\)を満たすとともに、関数が全微分可能ではない点をすべて特定する。
- 目的関数\(f\)の定義域\(X\)に含まれる境界点の中でも、制約条件\(a\cdot x\leq c\)を満たす点をすべて特定する。
- 以上の点の中でも\(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}
\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}\leq 2\end{array}$$
について考えます。制約集合は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq 2\right\}
\end{equation*}です。\(f\)の定義域\(\mathbb{R} ^{2}\)は\(\mathbb{R} ^{2}\)上の開集合であるとともに、\(f\)は\(\mathbb{R} ^{2}\)上の任意の点において全微分可能です。また、任意の\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)について、\begin{equation*}x_{1}^{2}+x_{2}^{2}\geq 0
\end{equation*}となるため、\(\mathbb{R} ^{2}\)における\(f\)の最小値は\(0\)です。先に求めたように、以下の点\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast },\lambda \right) =\left( 0,0,0\right)
\end{equation*}がクーン・タッカー条件を満たしますが、この点における\(f\)の値は、\begin{equation*}f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =0^{2}+0^{2}=0
\end{equation*}であり、この値は\(\mathbb{R} ^{2}\)における\(f\)の最小値と一致します。したがって、この値は\(G\)における\(f\)の最小値でもあり、\(f\)の最小点は、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}であることが明らかになりました。
演習問題
\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}\leq 1\end{array}$$
を解いてください。
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\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}\leq 3\end{array}$$
を解いてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】