WIIS

凸最適化・凹最適化

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

目次

次のページ:
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で保存

質問とコメント

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

関連知識

1変数の凸関数・凹関数

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

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

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

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

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

勾配ベクトル(グラディエント)

多変数関数が定義域上の点においてすべての変数に関して偏微分可能である場合、その点におけるそれぞれの変数に関する偏微分係数を成分とするベクトルが存在します。これを勾配ベクトル(グラディエント)と呼びます。

多変数関数の積の偏微分

偏微分可能な関数どうしの積として定義される関数もまた偏微分可能であり、その偏導関数や勾配ベクトル場は積の法則と呼ばれる規則から得られます。

多変数関数の商の偏微分

偏微分可能な関数どうしの商として定義される関数もまた偏微分可能であり、その偏導関数や勾配ベクトル場は商の法則と呼ばれる規則から得られます。

多変数関数の方向微分と偏微分の関係

多変数関数が任意の方向へ方向微分可能である場合、その関数は任意の変数について偏微分可能ですが、その逆は成り立つとは限りません。一定の条件のもとでは、方向微分係数は勾配ベクトルと方向ベクトルの内積として定まります。

多変数の凸関数・凹関数

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