凸最適化（Convex Optimization）は損失最小化・正則化・統計的推定問題の 数学的基盤であり、双対性（Duality）は最適化問題の構造を多角的に解析し 効率的なアルゴリズムを導く枠組みである。 本節では凸集合・凸関数の基礎から出発し、 最適性条件・双対理論・主要アルゴリズムを体系的に整理する。
ユークリッド空間 $\mathbb{R}^d$ を基本的な舞台とする。 内積を $\langle \boldsymbol{u}, \boldsymbol{v} \rangle = \boldsymbol{u}^\top \boldsymbol{v}$、 ノルムを $\|\boldsymbol{u}\| = \sqrt{\langle \boldsymbol{u}, \boldsymbol{u} \rangle}$ で表す。 最小化問題の標準形を
\[ \min_{\boldsymbol{x} \in \mathcal{C}} f(\boldsymbol{x})\]とし、$f: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ を目的関数、 $\mathcal{C} \subseteq \mathbb{R}^d$ を実行可能領域（Feasible Set）と呼ぶ。 より一般的な制約付き問題の標準形は
\[ \min_{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x}) \quad \text{subject to} \quad g_i(\boldsymbol{x}) \leq 0\ (i=1,\ldots,m),\quad h_j(\boldsymbol{x}) = 0\ (j=1,\ldots,p)\]と書く。$f, g_i$ を凸関数、$h_j$ をアフィン関数とするとき、 これを凸最適化問題（Convex Optimization Problem）と呼ぶ。
集合 $\mathcal{C} \subseteq \mathbb{R}^d$ が凸集合（Convex Set）であるとは、
\[ \forall \boldsymbol{x}, \boldsymbol{y} \in \mathcal{C},\; \forall \lambda \in [0,1],\quad \lambda \boldsymbol{x} + (1-\lambda)\boldsymbol{y} \in \mathcal{C}\]が成立することをいう。すなわち任意の二点を結ぶ線分が集合に含まれる。 凸集合の例として、アフィン部分空間・半空間 $\{\boldsymbol{x} : \boldsymbol{a}^\top \boldsymbol{x} \leq b\}$・ 球 $\{\boldsymbol{x} : \|\boldsymbol{x}\| \leq r\}$・ 多面体 $\{A\boldsymbol{x} \leq \boldsymbol{b}\}$・ 正半定値錐 $\mathbb{S}^d_+$ などが挙げられる。 凸集合は交叉について閉じており、任意個の凸集合の共通部分は凸である。
関数 $f: \mathcal{C} \to \mathbb{R}$（$\mathcal{C}$ は凸集合）が 凸関数（Convex Function）であるとは、
\[ \forall \boldsymbol{x}, \boldsymbol{y} \in \mathcal{C},\; \forall \lambda \in [0,1],\quad f(\lambda \boldsymbol{x} + (1-\lambda)\boldsymbol{y}) \leq \lambda f(\boldsymbol{x}) + (1-\lambda) f(\boldsymbol{y})\]が成立することをいう。不等号が狭義（$\boldsymbol{x} \neq \boldsymbol{y}$、 $\lambda \in (0,1)$ で $<$）のとき狭義凸関数（Strictly Convex Function）と呼ぶ。 $-f$ が凸のとき $f$ を凹関数（Concave Function）と呼ぶ。
微分可能な凸関数の同値な特徴づけを示す。
代表的な凸関数の例を示す。
凸関数の重要な性質を列挙する。
$f$ が$\mu$-強凸（$\mu$-Strongly Convex、$\mu > 0$）であるとは、
\[ f(\lambda \boldsymbol{x} + (1-\lambda)\boldsymbol{y}) \leq \lambda f(\boldsymbol{x}) + (1-\lambda)f(\boldsymbol{y}) - \frac{\mu}{2}\lambda(1-\lambda)\|\boldsymbol{x} - \boldsymbol{y}\|^2\]が成立することをいう。一階条件の形では、$f$ が微分可能のとき
\[ f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \langle \nabla f(\boldsymbol{x}),\, \boldsymbol{y} - \boldsymbol{x} \rangle + \frac{\mu}{2}\|\boldsymbol{y} - \boldsymbol{x}\|^2\]と同値である。強凸関数は狭義凸であり、最小化問題の解が一意に定まる。 二回微分可能の場合、$\nabla^2 f(\boldsymbol{x}) \succeq \mu I$ が強凸の十分条件である。 例として $f(\boldsymbol{x}) = \|\boldsymbol{x}\|^2$ は $\mu = 2$ の強凸、 $\ell_2$ 正則化された目的関数 $R_n(\boldsymbol{\theta}) + \lambda\|\boldsymbol{\theta}\|^2$ は $\mu = 2\lambda$ の強凸となる。
$f$ の勾配が$L$-リプシッツ連続（$L$-Smooth、$L > 0$）であるとは、
\[ \|\nabla f(\boldsymbol{x}) - \nabla f(\boldsymbol{y})\| \leq L\|\boldsymbol{x} - \boldsymbol{y}\| \quad \forall \boldsymbol{x}, \boldsymbol{y}\]が成立することをいう。これは
\[ f(\boldsymbol{y}) \leq f(\boldsymbol{x}) + \langle \nabla f(\boldsymbol{x}),\, \boldsymbol{y} - \boldsymbol{x} \rangle + \frac{L}{2}\|\boldsymbol{y} - \boldsymbol{x}\|^2\]と同値であり、関数が接超平面から二次関数で上から抑えられることを意味する。 二回微分可能の場合、$\nabla^2 f(\boldsymbol{x}) \preceq LI$ が等価条件となる。 強凸性 $\mu$ と平滑性 $L$ の比 $\kappa = L/\mu$ を条件数（Condition Number）と呼び、 最適化アルゴリズムの収束速度を規定する重要な量である。
凸最適化の最も根本的な性質は、局所最適解が大域最適解であることである。
定理（局所最適 $\Rightarrow$ 大域最適）： $f$ が凸、$\mathcal{C}$ が凸集合のとき、 $\boldsymbol{x}^*$ が局所最適解（$\exists \varepsilon > 0$ で $\|\boldsymbol{x} - \boldsymbol{x}^*\| < \varepsilon$ を満たす $\boldsymbol{x} \in \mathcal{C}$ すべてに対して $f(\boldsymbol{x}^*) \leq f(\boldsymbol{x})$） ならば大域最適解でもある。
証明の概略： $\boldsymbol{x}^*$ が局所最適だが大域最適でないと仮定し、 $f(\boldsymbol{y}) < f(\boldsymbol{x}^*)$ を満たす $\boldsymbol{y} \in \mathcal{C}$ を取る。 凸性より $f(\lambda \boldsymbol{y} + (1-\lambda)\boldsymbol{x}^*) \leq \lambda f(\boldsymbol{y}) + (1-\lambda)f(\boldsymbol{x}^*) < f(\boldsymbol{x}^*)$ が $\lambda \in (0,1)$ で成立し、$\lambda$ を小さくすれば $\lambda \boldsymbol{y} + (1-\lambda)\boldsymbol{x}^*$ は $\boldsymbol{x}^*$ の局所近傍に入るため矛盾。$\square$
さらに $f$ が狭義凸なら最適解は高々一意であり、 $f$ が強凸かつ $\mathcal{C}$ が閉凸集合なら最適解は一意に存在する。
劣微分（Subdifferential）： 凸関数 $f$ が $\boldsymbol{x}$ で微分不可能な場合、 勾配の一般化として劣微分
\[ \partial f(\boldsymbol{x}) = \bigl\{ \boldsymbol{g} \in \mathbb{R}^d : f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \langle \boldsymbol{g},\, \boldsymbol{y} - \boldsymbol{x} \rangle\; \forall \boldsymbol{y} \bigr\}\]を定義する。$\boldsymbol{g} \in \partial f(\boldsymbol{x})$ の元を劣勾配と呼ぶ。 $f$ が $\boldsymbol{x}$ で微分可能なら $\partial f(\boldsymbol{x}) = \{\nabla f(\boldsymbol{x})\}$。 例として $f(x) = |x|$ では $\partial f(0) = [-1, 1]$、 $f(\boldsymbol{x}) = \|\boldsymbol{x}\|_1$ では $[\partial f(\boldsymbol{x})]_k = \mathrm{sign}(x_k)$（$x_k \neq 0$）または $[-1,1]$（$x_k = 0$）。
定理（無制約問題の最適性条件）： $f$ が凸のとき、
\[ \boldsymbol{x}^* \text{ が最適解} \iff \boldsymbol{0} \in \partial f(\boldsymbol{x}^*)\]$f$ が微分可能なら $\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}$ と同値。
制約付き問題の最適性条件： 実行可能集合 $\mathcal{C}$ が凸のとき、
\[ \boldsymbol{x}^* \text{ が最適解} \iff \langle \nabla f(\boldsymbol{x}^*),\, \boldsymbol{y} - \boldsymbol{x}^* \rangle \geq 0 \quad \forall \boldsymbol{y} \in \mathcal{C}\]これを変分不等式条件と呼び、$\boldsymbol{x}^*$ における勾配が 実行可能方向のすべてに対して非負内積を持つことを意味する。
制約付き主問題
\[ p^* = \min_{\boldsymbol{x}} f(\boldsymbol{x}) \quad \text{s.t.} \quad g_i(\boldsymbol{x}) \leq 0\ (i=1,\ldots,m),\quad h_j(\boldsymbol{x}) = 0\ (j=1,\ldots,p)\]に対して、ラグランジュ関数（Lagrangian）を
\[ \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\boldsymbol{x}) + \sum_{i=1}^m \lambda_i g_i(\boldsymbol{x}) + \sum_{j=1}^p \nu_j h_j(\boldsymbol{x})\]と定義する。$\boldsymbol{\lambda} = (\lambda_1,\ldots,\lambda_m)^\top \geq \boldsymbol{0}$ を不等式制約のラグランジュ乗数（双対変数）、 $\boldsymbol{\nu} = (\nu_1,\ldots,\nu_p)^\top$ を等式制約の双対変数と呼ぶ。
ラグランジュ双対関数（Lagrange Dual Function）を
\[ q(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\boldsymbol{x}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})\]と定義する。$q$ は $(\boldsymbol{\lambda}, \boldsymbol{\nu})$ の関数として アフィン関数の下限であるから、常に凹関数である（$\boldsymbol{\lambda}, \boldsymbol{\nu}$ に関して）。
双対問題（Dual Problem）は
\[ d^* = \max_{\boldsymbol{\lambda} \geq \boldsymbol{0},\, \boldsymbol{\nu}} q(\boldsymbol{\lambda}, \boldsymbol{\nu})\]と定義される。双対問題は主問題の凸性にかかわらず常に凸最大化問題 （凹関数の最大化）である点が重要である。
弱双対定理： 任意の双対実行可能点 $(\boldsymbol{\lambda} \geq \boldsymbol{0}, \boldsymbol{\nu})$ と主実行可能点 $\boldsymbol{x}$ に対して
\[ q(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq p^*\]が成立する。すなわち双対目的値は常に主目的値の下界を与える。 この差 $p^* - d^* \geq 0$ を双対ギャップ（Duality Gap）と呼ぶ。
強双対定理： $p^* = d^*$（双対ギャップがゼロ）が成立する条件として、 以下のSlater 条件（制約想定）が十分条件を与える：
\[ \exists \hat{\boldsymbol{x}} \in \mathrm{relint}(\mathcal{C}) \text{ s.t. } g_i(\hat{\boldsymbol{x}}) < 0\ (i=1,\ldots,m),\quad h_j(\hat{\boldsymbol{x}}) = 0\ (j=1,\ldots,p)\]すなわち不等式制約をすべて狭義に満たす実行可能点（厳密実行可能点）が存在するとき、 凸最適化問題では強双対性が成立する。 Slater 条件は多くの機械学習の最適化問題（SVM・Lasso 等）で自然に満たされる。
強双対性が成立するとき、主問題の最適解 $\boldsymbol{x}^*$ と 双対問題の最適解 $(\boldsymbol{\lambda}^*, \boldsymbol{\nu}^*)$ は KKT 条件（Karush–Kuhn–Tucker Conditions）を満たす：
定理： 凸最適化問題で Slater 条件が成立するとき、 $\boldsymbol{x}^*$ が主問題の最適解であることと、 ある $(\boldsymbol{\lambda}^*, \boldsymbol{\nu}^*)$ とともに KKT 条件を満たすことは同値である。 KKT 条件は非線形最適化の最適性の必要十分条件を与える一般的な枠組みであり、 アルゴリズム設計の理論的根拠となる。
関数 $f: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ の 凸共役関数（Convex Conjugate、Legendre–Fenchel 変換）を
\[ f^*(\boldsymbol{y}) = \sup_{\boldsymbol{x} \in \mathbb{R}^d} \bigl[ \langle \boldsymbol{y}, \boldsymbol{x} \rangle - f(\boldsymbol{x}) \bigr]\]と定義する。$f^*$ はアフィン関数の上限として常に凸関数（かつ下半連続）であり、 $f$ の凸性にかかわらず成立する。
Fenchel–Moreau 定理： $f$ が閉凸関数（下半連続な真の凸関数）のとき、 $f^{**} = f$（双共役は元の関数に一致）。
代表的な共役関数の例を示す。
Young の不等式： 共役関数の定義から直ちに、任意の $\boldsymbol{x}, \boldsymbol{y}$ に対して
\[ \langle \boldsymbol{x}, \boldsymbol{y} \rangle \leq f(\boldsymbol{x}) + f^*(\boldsymbol{y})\]が成立する（等号成立 $\Longleftrightarrow$ $\boldsymbol{y} \in \partial f(\boldsymbol{x})$）。
主問題 $\min_{\boldsymbol{x}} [f(\boldsymbol{x}) + g(A\boldsymbol{x})]$ （$A \in \mathbb{R}^{m \times d}$、$f, g$ は凸）に対して、 Fenchel 双対問題は
\[ \max_{\boldsymbol{y}} \bigl[ -f^*(-A^\top \boldsymbol{y}) - g^*(\boldsymbol{y}) \bigr]\]と導かれる。Slater 条件のもとで強双対性 $p^* = d^*$ が成立する。 Fenchel 双対は正則化付き学習問題（Lasso、サポートベクターマシン等）の 双対導出に直接応用される。
線形 SVM（ハードマージン）の主問題は
\[ \min_{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^2 \quad \text{s.t.} \quad y_i(\boldsymbol{w}^\top \boldsymbol{x}_i + b) \geq 1 \quad (i=1,\ldots,n)\]と書ける（$y_i \in \{-1,+1\}$）。ラグランジュ関数は
\[ \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\boldsymbol{w}\|^2 - \sum_{i=1}^n \alpha_i \bigl[ y_i(\boldsymbol{w}^\top \boldsymbol{x}_i + b) - 1 \bigr], \quad \alpha_i \geq 0\]停留条件 $\nabla_{\boldsymbol{w}} \mathcal{L} = \boldsymbol{0}$、 $\partial_b \mathcal{L} = 0$ より
\[ \boldsymbol{w}^* = \sum_{i=1}^n \alpha_i y_i \boldsymbol{x}_i, \qquad \sum_{i=1}^n \alpha_i y_i = 0\]をラグランジュ双対関数に代入すると、双対問題
\[ \max_{\boldsymbol{\alpha} \geq \boldsymbol{0}} \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^\top \boldsymbol{x}_j \quad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0\]が得られる。これは $\boldsymbol{x}_i^\top \boldsymbol{x}_j$ のみに依存するため、 カーネル関数 $k(\boldsymbol{x}_i, \boldsymbol{x}_j)$ への置き換えにより カーネル SVM が自然に導かれる。相補性条件 $\alpha_i(y_i(\boldsymbol{w}^\top \boldsymbol{x}_i + b) - 1) = 0$ より、 $\alpha_i > 0$ となる点（サポートベクター）のみが解の構造に寄与する。 Slater 条件はデータが線形分離可能なとき満たされ、強双対性が成立する。
$f$ が微分可能・$L$-平滑な凸関数のとき、 ステップサイズ $\eta \leq 1/L$ の勾配降下法（Gradient Descent）
\[ \boldsymbol{x}_{t+1} = \boldsymbol{x}_t - \eta \nabla f(\boldsymbol{x}_t)\]は収束速度 $O(1/t)$ を達成する：
\[ f(\boldsymbol{x}_t) - f(\boldsymbol{x}^*) \leq \frac{L\|\boldsymbol{x}_0 - \boldsymbol{x}^*\|^2}{2t}\]$f$ が $\mu$-強凸かつ $L$-平滑なとき、同じ更新則は線形収束（指数収束）を達成する：
\[ \|\boldsymbol{x}_t - \boldsymbol{x}^*\|^2 \leq \left(1 - \frac{\mu}{L}\right)^t \|\boldsymbol{x}_0 - \boldsymbol{x}^*\|^2\]収束速度は条件数 $\kappa = L/\mu$ に依存し、$\kappa$ が大きいほど収束が遅い。
経験リスク $R_n(\boldsymbol{\theta}) = \frac{1}{n}\sum_{i=1}^n \ell_i(\boldsymbol{\theta})$ のように目的関数が和の形のとき、全勾配の計算に $O(n)$ コストを要する。 確率的勾配降下法（Stochastic Gradient Descent, SGD）は ランダムに選んだ一標本（またはミニバッチ）の勾配で全勾配を近似する：
\[ \boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t \nabla \ell_{i_t}(\boldsymbol{\theta}_t), \quad i_t \sim \mathrm{Uniform}(\{1,\ldots,n\})\]$\mathbb{E}[\nabla \ell_{i_t}(\boldsymbol{\theta}_t)] = \nabla R_n(\boldsymbol{\theta}_t)$ が成立するため、SGD の更新は真の勾配の不偏推定量に基づく。 ステップサイズを $\eta_t = O(1/\sqrt{t})$ と設定するとき、 凸関数で $O(1/\sqrt{t})$ の収束速度が達成される。 深層学習の最適化では Adam・RMSProp 等の適応的手法が広く用いられるが、 これらはすべて SGD の拡張として理解できる。
$f(\boldsymbol{x}) = g(\boldsymbol{x}) + h(\boldsymbol{x})$ （$g$：微分可能凸関数、$h$：非平滑凸関数、例：$\|\cdot\|_1$）の形の目的関数に対して、 近接勾配法（Proximal Gradient Method）は
\[ \boldsymbol{x}_{t+1} = \mathrm{prox}_{\eta h}\!\left(\boldsymbol{x}_t - \eta \nabla g(\boldsymbol{x}_t)\right)\]と更新する。ここで近接写像（Proximal Operator）は
\[ \mathrm{prox}_{\eta h}(\boldsymbol{v}) = \arg\min_{\boldsymbol{x}} \left[ h(\boldsymbol{x}) + \frac{1}{2\eta}\|\boldsymbol{x} - \boldsymbol{v}\|^2 \right]\]と定義される。$h(\boldsymbol{x}) = \lambda\|\boldsymbol{x}\|_1$ のとき 近接写像はソフト閾値処理
\[ [\mathrm{prox}_{\eta\lambda\|\cdot\|_1}(\boldsymbol{v})]_k = \mathrm{sign}(v_k) \max(|v_k| - \eta\lambda, 0)\]となり、Lasso の効率的な解法（ISTA・FISTA）が構成される。 FISTA（Fast ISTA）はモメンタム項の追加により収束速度を $O(1/t)$ から $O(1/t^2)$ に改善する。
| アルゴリズム | 条件 | 収束速度 |
|---|---|---|
| 勾配降下法 | 凸・$L$-平滑 | $O(1/t)$ |
| 勾配降下法 | $\mu$-強凸・$L$-平滑 | $O((1-\mu/L)^t)$（線形収束） |
| Nesterov 加速勾配法 | 凸・$L$-平滑 | $O(1/t^2)$（最適） |
| SGD | 凸・有界勾配 | $O(1/\sqrt{t})$ |
| SGD | $\mu$-強凸 | $O(1/(\mu t))$ |
| 近接勾配法（ISTA） | 凸・$L$-平滑＋非平滑 | $O(1/t)$ |
| FISTA | 凸・$L$-平滑＋非平滑 | $O(1/t^2)$（最適） |
一次法（勾配情報のみ使用）に対する下限として、 Nesterov（1983）の複雑度下界 $\Omega(1/t^2)$（凸・$L$-平滑）が知られており、 加速勾配法はこれを達成する最適アルゴリズムである。
凸集合・凸関数の定義から出発し、強凸性・平滑性による関数の特性化、 劣微分を用いた最適性条件の一般化、ラグランジュ双対理論と KKT 条件、 凸共役関数と Fenchel 双対性、そして主要最適化アルゴリズムの収束解析を体系化した。 凸最適化の本質は局所最適が大域最適に一致するという構造にあり、 KKT 条件が最適性の完全な特徴づけを与える。 双対理論は主問題の下界計算・アルゴリズム設計・カーネル法への拡張を可能にし、 Fenchel 双対と凸共役は正則化付き学習・スパース推定・変分推論と深く結びつく。 収束速度の観点では、関数の強凸性と平滑性が決定的な役割を果たし、 Nesterov 加速・確率的勾配降下・近接勾配法はそれぞれ異なる問題構造に 対応した最適なアルゴリズムを提供する。
Mathematics is the language with which God has written the universe.