凸集合→凸関数→凸計画問題

凸集合 (Convex Set)

• 定義: 任意の2点 $ x, y $ を含む集合 $ C $ に対して，線分 $\lambda x + (1 - \lambda)y$ ($0 \leq \lambda \leq 1$) も集合内に含まれるとき，集合 $ C $ を凸集合と呼びます．
• 直感的なイメージ: 集合内の任意の2点を結ぶ直線が，完全に集合内に収まる．
• 例: ユークリッド空間の球，直方体，半空間など．

---

凸関数 (Convex Function)

• 定義: 関数 $ f(x) $ が凸集合上で定義されていて，以下を満たすとき，凸関数と呼びます．

\[f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y) \quad (\forall x, y \in \text{dom}(f), \ 0 \leq \lambda \leq 1)\]

• 直感的なイメージ: 関数のグラフが「上に膨らむ」形状で，2点を結ぶ線分が常にグラフの上側にある．
• 例:
  • 二次関数: $f(x) = x^2$
  • 指数関数: $f(x) = e^x$
  • 絶対値関数: $f(x) = \mid x \mid$

---

凸計画問題 (Convex Optimization Problem)

• 定義: 目的関数が凸関数で，制約条件が凸集合で表される最適化問題．一般形は次の通りである．

\[\min_x \ f(x) \quad \text{subject to} \quad x \in C\]

ここで：

• $ f(x) $ は凸関数（目的関数）

• $ C $ は凸集合（制約集合）

• メリット: 局所最適解が全体最適解になることが保証されている！
• 典型例:
  • 線形計画問題 (LP)
  • 二次計画問題 (QP)
  • LASSO回帰

---