WIIS

凸最適化・凹最適化

多変数関数の凸最適化・凹最適化

目次

Twitter
Mailで保存

多変数関数の凸最適化

多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、\(f\left( x\right) \)の値を最小化するような点\(a\)が\(f\)の定義域\(X\)上に存在する場合には、すなわち、\begin{equation*}\exists a\in X,\ \forall x\in X:f\left( a\right) \leq f\left( x\right)
\end{equation*}が成り立つ場合には、このような点\(a\)を\(f\)の\(X\)における最小点(minimum point)や大域的最小点(global minimum point)もしくは絶対的最小点(absolute maximum point)などと呼びます。また、\(f\)の\(X\)における最小点\(a\)が存在する場合、\(f\)が点\(a\)に対して定める値\(f\left( a\right) \)を\(f\)の\(X\)における最小値(minimum value)や大域的最小値(global minimum value)もしくは絶対的最小値(absolute minimum value)などと呼び、これを、\begin{equation*}\min_{x\in X}f\left( x\right)
\end{equation*}で表記します。

関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の値域は、\begin{equation*}f\left( X\right) =\left\{ f\left( x\right) \in \mathbb{R} \ |\ x\in X\right\}
\end{equation*}と定義される\(\mathbb{R} \)の部分集合ですが、これと関数\(f\)の最小値の間には、\begin{equation*}\min_{x\in X}f\left( x\right) =\min f\left( X\right)
\end{equation*}という関係が成り立ちます。つまり、\(f\)の\(X\)における最小値は\(f\)の値域の最小値と一致します。一般に、\(\mathbb{R} \)の非空な部分集合は最小値を持つとは限りませんが、存在する場合には必ず1つの実数として定まります。したがって、\(\min f\left( X\right) \)やそれと一致する\(\min\_{x\in X}f\left( x\right) \)もまた存在するとは限らない一方、存在する場合には必ず1つの実数として定まります。

関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が\(X\)において最小値をとらない場合には、\(f\)の\(X\)における最小点は存在しません。また、関数\(f\)が\(X\)において最小値をとる場合、その最小値は1つの実数として定まる一方、最小点は一意的であるとは限りません。つまり、異なる点\(a,a^{\prime }\in X\)について、\begin{equation*}\min_{x\in X}f\left( x\right) =f\left( a\right) =f\left( a^{\prime }\right)
\end{equation*}が成り立つ状況が起こり得るということです。以上を踏まえた上で、\(f\)の\(X\)における最小点からなる集合を、\begin{equation*}\underset{x\in X}{\mathrm{argmin}}f\left( x\right) =\left\{ a\in X\ |\ f\left(
a\right) =\min_{x\in X}f\left( x\right) \right\}
\end{equation*}で表記します。

凸集合上に定義された凸関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられているものとします。関数\(f\)の定義域の部分集合であるような凸集合\(C\subset X\)が与えられたとき、\(f\)の変数\(x\)がとり得る値の範囲を\(C\)に制限した場合の\(f\)の最小点\begin{equation*}\underset{x\in C}{\mathrm{argmin}}f\left( x\right)
\end{equation*}を特定する問題を凸最適化(convex optimization)や凸計画問題(convex programming)など呼び、これを、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$で表記します。集合\(C\)を制約集合(constraint set)と呼び、凸最適化において最小化する対象となる関数\(f\)を目的関数(objective function)と呼びます。つまり、凸最適化とは制約集合が凸集合であり、目的関数が凸関数であるような制約条件付き最小化問題のことです。

例(凸最適化)
凸関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の定義域\(X\)は凸集合であるため、以下の最小化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in X
\end{array}$$は凸最適化です。

例(凸最適化)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =x^{2}+y^{2}
\end{equation*}を定めるものとします。\(f\)は凸関数です。\(a<b\)かつ\(c<d\)を満たす実数\(a,b,c,d\in \mathbb{R} \)から定義される以下の集合\begin{equation*}\left[ a,b\right] \times \left[ c,d\right] \end{equation*}は\(\mathbb{R} ^{2}\)上の凸集合であるため、以下の最小化問題
$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \left[ a,b\right] \times \left[ c,d\right] \end{array}$$は凸最適化です。これを、

$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & a\leq x\leq b \\
& c\leq y\leq d
\end{array}$$と表記することもできます。

例(凸最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凸関数であるものとします。凸関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c\in \mathbb{R} \)に関する下位集合\begin{equation*}L\left( c\right) =\left\{ x\in X\ |\ g\left( x\right) \leq c\right\}
\end{equation*}は凸集合であるため、以下の最小化問題

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in L\left( c\right)
\end{array}$$は凸最適化です。これを、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & g\left( x\right) \leq c \\
& x\in X
\end{array}$$と表記することもできます。

例(凸最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凸関数であるものとします。凹関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c\in \mathbb{R} \)に関する上位集合\begin{equation*}U\left( c\right) =\left\{ x\in X\ |\ g\left( x\right) \geq c\right\}
\end{equation*}は凸集合であるため、以下の最小化問題

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in U\left( c\right)
\end{array}$$は凸最適化です。これを、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & g\left( x\right) \geq c \\
& x\in X
\end{array}$$と表記することもできます。

例(凸最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凸関数であるものとします。2つの凸関数\(g_{1},g_{2}:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c_{1},c_{2}\in \mathbb{R} \)に関する下位集合\begin{eqnarray*}L\left( c_{1}\right) &=&\left\{ x\in X\ |\ g_{1}\left( x\right) \leq
c_{1}\right\} \\
L\left( c_{2}\right) &=&\left\{ x\in X\ |\ g_{2}\left( x\right) \leq
c_{2}\right\}
\end{eqnarray*}はともに凸集合です。凸集合どうしの共通部分は凸集合であるため、以下の最小化問題

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in L\left( c_{1}\right) \wedge L\left( c_{2}\right)
\end{array}$$は凸最適化です。これを、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & g_{1}\left( x\right) \leq c_{1} \\
& g_{2}\left( x\right) \leq c_{2} \\
& x\in X
\end{array}$$と表記することもできます。

例(凸最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凸関数であるものとします。線型関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、線型関数は凸関数かつ凹関数であるため、実数\(c\in \mathbb{R} \)に関する上位集合と下位集合\begin{eqnarray*}U\left( c\right) &=&\left\{ x\in X\ |\ g\left( x\right) \geq c\right\} \\
L\left( c\right) &=&\left\{ x\in X\ |\ g\left( x\right) \leq c\right\}
\end{eqnarray*}はともに凸集合です。凸集合どうしの共通部分は凸集合であるため、以下の最小化問題

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in U\left( c\right) \wedge L\left( c\right)
\end{array}$$は凸最適化です。これを、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & g\left( x\right) \geq c \\
& g\left( x\right) \leq c \\
& x\in X
\end{array}$$すなわち、

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & g\left( x\right) =c \\
& x\in X
\end{array}$$と表記することもできます。

 

多変数関数の凹最適化

多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、\(f\left( x\right) \)の値を最大化するような点\(a\)が定義域\(X\)上に存在する場合には、すなわち、\begin{equation*}\exists a\in X,\ \forall x\in X:f\left( a\right) \geq f\left( x\right)
\end{equation*}が成り立つ場合には、このような点\(a\)を\(f\)の\(X\)における最大点(maximum point)や大域的最大点(global maximum point)もしくは絶対的最大点(absolute maximum point)などと呼びます。また、\(f\)の\(X\)における最大点\(a\)が存在する場合、\(f\)が点\(a\)に対して定める値\(f\left( a\right) \)を\(f\)の\(X\)における最大値(maximum value)や大域的最大値(global maximum value)もしくは絶対的最大値(absolute maximum value)などと呼び、これを、\begin{equation*}\max_{x\in X}f\left( x\right)
\end{equation*}で表記します。

関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の値域は、\begin{equation*}f\left( X\right) =\left\{ f\left( x\right) \in \mathbb{R} \ |\ x\in X\right\}
\end{equation*}と定義される\(\mathbb{R} \)の部分集合ですが、これと関数\(f\)の最大値の間には、\begin{equation*}\max_{x\in X}f\left( x\right) =\max f\left( X\right)
\end{equation*}という関係が成り立ちます。つまり、\(f\)の\(X\)における最大値は\(f\)の値域の最大値と一致します。一般に、\(\mathbb{R} \)の非空な部分集合は最大値を持つとは限りませんが、存在する場合には必ず1つの実数として定まります。したがって、\(\max f\left( X\right) \)やそれと一致する\(\max\_{x\in X}f\left( x\right) \)もまた存在するとは限らない一方、存在する場合には必ず1つの実数として定まります。

関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が\(X\)において最大値をとらない場合には、\(f\)の\(X\)における最大点は存在しません。また、関数\(f\)が\(X\)において最大値をとる場合、その最大値は1つの実数として定まる一方、最大点は一意的であるとは限りません。つまり、異なる点\(a,a^{\prime }\in X\)に対して、\begin{equation*}\max_{x\in X}f\left( x\right) =f\left( a\right) =f\left( a^{\prime }\right)
\end{equation*}が成り立つ状況が起こり得るということです。以上を踏まえた上で、\(f\)の\(X\)における最大点からなる集合を、\begin{equation*}\underset{x\in X}{\mathrm{argmax}}f\left( x\right) =\left\{ a\in X\ |\
f\left( a\right) =\max_{x\in X}f\left( x\right) \right\}
\end{equation*}で表記します。

凸集合上に定義された凹関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられているものとします。関数\(f\)の定義域の部分集合であるような凸集合\(C\subset X\)が与えられたとき、\(f\)の変数\(x\)がとり得る値の範囲を\(C\)に制限した場合の\(f\)の最大点\begin{equation*}\underset{x\in C}{\mathrm{argmax}}f\left( x\right)
\end{equation*}を特定する問題を凹最適化(concave optimization)や凹計画問題(concave programming)など呼び、これを、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in C
\end{array}$$で表記します。集合\(C\)を制約集合(constraint set)と呼び、凹最適化において最小化する対象となる関数\(f\)を目的関数(objective function)と呼びます。つまり、凹最適化とは制約集合が凸集合であり、目的関数が凹関数であるような制約条件付き最大化問題のことです。

例(凹最適化)
凹関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の定義域\(X\)は凸集合であるため、以下の最大化問題
$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in X
\end{array}$$は凹最適化です。

例(凹最適化)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =-x^{2}-y^{2}
\end{equation*}を定めるものとします。\(f\)は凹関数です。\(a<b\)かつ\(c<d\)を満たす実数\(a,b,c,d\in \mathbb{R} \)から定義される以下の集合\begin{equation*}\left[ a,b\right] \times \left[ c,d\right] \end{equation*}は\(\mathbb{R} ^{2}\)上の凸集合であるため、以下の最大化問題
$$\begin{array}{cl}\max & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \left[ a,b\right] \times \left[ c,d\right] \end{array}$$は凹最適化です。これを、

$$\begin{array}{cl}\max & f\left( x,y\right) \\
s.t. & a\leq x\leq b \\
& c\leq y\leq d
\end{array}$$と表記することもできます。

例(凹最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凹関数であるものとします。凹関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c\in \mathbb{R} \)に関する上位集合\begin{equation*}U\left( c\right) =\left\{ x\in X\ |\ g\left( x\right) \geq c\right\}
\end{equation*}は凸集合であるため、以下の最大化問題

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in U\left( c\right)
\end{array}$$は凹最適化です。これを、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & g\left( x\right) \geq c \\
& x\in X
\end{array}$$と表記することもできます。

例(凹最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凹関数であるものとします。凸関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c\in \mathbb{R} \)に関する下位集合\begin{equation*}L\left( c\right) =\left\{ x\in X\ |\ g\left( x\right) \leq c\right\}
\end{equation*}は凸集合であるため、以下の最大化問題

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in L\left( c\right)
\end{array}$$は凹最適化です。これを、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & g\left( x\right) \leq c \\
& x\in X
\end{array}$$と表記することもできます。

例(凹最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凹関数であるものとします。2つの凹関数\(g_{1},g_{2}:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、実数\(c_{1},c_{2}\in \mathbb{R} \)に関する上位集合\begin{eqnarray*}U\left( c_{1}\right) &=&\left\{ x\in X\ |\ g_{1}\left( x\right) \geq
c_{1}\right\} \\
U\left( c_{2}\right) &=&\left\{ x\in X\ |\ g_{2}\left( x\right) \geq
c_{2}\right\}
\end{eqnarray*}はともに凸集合です。凸集合どうしの共通部分は凸集合であるため、以下の最大化問題

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in U\left( c_{1}\right) \wedge U\left( c_{2}\right)
\end{array}$$は凹最適化です。これを、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & g_{1}\left( x\right) \geq c_{1} \\
& g_{2}\left( x\right) \geq c_{2} \\
& x\in X
\end{array}$$と表記することもできます。

例(凹最適化)
凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凹関数であるものとします。線型関数\(g:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が与えられたとき、線型関数は凸関数かつ凹関数であるため、実数\(c\in \mathbb{R} \)に関する上位集合と下位集合\begin{eqnarray*}U\left( c\right) &=&\left\{ x\in X\ |\ g\left( x\right) \geq c\right\} \\
L\left( c\right) &=&\left\{ x\in X\ |\ g\left( x\right) \leq c\right\}
\end{eqnarray*}はともに凸集合です。凸集合どうしの共通部分は凸集合であるため、以下の最大化問題

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in U\left( c\right) \wedge L\left( c\right)
\end{array}$$は凹最適化です。これを、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & g\left( x\right) \geq c \\
& g\left( x\right) \leq c \\
& x\in X
\end{array}$$すなわち、

$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & g\left( x\right) =c \\
& x\in X
\end{array}$$と表記することもできます。

 

演習問題

問題(凸最適化問題)
関数\(f:\mathbb{R} ^{3}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y,z\right) \in \mathbb{R} ^{3}\)に対して、\begin{equation*}f\left( x,y,z\right) =x^{2}+2y^{2}+3z^{2}+2xy+2xz
\end{equation*}を定めるものとします。以下の最小化問題

$$\begin{array}{cl}\min & f\left( x,y,z\right) \\
s.t. & \left( x,y,z\right) \in \mathbb{R} ^{3}
\end{array}$$が凸最適化問題であることを確認してください。

証明

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

問題(凸最適化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =e^{x}+e^{y}
\end{equation*}を定めるものとします。以下の最小化問題

$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \left[ 0,1\right] \times \left[ 0,1\right] \end{array}$$が凸最適化問題であることを確認してください。

証明

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

問題(凸最適化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =x+2y+3
\end{equation*}を定めるものとします。以下の最小化問題

$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \mathbb{R} ^{2}
\end{array}$$が凸最適化問題であることを確認してください。

証明

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

問題(凸最適化問題)
関数\(f:\mathbb{R} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =\left\vert x\right\vert +\left\vert y\right\vert
\end{equation*}を定めるものとします。以下の最小化問題

$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \mathbb{R} ^{2}
\end{array}$$が凸最適化問題であることを確認してください。

解答を見る

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

Twitter
Mailで保存

質問とコメント

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

関連知識

1変数の凸関数・凹関数

定義域が区間であるとともに、そのグラフが直線もしくは谷型の曲線になるような関数を凸関数と呼び、グラフが直線もしくは山型の曲線になるような関数を凹関数と呼びます。

微分を用いた1変数の凸関数・凹関数の判定

微分可能な関数が凸関数であることは、導関数が単調増加関数であることと必要十分です。また、微分可能な関数が凹関数であることは、導関数が単調減少関数であることと必要十分です。

1変数の狭義凸関数・狭義凹関数

定義域が区間であるとともに、そのグラフが谷型の曲線になるような関数を狭義凸関数と呼び、グラフが山型の曲線になるような関数を狭義凹関数と呼びます。

多変数の凸関数・凹関数

定義域がユークリッド空間上の凸集合であるとともに、そのグラフが平面もしくは下に凸であるような関数を凸関数と呼びます。また、グラフが平面もしくは上に凸であるよう関数を凹関数と呼びます。

多変数の狭義凸関数・狭義凹関数

定義域がユークリッド空間上の凸集合であるとともに、そのグラフが下に凸であるような関数を狭義凸関数と呼びます。また、グラフが上に凸であるよう関数を狭義凹関数と呼びます。

凸関数・凹関数の定数倍

凸関数の正の定数倍として定義される関数は凸関数であり、凹関数の正の定数倍として定義される関数は凹関数です。

凸関数・凹関数の和

凸関数どうしの和として定義される関数は凸関数であり、凹関数どうしの和として定義される関数は凹関数です。

凸関数・凹関数の合成関数

凸関数どうしの合成関数が凸関数になるための条件、凹関数どうしの合成関数が凹関数になるための条件、凸関数と凹関数の合成関数が凸関数ないし凹関数になるための条件などを明らかにします。

凸関数・凹関数の逆関数

凸関数や凹関数の逆関数が存在する場合、その逆関数もまた凸関数や凹関数になるための条件を明らかにします。

アロー・プラットの絶対的リスク回避度

アロー・プラットの絶対的リスク回避度の符号を通じて主体のリスク選好(リスク回避的・中立的・愛好的)を判定できます。また、絶対的リスク回避度の値を通じてリスク回避の度合いを比較できます。