教材一覧
教材一覧
教材検索
OPTIMIZATION OF FUNCTIONS

1つの線型不等式制約条件のもとでの関数の最適化

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

1つの線型不等式制約条件のもとでの関数の最小化

多変数関数\(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\)の最小点\begin{equation*}\mathrm{argmin}_{x\in X\cap G}f\left( x\right)
\end{equation*}を特定する問題を線型不等式制約付き最小化問題(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\)が、\begin{equation*}a\cdot x=c
\end{equation*}を満たす場合、\(x\)のもとで制約条件はバインドする(binded)とか有効である(active)などと言います。

非ゼロベクトル\(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*}と表現できるため、目的関数を\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)とする線型不等式制約付き最小化問題を、
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & g\left( x\right) \leq 0
\end{array}$$
と表現することもできます。

例(線型不等式制約付き最小化問題)
1変数関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)に関する線型不等式制約付き最小化問題は、非ゼロの実数\(a\in \mathbb{R} \backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)を用いて、
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & ax\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_{\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:\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\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) \)の周辺の任意の点において定義されていることが保証されるため、\(f\)の微分可能性より、勾配ベクトル\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*}を得ます。仮定より\(\left( x_{1}^{\ast },x_{2}^{\ast }\right) \in X^{i}\)であるため、\(f\)は\(\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) \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( a\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( b\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( b\right) \)において\(\lambda =0\)とすれば\(\left( a\right) \)を得ます。したがって、これらの条件を、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
=-\lambda \left( a_{1},a_{2}\right)
\end{equation*}とまとめて表現することもできます。

命題(線型不等式制約付き最小化問題の解であるための必要条件)
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_{\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\)が最小点である場合には、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right)
=-\lambda \left( a_{1},a_{2}\right)
\end{equation*}が成り立つ。

目的関数が一般の多変数関数\(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}$$
についても同様の議論が成立します。したがって、関数\(f\)が微分可能であるとき、\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最小点である場合には、\begin{eqnarray*}&&\left( a\right) \ a\cdot x^{\ast }\leq c\Rightarrow \nabla f\left( x^{\ast
}\right) =0 \\
&&\left( b\right) \ a\cdot x^{\ast }=c\Rightarrow \exists \lambda \geq
0:\nabla f\left( x^{\ast }\right) =-\lambda a
\end{eqnarray*}が成り立ちます。\(\left(b\right) \)において\(\lambda =0\)とすれば\(\left( a\right) \)を得ます。したがって、これらの条件を、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x^{\ast }\right) =-\lambda a
\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^{\ast }\in X^{i}\cap G\)が最小点である場合には、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x^{\ast }\right) =-\lambda a
\end{equation*}が成り立つ。

上の命題の逆は成立するとは限りません。つまり、最小点であるための必要条件を満たす点は最小点であるとは限りません。以下の例より明らかです。

例(線型不等式制約付き最小化問題)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =x^{3}
\end{equation*}を定めるものとします。\(f\)は微分可能です。以下の制約付き最小化問題
$$\begin{array}{cl}\min\limits_{x\in \mathbb{R} } & f\left( x\right) \\
s.t. & -x\leq 1
\end{array}$$
について考えます。点\(0\)において、\begin{equation*}f^{\prime }\left( 0\right) =-\lambda \left( -1\right)
\end{equation*}すなわち、\begin{equation*}
0=\lambda
\end{equation*}となるため、点\(0\)は最小点であるための必要条件を満たします。ただ、\(f\)は狭義単調増加関数であるため最小点は\(-1\)であり、点\(0\)は最小点ではありません。

先の命題は\(f\)の定義域の内点が最小点であるための必要条件を与えており、内点ではない点、すなわち境界点については何も語っていません。\(f\)の定義域が境界点を含む場合、境界点が最小点になる状況は起こり得ます。以下の例より明らかです。

例(線型不等式制約付き最小化問題)
関数\(f:\mathbb{R} \supset \left[ -1,1\right] \rightarrow \mathbb{R} \)はそれぞれの\(x\in \left[ -1,1\right] \)に対して、\begin{equation*}f\left( x\right) =x^{3}
\end{equation*}を定めるものとします。\(f\)は微分可能です。以下の制約付き最小化問題
$$\begin{array}{cl}\min\limits_{x\in \mathbb{R} } & f\left( x\right) \\
s.t. & x\leq \frac{1}{2}
\end{array}$$
について考えます。\(f\)は狭義単調増加関数であるため最小点は\(-1\)ですが、これは\(f\)の定義域\(\left[ -1,1\right] \)の境界点です。

以上を踏まえると、線型不等式制約条件のもとでの関数の最小点を求めるためには以下の手順にしたがえばよいということになります。

  1. 最小点が存在することを確認する。その際、最大値・最小値の定理などを利用する。
  2. 関数の定義域の内点であるとともに制約条件を満たす点の中でも、最小点であるための必要条件を満たす点をすべて特定する。
  3. 関数の定義域の要素であるような境界点であるとともに制約条件を満たす点をすべて特定する。
  4. 以上のすべての点の中でも関数の値を最小化する点が最小点である。
例(線型不等式制約付き最小化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x_{1},x_{2}\right) =x_{1}^{2}+x_{2}^{2}
\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\)は下に凸であるため最小点が存在します。\(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}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最小点であるならば、最小点であるための必要条件より、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda \left(
1,1\right)
\end{equation*}すなわち、\begin{equation*}
\left( 2x_{1}^{\ast },2x_{2}^{\ast }\right) =\left( -\lambda ,-\lambda
\right)
\end{equation*}すなわち、\begin{equation}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{\lambda }{2},-\frac{\lambda }{2}\right) \quad \cdots (1)
\end{equation}を満たす\(\lambda \geq 0\)が存在します。仮に\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)において制約条件がバインドするならば、\begin{equation*}x_{1}^{\ast }+x_{2}^{\ast }=2
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}-\frac{\lambda }{2}-\frac{\lambda }{2}=2
\end{equation*}すなわち、\begin{equation*}
\lambda =-2
\end{equation*}となり矛盾です。したがって、\(\left( x_{1}^{\ast },x_{2}^{\ast}\right) \)において制約条件はバインドせず、\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)は停留点になるため、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( 2x_{1},2x_{2}\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}となります。\(\left( 0,0\right) \in G\)です。このとき、\begin{equation*}f\left( 0,0\right) =0^{2}+0^{2}=0
\end{equation*}となります。\(f\)の定義域\(\mathbb{R} ^{2}\)は開集合であるため境界点を含みません。以上より、最小点は\(\left( 0,0\right) \)であり、最小値が\(0\)であることが明らかになりました。

例(線型不等式制約付き最小化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x_{1},x_{2}\right) =x_{1}^{2}+x_{2}^{2}
\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}$$
を構成します。最小化問題の定義域は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq -1\right\}
\end{equation*}です。\(f\)は下に凸であるため最小点が存在します。\(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}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最小点であるならば、最小点であるための必要条件より、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =-\lambda \left(
1,1\right)
\end{equation*}すなわち、\begin{equation*}
\left( 2x_{1}^{\ast },2x_{2}^{\ast }\right) =\left( -\lambda ,-\lambda
\right)
\end{equation*}すなわち、\begin{equation}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{\lambda }{2},-\frac{\lambda }{2}\right) \quad \cdots (1)
\end{equation}を満たす\(\lambda \geq 0\)が存在します。仮に\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)において制約条件がバインドするならば、\begin{equation*}x_{1}^{\ast }+x_{2}^{\ast }=-1
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}-\frac{\lambda }{2}-\frac{\lambda }{2}=-1
\end{equation*}すなわち、\begin{equation*}
\lambda =1
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{1}{2},-\frac{1}{2}\right)
\end{equation*}を得ます。このとき、\begin{equation*}
f\left( -\frac{1}{2},-\frac{1}{2}\right) =\left( -\frac{1}{2}\right)
^{2}+\left( -\frac{1}{2}\right) ^{2}=\frac{1}{2}
\end{equation*}となります。\(f\)の定義域\(\mathbb{R} ^{2}\)は開集合であるため境界点を含みません。以上より、最小点は\(\left( -\frac{1}{2},-\frac{1}{2}\right) \)であり、最小値が\(\frac{1}{2}\)であることが明らかになりました。

 

1つの線型不等式制約条件のもとでの関数の最大化

多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられているものとします。また、非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)から以下の制約集合\begin{equation*}G=\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\}
\end{equation*}を定義します。その上で、\(f\)の変数\(x\)がとり得る値の範囲を\(X\cap G\)に制限した場合の\(f\)の最大点\begin{equation*}\mathrm{argmax}_{x\in X\cap G}f\left( x\right)
\end{equation*}を特定する問題を線型不等式制約付き最大化問題問題(maximization problem with one linear inequality constraint)と呼び、これを、

$$\begin{array}{cl}\max\limits_{x\in X} & f\left( x\right) \\
s.t. & a\cdot x\leq c
\end{array}$$
で表記します。集合\(X\cap G\)は最大化問題の定義域(domain of the maximization problem)です。\(X=\mathbb{R} ^{n}\)の場合には\(X\cap G=G\)です。

例(線型不等式制約付き最大化問題)
1変数関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)に関する線型不等式制約付き最大化問題は、非ゼロの実数\(a\in \mathbb{R} \backslash \left\{ 0\right\} \)およびスカラー\(c\in \mathbb{R} \)を用いて、
$$\begin{array}{cl}\max\limits_{x\in X} & f\left( x\right) \\
s.t. & ax\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}\max\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:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)および非ゼロベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)から以下の問題
$$\begin{array}{cl}\max\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}\max\limits_{x\in X} & f\left( x\right) \\
s.t. & -a\cdot x\leq -c
\end{array}$$
に読み替えることにより、通常の最大化問題として扱うことができます。

 

最大点であるための必要条件

関数\(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}\max\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\)が微分可能であるとき、\(f\)の定義域の内点\(x^{\ast }\in X^{i}\cap G\)が最大点である場合には、\begin{eqnarray*}&&\left( a\right) \ a\cdot x^{\ast }\leq c\Rightarrow -\nabla f\left(
x^{\ast }\right) =0 \\
&&\left( b\right) \ a\cdot x^{\ast }=c\Rightarrow \exists \lambda \geq
0:-\nabla f\left( x^{\ast }\right) =-\lambda \left( a\right)
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a\right) \ a\cdot x^{\ast }\leq c\Rightarrow \nabla f\left( x^{\ast
}\right) =0 \\
&&\left( b\right) \ a\cdot x^{\ast }=c\Rightarrow \exists \lambda \geq
0:\nabla f\left( x^{\ast }\right) =\lambda a
\end{eqnarray*}が成り立ちます。\(\left(b\right) \)において\(\lambda =0\)とすれば\(\left( a\right) \)を得ます。したがって、これらの条件を、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x^{\ast }\right) =\lambda a
\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}\max\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\)が最大点である場合には、\begin{equation*}\exists \lambda \geq 0:\nabla f\left( x^{\ast }\right) =\lambda a
\end{equation*}が成り立つ。

上の命題の逆は成立するとは限りません。つまり、最大点であるための必要条件を満たす点は最大点であるとは限りません。以下の例より明らかです。

例(線型不等式制約付き最大化問題)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =x^{3}
\end{equation*}を定めるものとします。\(f\)は微分可能です。以下の制約付き最小化問題
$$\begin{array}{cl}\min\limits_{x\in \mathbb{R} } & f\left( x\right) \\
s.t. & x\leq 1
\end{array}$$
について考えます。点\(0\)において、\begin{equation*}f^{\prime }\left( 0\right) =\lambda \cdot 1
\end{equation*}すなわち、\begin{equation*}
0=\lambda
\end{equation*}となるため、点\(0\)は最小点であるための必要条件を満たします。ただ、\(f\)は狭義単調増加関数であるため最大点は最小点は\(1\)であり、点\(0\)は最大点ではありません。

先の命題は\(f\)の定義域の内点が最大点であるための必要条件を与えており、内点ではない点、すなわち境界点については何も語っていません。\(f\)の定義域が境界点を含む場合、境界点が最大点になる状況は起こり得ます。以下の例より明らかです。

例(線型不等式制約付き最大化問題)
関数\(f:\mathbb{R} \supset \left[ -1,1\right] \rightarrow \mathbb{R} \)はそれぞれの\(x\in \left[ -1,1\right] \)に対して、\begin{equation*}f\left( x\right) =x^{3}
\end{equation*}を定めるものとします。\(f\)は微分可能です。以下の制約付き最小化問題
$$\begin{array}{cl}\min\limits_{x\in \mathbb{R} } & f\left( x\right) \\
s.t. & -x\leq \frac{1}{2}
\end{array}$$
について考えます。\(f\)は狭義単調増加関数であるため最大点は\(1\)ですが、これは\(f\)の定義域\(\left[ -1,1\right] \)の境界点です。

以上を踏まえると、線型不等式制約条件のもとでの関数の最大点を求めるためには以下の手順にしたがえばよいということになります。

  1. 最大点が存在することを確認する。その際、最大値・最小値の定理などを利用する。
  2. 関数の定義域の内点であるとともに制約条件を満たす点の中でも、最大点であるための必要条件を満たす点をすべて特定する。
  3. 関数の定義域の要素であるような境界点であるとともに制約条件を満たす点をすべて特定する。
  4. 以上のすべての点の中でも関数の値を最大化する点が最小点である。
例(線型不等式制約付き最大化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x_{1},x_{2}\right) =-x_{1}^{2}-x_{2}^{2}
\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 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\)は上に凸であるため最大点が存在します。\(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}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最大点であるならば、最大点であるための必要条件より、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\lambda \left( 1,1\right)
\end{equation*}すなわち、\begin{equation*}
\left( -2x_{1}^{\ast },-2x_{2}^{\ast }\right) =\left( \lambda ,\lambda
\right)
\end{equation*}すなわち、\begin{equation}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{\lambda }{2},-\frac{\lambda }{2}\right) \quad \cdots (1)
\end{equation}を満たす\(\lambda \geq 0\)が存在します。仮に\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)において制約条件がバインドするならば、\begin{equation*}x_{1}^{\ast }+x_{2}^{\ast }=2
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}-\frac{\lambda }{2}-\frac{\lambda }{2}=2
\end{equation*}すなわち、\begin{equation*}
\lambda =-2
\end{equation*}となり矛盾です。したがって、\(\left( x_{1}^{\ast },x_{2}^{\ast}\right) \)において制約条件はバインドせず、\(\left(x_{1}^{\ast },x_{2}^{\ast }\right) \)は停留点になるため、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( -2x_{1},-2x_{2}\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( 0,0\right)
\end{equation*}となります。\(\left( 0,0\right) \in G\)です。このとき、\begin{equation*}f\left( 0,0\right) =-0^{2}+-0^{2}=0
\end{equation*}となります。\(f\)の定義域\(\mathbb{R} ^{2}\)は開集合であるため境界点を含みません。以上より、最小点は\(\left( 0,0\right) \)であり、最小値が\(0\)であることが明らかになりました。

例(線型不等式制約付き最大化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x_{1},x_{2}\right)\in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x_{1},x_{2}\right) =-x_{1}^{2}-x_{2}^{2}
\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
\end{array}$$
を構成します。最大化問題の定義域は、\begin{equation*}
G=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{1}+x_{2}\leq -1\right\}
\end{equation*}です。\(f\)は上に凸であるため最大点が存在します。\(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}^{\ast},x_{2}^{\ast }\right) \in \mathbb{R} ^{2}\)が最大点であるならば、最大点であるための必要条件より、\begin{equation*}\nabla f\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\lambda \left( 1,1\right)
\end{equation*}すなわち、\begin{equation*}
\left( -2x_{1}^{\ast },-2x_{2}^{\ast }\right) =\left( \lambda ,\lambda
\right)
\end{equation*}すなわち、\begin{equation}
\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{\lambda }{2},-\frac{\lambda }{2}\right) \quad \cdots (1)
\end{equation}を満たす\(\lambda \geq 0\)が存在します。仮に\(\left( x_{1}^{\ast},x_{2}^{\ast }\right) \)において制約条件がバインドするならば、\begin{equation*}x_{1}^{\ast }+x_{2}^{\ast }=-1
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}-\frac{\lambda }{2}-\frac{\lambda }{2}=-1
\end{equation*}すなわち、\begin{equation*}
\lambda =1
\end{equation*}となるため、これと\(\left( 1\right) \)より、\begin{equation*}\left( x_{1}^{\ast },x_{2}^{\ast }\right) =\left( -\frac{1}{2},-\frac{1}{2}\right)
\end{equation*}を得ます。このとき、\begin{equation*}
f\left( -\frac{1}{2},-\frac{1}{2}\right) =-\left( -\frac{1}{2}\right)
^{2}-\left( -\frac{1}{2}\right) ^{2}=-\frac{1}{2}
\end{equation*}となります。\(f\)の定義域\(\mathbb{R} ^{2}\)は開集合であるため境界点を含みません。以上より、最小点は\(\left( -\frac{1}{2},-\frac{1}{2}\right) \)であり、最小値が\(-\frac{1}{2}\)であることが明らかになりました。

 

ラグランジュの未定乗数法

目的関数\(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*}を定める関数\(L:X\times \mathbb{R} \rightarrow \mathbb{R} \)を定義し、これをラグランジュ関数(Lagrangian)と呼びます。\(f\)が微分可能である場合には\(L\)もまた微分可能であるため、\(L\)をそれぞれの変数\(x_{i}\ \left( i=1,\cdots ,n\right) \)に関して偏微分して\(0\)とおくと、\begin{eqnarray*}\forall i:\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\quad \because L\text{の定義} \\
&\Leftrightarrow &\nabla f\left( x\right) =-\lambda a
\end{eqnarray*}となります。特に、最小点\(x^{\ast }\)が存在する場合には、\begin{equation*}\frac{\partial L\left( x^{\ast },\lambda \right) }{\partial x_{i}}=0\Leftrightarrow \nabla f\left( x^{\ast }\right) =-\lambda a
\end{equation*}という関係が成立します。つまり、最小点\(x^{\ast }\)が存在する場合、ラグランジュ関数\(L\)を点\(x^{\ast }\)においてそれぞれの変数\(x_{i}\ \left( i=1,\cdots ,n\right) \)に関して偏微分して\(0\)とおけば最小点であるための必要条件が得られるということです。これをラグランジュの未定乗数法(method of Lagrange multipler)と呼びます。

例(ラグランジュの未定乗数法)
目的関数\(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}\max\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}$$へと言い換え可能であるため、最大点であるための必要条件を特定するためには、ラグランジュ関数を、\begin{equation*}
L\left( x,\lambda \right) =-f\left( x\right) +\lambda \left( a\cdot
x-c\right)
\end{equation*}と定義することになります。実際、\begin{eqnarray*}
\forall i:\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\quad \because L\text{の定義} \\
&\Leftrightarrow &\nabla f\left( x\right) =\lambda a
\end{eqnarray*}となります。特に、最大点\(x^{\ast }\)が存在する場合には、\begin{equation*}\forall i:\frac{\partial L\left( x^{\ast },\lambda \right) }{\partial x_{i}}=0\Leftrightarrow \nabla f\left( x^{\ast }\right) =\lambda a
\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\geq c
\end{array}$$を定義します。本来の最小化問題とは異なり、制約条件\(a\cdot x\geq c\)の不等号の向きが逆になっている点に注意してください。ただ、これは以下の最小化問題
$$\begin{array}{cl}\min\limits_{x\in X} & f\left( x\right) \\
s.t. & -\left( a\cdot x\right) \leq -c
\end{array}$$へと言い換え可能であるため、最大点であるための必要条件を特定するためには、ラグランジュ関数を、\begin{equation*}
L\left( x,\lambda \right) =f\left( x\right) +\lambda \left[ -\left( a\cdot
x\right) +c\right] \end{equation*}と定義することになります。このとき、\begin{eqnarray*}
\forall i:\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\quad \because L\text{の定義} \\
&\Leftrightarrow &\nabla f\left( x\right) =\lambda a
\end{eqnarray*}となります。特に、最小点\(x^{\ast }\)が存在する場合には、\begin{equation*}\forall i:\frac{\partial L\left( x^{\ast },\lambda \right) }{\partial x_{i}}=0\Leftrightarrow \nabla f\left( x^{\ast }\right) =\lambda a
\end{equation*}となりますが、これは最小点であるための必要条件です。

 

演習問題

問題(線型不等式制約付き最適化問題)
関数\(f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x_{1},x_{2}\right)\in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}f\left( x_{1},x_{2}\right) =\ln \left( x_{1}\right) +\ln \left( x_{2}\right)
\end{equation*}を定めるものとします。ベクトル\(\left( a_{1},a_{2}\right)\in \mathbb{R} _{++}^{2}\)およびスカラー\(c\in \mathbb{R} _{+}\)から最大化問題
$$\begin{array}{cl}\max\limits_{\left( x_{1}x_{2}\right) \in \mathbb{R} _{++}^{2}} & f\left( x_{1},x_{2}\right) \\
s.t. & a_{1}x_{1}+a_{2}x_{2}\leq c
\end{array}$$
を構成します。この問題の最大点は存在しますか。存在する場合には具体的に求めてください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

RELATED KNOWLEDGE

関連知識

1階の必要条件
1変数関数の最適化のための1階の必要条件

関数が定義域において局所最適解(極大点・極小点)を持つための1階の必要条件を明らかにするとともに、関数の大域的最適解(最小点・最大点)を具体的に求める方法について解説します。

2階の必要条件
1変数凸関数・凹関数の無制約最適化

1変数の凸関数を目的関数とする制約条件のない最小化問題や、1変数の凹関数を目的関数とする制約条件のない最大化問題を解く方法を解説します。

最大値・最小値
多変数関数の大域的最適解

多変数関数の値を最大化するような点が定義域上に存在する場合、そのような点を最大点や大域的最大点と呼びます。また、多変数関数が最大点に対して定める値を最大値や大域的最大値と呼びます。

最大値・最小値
多変数関数の局所最適解

多変数関数の値を最大化するような点が定義域上に存在しない場合でも、変数がとり得る値を限定することにより、その範囲内において関数の値を最大化するような点が存在する状況は起こり得ます。そのような点を極大点や局所的最大点と呼びます。また、関数が極大点に対して定める値を極大値や大域的最大値と呼びます。

1階の必要条件
多変数関数の最適化のための1階の必要条件

多変数関数が定義域において局所最適解(極大点・極小点)を持つための1階の必要条件を明らかにするとともに、関数の大域的最適解(最小点・最大点)を具体的に求める方法について解説します。

凸関数・凹関数
多変数凸関数・凹関数の無制約最適化

多変数の凸関数を目的関数とする制約条件のない最小化問題や、多変数の凹関数を目的関数とする制約条件のない最大化問題を解く方法を解説します。