凸関数と凸最適化

「凸関数と凸最適化」は、機械学習や強化学習の最適化アルゴリズムの理論的基盤を成す極めて重要な概念です。以下に、厳密かつ具体的に解説します。

---

1. 凸関数とは

定義

実数値関数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ が凸関数 (convex function) であるとは、任意の2点 $x, y \in \mathbb{R}^n$ と $\lambda \in [0, 1]$ に対して以下の不等式が成り立つことを言います：

$$f(\lambda x + (1 – \lambda) y) \leq \lambda f(x) + (1 – \lambda) f(y)$$

これは幾何学的に、「関数のグラフが任意の2点を結ぶ直線よりも常に下にある」ことを意味します。

直感的な意味

• 凸関数は局所最小解が常に大域最小解となる性質を持ちます。

• この性質があるため、最適化問題を解く際に、計算効率や収束性が保証されやすくなります。

---

2. 凸集合と凸関数の関係

凸集合

集合 $C \subset \mathbb{R}^n$ が凸集合であるとは、任意の $x, y \in C$ に対して、$\lambda x + (1 – \lambda)y \in C$ が成立する（$\lambda \in [0,1]$）ことを意味します。

凸最適化問題では、目的関数が凸関数であり、制約条件が凸集合に基づいて定義されている必要があります。

---

3. 凸最適化問題とは

一般形

以下のような形の最適化問題を凸最適化問題 (convex optimization problem) と呼びます：

$$\begin{align*} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m \\ & h_j(x) = 0, \quad j = 1, \dots, p \end{align*}$$

ここで：

• $f(x)$ は凸関数

• $g_i(x)$ は凸関数（不等式制約）

• $h_j(x)$ は線形関数（等式制約）

---

4. 凸最適化の利点

1. 局所解 = 大域解：
   凸関数では局所最小値が常に大域最小値になるため、単純な勾配法でも正しい解に収束できる。

2. 理論解析が可能：
   強双対性（strong duality）やスレイターの条件（Slater’s condition）などの理論が適用できる。

3. 数値的に安定：
   ニュートン法や内点法などのアルゴリズムがよく機能する。

---

5. 機械学習における応用例

• 線形回帰・リッジ回帰：目的関数が2乗誤差であり凸。

• ロジスティック回帰：損失関数（クロスエントロピー）が凸。

• サポートベクターマシン（SVM）：凸二次計画問題に帰着。

• Lasso回帰：$L_1$ 正則化項を含む凸最適化問題。

---

6. 強凸性（strong convexity）

関数 $f(x)$ が 強凸関数 であるとは、ある定数 $\mu > 0$ に対して以下を満たすことです：

$$f(y) \geq f(x) + \nabla f(x)^T (y – x) + \frac{\mu}{2} \|y – x\|^2$$

強凸関数は単なる凸関数よりも「曲がり」が強く、収束解析や最適性の証明がより厳密に行えるため、多くのアルゴリズム設計において有利です。

---

7. 代表的な最適化手法

• 勾配降下法（Gradient Descent）

• 確率的勾配降下法（SGD）

• ニュートン法

• 内点法（Interior Point Method）

• 凸二次計画法（Quadratic Programming）

---

まとめ