第2章凸集合と凸関数

この章の目標

• 凸集合・凸包・錐・多面体を定義し、例と反例を挙げられる
• 閉凸集合への射影の存在・一意性と特徴づけを証明し、そこから分離定理・支持超平面定理を導ける
• 微分可能な関数の凸性を 1 次条件・2 次条件で判定でき、定義域が開凸集合という仮定の意味を説明できる
• 凸関数の局所最小は大域最小であることを証明し、凸性を保つ演算で凸性を確かめられる
• 強凸性と $L$-平滑性の同値な特徴づけを証明し、条件数の意味を説明できる
• 劣勾配を計算し、最適性条件 $0 \in \partial f(x)$ を使える

前提：第1章、01-calculus 第4章（1 変数の凸関数）、01-calculus 第7章、02-linear-algebra 第8章（正定値性）。2.7 節では 01-calculus 第5章 の微分積分学の基本定理と 第8章 の平均値の不等式を使う。

第1章で予告した「凸最適化問題では局所最小点が大域最小点になる」ことを証明し、それを支える理論を整える。柱は、閉凸集合への射影から導かれる分離定理（線形計画の双対定理（第3章）や強双対性（第4章）の証明の核）、凸性の判定法、勾配法の速さを決める強凸性と $L$-平滑性（第5章）の三つである。最後に、微分できない凸関数のための劣勾配と共役関数を導入する。

$\langle x, y \rangle = x^{\top}y$、$\lVert x \rVert$ はユークリッドノルムとする。対称行列 $A, B$ について、$A \succeq B$ は $A - B$ が半正定値、$A \succ B$ は正定値であることを表す。

2.1 凸集合

凸集合は第1章 定義 1.24 で定義した。

定義 2.1（凸結合・凸包・錐・多面体）$\lambda_i \geq 0$, $\sum_{i=1}^{k}\lambda_i = 1$ のとき、$\sum_i \lambda_ix_i$ を $x_1, \dots, x_k$ の凸結合 (convex combination) という。$S \subset \mathbb{R}^n$ の有限個の元の凸結合全体を凸包 (convex hull) $\operatorname{conv} S$ という。「$x \in K$, $\lambda \geq 0$ ならば $\lambda x \in K$」を満たす $K$ を錐 (cone)、凸な錐を凸錐という。有限個の閉半空間の共通部分 $\lbrace x \mid Ax \leq b \rbrace$ を多面体 (polyhedron) という。

命題 2.2 (1) 凸集合の任意個の共通部分は凸である。(2) 凸集合のアフィン写像 $x \mapsto Ax + b$ による像と逆像は凸である。(3) 凸集合 $C$ は、$C$ の元の凸結合をすべて含む。(4) $\operatorname{conv} S$ は $S$ を含む最小の凸集合である。

証明. (1) は明らか。(2) は $A((1 - t)x + ty) + b = (1 - t)(Ax + b) + t(Ay + b)$ による。(3) $k$ についての帰納法。$\lambda_k = 1$ なら和は $x_k$ である。$\lambda_k < 1$ なら $\sum_{i=1}^{k}\lambda_ix_i = (1 - \lambda_k)z + \lambda_kx_k$, $z = \sum_{i=1}^{k-1}\frac{\lambda_i}{1 - \lambda_k}x_i \in C$（帰納法の仮定）。(4) 凸結合の凸結合は凸結合なので $\operatorname{conv} S$ は凸で、$S$ を含む凸集合は (3) より $\operatorname{conv} S$ を含む。$\square$

例 2.3 (1) 超平面・閉半空間 $\lbrace a^{\top}x \leq b \rbrace$・球（三角不等式による）・多面体は凸である。線形計画の実行可能領域（第1章 例 1.2・1.3）は多面体である。(2) 確率単体 $\lbrace w \geq 0 \mid \sum_i w_i = 1 \rbrace = \operatorname{conv}\lbrace e_1, \dots, e_n \rbrace$ は空売りなしのポートフォリオ全体である。(3) 非負象限 $\mathbb{R}^n_{+}$、二次錐 $\lbrace (x, t) \mid \lVert x \rVert \leq t \rbrace$、半正定値対称行列全体（一次不等式 $v^{\top}Xv \geq 0$ の共通部分）は凸錐で、線形計画・二次錐計画・半正定値計画の基礎になる。(4) 交わらない 2 つの球の和集合、$\mathbb{Z}^n$、球面は凸でない。

凸集合 $C$ の点 $x$ が、$x = (1 - t)y + tz$（$y, z \in C$, $0 < t < 1$）なら $y = z = x$ となるとき、端点 (extreme point) という。有界な多面体は有限個の端点（頂点）の凸包に等しい（ミンコフスキー–ワイルの定理。証明は Schrijver, Theory of Linear and Integer Programming などを参照）。

2.2 射影定理

02-linear-algebra 第7章 定理 7.17 の正射影を、部分空間から閉凸集合に一般化する。

定理 2.4（射影定理, projection theorem）$C \subset \mathbb{R}^n$ を空でない閉凸集合とする。各 $x \in \mathbb{R}^n$ に対し、$\lVert x - p \rVert = \min_{y \in C}\lVert x - y \rVert$ となる $p \in C$ がただ一つ存在する。これを $P_C(x)$ と書き、$x$ の $C$ への射影という。$p \in C$ について

$$p = P_C(x) \iff \langle x - p, y - p \rangle \leq 0 \quad (\forall y \in C) \tag{2.1}$$

であり、$\lVert P_C(x) - P_C(x') \rVert \leq \lVert x - x' \rVert$（非拡大性）が成り立つ。

証明. 存在：$y \mapsto \lVert x - y \rVert^2$ は連続で強圧的なので、第1章 定理 1.11 より閉集合 $C$ 上で最小値をとる。一意性：$p_1, p_2$ がともに最小距離 $d$ を与えるなら、中点 $m \in C$ について中線定理より

で、$d$ の最小性から $p_1 = p_2$。(2.1) の ⇒：$y \in C$, $0 < t \leq 1$ なら $p + t(y - p) \in C$ なので $0 \leq \lVert x - p - t(y - p) \rVert^2 - \lVert x - p \rVert^2 = -2t\langle x - p, y - p \rangle + t^2\lVert y - p \rVert^2$。$t$ で割って $t \to +0$ とする。⇐：$\lVert x - y \rVert^2 = \lVert x - p \rVert^2 - 2\langle x - p, y - p \rangle + \lVert y - p \rVert^2 \geq \lVert x - p \rVert^2$。非拡大性：$p = P_C(x)$, $p' = P_C(x')$ として (2.1) を $(x, p, y = p')$ と $(x', p', y = p)$ に使って足すと、$\lVert p - p' \rVert^2 \leq \langle x - x', p - p' \rangle \leq \lVert x - x' \rVert\lVert p - p' \rVert$。$\square$

(2.1) は「$x - p$ と $y - p$ のなす角が直角以上」という意味である。$C$ が閉でないと最も近い点がないことがあり（開球と外の点）、凸でないと一意性が崩れる（球面と中心）。

例 2.5（射影の計算）(1) 箱 $\lbrace l \leq y \leq u \rbrace$ への射影は成分ごとの切り詰め $\min(\max(x_i, l_i), u_i)$（$[0, 1]^2$ への $(2, -0.5)$ の射影は $(1, 0)$）。(2) 球 $\lbrace \lVert y \rVert \leq r \rbrace$ への射影は、$\lVert x \rVert > r$ なら $rx/\lVert x \rVert$。(3) 半空間 $\lbrace a^{\top}y \leq b \rbrace$ への射影は $x - \frac{\max(0, a^{\top}x - b)}{\lVert a \rVert^2}a$（$a^{\top}x > b$ なら $x - p = ca$, $c > 0$, $a^{\top}p = b$ で、$\langle x - p, y - p \rangle = c(a^{\top}y - b) \leq 0$）。射影が簡単な集合の上では、第5章の射影勾配法が使える。

2.3 分離定理と支持超平面定理

交わらない凸集合の間には超平面を引ける。これが実行不能性や最適性の証明書（第3章・第4章の双対変数）を作る道具になる。仮定（閉・コンパクト・開）と分離の強さの対応に注意する。

定理 2.6（点と閉凸集合の分離）$C$ を空でない閉凸集合、$x_0 \notin C$ とする。このとき $a \neq 0$ があって $\sup_{y \in C} a^{\top}y < a^{\top}x_0$ となる。

証明. $p = P_C(x_0)$, $a = x_0 - p \neq 0$ とおくと、(2.1) より $y \in C$ で $a^{\top}(y - p) \leq 0$、すなわち $a^{\top}y \leq a^{\top}p = a^{\top}x_0 - \lVert a \rVert^2$。$\square$

定理 2.7（閉凸集合とコンパクト凸集合の強分離）$C$ を空でない閉凸集合、$K$ を空でないコンパクト凸集合とし、$C \cap K = \emptyset$ とする。このとき $a \neq 0$ があって $\sup_{y \in C} a^{\top}y < \min_{z \in K} a^{\top}z$ となる。

証明. $D = C - K = \lbrace y - z \mid y \in C, z \in K \rbrace$ は凸で $0 \notin D$。$D$ は閉である：$y_k - z_k \to w$（$y_k \in C$, $z_k \in K$）なら、$K$ のコンパクト性から部分列で $z_{k_j} \to z \in K$、すると $y_{k_j} \to w + z \in C$ で、$w \in D$。定理 2.6 を $D$ と $0$ に使うと、$a \neq 0$, $\varepsilon > 0$ があってすべての $y \in C$, $z \in K$ で $a^{\top}y \leq a^{\top}z - \varepsilon$。$\square$

例 2.8（コンパクト性は外せない）$C = \lbrace (x, y) \mid x > 0, \ xy \geq 1 \rbrace$（凸関数 $1/x$ のエピグラフ）と $K = \lbrace (x, y) \mid y \leq 0 \rbrace$ は交わらない閉凸集合だが、$(t, 1/t) \in C$ と $(t, 0) \in K$ の距離は $0$ に近づく。$\inf_K a^{\top}z > -\infty$ となるのは $a = (0, a_2)$, $a_2 < 0$ のときだけで、そのとき $\inf_K a^{\top}z = 0 = \sup_C a^{\top}y$ だから、定理 2.7 の形の分離はできない（$C$ と $K$ を入れ替えても同様）。

閉でない凸集合も扱うために、有限次元の次の性質を使う。

補題 2.9 凸集合 $C \subset \mathbb{R}^n$ について、閉包の内部は $C$ の内部に等しい：$(\overline{C})^{\circ} = C^{\circ}$。

証明. $\supset$ は明らか。$x_0 \in (\overline{C})^{\circ}$ とし、閉球 $\overline{B}(x_0, \delta\sqrt{n}) \subset \overline{C}$ となる $\delta > 0$ をとる。$v_i = x_0 + \delta e_i$（$1 \leq i \leq n$）、$v_0 = x_0 - \delta(e_1 + \cdots + e_n)$ はこの閉球に属し、$x_0 = \frac{1}{n+1}\sum_{i=0}^{n}v_i$。点 $w_0, \dots, w_n$ に対し、$(w_0, 1), \dots, (w_n, 1) \in \mathbb{R}^{n+1}$ を列とする正方行列を $M(w)$ とする。$v_i - v_0 = \delta(e_i + e_1 + \cdots + e_n)$（$i \geq 1$）は一次独立（係数行列 $\delta(I + \mathbf{1}\mathbf{1}^{\top})$ の固有値は $\delta(n + 1)$ と $\delta$）なので $M(v)$ は正則で、クラメルの公式より $\lambda(w) = M(w)^{-1}(x_0, 1)$ は $v$ の近くで $w$ について連続、$\lambda(v) = (\frac{1}{n+1}, \dots, \frac{1}{n+1})$。よって $w_i \in C$ を $v_i$ の十分近くにとれば、$M(w)$ は正則で $\lambda(w)$ の成分はすべて正となり、$x_0 = \sum_i \lambda_i(w)w_i$, $\sum_i \lambda_i(w) = 1$ だから $x_0 \in C$（命題 2.2 (3)）。開集合 $(\overline{C})^{\circ}$ が $C$ に含まれたので、$C^{\circ}$ に含まれる。$\square$

定理 2.10（支持超平面定理, supporting hyperplane theorem）$C \subset \mathbb{R}^n$ を空でない凸集合、$x_0 \notin C^{\circ}$（たとえば $C$ の境界点）とする。このとき $a \neq 0$ があって、すべての $y \in C$ で $a^{\top}y \leq a^{\top}x_0$ となる。

証明. 補題 2.9 より $x_0 \notin (\overline{C})^{\circ}$ なので、$\overline{C}$ に属さない点列 $x_k \to x_0$ がとれる。凸集合の閉包は凸だから（$C$ の点列 $y_k \to y$, $z_k \to z$ について $(1 - t)y_k + tz_k \to (1 - t)y + tz$）、定理 2.6 より $\lVert a_k \rVert = 1$ で $a_k^{\top}y < a_k^{\top}x_k$（$y \in \overline{C}$）となる $a_k$ がある。部分列で $a_k \to a$（$\lVert a \rVert = 1$）とし、$y \in C$ を固定して極限をとればよい。$\square$

定理 2.11（分離定理, separating hyperplane theorem）$C_1, C_2 \subset \mathbb{R}^n$ を交わらない空でない凸集合とする。

1. $a \neq 0$ があって、すべての $x \in C_1$, $y \in C_2$ で $a^{\top}x \leq a^{\top}y$ となる。
2. さらに $C_1$ が開集合なら、$\alpha = \sup_{C_1}a^{\top}x$ について、すべての $x \in C_1$, $y \in C_2$ で $a^{\top}x < \alpha \leq a^{\top}y$ となる。

証明. (1) $D = C_1 - C_2$ は凸で $0 \notin D$ なので、定理 2.10 を $D$ と $0$ に使う。(2) $x \in C_1$ なら小さい $\varepsilon > 0$ で $x + \varepsilon a \in C_1$ だから、$a^{\top}x < a^{\top}(x + \varepsilon a) \leq \alpha$。$\square$

2.4 凸関数とその判定

定義 2.12 凸集合 $C$ 上の関数 $f$ が、$x \neq y$, $0 < t < 1$ で $f((1 - t)x + ty) < (1 - t)f(x) + tf(y)$ を満たすとき狭義凸、$-f$ が凸のとき凹という。$\operatorname{epi} f = \lbrace (x, s) \in C \times \mathbb{R} \mid f(x) \leq s \rbrace$ をエピグラフ (epigraph) という。

命題 2.13 $C$ を凸集合、$f\colon C \to \mathbb{R}$ とする。

1. $f$ が凸 $\iff$ $\operatorname{epi} f$ が凸集合。
2. $f$ が凸なら、下位集合 $\lbrace x \in C \mid f(x) \leq \alpha \rbrace$ は凸である（逆は成り立たない：$\sqrt{\lvert x \rvert}$）。
3. $f$ が凸 $\iff$ 任意の $x \in C$, $d$ について、$t \mapsto f(x + td)$ が区間 $\lbrace t \mid x + td \in C \rbrace$ 上で凸。
4. （イェンセンの不等式）$f$ が凸で $\lambda_i \geq 0$, $\sum_i \lambda_i = 1$ なら $f(\sum_i \lambda_ix_i) \leq \sum_i \lambda_if(x_i)$。

証明. 1 は、$(x, s), (y, u) \in \operatorname{epi} f$ について $f((1 - t)x + ty) \leq (1 - t)s + tu$ となることが凸性と同値であることによる。2・3 は定義から従う。4 は 01-calculus 第4章 定理 4.31 と同じ帰納法による。$\square$

定理 2.14（1 次条件）$U \subset \mathbb{R}^n$ を開凸集合、$f\colon U \to \mathbb{R}$ を微分可能とする。次は同値である。

1. $f$ は凸である。
2. すべての $x, y \in U$ で $f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle$。
3. すべての $x, y \in U$ で $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq 0$（勾配の単調性）。

証明. (1⇒2) $0 < t \leq 1$ で $f(x + t(y - x)) - f(x) \leq t(f(y) - f(x))$。$t$ で割って $t \to +0$ とすると、左辺は方向微分 $\langle \nabla f(x), y - x \rangle$ に収束する（01-calculus 第7章 命題 7.11）。(2⇒1) $z = (1 - t)x + ty$ とし、2 を $(z, x)$ と $(z, y)$ に使って $1 - t$ 倍と $t$ 倍して足すと、$(1 - t)(x - z) + t(y - z) = 0$ より $(1 - t)f(x) + tf(y) \geq f(z)$。(2⇒3) 2 を $(x, y)$ と $(y, x)$ に使って足す。(3⇒1) $x_t = x + t(y - x)$, $\varphi(t) = f(x_t)$ は $[0, 1]$ を含む開区間で微分可能で、$\varphi'(t) = \langle \nabla f(x_t), y - x \rangle$。$s < t$ なら $\varphi'(t) - \varphi'(s) = \frac{1}{t - s}\langle \nabla f(x_t) - \nabla f(x_s), x_t - x_s \rangle \geq 0$ で、$\varphi'$ が単調増加なので $\varphi$ は凸（01-calculus 第4章 定理 4.30）。$\varphi(t) \leq (1 - t)\varphi(0) + t\varphi(1)$ が求める不等式である。$\square$

2 は「接平面がグラフ全体の下にある」こと、つまり局所的な情報 $\nabla f(x)$ が大域的な下界を与えることを意味し、凸最適化の要である。

定理 2.15（2 次条件）$U \subset \mathbb{R}^n$ を開凸集合、$f$ を $U$ 上の $C^2$ 級関数とする。

1. $f$ が凸 $\iff$ すべての $x \in U$ で $\nabla^2 f(x) \succeq 0$。
2. すべての $x \in U$ で $\nabla^2 f(x) \succ 0$ ならば $f$ は狭義凸である（逆は成り立たない：$x^4$）。

証明. $\varphi(t) = f(x + td)$ は $0$ を含む開区間で $C^2$ 級で、$\varphi''(t) = d^{\top}\nabla^2 f(x + td)d$（01-calculus 第7章 7.6 節）。(1) ⇒：$\varphi$ は凸なので（命題 2.13 (3)）$\varphi''(0) \geq 0$（01-calculus 第4章 定理 4.30）。⇐：$d = y - x$ とすると $\varphi'' \geq 0$ より $\varphi$ は凸で、命題 2.13 (3) より $f$ は凸。(2) $d \neq 0$ なら $\varphi'$ は狭義単調増加なので、平均値の定理より $0 < t < 1$ で $\frac{\varphi(t) - \varphi(0)}{t} = \varphi'(\xi) < \varphi'(\eta) = \frac{\varphi(1) - \varphi(t)}{1 - t}$（$\xi < t < \eta$）。これは $\varphi(t) < (1 - t)\varphi(0) + t\varphi(1)$ と同値である。$\square$

例 2.16（定義域が開であることの意味）$f(x_1, x_2) = x_1^2 - x_2^2$ を内部が空の凸集合 $C = \lbrace (x_1, 0) \rbrace$ に制限すると $x_1^2$ で凸だが、$\nabla^2 f = \operatorname{diag}(2, -2)$ は半正定値でない。定理 2.15 の「⇒」は、定義域が開でないと成り立たない。

例 2.17（凸関数の例）(1) アフィン関数、ノルム。(2) 二次関数 $\frac{1}{2}x^{\top}Qx + c^{\top}x$ は凸 $\iff Q \succeq 0$ で、分散 $w^{\top}\Sigma w$ や $\lVert Ax - b \rVert^2$ は凸。(3) $e^{ax}$、$-\log x$、$x\log x$（$x > 0$）、$\lvert x \rvert^p$（$p \geq 1$）、log-sum-exp（問題 2.3）。(4) $\log(1 + e^{t})$ は 2 階導関数 $\sigma(1 - \sigma)$ が正（$\sigma$ はシグモイド関数）なので凸で、ロジスティック回帰の損失（第1章 例 1.6）は $\nabla^2\ell(x) = \sum_i \sigma(a_i^{\top}x)(1 - \sigma(a_i^{\top}x))a_ia_i^{\top} \succeq 0$ より凸。(5) $x^3$、$\sin x$、$x_1x_2$ は凸でない。

2.5 凸最適化の基本定理

定理 2.18 $C$ を凸集合、$f\colon C \to \mathbb{R}$ を凸関数とする。

1. $f$ の局所最小点は大域最小点である。
2. 最小点の全体は凸集合である。
3. $f$ が狭義凸なら、最小点は（存在すれば）ただ一つである。

証明. (1) $x^{\ast}$ を局所最小点とし、$f(y) < f(x^{\ast})$ となる $y \in C$ があったとする。$0 < t \leq 1$ で $x_t = x^{\ast} + t(y - x^{\ast}) \in C$ かつ $f(x_t) \leq (1 - t)f(x^{\ast}) + tf(y) < f(x^{\ast})$ で、$t \to 0$ で $x_t \to x^{\ast}$ だから局所最小性に反する。(2) 最小値を $p^{\ast}$ とすると、最小点の全体は下位集合 $\lbrace f \leq p^{\ast} \rbrace$ である。(3) 最小点 $x \neq y$ があれば $f(\frac{x + y}{2}) < p^{\ast}$ となり矛盾。$\square$

定理 2.19（凸最適化の最適性条件）$U \subset \mathbb{R}^n$ を開凸集合、$f\colon U \to \mathbb{R}$ を微分可能な凸関数とする。

1. $x^{\ast} \in U$ が $U$ 上の最小点 $\iff$ $\nabla f(x^{\ast}) = 0$。
2. $C \subset U$ を凸集合とする。$x^{\ast} \in C$ が $C$ 上の最小点 $\iff$ すべての $y \in C$ で $\langle \nabla f(x^{\ast}), y - x^{\ast} \rangle \geq 0$。

証明. (1) ⇒ は第1章 定理 1.17。(1)・(2) の ⇐ は 1 次条件（定理 2.14）による。(2) ⇒：ある $y \in C$ で $\langle \nabla f(x^{\ast}), y - x^{\ast} \rangle < 0$ なら、$y - x^{\ast}$ は降下方向で（第1章 補題 1.16）、小さい $t > 0$ で $x^{\ast} + t(y - x^{\ast}) \in C$ の値は $f(x^{\ast})$ より小さく、矛盾する。$\square$

(2) で $f(y) = \frac{1}{2}\lVert y - x \rVert^2$ とすると、射影の特徴づけ (2.1) になる。

2.6 凸性を保つ演算

命題 2.20 $f, f_i, g$ を凸関数とする（定義域は凸集合とする）。次の関数は凸である。

1. 非負の重みつき和 $\sum_i \alpha_if_i$（$\alpha_i \geq 0$）。
2. アフィン写像との合成 $f(Ax + b)$。
3. 各点ごとの上限 $\sup_{i \in I} f_i(x)$（$I$ は任意の集合で、上限は有限とする）。
4. $h\colon \mathbb{R} \to \mathbb{R}$ が凸かつ単調非減少のときの $h(g(x))$。

証明. 1・2 は定義から従う。3：各 $i$ で $f_i((1 - t)x + ty) \leq (1 - t)\sup_j f_j(x) + t\sup_j f_j(y)$ で、左辺の上限をとる。4：$h(g((1 - t)x + ty)) \leq h((1 - t)g(x) + tg(y)) \leq (1 - t)h(g(x)) + th(g(y))$。$\square$

たとえば $\max_i(a_i^{\top}x + b_i)$、ヒンジ損失 $\max(0, 1 - t)$、$\lVert x \rVert_1$、対称行列の最大固有値 $\lambda_{\max}(X) = \max_{\lVert v \rVert = 1}v^{\top}Xv$（02-linear-algebra 第8章 命題 8.29）は 3 より、$\ell(x) + \frac{\lambda}{2}\lVert x \rVert^2$ やラッソの目的関数 $\frac{1}{2}\lVert Ax - b \rVert^2 + \lambda\lVert x \rVert_1$ は 1・2 より凸である。凸関数の最小値・差・積は凸とは限らない（$\min(x^2, (x - 2)^2)$、$-x^2$、$x \cdot x^2$）。

2.7 強凸性と $L$-平滑性

勾配法の速さを論じるには、$f$ を上下から二次関数で挟む定量的な情報が要る。

定義 2.21 $U \subset \mathbb{R}^n$ を開凸集合、$f\colon U \to \mathbb{R}$, $\mu > 0$, $L > 0$ とする。

1. $f(x) - \frac{\mu}{2}\lVert x \rVert^2$ が凸のとき、$f$ は $\mu$-強凸 ($\mu$-strongly convex) であるという。
2. $f$ が微分可能で、すべての $x, y \in U$ で $\lVert \nabla f(x) - \nabla f(y) \rVert \leq L\lVert x - y \rVert$ のとき、$f$ は $L$-平滑 ($L$-smooth) であるという。

定理 2.22（強凸性の特徴づけ）$U$ を開凸集合、$f\colon U \to \mathbb{R}$ を微分可能とする。次は同値である。

1. $f$ は $\mu$-強凸である。
2. すべての $x, y \in U$ で $f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2}\lVert y - x \rVert^2$。
3. すべての $x, y \in U$ で $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \mu\lVert x - y \rVert^2$。

$f$ が $C^2$ 級なら、これらは「すべての $x \in U$ で $\nabla^2 f(x) \succeq \mu I$」とも同値である。

証明. $g(x) = f(x) - \frac{\mu}{2}\lVert x \rVert^2$ に定理 2.14・2.15 を適用する。$\nabla g(x) = \nabla f(x) - \mu x$, $\nabla^2 g = \nabla^2 f - \mu I$ と、恒等式 $\lVert y \rVert^2 - \lVert x \rVert^2 - 2\langle x, y - x \rangle = \lVert y - x \rVert^2$ により、$g$ の 1 次条件は 2 に、$\nabla g$ の単調性は 3 に、$\nabla^2 g \succeq 0$ は $\nabla^2 f \succeq \mu I$ に書き換わる。$\square$

定理 2.23（$L$-平滑性の特徴づけ）

1. $U$ を開凸集合、$f\colon U \to \mathbb{R}$ を $L$-平滑とすると、すべての $x, y \in U$ で

$$f(y) \leq f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2}\lVert y - x \rVert^2 \tag{2.2}$$

が成り立つ（降下補題）。$f$ が $C^2$ 級なら、$L$-平滑性はすべての $x \in U$ で $-LI \preceq \nabla^2 f(x) \preceq LI$ となることと同値である。 2. $f\colon \mathbb{R}^n \to \mathbb{R}$ を微分可能な凸関数とすると、次は同値である。(a) $L$-平滑。(b) すべての $x, y$ で (2.2)。(c) すべての $x, y$ で $f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{1}{2L}\lVert \nabla f(y) - \nabla f(x) \rVert^2$。(d) すべての $x, y$ で $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \frac{1}{L}\lVert \nabla f(x) - \nabla f(y) \rVert^2$。

特に $C^2$ 級の凸関数では、$L$-平滑性は $0 \preceq \nabla^2 f(x) \preceq LI$（$\forall x$）と同値である。

証明. (1) $\nabla f$ は連続なので $t \mapsto f(x + t(y - x))$ は $[0, 1]$ で $C^1$ 級であり、微分積分学の基本定理（01-calculus 第5章 定理 5.13）とコーシー–シュワルツの不等式より

$C^2$ 級の場合、$L$-平滑なら $\nabla^2 f(x)d = \lim_{t \to 0}(\nabla f(x + td) - \nabla f(x))/t$ より作用素ノルムで $\lVert \nabla^2 f(x) \rVert \leq L$。逆に $\lVert \nabla^2 f \rVert \leq L$ なら、平均値の不等式（01-calculus 第8章 定理 8.4）を $\nabla f$ に使えばよい。対称行列の作用素ノルムは固有値の絶対値の最大値なので（02-linear-algebra 第8章 命題 8.21・問題 8.6）、$\lVert \nabla^2 f(x) \rVert \leq L \iff -LI \preceq \nabla^2 f(x) \preceq LI$。

(2) (a⇒b) は (1)。(b⇒c) $x$ を固定し $\phi(z) = f(z) - \langle \nabla f(x), z \rangle$ とおく。$\phi$ は凸で $\nabla\phi(x) = 0$ だから $x$ は $\phi$ の最小点で（定理 2.19）、$\phi$ も (2.2) を満たす（一次関数の項は両辺で打ち消し合う）。$z = y - \frac{1}{L}\nabla\phi(y)$ に (2.2) を使うと

で、書き直すと (c)。(c⇒d) (c) を $(x, y)$ と $(y, x)$ について足す。(d⇒a) コーシー–シュワルツの不等式より $\frac{1}{L}\lVert \nabla f(x) - \nabla f(y) \rVert^2 \leq \lVert \nabla f(x) - \nabla f(y) \rVert\lVert x - y \rVert$。最後の主張は (1) と定理 2.15 による。$\square$