【第4回】凸集合 〜凸最適化問題の準備〜

前回のおさらい

前回、この記事で以下の内容をご説明しました。

• • 機械学習で出てくる最適化問題

この記事の目標：

準備：線分

凸集合に触れる前に、線分を紹介します。

2 つの点 \(x_1, x_2\) を通る線分は以下で表現できます。

\begin{eqnarray}y = \theta x_1 + (1-\theta) x_2 = x_2 + \theta(x_1 – x_2)\end{eqnarray}

ただし \(0 \leq \theta \leq 1\).

\(\theta\) の値を 0 から 1 の間で変えると、
図中の黒い線分を表現できます。

\(\theta\) に具体的な値を入れてみると

• \(\theta = 0\) のとき、\(y=x_2\)
• \(\theta = 1\) のとき、\(y=x_1\)
• \(\theta = 1/2\) のとき、\(y=\frac{x_1+x_2}{2}\) （中点）

となります。これにより図の黒い線分の各点を表現できます。

線分を用いて凸集合を定義しましょう。

 

定義：凸集合

集合 \(S\) が凸集合であるとは、
\(S\) 内のどの2点 \(x_1 , x_2\) を取ってきて線分を引いても、
\(S\) からはみ出ない。

数式で書くと：

集合 \(S \subseteq \mathbb{R}^n\) が凸集合であるとは
任意の \(x_1, x_2 \in S\) に対して以下が成立すること。

\begin{eqnarray}\theta x_1 + (1-\theta) x_2 \in S, \ \forall \theta \in [0,1]\end{eqnarray}

凸集合の例

例としては円、多角形などがあります。

 

凸でない集合の例

もちろん凸集合でない場合もたくさんあります。

たとえば、三日月は凸集合ではありません。

 

まとめ

最適化問題では、「凸最適化問題」が重要な役割を演じます。
それを議論するため、凸集合をご紹介しました。

 

次回予告

次回は今回紹介した凸集合を用いて、

第5回「凸関数」というものを紹介します。

 

参考文献

[1] S.Boyd and L. Vandenberghe, “Convex Optimization,” Cambridge University Press, Cambridge, 2004.
[2] 寒野, 土屋著 “東京大学工学教程 基礎系数学 最適化と変分法,” 丸善出版, 2014.