二次計画（QP）｜数理最適化

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：凸集合と凸関数・不等式制約とKKT条件　|　関連：ポートフォリオ最適化のモデル化

要点（BLUF）

二次計画（QP）は 目的が二次・制約が線形の最適化。 $\min \tfrac12 x^\top Q x + c^\top x$ s.t. 線形制約。
$Q \succeq 0$ （半正定値）なら 凸 QPで、大域最適が効率的に解ける。 $Q \not\succeq 0$ なら非凸で難しい。
等式制約だけの QP は KKT 条件が線形方程式になり、行列を解くだけで最適解が出る。

概念 ── 二次の目的・線形の制約

QP は LP（線形計画章目次）の目的を二次に拡張した問題：

\min_x\ \tfrac12 x^\top Q x + c^\top x \quad \text{s.t.}\quad Ax \le b,\ Ex = d

$Q$ は対称行列。 $Q \succeq 0$ （半正定値、固有値が非負）なら目的は凸（凸集合と凸関数の2次条件）で、線形制約の凸領域と合わせて 凸 QP。これは多項式時間で大域最適が解ける。 $Q$ が不定（負の固有値を持つ）なら 非凸 QPで、一般に NP 困難。

QP の応用は広い：最小二乗（ $Q=A^\top A$ ）、リッジ回帰、SVM、そして金融のポートフォリオ最適化（リスク $=$ 分散 $=$ 二次形式、ポートフォリオ最適化のモデル化）。

等式制約 QP は線形方程式

等式制約だけの凸 QP $\min \tfrac12 x^\top Q x + c^\top x$ s.t. $Ex=d$ は、KKT 条件（不等式制約とKKT条件）が線形になる。ラグランジュ $\mathcal{L}=\tfrac12 x^\top Qx + c^\top x + \nu^\top(Ex-d)$ の停留条件：

\begin{bmatrix} Q & E^\top \\ E & 0 \end{bmatrix} \begin{bmatrix} x \\ \nu \end{bmatrix} = \begin{bmatrix} -c \\ d \end{bmatrix}

この KKT 系（鞍点系）を解くだけで最適解 $x$ と乗数 $\nu$ が同時に求まる。不等式が入ると有効制約集合を探す必要があり、有効制約法（active-set） や内点法（内点法入門）を使う。

Pythonで凸QPを解く

$\min (x-1)^2 + (y-2)^2$ s.t. $x+y\le2,\ x,y\ge0$ 。これは $Q=2I,\ c=(-2,-4)$ の凸 QP（定数項を除く）。cvxpy で解く。

import numpy as np
import cvxpy as cp

x = cp.Variable(2)
# (x-1)^2 + (y-2)^2 = sum_squares(x - [1,2])
obj = cp.Minimize(cp.sum_squares(x - np.array([1.0, 2.0])))
cons = [x[0] + x[1] <= 2, x >= 0]
prob = cp.Problem(obj, cons)
prob.solve()

print(f"最適解 x={x.value[0]:.4f}, y={x.value[1]:.4f}")
print(f"最適値 f={prob.value:.4f}")

実行結果：

最適解 x=0.5000, y=1.5000
最適値 f=0.5000

無制約なら最小は $(1,2)$ だが、 $x+y\le2$ に阻まれ、境界 $x+y=2$ 上の最近点 $(0.5,1.5)$ が最適（不等式制約とKKT条件の例と同じ構造）。二次の目的の等高線（同心円）が制約直線に接する点が答え。

QP の解法

状況	解法
等式制約のみ・凸	KKT 線形系を直接解く
不等式制約・凸	有効制約法（active-set）、内点法
大規模・疎	内点法（内点法入門）、作用素分割（OSQP, ADMM）
非凸（ $Q$ 不定）	分枝限定・SDP 緩和など（一般に困難）

数式の直観的意味

QP が「凸最適化の入口」として重要なのは、二次形式 $\tfrac12 x^\top Qx$ の曲率が 行列 $Q$ で完全に決まるから。 $Q$ の固有値が曲率で、すべて正なら真のお椀型（狭義凸）、ゼロ固有値があると平らな谷（複数最適）、負があると鞍型（非凸）。線形制約は凸多面体（線形計画の標準形と幾何）を切り出し、その上で放物面の最小を探す。ニュートン法（ニュートン法・準ニュートン法）が二次近似の最小へ一気に進むのと同じ原理が、QP では問題そのものに組み込まれている ── だから QP は「ニュートンステップを制約付きで解く」基本部品として、非線形ソルバー（逐次二次計画 SQP）の心臓部にもなる。

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

凸 QP と非凸 QP は天と地： $Q\succeq0$ の確認（固有値が非負）が最初の一歩。共分散行列は半正定値なのでポートフォリオは凸。
$Q$ の対称化： $x^\top Q x = x^\top \tfrac{Q+Q^\top}{2} x$ なので、非対称 $Q$ は対称部分だけが効く。
最小二乗は QP の特例： $\|Ax-b\|^2$ の $Q=A^\top A\succeq0$ 。正則化（リッジ）で $Q+\lambda I\succ0$ にして一意性を確保。
不等式制約があると閉形式解は無い（有効制約が事前に分からない）。反復解法が要る。