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

多変数関数の凸最適化

多変数関数\(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} \)が与えられたとき、\(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）と呼びます。つまり、凹最適化とは制約集合が凸集合であり、目的関数が凹関数であるような制約条件付き最大化問題のことです。

演習問題