WIIS

凸最適化・凹最適化

1変数関数の凸最適化問題の解

目次

Twitter
Mailで保存

凸最適化の内点解であるための必要十分条件

目的関数である凸関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)と制約集合である凸集合\(C\subset X\)のもとでの凸最適化問題$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$に解が存在する場合、それはどのような条件を満たすのでしょうか。以下では、制約集合の内点が凸最適化問題の解であるための必要条件と十分条件を特定します。

制約集合の内点\(x_{0}\in C^{i}\)が凸最適化問題の解、すなわち\(C\)における\(f\)の最小点であるものとします。凸関数は定義域の内点において劣勾配を持つため、関数\(f\)の点\(x_{0}\)における劣勾配が存在すること、すなわち劣微分\begin{equation*}\partial f\left( x_{0}\right) =\left\{ c\in \mathbb{R} \ |\ \forall x\in I:f\left( x\right) -f\left( x_{0}\right) \geq c\left(
x-x_{0}\right) \right\}
\end{equation*}が非空であることが保証されますが、以上の条件のもとでは、\begin{equation*}
0\in \partial f\left( x_{0}\right)
\end{equation*}が成り立つこと、すなわち\(0\)が点\(x_{0}\)における劣勾配であることが保証されます。凸最適化問題の内点解\(x_{0}\)における劣勾配の中には\(0\)が必ず存在するということです。

命題(凸最適化の内点解であるための必要条件)
凸関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)および凸集合\(C\subset X\)のもとでの凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられたとき、制約集合の内点\(x_{0}\in C^{i}\)が先の問題の解であるならば、\begin{equation*}0\in \partial f\left( x_{0}\right)
\end{equation*}が成り立つ。

証明

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

実は、上の命題の逆もまた成立します。つまり、制約集合の内点\(x_{0}\in C^{i}\)における凸関数\(f\)の劣勾配の中に\(0\)が存在する場合、その内点\(x_{0}\)は凸最適化問題の解であることが保証されます。

命題(凸最適化の内点解であるための十分条件)
凸関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)および凸集合\(C\subset X\)のもとでの凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられたとき、制約集合の内点\(x_{0}\in C^{i}\)について、\begin{equation*}0\in \partial f\left( x_{0}\right)
\end{equation*}が成り立つならば、この内点\(x_{0}\)は先の問題の解である。
証明

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

以上の2つの命題により、凸最適問題に関しては、制約集合の内点における目的関数の劣勾配の中に\(0\)が存在することと、その内点が凸最適問題の解であることが必要十分であることが明らかになりました。

命題(凸最適化の内点解であるための必要十分条件)
凸関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)および凸集合\(C\subset X\)のもとでの凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられたとき、制約集合の内点\(x_{0}\in C^{i}\)について、\begin{equation*}0\in \partial f\left( x_{0}\right)
\end{equation*}が成り立つことは、この内点\(x_{0}\)が先の問題の解であるための必要十分条件である。

この命題では目的関数が微分可能であることを要求していません。つまり、目的関数である凸関数が微分可能でない場合においても、上の命題を用いて内点解を特定できるということです。以下が具体例です。

例(凸最適化問題の内点解)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =\left\vert x\right\vert
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} \)は\(\mathbb{R} \)自身の部分集合であり、さらに\(\mathbb{R} \)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}
\end{array}$$を構成できます。点\(x_{0}\in \mathbb{R} \)を任意に選びます。\(\mathbb{R} \)は開集合であるため\(x_{0}\)は\(\mathbb{R} \)の内点です。この関数\(f\)のそれぞれの内点\(x_{0}\in \mathbb{R} \)における劣微分は、\begin{equation*}\partial f\left( x_{0}\right) =\left\{
\begin{array}{cc}
\left\{ 1\right\} & \left( if\ x_{0}>0\right) \\
\left[ -1,1\right] & \left( if\ x_{0}=0\right) \\
\left\{ -1\right\} & \left( if\ x_{0}<0\right)
\end{array}\right.
\end{equation*}であるため、\begin{equation*}
0\in \partial f\left( 0\right)
\end{equation*}が成り立ちます。したがって、先の命題より、この凸最適化問題の解は点\(0\)であり、\(f\)の最小値は\(f\left( 0\right) =0\)です。

 

目的関数が微分可能である場合の凸最適化の内点解であるための必要十分条件

先の例が示唆するように、劣微分を用いた凸最適化の内点解であるための必要十分条件は、目的関数が微分可能ではない場合にも適用可能です。一方、関数が微分可能である場合、劣微分と微分係数は概念として一致するため以下の命題を得ます。つまり、凸最適化問題において、最小化のための1階の必要条件は十分条件でもあるということです。

命題(目的関数が微分可能である場合の凸最適化の内点解であるための必要十分条件)
凸関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)および凸集合\(C\subset X\)のもとでの凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられたとき、目的関数\(f\)が制約集合の内点\(x_{0}\in C^{i}\)において微分可能である場合、\begin{equation*}f^{\prime }\left( x_{0}\right) =0
\end{equation*}が成り立つことは、この内点\(x_{0}\)が先の問題の解であるための必要十分条件である。
証明

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

例(凸最適化問題の内点解)
関数\(f:\mathbb{R} _{++}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}\)に対して、\begin{equation*}f\left( x\right) =x\ln \left( x\right)
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} _{++}\)は\(\mathbb{R} _{++}\)自身の部分集合であり、さらに\(\mathbb{R} _{++}\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}_{++}
\end{array}$$を構成できます。点\(x_{0}\in \mathbb{R} _{++}\)を任意に選びます。\(\mathbb{R} _{++}\)は開集合であるため\(x_{0}\)は\(\mathbb{R} _{++}\)の内点です。この関数\(f\)は微分可能であり、導関数\(f^{\prime }:\mathbb{R} _{++}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}\)に対して、\begin{equation*}f^{\prime }\left( x\right) =\ln \left( x\right) +1
\end{equation*}を定めます。\begin{equation*}
f^{\prime }\left( x\right) =0
\end{equation*}すなわち、\begin{equation*}
\ln \left( x\right) +1=0
\end{equation*}を解くと、\begin{equation*}
x=e^{-1}
\end{equation*}を得るため、先の命題より、この凸最適化問題の解は点\(e^{-1}\)であり、\(f\)の最小値は\(f\left(e^{-1}\right) =-e^{-1}\)です。

 

凸最適化問題の解

凸最適化問題の制約集合の内点が問題の解であるための必要十分条件が明らかになりました。これは必要十分条件であるため、条件を満たす内点が存在する場合には、それは凸最適化問題の解であることが保証されます。では、条件を満たす内点が存在しない場合には、凸最適化問題に解は存在しないとまで言えるのでしょうか。制約集合が開集合である場合、その任意の点は制約集合の内点であるため、条件を満たす内点が存在しない場合には、凸最適化問題には解は存在しないことが確定します。一方、制約集合が開集合ではない場合、すなわち、制約集合がその境界点を要素として持つ場合には、凸最適化問題に端点解が存在する可能性が残されています。以上を踏まえると、凸最適化問題の解について以下のように整理できます。

  1. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在する場合、それは凸最適化問題の解であることが保証される。しかも、他に解は存在しない。
  2. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在せず、しかも制約集合が開集合である場合、凸最適化問題には解は存在しない。
  3. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在せず、しかも制約集合が開集合ではない場合、凸最適化問題には端点解が存在する可能性がある。
例(解が存在しない場合)
関数\(f:\mathbb{R} _{++}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}\)に対して、\begin{equation*}f\left( x\right) =\frac{1}{x}
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} _{++}\)は\(\mathbb{R} _{++}\)自身の部分集合であり、さらに\(\mathbb{R} _{++}\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}_{++}
\end{array}$$を構成できます。点\(x_{0}\in \mathbb{R} _{++}\)を任意に選びます。\(\mathbb{R} _{++}\)は開集合であるため\(x_{0}\)は\(\mathbb{R} _{++}\)の内点です。この関数\(f\)は微分可能であり、導関数\(f^{\prime }:\mathbb{R} _{++}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}\)に対して、\begin{equation*}f^{\prime }\left( x\right) =-\frac{1}{x^{2}}
\end{equation*}を定めますが、\begin{equation*}
f^{\prime }\left( x\right) =0
\end{equation*}すなわち、\begin{equation*}
-\frac{1}{x^{2}}=0
\end{equation*}を満たす点\(x\)は制約集合\(\mathbb{R} _{++}\)に存在しないため、この凸最適化問題に内点解は存在しません。加えて、この制約集合\(\mathbb{R} _{++}\)は開集合であるため、この凸最適化問題に端点解も存在せず、したがって解は存在しません。
例(端点解が存在する場合)
関数\(f:\mathbb{R} _{++}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}\)に対して、\begin{equation*}f\left( x\right) =\frac{1}{x}
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\((0,1]\)は\(\mathbb{R} _{++}\)の部分集合であり、さらに\((0,1]\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in (0,1] \end{array}$$を構成できます。先と同様の議論より、制約集合の内部\(\left( 0,1\right) \)には凸最適化のための必要十分条件を満たす内点は存在しないため、この凸最適化問題に内点解は存在しません。その一方で、制約集合\((0,1]\)は開集合ではなく、境界点\(1\)を要素として持ちます。さらに、任意の\(x\in (0,1]\)に対して、\begin{equation*}\frac{1}{x}\geq 1=f\left( 1\right)
\end{equation*}が成り立つため、この凸最適化問題には端点解\(1\)が存在し、\(f\)の最小値は\(f\left( 1\right) =1\)です。

 

演習問題

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

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}
\end{array}$$の解を求めてください。

解答を見る

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

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

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \left[ 0,1\right] \end{array}$$の解を求めてください。

解答を見る

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

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

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}
\end{array}$$の解を求めてください。

証明

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

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

$$\begin{array}{cl}\min & f\left( x\right) \\
s.t. & x\in \mathbb{R}
\end{array}$$の解を求めてください。

証明

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

Twitter
Mailで保存

質問とコメント

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

関連知識

1変数の凸関数・凹関数

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

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

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

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

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

多変数の凸関数・凹関数

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

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

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

凸関数・凹関数の定数倍

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

凸関数・凹関数の和

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

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

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

凸関数・凹関数の逆関数

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

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

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