二次計画法（にじけいかくほう、英: quadratic programming, QP）は、数理最適化における非線形計画法の代表例の一つであり、いくつかの変数からなる二次関数を線形制約の下で最適化（最小化ないしは最大化）する方法である。二次計画法の対象となる最適化問題を二次計画問題という。

n の変数と m の制約からなる二次計画問題は以下のように定式化することができる^[1]。

以下を所与とする：

• 実数値の n 次元ベクトル c
• n 行 n 列の実数値対称行列 Q
• m 行 n 列の実数値行列 A
• 実数値の m 次元ベクトル b

二次計画問題の目的は以下の問題の解となる n 次元ベクトル x を見つけることである。

${\displaystyle {\text{minimize}}}$	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
${\displaystyle {\text{subject to}}}$	${\displaystyle A\mathbf {x} \leq \mathbf {b} ,}$

ここで x^T はベクトル x の転置を表す。Ax ≤ b という記法はベクトル Ax の全ての要素が対応するベクトル b の要素より小さいもしくは等しいことを意味する。

関係する最適化問題として、二次制約付き二次計画問題（英語版）があり、二次制約付き二次計画問題では二次の制約が足されている。

一般の問題について、多様な解法が広く用いられており、例えば

• 内点法
• 有効制約法（英語版）^[2]
• 拡張ラグランジュ乗数法（英語版）^[3]
• 共役勾配法
• 勾配射影法
• シンプレックス法の拡張^[2]

などがある。行列 Q が正値定符号ならば、問題はより一般的な凸最適化の領域の特殊ケースとなる。

二次計画問題は行列 Q が正値定符号であり、等式制約のみを含む時、特に簡単になり、解の過程は線形となる。ラグランジュの未定乗数法を用い、ラグランジアンの極値を探せば、以下の等式制約問題

${\displaystyle {\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$,

${\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} }$.

の解は次の線形システム

${\displaystyle {\begin{bmatrix}Q&E^{T}\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$.

の解として与えられることが容易に示される。ここで ${\displaystyle \lambda }$ はラグランジュ乗数の集合で x と共に計算される。

このシステムを解く最も簡単な方法は直接的に問題を解くこと（例えばLU分解）で、問題の規模が小さければ非常に有用である。問題の規模が大きければ、このシステムは特異な難しさに直面する。もっとも重要なのは（Q が正値定符号であったとしても、）問題自体は正値定符号と決してならないことである。そのためうまくいく数値解法を見いだすことは非常に難しいので、問題に依存した様々な方法がある^[4]。

もしも、制約があまり多くの変数を含んでいなければ、比較的簡単な方法として制約を無条件で満たすように変数を変換する方法がある。例えば、d = 0（非ゼロの場合にも一般化できる）と仮定する。制約方程式を見ると

${\displaystyle E\mathbf {x} =0}$.

となる。新しい変数として y を以下のように定義する。

${\displaystyle Z\mathbf {y} =\mathbf {x} }$.

ここで y の次元は x の次元から制約の数を引いたものである。この時、

${\displaystyle EZ\mathbf {y} =0}$.

であり、もし Z を EZ = 0 となるように選べば、制約方程式は常に満たされるようになる。このような Z を見つけるということは E の零空間を見つけることを意味し、E の構造に依存するが多かれ少なかれ単純である。二次形式に代入すると次の無制約の最小化問題が得られる。

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad {\tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y} .}$

この解は以下で与えられる。

${\displaystyle Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c} .}$

Q についてのある条件の下で、退化した行列 Z^TQZ は正値定符号となる。Z の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である^[5]。

二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。

${\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).}$

（ラグランジュ）双対関数を ${\displaystyle g(\lambda )}$ とし、${\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )}$ を満たすものとすれば、${\displaystyle \nabla _{x}L(x,\lambda )=0}$ という条件と Q の正値定符号性を用いることで、L の下限を見つけることができる。

${\displaystyle x^{*}=-Q^{-1}A^{T}\lambda .}$

ゆえに双対関数は

${\displaystyle g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b,}$

であり、二次計画問題のラグランジュ双対は

${\displaystyle {\text{ maximize}}\quad -{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b}$

${\displaystyle \,\,{\text{subject to}}\quad \lambda \geqslant 0}$

となる。ラグランジュ双対理論の他にも他の双対性が存在する（例えばWolfe双対（英語版））。

正値定符号行列である Q について楕円体法（英語版）は多項式時間で二次計画問題を解くことができる^[6]。一方で、Q の符号が不定ならば、二次計画問題はNP困難となる^[7]。実際、Q のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である^[8]。

• サポートベクターマシン
• 逐次二次計画法
• 線形計画法

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9. MR1150683 
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5  A6: MP2, pg.245.

• 二次計画法についてのページ (英語)
• NEOS Optimization Guide: Quadratic Programming
• Solve an example Quadratic Programming (QP) problem

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版） 有効制約法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）