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

凸最適化・凹最適化

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

目次

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で保存

質問とコメント