錐計画（SOCP・SDP）入門

🎓 レベル：発展　|　重要度：B（標準）

📎 前提：二次計画（QP）・凸最適化問題と双対理論　|　関連：実装：cvxpyで凸問題を解く

要点（BLUF）

錐計画は 「線形目的を、変数が錐に属する制約のもとで最小化」 する統一枠組み。
錐の種類で階層：LP（非負錐）⊂ QP/SOCP（二次錐）⊂ SDP（半正定値錐）。
SOCP は「ノルム ≤ 線形」、SDP は「行列が半正定値」を表現でき、ロバスト最適化や制御へ広く応用。

概念 ── 「錐」で最適化を統一する

LP・QP・SOCP・SDP は別々の問題に見えて、実は 錐 $K$ を取り替えただけの同じ形：

\min_x\ c^\top x \quad \text{s.t.}\quad Ax = b,\ x \in K

$K$ を非負象限 $\mathbb{R}^n_+$ にすれば LP、二次錐（ローレンツ錐） にすれば SOCP、半正定値錐（対称半正定値行列の集合）にすれば SDP。錐はすべて凸なので、これらはすべて凸最適化（凸最適化問題と双対理論）。統一することで、双対理論・内点法（内点法入門）を1つの理論で扱える。

graph LR
  LP["LP 非負錐 x>=0"] --> SOCP["SOCP 二次錐 ||u||<=t"]
  SOCP --> SDP["SDP 半正定値錐 X>=0 (行列)"]
  QP["QP 凸二次"] --> SOCP

二次錐計画（SOCP）

二次錐（ローレンツ錐） は $\{(u,t): \|u\|_2 \le t\}$ 。SOCP は「ノルムが線形式以下」という制約を扱う：

\min\ c^\top x \quad \text{s.t.}\quad \|A_i x + b_i\|_2 \le c_i^\top x + d_i

これで最小二乗・ロバスト線形計画（係数が不確実、ロバスト最適化）・到達距離制約などが表せる。LP・凸 QP は SOCP の特殊例（QP の二次目的はエピグラフ変換で二次錐制約になる）。

Pythonで最小ノルム解（SOCP）

$\min \|x\|_2$ s.t. $Ax=b$ （連立を満たす中で最も小さいベクトル）。

import numpy as np
import cvxpy as cp

A = np.array([[1.0, 1.0, 1.0]])    # x1+x2+x3 = 3
b = np.array([3.0])
x = cp.Variable(3)
prob = cp.Problem(cp.Minimize(cp.norm(x, 2)), [A @ x == b])
prob.solve()
print(f"最小ノルム解 x={np.round(x.value, 4)}, ||x||={prob.value:.4f}")
print(f"理論値: (1,1,1), ||x||=sqrt(3)={np.sqrt(3):.4f}")

実行結果：

最小ノルム解 x=[1. 1. 1.], ||x||=1.7321
理論値: (1,1,1), ||x||=sqrt(3)=1.7321

$x_1+x_2+x_3=3$ を満たす中で最小ノルムは、対称性から $(1,1,1)$ 、ノルム $\sqrt3\approx1.732$ 。これは「制約超平面への原点からの垂線の足」で、最小二乗解（疑似逆 $A^+b$ ）に一致する。

半正定値計画（SDP）

半正定値錐 は対称半正定値行列の集合 $\{X: X \succeq 0\}$ 。SDP は行列変数を扱う：

\min\ \langle C, X\rangle \quad \text{s.t.}\quad \langle A_i, X\rangle = b_i,\ X \succeq 0

固有値・行列ノルム・分散などの制約を表せ、組合せ最適化の緩和（Max-Cut の SDP 緩和）、制御の LMI、共分散推定に強力。SOCP は SDP の特殊例（二次錐はブロック対角の PSD で表せる）。

Pythonで固有値制約（SDP）

$\min t$ s.t. $\begin{bmatrix} t & 1 \\ 1 & t\end{bmatrix}\succeq0$ 。この行列の固有値は $t\pm1$ なので、半正定値 $\iff t\ge1$ 。最適 $t=1$ 。

import cvxpy as cp

t = cp.Variable()
M = cp.bmat([[t, cp.Constant(1)],
             [cp.Constant(1), t]])   # 2x2対称行列
prob = cp.Problem(cp.Minimize(t), [M >> 0])   # >> 0 は半正定値制約
prob.solve()
print(f"最適 t={prob.value:.4f}  (理論: 固有値 t±1>=0 より t>=1)")

実行結果：

最適 t=1.0000  (理論: 固有値 t±1>=0 より t>=1)

半正定値制約（最小固有値 $\ge0$ ）が $t\ge1$ を強制し、最適 $t=1$ 。SDP は「最小固有値を最大化する」型の問題（スペクトル最適化）を自然に書ける。

数式の直観的意味

錐計画の威力は「凸性を錐という1つの幾何対象に集約した」こと。非負錐・二次錐・半正定値錐はすべて 自己双対に近い良い構造を持ち、内点法の対数障壁（ペナルティ法・障壁法）が各錐に定義できる ── だから LP の内点法（内点法入門）がそのまま SOCP・SDP へ多項式時間で拡張される。階層 LP⊂SOCP⊂SDP は「表現力」の階層で、上に行くほど書ける制約が広がる（ノルム→固有値）が、計算コストも増す。実務では「その制約を表せる最小の錐」を選ぶのが定石（ノルム制約なら SDP でなく SOCP で十分）。この統一視点が、cvxpy のような DCP モデリング（実装：cvxpyで凸問題を解く）を可能にしている。

⚠️ よくある誤解・落とし穴

「二次錐 $\|u\|\le t$ 」と「二次不等式 $\|u\|^2\le t$ 」は別物：前者は SOCP、後者は QP 制約。エピグラフ変換で行き来する。
必要以上に強い錐を使わない：SOCP で足りる問題を SDP にすると無駄に重い。
SDP は変数が行列： $n\times n$ で変数が $O(n^2)$ 、大規模では急速に重くなる。
半正定値制約 >> 0 は対称行列にのみ意味を持つ。対称性を保証する。