データサイエンティストスキルチェックリストver.3

『データサイエンティストスキルチェックリストver.3』はデータサイエンティストに必要とされるスキルをチェックリスト化したもので、データサイエンティストに求められるスキルを「ビジネス力」「データサイエンス力」「データエンジニアリング力」の３分野に分けて定義したものです。

本記事では、データサイエンス力のチェックリストNo.266にある項目について、学んだことをまとめてみます。

スキルカテゴリ	スキルレベル	サブカテゴリ	チェック項目
最適化	★★	最適化	凸関数および、凸計画問題の条件や特徴を説明できる

凸集合

Wikipediaの内容を一部引用します。

ユークリッド空間における物体が凸（とつ、英: convex）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。

[定義]
集合$X$が凸集合であるとは、

x_1,x_2 \in X , \lambda \in [0,1]\ \Rightarrow \ (1-\lambda)x_1 + \lambda x_2 \in X

なお、空集合も凸集合になります。
ある$\lambda \in [0,1]$に対し、$(1−\lambda)x+\lambda y$で表される点を点$x$と点$y$の凸結合と言います。

凸関数

ここでもWikipediaを参照し、凸関数の定義を以下に記します。

[定義]
関数$f$が凸関数であるとは、

\boldsymbol{x_1},\boldsymbol{x_2} \in \mathbb{R}^n , \lambda \in [0,1]\ \Rightarrow \ (1-\lambda) f(\boldsymbol{x_1}) + \lambda f(\boldsymbol{x_2}) \geq  f((1-\lambda)\boldsymbol{x_1} + \lambda \boldsymbol{x_2})

以下に凸関数のイメージを示します(参考：高校数学の美しい物語-イェンゼンの不等式の３通りの証明)

凸集合との関係

ここで、エピグラフを定義します。Wikipediaの内容を一部引用します。

数学の分野においてエピグラフ (epigraph) とはある関数の上側の領域を指す。

[定義]
関数$f:\mathbb{R}^n \rightarrow \mathbb{R}$のエピグラフは以下のように定義できます。

{\rm epi} f := \{ {\boldsymbol{x},y} \in \mathbb{R}^n \times \mathbb{R} : y \geq f(\boldsymbol{x}) \}

これを用いて、凸関数と凸集合の関係を以下に記します。
関数fのエピグラフが凸集合であることと、関数fが凸関数であることとは同値である。

凸計画問題

最小化すべき目的関数が凸関数であり，さらに実行可能領域が凸集合である数理計画問題のことを凸計画問題と呼びます。
具体的に、数式に起こすと

\begin{align}
目的 &: f(x) \rightarrow 最小化\\
条件 &: x \in X
\end{align}

ここで実現可能集合$X \subset \mathbb{R}^n$は凸集合で、目的関数$f(x)$は凸関数です。
この定義において実現可能集合$X$は、凸関数$g_i(x),(i=1,\dots,m)$を用いて以下のように書き換えることもできます。

\begin{align}
X := \{x \in \mathbb{R}^n : g_i(x) \leq 0, i=1,\dots,m \}
\end{align}

その場合、凸計画問題は以下のように定義できます。

\begin{align}
目的 &: f(x) \rightarrow 最小化\\
条件 &: g_i(x) \leq 0 , i=1,\dots,m
\end{align}

さらに、凸関数$f(x),g_i(x)$、および、線形関数$h_j(x)$を用いて以下のように定義する場合もあります。

\begin{align}
目的 &: f(x) \rightarrow 最小化 \\
条件 &: g_i(x) \leq 0 , i=1,\dots,m \\
&: h_j(x) = 0 , j=1,\dots,p
\end{align}

性質

凸計画問題では局所的最適解は大域的最適解でもあるという性質があります。
従って、凸計画問題は最適化としては解きやすい問題であると言えます。

参考資料

凸集合-Wikipedia
凸関数-Wikipedia
高校数学の美しい物語-イェンゼンの不等式の３通りの証明
エピグラフ(数学)-Wikipedia
凸最適化-Wikipedia