二次計画問題#
読み: にじけいかくもんだい
英名: Quadratic Programming Problem
別名: QP
目的関数が二次関数であり制約条件が一次関数である最適化問題のことを二次計画問題と呼ぶ． 目的関数が下に凸な最小化問題に帰着できるケースは単体法の拡張である有効制約法あるいは内点法によって安定かつ高速に解くことができる．
実務的に重要な二次計画問題としてよく知られているものに， 重回帰（最小二乗法），金融工学におけるポートフォリオ最適解問題（マルコビッツモデル）がある． 近年では偏微分方程式制約付きの最適化問題や画像復元の問題が，大規模な二次計画法に帰着して解かれている．
一方で目的関数が下に凸な最小化問題に帰着できないケース，一部の変数に整数性の制約があるケースは近年も研究対象となっている． 具体的には標準単体上でヘッセ行列が不定値な二次関数を最小化する問題（stQP）の凸な定式化 [1]， 銘柄数制約付きのポートフォリオ問題 [2]， 0-1 混合整数二次計画法をCopositive Programming（の dual）による定式化 [3] などが挙げられる．
参考文献
Immanuel M Bomze and Etienne De Klerk. Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming. Journal of Global Optimization, 24(2):163–185, 2002. URL: https://doi.org/10.1023/A:1020209017701, doi:10.1023/A:1020209017701.
Francesco Cesarone, Andrea Scozzari, and Fabio Tardella. A new method for mean-variance portfolio optimization with cardinality constraints. Annals of Operations Research, 205(1):213–234, may 2013. URL: http://link.springer.com/10.1007/s10479-012-1165-7, doi:10.1007/s10479-012-1165-7.
Samuel Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, 120(2):479–495, sep 2009. URL: http://link.springer.com/10.1007/s10107-008-0223-z, doi:10.1007/s10107-008-0223-z.