前回のおさらい
前回、この記事で以下の内容をご説明しました。
-
- 機械学習で出てくる最適化問題
この記事の目標:

応用上重要な「凸最適化問題」を理解するため、凸集合を説明する。
準備:線分
凸集合に触れる前に、線分を紹介します。

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.
北海道大学大学院情報科学研究科修士課程修了。
機械メーカにて開発業務に従事したのち、フリーのエンジニア・講師として活動中。