下位集合を用いた多変数の準凸関数の判定
ユークリッド空間\(\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\)が\(C^{1}\)級である場合、\begin{equation*}\forall x,y\in X:\left[ f\left( y\right) \leq f\left( x\right) \Rightarrow
\left( y-x\right) \cdot \nabla f\left( x\right) \leq 0\right]
\end{equation*}が成り立つことは、\(f\)は準凸関数であるための必要十分条件です。では、関数\(f\)が偏微分可能でない場合、\(f\)が準凸関数であることを簡単に判定する方法はあるのでしょうか。
関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)が与えられたとき、\(f\left( x\right) \)の値がある実数\(c\in \mathbb{R} \)以下になるような定義域の点\(x\in X\)からなる集合を、\begin{equation*}L\left( c\right) =\left\{ x\in X\ |\ f\left( x\right) \leq c\right\}
\end{equation*}で表記し、これを\(f\)の\(c\)に関する下位集合（lower level set）や劣位集合（sublevel set）などと呼びます。
x_{1},x_{2}\right) \leq c\right\}
\end{equation*}となります。
x_{1},x_{2},x_{3}\right) \leq c\right\}
\end{equation*}となります。
関数\(f\)が準凸関数であることは、任意の実数\(c\)に関する\(f\)の下位集合\(L\left( c\right) \)が凸集合であることとして特徴づけられます。ちなみに、ある値\(c\)に対する下位集合\(L\left( c\right) \)が空集合であるような状況は起こり得ますが、空集合は凸集合であるためそのような値\(c\)は問題になりません。
\end{equation*}が凸集合であることは、\(f\)が準凸関数であるための必要十分条件である。
\end{equation*}を定めるものとします。\(f\)の定義域\(\mathbb{R} _{+}^{2}\)は凸集合です。実数\(c\in \mathbb{R} \)を任意に選んだとき、\begin{eqnarray*}L\left( c\right) &=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ f\left( x,y\right) \leq c\right\} \quad \because \text{下位集合の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ x^{2}+y^{2}\leq c\right\} \quad \because f\text{の定義}
\end{eqnarray*}となります。\(c>0\)の場合、\(L\left( c\right) \)は原点を中心とする円盤であるため凸集合です。\(c=0\)の場合には、\begin{equation*}L\left( 0\right) =\left\{ \left( 0,0\right) \right\}
\end{equation*}ですが、1点集合は凸集合であるため\(L\left( 0\right) \)は凸集合です。\(c<0\)の場合には、\begin{equation*}L\left( c\right) =\phi
\end{equation*}ですが、空集合は凸集合であるため\(L\left( c\right) \)は凸集合です。したがって\(f\)は準凸関数です。
先の命題は関数が準凸であるための必要十分条件を与えているため、関数が準凸ではないことを証明する際にも利用できます。具体的には、凸集合上に定義された多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、少なくとも1つの実数\(c\in \mathbb{R} \)に関する下位集合\begin{equation*}L\left( c\right) =\left\{ x\in X\ |\ f\left( x\right) \leq c\right\}
\end{equation*}が凸集合ではない場合、\(f\)は準凸関数ではありません。
\end{equation*}を定めるものとします。\(f\)の定義域\(\mathbb{R} _{+}^{2}\)は凸集合です。実数\(-1\in \mathbb{R} \)について、\begin{eqnarray*}L\left( -1\right) &=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ f\left( x,y\right) \leq -1\right\} \quad \because \text{下位集合の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ -x^{2}-y^{2}\leq -1\right\} \quad \because f\text{の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ x^{2}+y^{2}\geq 1\right\}
\end{eqnarray*}となりますが、これは凸集合ではないため\(f\)は準凸関数ではありません。
上位集合を用いた多変数の準凹関数の判定
ユークリッド空間\(\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] :\min \left\{
f\left( x\right) ,f\left( y\right) \right\} \leq f\left( \lambda x+\left(
1-\lambda \right) y\right)
\end{equation*}が成り立つこととして定義されますが、定義にもとづいて関数が準凹であることを示す作業は煩雑になりがちです。ただし、凸集合上に定義された関数\(f\)が\(C^{1}\)級である場合、\begin{equation*}\forall x,y\in X:\left[ f\left( y\right) \geq f\left( x\right) \Rightarrow
\left( y-x\right) \cdot \nabla f\left( x\right) \geq 0\right]
\end{equation*}が成り立つことは、\(f\)は準凹関数であるための必要十分条件です。では、関数\(f\)が偏微分可能でない場合、\(f\)が準凹関数であることを簡単に判定する方法はあるのでしょうか。
関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)が与えられたとき、\(f\left( x\right) \)の値がある実数\(c\in \mathbb{R} \)以上になるような定義域の点\(x\in X\)からなる集合を、\begin{equation*}U\left( c\right) =\left\{ x\in X\ |\ f\left( x\right) \geq c\right\}
\end{equation*}で表記し、これを\(f\)の\(c\)に関する上位集合（upper level set）や優位集合（superlevel set）などと呼びます。
x_{1},x_{2}\right) \geq c\right\}
\end{equation*}となります。
x_{1},x_{2},x_{3}\right) \geq c\right\}
\end{equation*}となります。
関数\(f\)が準凹関数であることは、任意の実数\(c\)に関する\(f\)の上位集合\(U\left( c\right) \)が凸集合であることとして特徴づけられます。ちなみに、ある値\(c\)に対する上位集合\(U\left( c\right) \)が空集合であるような状況は起こり得ますが、空集合は凸集合であるためそのような値\(c\)は問題になりません。
\end{equation*}が凸集合であることは、\(f\)が準凹関数であるための必要十分条件である。
\end{equation*}を定めるものとします。\(f\)の定義域\(\mathbb{R} _{+}^{2}\)は凸集合です。実数\(c\in \mathbb{R} \)を任意に選んだとき、\begin{eqnarray*}U\left( c\right) &=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ f\left( x,y\right) \geq c\right\} \quad \because \text{下位集合の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ -x^{2}-y^{2}\geq c\right\} \quad \because f\text{の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ x^{2}+y^{2}\leq -c\right\}
\end{eqnarray*}となります。\(c<0\)の場合、\(U\left( c\right) \)は原点を中心とする円盤であるため凸集合です。\(c=0\)の場合には、\begin{equation*}U\left( 0\right) =\left\{ \left( 0,0\right) \right\}
\end{equation*}ですが、1点集合は凸集合であるため\(U\left( 0\right) \)は凸集合です。\(c>0\)の場合には、\begin{equation*}U\left( c\right) =\phi
\end{equation*}ですが、空集合は凸集合であるため\(U\left( c\right) \)は凸集合です。したがって\(f\)は準凹関数です。
先の命題は関数が準凹であるための必要十分条件を与えているため、関数が準凹ではないことを証明する際にも利用できます。具体的には、凸集合上に定義された多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、少なくとも1つの実数\(c\in \mathbb{R} \)に関する上位集合\begin{equation*}U\left( c\right) =\left\{ x\in X\ |\ f\left( x\right) \geq c\right\}
\end{equation*}が凸集合ではない場合、\(f\)は準凹関数ではありません。
\end{equation*}を定めるものとします。\(f\)の定義域\(\mathbb{R} _{+}^{2}\)は凸集合です。実数\(1\in \mathbb{R} \)について、\begin{eqnarray*}U\left( 1\right) &=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ f\left( x,y\right) \geq 1\right\} \quad \because \text{上位集合の定義} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} _{+}^{2}\ |\ x^{2}+y^{2}\geq 1\right\} \quad \because f\text{の定義}
\end{eqnarray*}となりますが、これは凸集合ではないため\(f\)は準凸関数ではありません。
演習問題
\end{equation*}を定めるものとします。\(f\)が準凸関数であることを示してください。
\end{equation*}を定めるものとします。\(f\)が準凹関数ではないことを示してください。
