二次計画法
n の変数と m の制約からなる二次計画問題は以下のように定式化することができる。
以下を所与とする:
実数値の n 次元ベクトル c
n 行 n 列の実数値対称行列 Q
m 行 n 列の実数値行列 A
実数値の m 次元ベクトル b
二次計画問題の目的は以下の問題の解となる n 次元ベクトル x を見つけることである。
ここで x はベクトル x の転置を表す。Ax ≤ b という記法はベクトル Ax の全ての要素が対応するベクトル b の要素より小さいもしくは等しいことを意味する。
関係する最適化問題として、二次制約付き二次計画問題(英語版)があり、二次制約付き二次計画問題では二次の制約が足されている。
de/jca/jca12/jca1203_b.pdf.
↑ Google search.
↑ Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization. 23. SIAM Journal of Scientific Computing. pp. 1376–1395. CiteSeer: 10.1.1.129.7555.
↑ Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). “[Polynomial solvability of convex quadratic programming]”. Doklady Akademii Nauk SSSR 248: 1049–1051. Translated in: Soviet Mathematics - Doklady 20: 1108–1111.
↑ Sahni, S. (1974). “Computationally related problems”. SIAM Journal on Computing 3: 262–279. doi:10.1137/0203021.
↑ Pardalos, Panos M.; Vavasis, Stephen A. (1991). “Quadratic programming with one negative eigenvalue is NP-hard”.