教材一覧
教材一覧
教材検索

関数の最適化

複数の線型不等式制約条件のもとでの多変数関数の最小化問題

目次

Twitterで共有
メールで共有

複数の線型不等式制約条件のもとでの多変数関数の最小化問題

多変数関数\(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\) thconstraint 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\)の最小点を特定する問題を線型不等式制約付き最小化問題(minimization problem with linear constraints)と呼び、これを、$$\begin{array}{cl}\min\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 minimization problem)と呼びます。\(X=\mathbb{R} ^{n}\)の場合には\(X\cap G=G\)です。最小化問題において最小化する対象となる関数\(f\)を目的関数(objective mathrmtion)と呼び、制約集合\(G\)を規定するそれぞれの条件\(a_{i}\cdot x\leq c_{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) =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*}と表現できるため、先の最小化問題を、
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & g_{1}\left( x\right) \leq 0 \\
& \vdots \\
& g_{m}\left( x\right) \leq 0
\end{array}$$と表現することもできます。

例(線型不等式制約付き最小化問題)
1変数関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)を目的関数とする2つの線型不等式制約付き最小化問題は、非ゼロの実数\(a_{1},a_{2}\in \mathbb{R} \backslash \left\{ 0\right\} \)およびスカラー\(c_{1},c_{2}\in \mathbb{R} \)を用いて、$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & a_{1}x\leq c_{1} \\
& a_{2}x\leq c_{2}
\end{array}$$と定式化されます。

例(線型不等式制約付き最小化問題)
2変数関数\(f:\mathbb{R} ^{2}\supset X\rightarrow \mathbb{R} \)を目的関数とする2つの線型不等式制約付き最小化問題は、非ゼロのベクトル\(\left(a_{11},a_{12}\right) ,\left( a_{21},a_{22}\right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)およびスカラー\(c_{1},c_{2}\in \mathbb{R} \)を用いて、$$\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}
\end{array}$$と定式化されます。

例(線型不等式制約付き最小化問題)
関数\(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}\min\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}\min\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}$$に読み替えることにより、通常の最小化問題として扱うことができます。

 

最小点であるための必要条件(クーン・タッカー条件)

複数の線型不等式制約条件を持つ最小化問題に解が存在する場合、それはどのような条件を満たすのでしょうか。2変数関数を目的関数とする2つの制約条件のもとでの最小化問題について議論した上で、後に結論を一般化します。

目的関数\(f:\mathbb{R} ^{2}\supset X\rightarrow \mathbb{R} \)と非ゼロベクトル\(\left(a_{11},a_{12}\right) ,\left( a_{21},a_{22}\right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)およびスカラー\(c_{1},c_{2}\in \mathbb{R} \)から最小化問題
$$\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}
\end{array}$$を定義します。それぞれの制約条件に関する制約集合は、\begin{eqnarray*}
G_{1} &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{11}x_{1}+a_{12}x_{2}\leq c_{1}\right\} \\
G_{2} &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{21}x_{1}+a_{22}x_{2}\leq c_{2}\right\}
\end{eqnarray*}であり、全体の制約集合は、\begin{equation*}
G=G_{1}\cap G_{2}
\end{equation*}です。最小点\(\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\)のもとで2つの制約条件がともにバインドしない場合、すなわち、\begin{eqnarray*}a_{11}x_{1}^{\ast }+a_{12}x_{2}^{\ast } &<&c_{1} \\
a_{21}x_{1}^{\ast }+a_{22}x_{2}^{\ast } &<&c_{2}
\end{eqnarray*}が成り立つ場合について考えます。これは\(\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\)のもとで1番目の制約条件がバインドする一方で2番目の制約条件がバインドしない場合、すなわち、\begin{eqnarray*}a_{11}x_{1}^{\ast }+a_{12}x_{2}^{\ast } &=&c_{1} \\
a_{21}x_{1}^{\ast }+a_{22}x_{2}^{\ast } &<&c_{2}
\end{eqnarray*}が成り立つ場合について考えます。これは\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が制約集合\(G_{1}\)の境界点である一方で制約集合\(G_{2}\)の内点であることを意味します。つまり\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G_{1}^{f}\cap G_{2}^{i}\)です。この場合には\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)は直線\(a_{11}x_{1}+a_{12}x_{2}=c_{1}\)上の点である一方で直線\(a_{21}x_{1}+a_{22}x_{2}=c_{2}\)上の点ではありません。なお、直線\(a_{11}x_{1}+a_{12}x_{2}=c_{1}\)の法線ベクトルは\(\left( a_{11},a_{12}\right) \)です(下図)。

図:一方の制約条件がバインドする解
図:一方の制約条件がバインドする解

点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G_{1}^{f}\cap G_{2}^{i}\)が与えられたとき、十分小さい\(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) &\Rightarrow &\left( a_{11},a_{12}\right) \cdot \left(
x_{1}^{\ast }+td_{1},x_{2}^{\ast }+td_{2}\right) \leq c_{1}\quad \because G\text{の定義} \\
&\Leftrightarrow &\left( a_{11},a_{12}\right) \cdot \left( x_{1}^{\ast
}+td_{1},x_{2}^{\ast }+td_{2}\right) \leq a_{11}x_{1}+a_{12}x_{2}\quad
\because a_{11}x_{1}+a_{12}x_{2}=c_{1} \\
&\Leftrightarrow &\left( a_{11},a_{12}\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_{11},a_{12}\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) \geq 0
\end{equation*}を得ます。これは\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)と\(\left(d_{1},d_{2}\right) \)が作る角が直角または鈍角であることを意味します。

議論を整理しましょう。1番目の制約条件がバインドする一方で2番目の制約条件がバインドしない最小点\(\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{eqnarray*}&&\left( a\right) \ \left( a_{11},a_{12}\right) \cdot \left(
d_{1},d_{2}\right) \leq 0 \\
&&\left( b\right) \ -\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \cdot
\left( d_{1},d_{2}\right) \leq 0
\end{eqnarray*}がともに成り立つことが保証されます。つまり、\(\left( a_{11},a_{12}\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_{11},a_{12}\right) \)と\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast}\right) \)は同方向である必要があります(下図)。なぜなら、\(\left(a_{11},a_{12}\right) \)と\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast}\right) \)の方向が異なる場合には\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)と直線\(a_{11}x_{1}+a_{12}x_{2}=c_{1}\)が作る角は鋭角になるため、\(\left( a_{11},a_{12}\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_{11},a_{12}\right)
\end{equation*}すなわち、\begin{equation*}
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda \left(
a_{11},a_{12}\right)
\end{equation*}を満たす非負の実数\(\lambda \geq 0\)が存在することが明らかになりました。

続いて、最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)のもとで1番目の制約条件がバインドしない一方で2番目の制約条件がする場合、すなわち、\begin{eqnarray*}a_{11}x_{1}^{\ast }+a_{12}x_{2}^{\ast } &<&c_{1} \\
a_{21}x_{1}^{\ast }+a_{22}x_{2}^{\ast } &=&c_{2}
\end{eqnarray*}が成り立つ場合について考えます。この場合にも先と同様の議論より、\begin{equation*}
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda \left(
a_{21},a_{22}\right)
\end{equation*}を満たす非負の実数\(\lambda \geq 0\)が存在することが明らかになります。

最後に、最小点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)のもとで2つの制約条件がともにバインドする場合、すなわち、\begin{eqnarray*}a_{11}x_{1}^{\ast }+a_{12}x_{2}^{\ast } &=&c_{1} \\
a_{21}x_{1}^{\ast }+a_{22}x_{2}^{\ast } &=&c_{2}
\end{eqnarray*}が成り立つ場合について考えます。これは\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)が\(G_{1}\)の境界点であるとともに\(G_{2}\)の境界点でもあることを意味します。つまり\(\left( x_{1}^{\ast },x_{2}^{\ast }\right)\in X^{i}\cap G_{1}^{f}\cap G_{2}^{f}\)です。この場合には、\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)は2つの直線\(a_{11}x_{1}+a_{12}x_{2}=c_{1}\)と\(a_{21}x_{1}+a_{22}x_{2}=c_{2}\)の交点です(下図)。

図:両方の制約条件がバインドする解
図:両方の制約条件がバインドする解

点\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\cap G_{1}^{f}\cap G_{2}^{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}\)を任意に選んで固定します。このとき、\begin{eqnarray*}\left( 1\right) &\Leftrightarrow &\forall i\in \left\{ 1,2\right\} :\left(
a_{i1},a_{i2}\right) \cdot \left( x_{1}^{\ast }+td_{1},x_{2}^{\ast
}+td_{2}\right) \leq c_{i}\quad \because G\text{の定義} \\
&\Leftrightarrow &\forall i\in \left\{ 1,2\right\} :\left(
a_{i1},a_{i2}\right) \cdot \left( x_{1}^{\ast }+td_{1},x_{2}^{\ast
}+td_{2}\right) \leq a_{i1}x_{1}+a_{i2}x_{2}\quad \because
a_{i1}x_{1}+a_{i2}x_{2}=c_{i} \\
&\Leftrightarrow &\forall i\in \left\{ 1,2\right\} :\left(
a_{i1},a_{i2}\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_{11},a_{12}\right) \)と\(\left( d_{1},d_{2}\right) \)が作る角と\(\left(a_{21},a_{22}\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) \)が最小点であることから、先と同様の理由により、\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) \)が作る角が直角または鈍角であることを意味します。

議論を整理しましょう。2つの制約条件がバインドする最小点\(\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{eqnarray*}&&\left( a\right) \ \left( a_{11},a_{12}\right) \cdot \left(
d_{1},d_{2}\right) \leq 0 \\
&&\left( b\right) \ \left( a_{21},a_{22}\right) \cdot \left(
d_{1},d_{2}\right) \leq 0 \\
&&\left( c\right) \ -\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \cdot
\left( d_{1},d_{2}\right) \leq 0
\end{eqnarray*}がすべて成り立つことが保証されます。つまり、\(\left( a_{11},a_{12}\right) \)や\(\left( a_{21},a_{22}\right) \)と直角または鈍角をなす\(\left( d_{1},d_{2}\right) \)を任意に選んだとき、この\(\left( d_{1},d_{2}\right) \)は\(-\nabla f\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)とも直角または鈍角をなすことが保証されるということです。このような条件を満たすためには\(-\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) \)は\(\left( a_{11},a_{12}\right) \)と\(\left( a_{21},a_{22}\right) \)が作る角の間にある必要があります(下図)。なぜなら、そうでない場合には\(-\nabla f\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)と少なくとも一本の直線が作る角が鈍角になるため、\(\left( a_{11},a_{12}\right) \)と\(\left( a_{21},a_{22}\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 _{1}\left(
a_{11},a_{12}\right) +\lambda _{2}\left( a_{21},a_{22}\right)
\end{equation*}すなわち、\begin{equation*}
\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda _{1}\left(
a_{11},a_{12}\right) -\lambda _{2}\left( a_{21},a_{22}\right)
\end{equation*}を満たす非負の実数\(\lambda _{1},\lambda _{2}\geq 0\)が存在することが明らかになりました。

得られた結果を整理します。2変数関数\(f\)の定義域の内点\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \in X^{i}\cap G\)が最小点である場合には、\begin{eqnarray*}&&\left( 1\right) \ \left.
\begin{array}{c}
a_{11}x_{1}^{\ast }+a_