偏微分を用いた多変数の準凸関数の判定
ユークリッド空間\(\mathbb{R} ^{n}\)もしくはその部分集合を定義域とする多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が準凸関数であることは、定義域\(X\)が凸集合であるとともに、\begin{equation*}\forall x,y\in X,\ \forall \lambda \in \left[ 0,1\right] :f\left( \lambda
x+\left( 1-\lambda \right) y\right) \leq \max \left\{ f\left( x\right)
,f\left( y\right) \right\}
\end{equation*}が成り立つこととして定義されますが、定義にもとづいて関数が準凸であることを示す作業は煩雑になりがちです。多変数関数が偏微分可能である場合、それが準凸関数であることを比較的容易に示すことができます。
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が以下の2つの性質を満たすものとします。1つ目の性質は、\(f\)の定義域\(X\)が非空の凸集合であるとともに\(\mathbb{R} ^{n}\)上の開集合であるということです。2つ目の性質は、\(f\)が\(C^{1}\)級であるということです。つまり、\(f\)は定義域上の任意の点\(x\in X\)において任意の変数\(x_{k}\ \left(k=1,\cdots ,n\right) \)に関して偏微分可能であるとともに、偏導関数\(f_{x_{k}}:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)は連続です。以上の条件を満たす多変数関数\(f\)に関して、それが準凸関数であることを以下のように特徴づけることができます。
\left( y-x\right) \cdot \nabla f\left( x\right) \leq 0\right] \end{equation*}が成り立つことは、\(f\)は準凸関数であるための必要十分条件である。
以上の命題を踏まえると、多変数関数\(f\)が\(C^{2}\)級である場合には、\(f\)が準凸関数であるための必要条件と十分条件をそれぞれ以下のように特定できます。
h=0\Rightarrow h^{t}H_{f}\left( x\right) h\geq 0\right] \end{equation*}が成り立つ。逆に、\begin{equation*}
\forall x\in X,\ \forall h\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} :\left[ \nabla f\left( x\right) \cdot
h=0\Rightarrow h^{t}H_{f}\left( x\right) h>0\right] \end{equation*}が成り立つならば\(f\)は準凸関数である。ただし、\begin{equation*}H_{f}\left( x\right) =\begin{pmatrix}
f_{x_{1}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{1}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{1}x_{n}}^{\prime \prime }\left(
x\right) \\
f_{x_{2}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{2}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{2}x_{n}}^{\prime \prime }\left(
x\right) \\
\vdots & \vdots & \ddots & \vdots \\
f_{x_{n}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{n}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{n}x_{n}}^{\prime \prime }\left(
x\right)
\end{pmatrix}\end{equation*}である。
多変数関数\(f\)が\(C^{2}\)級である場合、そのヘッセ行列\(H_{f}\left( x\right) \)は対称行列になります。制約条件のもとで対称行列が半正定値であることと、その任意の狭義の首座小行列の行列式の値が非負であることは必要十分であるため、先の命題を以下のように言い換えることができます。
A_{k}\left( x\right) \right) \leq 0
\end{equation*}が成り立つ。逆に、\begin{equation*}
\forall x\in X,\ \forall k\in \left\{ 1,\cdots ,n\right\} :\det \left(
A_{k}\left( x\right) \right) <0
\end{equation*}が成り立つならば、\(f\)は準凸関数である。ただし、\(A_{k}\left( x\right) \)は\(f\)の点\(x\)における縁付きヘッセ行列\begin{equation*}D_{f}\left( x\right) =\begin{pmatrix}
0 & f_{x_{1}}^{\prime }\left( x\right) & f_{x_{2}}^{\prime }\left( x\right)
& \cdots & f_{x_{n}}^{\prime }\left( x\right) \\
f_{x_{1}}^{\prime }\left( x\right) & f_{x_{1}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{1}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{1}x_{n}}^{\prime \prime }\left( x\right) \\
f_{x_{2}}^{\prime }\left( x\right) & f_{x_{2}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{2}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{2}x_{n}}^{\prime \prime }\left( x\right) \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
f_{x_{n}}^{\prime }\left( x\right) & f_{x_{n}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{n}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{n}x_{n}}^{\prime \prime }\left( x\right)
\end{pmatrix}\end{equation*}の\(k\)次首座小行列式であり、具体的には、\begin{equation*}A_{k}\left( x\right) =\begin{pmatrix}
0 & f_{x_{1}}^{\prime }\left( x\right) & f_{x_{2}}^{\prime }\left( x\right)
& \cdots & f_{x_{k}}^{\prime }\left( x\right) \\
f_{x_{1}}^{\prime }\left( x\right) & f_{x_{1}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{1}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{1}x_{k}}^{\prime \prime }\left( x\right) \\
f_{x_{2}}^{\prime }\left( x\right) & f_{x_{2}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{2}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{2}x_{k}}^{\prime \prime }\left( x\right) \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
f_{x_{k}}^{\prime }\left( x\right) & f_{x_{k}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{k}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{n}x_{k}}^{\prime \prime }\left( x\right)
\end{pmatrix}\end{equation*}である。
\end{equation*}を定めるものとします。\(f\)は多変数の多項式関数であるため\(C^{2}\)級であり、点\(\left( x,y\right) \in X\)における縁付きヘッセ行列は、\begin{equation*}D_{f}\left( x,y\right) =\begin{pmatrix}
0 & f_{x}\left( x,y\right) & f_{y}\left( x,y\right) \\
f_{x}\left( x,y\right) & f_{xx}\left( x,y\right) & f_{xy}\left( x,y\right)
\\
f_{y}\left( x,y\right) & f_{yx}\left( x,y\right) & f_{yy}\left( x,y\right)
\end{pmatrix}=\begin{pmatrix}
0 & -y & -x \\
-y & 0 & -1 \\
-x & -1 & 0\end{pmatrix}\end{equation*}です。首座小行列式の値は、\begin{eqnarray*}
\det \left( A_{1}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & -y \\
-y & 0\end{pmatrix}=-y^{2} \\
\det \left( A_{2}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & -y & -x \\
-y & 0 & -1 \\
-x & -1 & 0\end{pmatrix}=-2xy
\end{eqnarray*}を満たします。したがって、例えば、\(f\)の定義域が、\begin{equation*}X=\mathbb{R} _{++}^{2}
\end{equation*}である場合には、\begin{eqnarray*}
\det \left( A_{1}\left( x,y\right) \right) &<&0 \\
\det \left( A_{2}\left( x,y\right) \right) &<&0
\end{eqnarray*}が成り立つため、\(f\)は\(\mathbb{R} _{++}^{2}\)上において準凸関数です。一方、\(f\)の定義域が、\begin{equation*}X=\mathbb{R} ^{2}
\end{equation*}である場合、例えば、点\(\left( 1,-1\right) \)において、\begin{equation*}\det \left( A_{2}\left( 1,-1\right) \right) =2>0
\end{equation*}が成り立つため、\(f\)は\(\mathbb{R} ^{2}\)上では準凸関数ではありません。
\end{equation*}を定めるものとします。定義域\(\mathbb{R} ^{2}\)は非空の凸な開集合です。\(f\)は多変数の多項式関数であるため\(C^{2}\)級であり、点\(\left( x,y\right) \in \mathbb{R} ^{2}\)における縁付きヘッセ行列は、\begin{equation*}D_{f}\left( x,y\right) =\begin{pmatrix}
0 & f_{x}\left( x,y\right) & f_{y}\left( x,y\right) \\
f_{x}\left( x,y\right) & f_{xx}\left( x,y\right) & f_{xy}\left( x,y\right)
\\
f_{y}\left( x,y\right) & f_{yx}\left( x,y\right) & f_{yy}\left( x,y\right)
\end{pmatrix}=\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0\end{pmatrix}\end{equation*}です。首座小行列式の値は、\begin{eqnarray*}
\det \left( A_{1}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & 1 \\
1 & 0\end{pmatrix}=-1\leq 0 \\
\det \left( A_{2}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0\end{pmatrix}=0
\end{eqnarray*}となるため、\(f\)は準凸関数であるための必要条件を満たしています。ちなみに、\(f\)は準凸関数です。
偏微分を用いた多変数の準凹関数の判定
多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が準凹関数であることは、定義域\(X\)が凸集合であるとともに、\begin{equation*}\forall x,y\in X,\ \forall \lambda \in \left[ 0,1\right] :\min \left\{
f\left( x\right) ,f\left( y\right) \right\} \leq f\left( \lambda x+\left(
1-\lambda \right) y\right)
\end{equation*}が成り立つこととして定義されますが、準凸関数に関する先の議論と同様の議論を展開することにより、準凹関数に関しても同様の諸命題を導くことができます。
まず、非空の凸な開集合上に定義された\(C^{1}\)級に対して、それが準凹関数であることを以下のように特徴づけることができます。
\left( y-x\right) \cdot \nabla f\left( x\right) \geq 0\right] \end{equation*}が成り立つことは、\(f\)は準凹関数であるための必要十分条件である。
以上の命題を踏まえると、多変数関数\(f\)が\(C^{2}\)級である場合には、\(f\)が準凹関数であるための必要条件と十分条件をそれぞれ以下のように特定できます。
h=0\Rightarrow h^{t}H_{f}\left( x\right) h\leq 0\right] \end{equation*}が成り立つ。逆に、\begin{equation*}
\forall x\in X,\ \forall h\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} :\left[ \nabla f\left( x\right) \cdot
h=0\Rightarrow h^{t}H_{f}\left( x\right) h<0\right] \end{equation*}が成り立つならば\(f\)は準凹関数である。ただし、\begin{equation*}H_{f}\left( x\right) =\begin{pmatrix}
f_{x_{1}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{1}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{1}x_{n}}^{\prime \prime }\left(
x\right) \\
f_{x_{2}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{2}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{2}x_{n}}^{\prime \prime }\left(
x\right) \\
\vdots & \vdots & \ddots & \vdots \\
f_{x_{n}x_{1}}^{\prime \prime }\left( x\right) & f_{x_{n}x_{2}}^{\prime
\prime }\left( x\right) & \cdots & f_{x_{n}x_{n}}^{\prime \prime }\left(
x\right)
\end{pmatrix}\end{equation*}である。
多変数関数\(f\)が\(C^{2}\)級である場合、そのヘッセ行列\(H_{f}\left( x\right) \)は対称行列になります。制約条件のもとで対称行列が半負定値であることと、その第\(k\)次の首座小行列の行列式の値に\(\left( -1\right) ^{k}\)をかけて得られる値が非負であることは必要十分であるため、先の命題を以下のように言い換えることができます。
^{k}\det \left( A_{k}\left( x\right) \right) \geq 0
\end{equation*}が成り立つ。逆に、\begin{equation*}
\forall x\in X,\ \forall k\in \left\{ 1,\cdots ,n\right\} :\left( -1\right)
^{k}\det \left( A_{k}\left( x\right) \right) >0
\end{equation*}が成り立つならば、\(f\)は準凹関数である。ただし、\(A_{k}\left( x\right) \)は\(f\)の点\(x\)における縁付きヘッセ行列\begin{equation*}D_{f}\left( x\right) =\begin{pmatrix}
0 & f_{x_{1}}^{\prime }\left( x\right) & f_{x_{2}}^{\prime }\left( x\right)
& \cdots & f_{x_{n}}^{\prime }\left( x\right) \\
f_{x_{1}}^{\prime }\left( x\right) & f_{x_{1}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{1}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{1}x_{n}}^{\prime \prime }\left( x\right) \\
f_{x_{2}}^{\prime }\left( x\right) & f_{x_{2}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{2}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{2}x_{n}}^{\prime \prime }\left( x\right) \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
f_{x_{n}}^{\prime }\left( x\right) & f_{x_{n}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{n}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{n}x_{n}}^{\prime \prime }\left( x\right)
\end{pmatrix}\end{equation*}の\(k\)次首座小行列式であり、具体的には、\begin{equation*}A_{k}\left( x\right) =\begin{pmatrix}
0 & f_{x_{1}}^{\prime }\left( x\right) & f_{x_{2}}^{\prime }\left( x\right)
& \cdots & f_{x_{k}}^{\prime }\left( x\right) \\
f_{x_{1}}^{\prime }\left( x\right) & f_{x_{1}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{1}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{1}x_{k}}^{\prime \prime }\left( x\right) \\
f_{x_{2}}^{\prime }\left( x\right) & f_{x_{2}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{2}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{2}x_{k}}^{\prime \prime }\left( x\right) \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
f_{x_{k}}^{\prime }\left( x\right) & f_{x_{k}x_{1}}^{\prime \prime }\left(
x\right) & f_{x_{k}x_{2}}^{\prime \prime }\left( x\right) & \cdots &
f_{x_{n}x_{k}}^{\prime \prime }\left( x\right)
\end{pmatrix}\end{equation*}である。
\end{equation*}を定めるものとします。\(f\)は多変数の多項式関数であるため\(C^{2}\)級であり、点\(\left( x,y\right) \in X\)における縁付きヘッセ行列は、\begin{equation*}D_{f}\left( x,y\right) =\begin{pmatrix}
0 & f_{x}\left( x,y\right) & f_{y}\left( x,y\right) \\
f_{x}\left( x,y\right) & f_{xx}\left( x,y\right) & f_{xy}\left( x,y\right)
\\
f_{y}\left( x,y\right) & f_{yx}\left( x,y\right) & f_{yy}\left( x,y\right)
\end{pmatrix}=\begin{pmatrix}
0 & y & x \\
y & 0 & 1 \\
x & 1 & 0\end{pmatrix}\end{equation*}です。首座小行列式の値は、\begin{eqnarray*}
-\det \left( A_{1}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & y \\
y & 0\end{pmatrix}=y^{2} \\
\det \left( A_{2}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & y & x \\
y & 0 & 1 \\
x & 1 & 0\end{pmatrix}=2xy
\end{eqnarray*}を満たします。したがって、例えば、\(f\)の定義域が、\begin{equation*}X=\mathbb{R} _{++}^{2}
\end{equation*}である場合には、\begin{eqnarray*}
-\det \left( A_{1}\left( x,y\right) \right) &>&0 \\
\det \left( A_{2}\left( x,y\right) \right) &>&0
\end{eqnarray*}が成り立つため、\(f\)は\(\mathbb{R} _{++}^{2}\)上において準凹関数です。一方、\(f\)の定義域が、\begin{equation*}X=\mathbb{R} ^{2}
\end{equation*}である場合、例えば、点\(\left( 1,-1\right) \)において、\begin{equation*}\det \left( A_{2}\left( 1,-1\right) \right) =-2<0
\end{equation*}が成り立つため、\(f\)は\(\mathbb{R} ^{2}\)上では準凹関数ではありません。
\end{equation*}を定めるものとします。定義域\(\mathbb{R} ^{2}\)は非空の凸な開集合です。\(f\)は多変数の多項式関数であるため\(C^{2}\)級であり、点\(\left( x,y\right) \in \mathbb{R} ^{2}\)における縁付きヘッセ行列は、\begin{equation*}D_{f}\left( x,y\right) =\begin{pmatrix}
0 & f_{x}\left( x,y\right) & f_{y}\left( x,y\right) \\
f_{x}\left( x,y\right) & f_{xx}\left( x,y\right) & f_{xy}\left( x,y\right)
\\
f_{y}\left( x,y\right) & f_{yx}\left( x,y\right) & f_{yy}\left( x,y\right)
\end{pmatrix}=\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0\end{pmatrix}\end{equation*}です。首座小行列式の値は、\begin{eqnarray*}
-\det \left( A_{1}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & 1 \\
1 & 0\end{pmatrix}=1\geq 0 \\
\det \left( A_{2}\left( x,y\right) \right) &=&\det
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0\end{pmatrix}=0
\end{eqnarray*}となるため、\(f\)は準凹関数であるための必要条件を満たしています。ちなみに、\(f\)は準凹関数です。
演習問題
\end{equation*}を定めるものとします。\(f\)は準凸関数、準凹関数、どちらでもない、のどれでしょうか。
\end{equation*}を定めるものとします。\(f\)は準凸関数、準凹関数、どちらでもない、のどれでしょうか。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】