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

凸最適化・凹最適化

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

目次

Twitter
Mailで保存

凹最適化問題と凸最適化問題の関係

目的関数である凹関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)と制約集合である凸集合\(C\subset X\)のもとでの凹最適化問題
$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられているものとします。この凹最適化問題の目的関数である凹関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)が与えられたとき、それぞれの\(x\in X\)に対して、\begin{equation*}\left( -f\right) \left( x\right) =-f\left( x\right)
\end{equation*}を定める関数\(-f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)を定義した上で、以下の最小化問題
$$\begin{array}{cl}\min & \left( -f\right) \left( x\right) \\
s.t. & x\in C
\end{array}$$を定義します。

関数\(f\)が凹関数であることと関数\(-f\)が凸関数であることは必要十分であるため、上の最小化問題は凸最適化問題です。加えて、点\(x^{\ast }\in \mathbb{R} \)を任意に選んだとき、\begin{eqnarray*}\forall x\in C:f\left( x^{\ast }\right) \geq f\left( x\right)
&\Leftrightarrow &\forall x\in C:-f\left( x^{\ast }\right) \leq -f\left(
x\right) \\
&\Leftrightarrow &\forall x\in C:\left( -f\right) \left( x^{\ast }\right)
\leq \left( -f\right) \left( x\right)
\end{eqnarray*}という関係が成り立つため、点\(x^{\ast }\)が先の凹最適化問題の解であることと、この点\(x^{\ast }\)が先の凸最適化問題の解であることは必要十分であるため、以上の2つの問題は実質的に等しいことが明らかになりました。つまり、凹最適化問題を凸最適化問題として考えることができるため、凸最適化問題について成り立つ性質がそのまま凹最適化問題についても成立するということです。以下ではこの事実を利用して諸々の命題を証明します。

 

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

目的関数である凹関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)と制約集合である凸集合\(C\subset X\)のもとでの凹最適化問題
$$\begin{array}{cl}\max & f\left( x\right) \\
s.t. & x\in C
\end{array}$$が与えられているものとします。この問題に解が存在する場合、それはどのような条件を満たすのでしょうか。

凹関数は定義域の内点において劣勾配を持つため、関数\(f\)の定義域の内点\(x_{0}\in X^{i}\)における劣勾配が存在すること、すなわち劣微分\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) \leq c\left(
x-x_{0}\right) \right\}
\end{equation*}が非空であることが保証されますが、この内点\(x_{0}\)について、\begin{equation*}0\in \partial f\left( x_{0}\right)
\end{equation*}が成り立つことは、この内点\(x_{0}\)が先の凹最適化問題の解であるための必要十分条件です。

命題(凹最適化の内点解であるための必要十分条件)
凹関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)および凸集合\(C\subset X\)のもとでの凹最適化問題
$$\begin{array}{cl}\max & 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}\max & 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}\max & 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}\max & 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}\max & 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}\max & 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}\leq -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}\max & 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}\max & 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}\max & 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}\max & f\left( x\right) \\
s.t. & x\in \mathbb{R}
\end{array}$$の解を求めてください。

証明

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

Twitter
Mailで保存

質問とコメント