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

凸最適化・凹最適化

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

目次

次のページ:
Twitter
Mailで保存

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

目的関数である凸関数\(f:\mathbb{R} ^{n}\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} ^{n}\ |\ \forall x\in X:f\left( x\right) -f\left( x_{0}\right) \geq c\cdot
\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} ^{n}\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} ^{n}\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} ^{n}\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} ^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}f\left( x,y\right) =\sqrt{x^{2}+y^{2}}
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} ^{2}\)は\(\mathbb{R} ^{2}\)自身の部分集合であり、さらに\(\mathbb{R} ^{2}\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & x\in \mathbb{R} ^{2}
\end{array}$$

を構成できます。点\(\left( x_{0},y_{0}\right) \in \mathbb{R} ^{2}\)を任意に選びます。\(\mathbb{R} ^{2}\)は開集合であるため\(\left( x_{0},y_{0}\right) \)は\(\mathbb{R} ^{2}\)の内点です。この関数\(f\)のそれぞれの内点\(\left( x_{0},y_{0}\right) \in \mathbb{R} ^{2}\)における劣微分は、\begin{equation*}\partial f\left( x_{0},y_{0}\right) =\left\{
\begin{array}{cc}
\left\{ \left( \frac{x_{0}}{\sqrt{x_{0}^{2}+y_{0}^{2}}},\frac{y_{0}}{\sqrt{x_{0}^{2}+y_{0}^{2}}}\right) \right\} & \left( if\ \left(
x_{0},y_{0}\right) \not=\left( 0,0\right) \right) \\
\left\{ \left( c_{1},c_{2}\right) \in \mathbb{R} ^{2}\ |\ \sqrt{c_{1}^{2}+c_{2}^{2}}\leq 1\right\} & \left( if\ \left(
x_{0},y_{0}\right) =\left( 0,0\right) \right)
\end{array}\right.
\end{equation*}であるため、\begin{equation*}
\left( 0,0\right) \in \partial f\left( 0,0\right)
\end{equation*}が成り立ちます。したがって、先の命題より、この凸最適化問題の解は点\(\left( 0,0\right) \)であり、\(f\)の最小値は\(f\left(0,0\right) =0\)です。

 

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

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

命題(目的関数が全微分可能である場合の凸最適化の内点解であるための必要十分条件)
凸関数\(f:\mathbb{R} ^{n}\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*}\nabla f\left( x_{0}\right) =0
\end{equation*}が成り立つことは、この内点\(x_{0}\)が先の問題の解であるための必要十分条件である。

証明

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

例(凸最適化問題の内点解)
関数\(f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}f\left( x,y\right) =x\ln \left( x\right) +y\ln \left( y\right)
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} _{++}^{2}\)は\(\mathbb{R} _{++}^{2}\)自身の部分集合であり、さらに\(\mathbb{R} _{++}^{2}\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \mathbb{R} _{++}^{2}
\end{array}$$

を構成できます。点\(\left( x_{0},y_{0}\right) \in \mathbb{R} _{++}^{2}\)を任意に選びます。\(\mathbb{R} _{++}^{2}\)は開集合であるため\(\left( x_{0},y_{0}\right) \)は\(\mathbb{R} _{++}^{2}\)の内点です。この関数\(f\)は全微分可能であり、勾配ベクトル場\(\nabla f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}\nabla f\left( x,y\right) =\left( \ln \left( x\right) +1,\ln \left( y\right)
+1\right)
\end{equation*}を定めます。\begin{equation*}
\nabla f\left( x,y\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( \ln \left( x\right) +1,\ln \left( y\right) +1\right) =\left(
0,0\right)
\end{equation*}を解くと、\begin{equation*}
\left( x,y\right) =\left( e^{-1},e^{-1}\right)
\end{equation*}を得るため、先の命題より、この凸最適化問題の解は点\(\left(e^{-1},e^{-1}\right) \)であり、\(f\)の最小値は\(f\left( e^{-1},e^{-1}\right) =-2e^{-1}\)です。

 

凸最適化問題の解

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

  1. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在する場合、それは凸最適化問題の解であることが保証される。しかも、他に解は存在しない。
  2. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在せず、しかも制約集合が開集合である場合、凸最適化問題には解は存在しない。
  3. 制約集合の内点の中に凸最適化問題の解であるための必要十分条件を満たすものが存在せず、しかも制約集合が開集合ではない場合、凸最適化問題には端点解が存在する可能性がある。
例(解が存在しない場合)
関数\(f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}f\left( x,y\right) =\frac{1}{x}+\frac{1}{y}
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。\(\mathbb{R} _{++}^{2}\)は\(\mathbb{R} _{++}^{2}\)自身の部分集合であり、さらに\(\mathbb{R} _{++}^{2}\)は凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in \mathbb{R} _{++}^{2}
\end{array}$$

を構成できます。点\(\left( x_{0},y_{0}\right) \in \mathbb{R} _{++}^{2}\)を任意に選びます。\(\mathbb{R} _{++}^{2}\)は開集合であるため\(\left( x_{0},y_{0}\right) \)は\(\mathbb{R} _{++}^{2}\)の内点です。この関数\(f\)は全微分可能であり、勾配ベクトル場\(\nabla f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}\nabla f\left( x,y\right) =\left( -\frac{1}{x^{2}},-\frac{1}{y^{2}}\right)
\end{equation*}を定めますが、\begin{equation*}
\nabla f\left( x,y\right) =\left( 0,0\right)
\end{equation*}すなわち、\begin{equation*}
\left( -\frac{1}{x^{2}},-\frac{1}{y^{2}}\right) =\left( 0,0\right)
\end{equation*}を満たす点\(\left( x,y\right) \)は制約集合\(\mathbb{R} _{++}^{2}\)に存在しないため、この凸最適化問題に内点解は存在しません。加えて、この制約集合\(\mathbb{R} _{++}^{2}\)は開集合であるため、この凸最適化問題に端点解も存在せず、したがって解は存在しません。

例(端点解が存在する場合)
関数\(f:\mathbb{R} _{++}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( x,y\right) \in \mathbb{R} _{++}^{2}\)に対して、\begin{equation*}f\left( x,y\right) =\frac{1}{x}+\frac{1}{y}
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。以下の集合\begin{equation*}(0,1]\times (0,1] \end{equation*}は\(\mathbb{R} _{++}^{2}\)の部分集合であるような凸集合であるため、以下の凸最適化問題
$$\begin{array}{cl}\min & f\left( x,y\right) \\
s.t. & \left( x,y\right) \in (0,1]\times (0,1] \end{array}$$

を構成できます。先と同様の議論より、制約集合の内部\(\left( 0,1\right) \)には凸最適化のための必要十分条件を満たす内点は存在しないため、この凸最適化問題に内点解は存在しません。その一方で、制約集合\((0,1]\times (0,1]\)は開集合ではなく、境界点を要素として持ちます。特に、境界点\(\left( 1,1\right) \)に注目すると、任意の\(\left( x,y\right) \in (0,1]\times(0,1]\)に対して、\begin{equation*}\frac{1}{x}+\frac{1}{y}\geq 2=f\left( 1,1\right)
\end{equation*}が成り立つため、この凸最適化問題には端点解\(\left( 1,1\right) \)が存在し、\(f\)の最小値は\(f\left( 1,1\right) =2\)です。

 

演習問題

問題(凸最適化問題の解)
関数\(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で保存

質問とコメント